# Tag Info

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

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

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

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

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

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

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

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

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

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 ...
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, ...
1 vote

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

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

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

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