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 ...
- 39.5k
14
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 ...
- 39.5k
11
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 ...
- 9,207
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 ...
- 9,207
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 ...
- 39.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 ...
- 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, ...
- 30.3k
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-...
- 39.5k
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,186
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 ...
- 39.5k
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,536
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
Is size of trained model on disk a good measure of model complexity?
The title of your question asks about model complexity. Yet the body of your question talks about this metric as being useful for embedded systems like a smartphone, which have more limited memory.
I ...
- 2,255
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 ...
- 11
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 ...
- 39.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 ...
- 932
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 ...
- 118
1
vote
What is the space complexity for training a neural network using back-propagation?
I will not tell you what the exact space complexity of training an FFNN with GD and BP is (because that actually depends on the specific implementation of GD and BP and I don't want to dive into the ...
- 39.5k
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-...
- 9,207
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, ...
- 39.5k
Only top scored, non community-wiki answers of a minimum length are eligible