Questions tagged [computational-complexity]

The amount of resources required to run a given algorithm in relation to a given task.

Filter by
Sorted by
Tagged with
31
votes
7answers
7k views

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

To produce tangible results in the field of AI/ML, one must take theoretical results under the lens of computational complexity. Indeed, minimax effectively solves any two-person "board game"...
6
votes
1answer
234 views

What does "hard for AI" look like?

In theoretical computer science, there is a massive categorization of the difficulty of various computational problems in terms of their asymptotic worst-time computational complexity. There doesn't ...
4
votes
0answers
54 views

Given an input $x \in R^{1\times d}$ and a network with $s$ hidden layers, is the time complexity of the forward pass $O(d^{2}s)$? [duplicate]

I have a neural network that takes as an input a vector of $x \in R^{1\times d}$ with $s$ hidden layers and each layer has $d$ neurons (including the output layer). If I understand correctly the ...
3
votes
1answer
1k views

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

From this link, AlphaGo would take millennia to run in regular hardware. They generated 29 million games for the final result, which means it's going to take me about 1700 years to replicate this. ...
3
votes
0answers
49 views

Do we need as much information to know if we can can answer a question as we need to actually answer the question?

I am reading The Book of Why: The New Science of Cause and Effect by Judea Pearl, and in page 12 I see the following diagram. The box on the right side of box 5 "Can the query be answered?" ...
3
votes
1answer
123 views

Why multiplayer, imperfect information, trick-taking card games are hard for AI?

AI reached a super-human level in many complex games such as Chess, Go ,Texas hold’em Poker, Dota2 and StarCarft2. However it still did not reach this level in trick-taking card games. Why there is no ...
3
votes
0answers
874 views

How much time does it take to train DQN on Atari environment?

I am trying to build a DQN model for the Atari Pong game, but I am not sure whether the model is learning at all. I am using the architecture described in the paper Playing Atari with Deep ...
3
votes
0answers
182 views

When using hashing in tile coding, why are memory requirements reduced and there is only a little loss of performance?

In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto explain, on page 221, a form of tile coding using hashing, to reduce memory consumption. I have two questions ...
3
votes
1answer
307 views

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

Given infinite resources/time, one could create AGIs by writing code to simulate infinite worlds. By doing that, in some of the worlds, AGIs would be created. Detecting them would be another issue. ...
2
votes
1answer
86 views

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

Say I have an Machine/Deep learning algorithm I developed on a desktop pc to achieve a real-time classification of time series events from a sensor. Once the algorithm is trained and performs good, I ...
2
votes
2answers
2k views

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

I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$. While I am reading, at some points, I found ...
2
votes
1answer
593 views

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

I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem. So, I did formulate a 3-SAT problem by defining 3-CNF: $$(x_1 \lor x_2) \land (\neg x_3 \...
2
votes
0answers
206 views

What is symbol-to-number differentiation?

I recently came across symbol-to-symbol and symbol-to-number differentiation, out of which symbol to symbol seemed fairly straightforward - the computational graph is extended to include gradient ...
1
vote
1answer
4k views

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

How do I determine the computational complexity (big-O notation) of the forward pass of a convolutional neural network? Let's assume for simplicity that we use zero-padding such that the input size ...
1
vote
1answer
366 views

How to estimate the cost and time to complete an AI Project [closed]

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

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

In the data preparation phase, we have to divide the dataset into two parts: the training dataset and the test dataset. I have seen this post regarding the time complexity for training a model. ...
1
vote
1answer
38 views

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

I have an input tensor of shape $\mathbf{(3, 32, 32)}$ consisting of 3 channels, 16 rows, and 16 columns. I want to convolve the input tensor using $\mathbf{(3 \times 3)}$ kernel/filter. How can I ...
1
vote
0answers
31 views

Why does research on faster Transformers focus on the query-key product?

A lot of recent research on Transformers has been devoted to reducing the cost of the self-attention mechanism: $$\text{softmax}\left(\frac{Q K^T}{\sqrt{d}} \right)V,$$ As I understand it, the runtime,...
1
vote
1answer
736 views

What is the space complexity for training a neural network using back-propagation?

Suppose that a simple feedforward neural network (FFNN) contains $n$ hidden layers, $m$ training examples, $x$ features, and $n_l$ nodes in each layer. What is the space complexity to train this FFNN ...
1
vote
0answers
477 views

What is the computational complexity in terms of Big-O notation of a Gated Recurrent Unit Neural network?

I have been digging up of articles across the internet in context of computational complexity of GRU. Interestingly, I came across this article, http://cse.iitkgp.ac.in/~psraja/FNNs%20,RNNs%20,LSTM%...
1
vote
0answers
50 views

What is the efficiency of trained neural networks?

Training neural networks takes a while. My question is, how efficient is a neural network that is completely trained (assuming it's not a model that is constantly learning)? I understand that this is ...
1
vote
1answer
230 views

What is the time complexity of the upsampling stage of the U-net?

I am trying to determine the complexity of the neural network we use. The neural network is a U-net generator with an input shape of NxN (not an image but image-like data) and output of the same shape....
0
votes
0answers
9 views

Why is the maximal data path of RNNs $O(logk(n))$

On this video https://www.youtube.com/watch?v=OyFJWRnt_AY at about 1:07:00, complexity and maximal data path for transformers and RNNs is compared. What it says about maximal data path : The maximal ...
0
votes
0answers
24 views

How to calculate computational efficiency of Deep Learning Models?

I am trying to make a comparison between two simple 5 layer neural network models. One of the models has 3 frozen layers as I've implemented transfer learning in that architecture. The other is ...
0
votes
0answers
15 views

In terms of self play which is a harder problem: chess or kung-fu

Giraffe (or Alpha Zero) do a very solid job on superhuman chess. How does the complexity of the "game", especially for simulation in 3d competitive play environments, differ between chess ...