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 ...
  • 36.4k
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 ...
  • 36.4k
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 ...
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 ...
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, ...
  • 221
5 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 ...
  • 36.4k
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 ...
  • 221
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 ...
  • 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, ...
  • 25.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-...
  • 36.4k
3 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. ...
  • 1,176
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 ...
  • 36.4k
2 votes

Instead of accumulating the gradient, can we accumulate loss values?

Accumulating the loss like that doesn't improve the memory requirements, because the memory consumption depends on the size of your computational graph. In other words, each time you add a term to the ...
  • 1,157
2 votes
Accepted

Why is the time complexity of the Triplet Loss $O(N^3)$

For each anchor data point $x_i^a$ in class $j$, the intra-distance should be computed $g_j$ times, where $g_j$ is the sample size of that class and the inter-distance should be computed as $N$ times, ...
  • 36
1 vote

computational complexity for batch normalization technique

Batch Normalization is achieved through a normalization step that fixes the means and variances of each layer's inputs. For a Batch of size N, computing the mean and variance will have a complexity of ...
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 ...
  • 36.4k
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 ...
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 ...
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 ...
  • 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 ...
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-...
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, ...
  • 36.4k

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