16 votes

What are examples of promising AI/ML techniques that are computationally intractable?

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 ...
user avatar
  • 34.5k
13 votes

What are examples of promising AI/ML techniques that are computationally intractable?

Exact Bayesian inference is (often) intractable (i.e. there is no closed-form solution, or numerical approximations are also computationally expensive) because it involves the computation of an ...
user avatar
  • 34.5k
10 votes

What are examples of promising AI/ML techniques that are computationally intractable?

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 ...
user avatar
5 votes
Accepted

What does "hard for AI" look like?

Nice Question! This is a perennial topic of discussion among AI researchers. The short answer is "we don't really know which topics are hard in general, but we do know which we haven't got good ...
user avatar
5 votes

What are examples of promising AI/ML techniques that are computationally intractable?

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, ...
user avatar
  • 221
4 votes

What is the computational complexity of the forward pass of a convolutional neural network?

What is the time complexity? The time complexity of an algorithm is the number of basic operations, such as multiplications and summations, that the algorithm performs. The time complexity is usually ...
user avatar
  • 34.5k
4 votes

What are examples of promising AI/ML techniques that are computationally intractable?

Hutter's "fastest and shortest algorithm for all well-defined problems" is the ultimate just-in-time compiler. It runs a given program and, in parallel, searches for proofs that some other program is ...
user avatar
  • 221
3 votes
Accepted

How to estimate the cost and time to complete an AI Project

If you are a freelancer, when a client asks to create a website we can easily measure how much the total cost is needed based on the requirements of the client. (the backend, UI/UX design, features, ...
user avatar
  • 24.5k
3 votes

What are examples of promising AI/ML techniques that are computationally intractable?

In general, partially-observable Markov decision processes (POMDPs) are also computationally intractable to solve exactly. However, there are several approximations methods. See, for example, Value-...
user avatar
  • 34.5k
3 votes

What are examples of promising AI/ML techniques that are computationally intractable?

Levin's search algorithm is a general method of function inversion. Many AI tasks are of this sort, e.g. given a cost or reward function (object -> cost or ...
user avatar
  • 221
2 votes

Would it take 1700 years to run AlphaGo Zero in commodity hardware?

Although the above statement holds important analogies to communicate the technical advances made by deep mind in the development of Alpha Go. It is inaccurate and should be taken skeptically. ...
user avatar
  • 1,146
2 votes
Accepted

What is the time complexity for testing a stacked LSTM model?

The time complexity of an algorithm always depends on its implementation (e.g. searching in a red-black tree has a different time complexity than searching in an unbalanced binary search tree). This ...
user avatar
  • 34.5k
1 vote
Accepted

If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?

This is just a partial/general answer that addresses one of your doubts. I will let others address your question about the specific algorithms that you are mentioning. Data efficiency refers to the ...
user avatar
  • 34.5k
1 vote
Accepted

Given an input of shape $(3, 32, 32)$, which is convolved with a $(3 \times 3)$ kernel, how do I calculate the FLOPS?

Each output pixel channel is a 3x3x3 filter, so 27 inputs which get multiplied by 27 weights and then added together. This is 27 FMA (fused-multiply-add) operations, or 27 multiply operations and 26 ...
user avatar
1 vote

How to know if a real-time classifier is achivable in a low-power emdedded system?

Regarding your first point, it depends on what neural network you would like to use, the sensor temporal resolution, and the capabilities of the embedded system. You can figure out the number of ...
user avatar
1 vote

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

I was struggling with the same question. This is what I came up with after thinking it through. With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the ...
user avatar
  • 11
1 vote
Accepted

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

After spending some time on the problem, I concluded that it is due to the fact that we need to store the heuristic function evaluations for all nodes during the traversal. So, one might claim that it ...
user avatar
1 vote

Why is exact inference in a Bayesian network both NP-hard and P-hard?

It's not completely clear from your question, but it looks like you want to prove that exact inference in a Bayesian Network is both NP-Hard and P-Hard. It appears that you have proven that it is NP-...
user avatar
1 vote

Is time/space estimation of possible actions required for creating an AGI?

I don't know if time/space estimation will be explicitly programmed into an AGI, but the estimation of the computational resources to perform a certain action is definitely useful. Humans (especially, ...
user avatar
  • 34.5k

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