Questions tagged [computational-complexity]
The amount of resources required to run a given algorithm in relation to a given task.
13
questions
1
vote
0answers
37 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
49 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
55 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
298 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
0answers
26 views
How to derive asymptotic run-time of seq2seq RNN? [duplicate]
I want to know the computational complexity of a sequence to sequence RNN in terms of the input and output length. I was wondering how I might go about deriving this in both training and inference.
2
votes
0answers
76 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 ...
2
votes
0answers
212 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
55 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
1answer
353 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
42 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 ...
2
votes
2answers
68 views
Using human driver behavior data to train autonomous vehicles
If I have a car and a human is driving a car on a daily basis. I create a system to analyze the human routines of driving and implement this system in maybe 10,000 cars. I use that data to train an ...
1
vote
1answer
335 views
How to estimate the cost and time to complete an AI Projects
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, ...
2
votes
1answer
359 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 \...
