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
1
vote
0answers
22 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,...
0
votes
0answers
14 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 ...
1
vote
1answer
34 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 ...
0
votes
0answers
14 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 ...
3
votes
0answers
47 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?" ...
2
votes
1answer
82 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 ...
3
votes
0answers
96 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 ...
1
vote
1answer
467 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
338 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
205 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....
1
vote
1answer
3k 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 ...
2
votes
0answers
177 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 ...
3
votes
0answers
788 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 ...
1
vote
0answers
76 views

Why would my neural network run faster on my laptop than on my university's supercomputer?

I am trying to get my neural network running on my university's supercomputer in order to decrease its runtime (not for training, for testing - feedforward runs only). However, the Matlab function 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 ...
4
votes
0answers
49 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 ...
30
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"...
1
vote
1answer
361 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, ...
3
votes
0answers
165 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 ...
6
votes
1answer
214 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 ...
2
votes
1answer
548 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 \...