Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Hot answers tagged

15

There is no direct way to find the optimal number of them: people empirically try and see (e.g., using cross-validation). The most common search techniques are random, manual, and grid searches. There exist more advanced techniques such as Gaussian processes, e.g. Optimizing Neural Network Hyperparameters with Gaussian Processes for Dialog Act ...


8

If one thinks of intelligence as a continuous measure of optimization power (that is, how much better are outcomes for any unit of cognitive effort expended), then exhaustive search has non-zero intelligence (in that it does actually give better outcomes as more effort is expended) but very, very low intelligence (as the outcomes are better mostly by luck, ...


8

In English, the fringe is (also) defined as the outer, marginal, or extreme part of an area, group, or sphere of activity. In the context of AI search algorithms, the state (or search) space is usually represented as a graph, where nodes are states and the edges are the connections (or actions) between the corresponding states. If you're performing a tree (...


7

For a more intelligent approach than random or exhaustive searches, you could try a genetic algorithm such as NEAT http://nn.cs.utexas.edu/?neat. However, this has no guarantee to find a global optima, it is simply an optimization algorithm based on performance and is therefore vulnerable to getting stuck in a local optima.


7

If a computer is just brute-forcing the solution, it's not learning anything or using any kind of intelligence at all, and therefore it shouldn't be called "artificial intelligence." It has to make decisions based on what's happened before in similar instances. For something to be intelligent, it needs a way to keep track of what it's learned. A chess ...


6

There is lots of misconceptions about AI, specifically the idea that it is about making computers "think" like humans, simulating brain, the sci-fi robots taking over the world, all the philosophical discussions around brain as machine etc. The practice/reality of AI is about "using computing to solve problems" which basically means you take any problem, ...


6

This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details. First, let's review the definitions: Your definitions of admissible and consistent are correct. An admissible heuristic is basically just "optimistic". It never overestimates a distance. A consistent ...


6

As @nbro has already said that Hill Climbing is a family of local search algorithms. So, when you said Hill Climbing in the question I have assumed you are talking about the standard hill climbing. The standard version of hill climb has some limitations and often gets stuck in the following scenario: Local Maxima: Hill-climbing algorithm reaching on the ...


6

In the context of AI: Search refers to Simon & Newell's General Problem Solver, and it's many (many) descendant algorithms. These algorithms take the form: a. Represent a current state of some part of the world as a vertex in a graph. b. Represent, connected to the current state by edges, all states of the world that could be reached from the current ...


5

Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.


5

State space search is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case. State space search is an abstraction which can be customized for a particular problem via three ingredients: Some representation for candidate solutions to the problem (e.g. permutation ...


5

Strictly speaking, a tree is a graph, but one which among other criteria is minimally connected (only one path between any two nodes) and acyclic (ie no loops). Tree search, also known as tree traversal, visits each node in a tree structure exactly once. There are different orders in which the nodes are visited depending on the type of search (breadth-first ...


5

There is always a lot of confusion about this concept, because the naming is misleading, given that both tree and graph searches produce a tree while exploring the search space, which is usually represented as a graph. The other answers are currently incorrect. Differences Firstly, we have to understand that the underlying problem (or search space) is ...


5

Hill climbing is not an algorithm, but a family of "local search" algorithms. Specific algorithms which fall into the category of "hill climbing" algorithms are 2-opt, 3-opt, 2.5-opt, 4-opt, or, in general, any N-opt. See chapter 3 of the paper "The Traveling Salesman Problem: A Case Study in Local Optimization" (by David S. Johnson and Lyle A. McGeoch) for ...


4

Paper Szegedy C, Vanhoucke V, Ioffe S, et al. Rethinking the inception architecture for computer vision[J]. arXiv preprint arXiv:1512.00567, 2015. gives some general design principles: Avoid representational bottlenecks, especially early in the network; Balance the width and depth of the network. Optimal performance of the network can be reached ...


4

The difference between a local search algorithm (like beam search) and a complete search algorithm (like A*) is, for the most part, small. Local search algorithms will not always find the correct or optimal solution, if one exists. For example, with beam search (excluding an infinite beam width), it sacrifices completeness for greater efficiency by ordering ...


4

What it comes down to is that most AI problems can be characterized as search problems. Let's just go through some examples: Object recognition & scene building (e.g. the process of taking audio-visual input of your surroundings and understanding it in a 3D and contextual sense) can be treated as searching for known objects in the input. Mathematical ...


4

A* is a best-first search algorithm, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an admissible heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$. There are other best-first search algorithms, which differ only in ...


4

Yes, UCS is a special case of A*. UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ means the same thing as in UCS and $h(n)$, called the "heuristic" function, is an estimate of the distance from $n$ to the goal ...


4

This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another and vice-versa. Think of it as a game of rock paper scissors. Specifically, you may find that sometimes $h_1 < h_2$ and in other times $h_2 < h_1$, where $...


3

When we climb a hill: We move higher in altitude. The person who is climbing, will always look for rocks/mud on the hill that are higher, so that he can climb higher. That is what the algorithm does too. We are assuming that there is a hill of numbers. The larger numbers are placed higher than the smaller numbers. So if we want to climb up the hill, we ...


3

In general, Google autocompletes (and produces search results) based on wide variety of factors, including (but not limited to) your location, your search history, your other Google accounts, your site visit history, your language settings, etc. For the specific question, I see a few ways in which Google might have access to the relevant information: If ...


3

If I am correct, the branching factor is the maximum number of successors of any node You are correct, they should also be the immediate ones: If 11 is the goal state and I start going backwards, is 10 considered as successor of 5? Even if it do not leads me further to my start state 1? No, there is also a bit of misunderstanding of bidirectional search:...


3

Why would one professor only teach searching algorithms in AI course? What are the advantages/disadvantages? My answer to this question is that there are lots of problems where the solution can be found using searching. Take an example of Tic Tac Toe. If you are designing an intelligent computer player for this, then what you will do is that you will form a ...


3

The steepest hill climbing algorithms works well for convex optimization. However, real world problems are typically of the non-convex optimization type: there are multiple peaks. In such cases, when this algorithm starts at a random solution, the likelihood of it reaching one of the local peaks, instead of the global peak, is high. Improvements like ...


3

Tabu search uses memory to rule out parts of the neighborhood for local search, allowing the trajectory to typically pass through local optima instead of getting stuck in them.


3

You could parallelize the search by dividing the global space in distinct regions/subsets. Then apply in each region a local search. This way you can search the global space systematically, more exhaustively and perhaps in different ways (e.g by applying a different local search method to each region). Finally you can compare the results and choose the best ...


3

The answer is yes, exhaustive search is a fundamental principle in AI. Like the OP recognized it is used for solving chess-like games and can also be used in many other domains like pathplanning or PDDL-solving. From a theoretical point of view, a brute-force search is an elegant method for solving every problem. The reason, why heuristics are used in real-...


3

First of all you need an initial solution. You will then improve this solution with hill climbing. For your initial solution, you can color the map randomly using the K colors. This will most likely result in conflicts (adjacent regions of the same color). Then the hill climbing part: Find a region which has conflicts and swap its color for another color, ...


Only top voted, non community-wiki answers of a minimum length are eligible