Tag Info

16

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search. However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an ...

15

AIXI is a Bayesian, non-Markov, reinforcement learning and artificial general intelligence agent that is incomputable, given the involved incomputable Kolmogorov complexity. However, there are approximations of AIXI, such as AIXItl, described in Universal Artificial Intelligence: Universal Artificial Intelligence: Sequential Decisions based on Algorithmic ...

13

To be concrete, exact Bayesian inference is (often) intractable (that is, not polynomially computable) because it involves the computation of an integral over a range of real (or even floating-point) numbers, which is not a polynomial-time operation. More precisely, for example, if you want to find the parameters $\mathbf{\theta} \in \Theta$ of a model given ...

9

I think you're coming at your problem slightly wrong... what you're essentially talking about is a belief network. You may want to look into existing Bayesian Learning techniques to get your head around this, but belief networks commonly use the exact scenario you're talking about; using a set of known (or uncertain facts) statements to produce some ...

9

This question gets at a really interesting fact about AI research in general: AI is hard. In fact, almost every AI problem is computationally hard (typically NP-Hard, or #P-Hard). This means that most new areas of AI research starts out by characterizing some problem that is intractable, and proposing an algorithm that technically works, but is too slow to ...

8

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are: inserting elements testing if elements are already in there Pretty much every programming language should already have support for a data ...

7

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here: http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf A few key points: In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM....

6

It appears to use Recurrent NNs (RNNs) that have a 'Long Short-Term Memory' (LTSM) architecture. Here's a summary of the development process that the author, Ross Goodwin, went through to create it. It seems to me (and is also observed in the above link) that the output is rather poor - simply comparable to what one might expect from Markov chains, a ...

6

The following post has a bit of math, which I hope helps to explain the problem better. Unfortunately it seems, this SE site does not support LaTex: Document summarization is very much an open problem in AI research. One way this task is currently handled is called "extractive summarization". The basic strategy is as follows: Split this document into ...

6

Yes, this is possible. There is actually a pretty easy way that doesn't even require machine learning and can be implemented with a small amount of code. You just use a framework for image processing (e.g. PIL for Python), find the marks by going over your image with an appropriate filter and use the implemented crop function, that the framework hopefully ...

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 ...

5

A closed expression refers to a formula which has no free variables [1]. This is also called sentence. In a logic system you have a set of axioms which are sentences and rules which state how to derive a sentence from this [2]. If a sentence can be derived from the axioms, this means that the axioms entail this sentence. If a sentence is not derivable, it is ...

5

A simple form of sarcasm involves a direct reversal of the literal meaning of the statement, eg "Great weather we're having" (during a thunderstorm), "just what I needed" (when something goes wrong). The problem with doing this in random sentences is that you may have no context to establish the reversal of the literal meaning. You could possibly construct ...

5

The discount factor does appear twice, and this is correct. This is because the function you are trying to maximise in REINFORCE for an episodic problem (by taking the gradient) is the expected return from a given (distribution of) start state: $$J(\theta) = \mathbb{E}_{\pi(\theta)}[G_t|S_t = s_0, t=0]$$ Therefore, during the episode, when you sample the ...

5

Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available. I don't have experience with the specific game you mentioned (Connect6), but from a quick look ...

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 ...

5

The logical induction algorithm can make predictions about whether mathematical statements are true or false, which are eventually consistent; e.g. if A is true, its probability will eventually reach 1; if B implies C then C's probability will eventually reach or exceed B's; the probability of D will eventually be the inverse of not(D); the probabilities of ...

4

It will not be single DNN architecture, rather it will be a collection of different DNN architectures that are used together to make the final decision. Convolutions are using the images/videos from the camera. Other architectures use other sensory sources. These DNNs will be trained to compute the high-level features from their sensory sources and then ...

4

Semantics Matters The answer depends on the definition intelligence being used. If you define intelligence as the ability to adapt, a number of things could be considered intelligent that don't normally fit under the classic AI umbrella. Nonlinear least-squares Marquardt-Levenberg curve fitting algorithm with a substantial but finite set of models, ...

4

Some good places to start would be cognitive architectures and as mentioned in another answer intelligent agents. The question is broad but you definitely want to look into planning & decision making. You might also want to check out the L5 and L6 layers of Hierarchical Temporal Memory (As in Nupic) as it relates to feedback, behavior and attention. If ...

4

For future reference, I will merely point you to a technique you can implement to test the correctness or lack thereof, of your backpropagation implementation. Ps: don't feel too bad for having gotten it slightly wrong, "backpropagation is notoriously difficult to implement" - source :). In fact, there is a technique called "Gradient checking" meant ...

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

This will not be that hard of a problem once you have a lot of training data. But, before you have a lot of training data, you will need to get some training data one way or another. You will need a lot of training data for quite a few of the models that will give you a high accuracy. Then, you will probably want to use a Long short term memory recurrent ...

4

Neil's answer already provides some intuition as to why the pseudocode (with the extra $\gamma^t$ term) is correct. I'd just like to additionally clarify that you do not seem to be misunderstanding anything, Equation (13.6) in the book is indeed different from the pseudocode. Now, I don't have the edition of the book that you mentioned right here, but I ...

3

In-between your input and desired output, there's obviously a huge space to search. The more relevant domain information you include as features, the higher chance that the Deep Learning (DL) algorithm can find the desired mapping. At this early stage in DL research, there aren't so many rules of thumb to tell you what features to explicitly encode - not ...

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

AFAIK, normally detection algorithms work in a sub-window of the image and not the whole of it. For example, for a specific size and orientation you slide a sub-window on the image and extract sub-images. Then you apply your algorithm on every sub-image for detection and report the size-and-orientations with positive results. You can have a single neural ...

3

What you are calling 'analyzing the surroundings' is generally referred to as perception. Self-driving cars sense their surroundings using cameras, radars, lidars often combining or fusing more than one sensor to paint a picture of the environment. A lot of algorithms get used for fusing the sensor data and then deriving an understanding of the surrounding. ...

3

Here is a paper called "StackGAN: Text to Photo-realistic Image Synthesis with Stacked Generative Adversarial Networks". Does it answer your question?

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