Tag Info

23

I haven't seen an answer from a trusted source, but I'll try to answer this myself, with a simple example (with my current knowledge). In general, note that training an MLP using back-propagation is usually implemented with matrices. Time complexity of matrix multiplication The time complexity of matrix multiplication for $M_{ij} * M_{jk}$ is simply $\... 9 Let's suppose that we have an MLP with$15$inputs,$20$hidden neurons and$2$output neurons. The operations performed are only in the hidden and output neurons, given that the input neurons only represent the inputs (so they do not perform any operation). Each hidden neuron performs a linear combination of its inputs followed by the application of a non-... 5 For the evaluation of a single pattern, you need to process all weights and all neurons. Given that every neuron has at least one weight, we can ignore them, and have$\mathcal{O}(w)$where$w$is the number of weights, i.e.,$n * n_i$, assuming full connectivity between your layers. The back-propagation has the same complexity as the forward evaluation (... 3 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 expressed as a function of the input's size$n$(but this does not always have to be the case: for instance, you can express the time complexity as a function ... 3 To the best of my knowledge, there haven't yet been many academic publications in this area, which could be broadly said to fall within Search-Based Software Engineering. Here are the ones I know of. Jerry Swan and Nathan Burles. Templar - A Framework for Template-Method Hyper-Heuristics. In: Genetic Programming - 18th European Conference, EuroGP 2015, ... 2 I found a paper that gives a table of time complexities for different architectures using linear programming-based training: https://arxiv.org/abs/1810.03218 2 A potential disadvantage of gradient-based methods is that they head for the nearest minimum, which is usually not the global minimum. This means that the only difference between these search methods is the speed with which solutions are obtained, and not the nature of those solutions. An important consideration is time complexity, which is the rate at ... 2 There is some recent work addressing this issue, to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. See Pointer Networks. 2 To the best of my knowledge, there isn't any difference between the algorithmic methods and the NN methods. Those that can solve in polynomial time do not give a precise solution. Those that do give a precise solution do not solve in polynomial time. Of those that give a precise solution, the fastest takes$2^N$, but it blows up in terms of memory. The ... 2 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 also applies to the case of computing the time complexity of the algorithm that tests a neural network with multiple LSTM layers, so one may need to assume how ... 1 First of all, for a lot of realistic problems, the fitness function evaluation is usually orders of magnitude greater in complexity than the rest of the genetic algorithm. This is not always true, but often is true (e.g. imagine trying to optimise a simulation where you need to execute the simulation completely to obtain the fitness). So optimising the GA ... 1 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 parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and ... 1 No. In general, you can't find a tight bound for evolutionary algorithms, and it is one of the main difference of these algorithms with the classical algorithms. You should notice that it does not mean you can't find when the evolutionary algorithms are finished! But, you can't find a tight bound for the algorithms time complexity to reach to the optimal ... 1 The update equation for value iteration that you show is time complexity$O(|\mathcal{S}\times\mathcal{A}|)$for each update to a single$V(s)$estimate, because it iterates over all actions to perform$\text{max}_a$and over all next states for$\sum_{s'}\$. The sources you have found are probably counting an entire sweep through the state space as an "...

1

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-Hard, but are unsure how to show that it is also P-Hard. This is more of a TCS question than an AI question, but shouldn't be too difficult. You just need to ...

1

There are a few technical papers and books on the topic Computational Limitations on Learning from Examples (1988) by Leonard Pitt and Leslie G. Valiant, published in Journal of the ACM Training a 3-node neural network is NP-complete (1992) by Avrim L. Blum and Ronald L. Rivest, published in Neural Networks Computational complexity of neural networks: a ...

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