Предположим, что NN содержит скрытых слоев, обучающих примеров, объектов и узлов на каждом уровне. Какова сложность времени для обучения этой NN с использованием обратного распространения?
У меня есть базовая идея о том, как они находят временную сложность алгоритмов, но здесь есть 4 различных фактора, которые необходимо учитывать: итерации, уровни, узлы в каждом слое, примеры обучения и, возможно, другие факторы. Я нашел ответ здесь но он не был достаточно ясен.
Существуют ли другие факторы, помимо упомянутых выше, которые влияют на временную сложность алгоритма обучения NN?
Ответы:
Я не видел ответа из надежного источника, но постараюсь ответить на него сам, на простом примере (с моими нынешними знаниями).
В общем, обратите внимание, что обучение MLP с использованием обратного распространения обычно осуществляется с помощью матриц.
Временная сложность умножения матриц
Временная сложность умножения матриц дляMij∗Mjk просто O(i∗j∗k) .
Обратите внимание, что здесь мы предполагаем простейший алгоритм умножения: существуют некоторые другие алгоритмы с несколько лучшей временной сложностью.
Алгоритм прямой связи
Алгоритм прямого распространения заключается в следующем.
Во-первых, чтобы перейти от слояi к j , вы делаете
Затем вы применяете функцию активации
Если у нас естьN слоев (включая слой ввода и вывода), это будет выполнено N−1 раз.
пример
В качестве примера, давайте вычислим временную сложность для алгоритма прямого прохода для MLP с4 уровнями, где i обозначает количество узлов входного уровня, j количество узлов на втором уровне, k количество узлов в третий слой и l количество узлов в выходном слое.
Поскольку существует4 слоя, вам нужно 3 матрицы для представления весов между этими слоями. Обозначим их через Wji , Wkj и Wlk , где Wji - матрица с j строками и столбцами i ( таким образом, Wji содержит веса, идущие от слоя i к слою j ).
Предположим , у вас естьt примеры обучения. Для распространения от слоя i к j , мы сначала
и эта операция (т.е. умножение матрицы) имеетO(j∗i∗t) временную сложность. Затем мы применяем функцию активации
и это имеетO(j∗t) временную сложность, потому что это поэлементная операция.
Итак, в итоге мы имеем
Используя ту же логику, для переходаj→k имеем O(k∗j∗t) , а при k→l имеем O(l∗k∗t) .
In total, the time complexity for feedforward propagation will be
I'm not sure if this can be simplified further or not. Maybe it's justO(t∗i∗j∗k∗l) , but I'm not sure.
Back-propagation algorithm
The back-propagation algorithm proceeds as follows. Starting from the output layerl→k , we compute the error signal, Elt , a matrix containing the error signals for nodes at layer l
where⊙ means element-wise multiplication. Note that Elt has l rows and t columns: it simply means each column is the error signal for training example t .
Затем мы корректируем вес
Forl→k , we thus have the time complexity O(lt+lt+ltk+lk)=O(l∗t∗k) .
Now, going back fromk→j . We first have
Then
And then
whereWkl is the transpose of Wlk . For k→j , we have the time complexity O(kt+klt+ktj+kj)=O(k∗t(l+j)) .
And finally, forj→i , we have O(j∗t(k+i)) . In total, we have
which is same as feedforward pass algorithm. Since they are same, the total time complexity for one epoch will beO(t∗(ij+jk+kl)).
This time complexity is then multiplied by number of iterations (epochs). So, we haveO(n∗t∗(ij+jk+kl)), where n is number of iterations.
Notes
Note that these matrix operations can greatly be paralelized by GPUs.
Conclusion
We tried to find the time complexity for training a neural network that has 4 layers with respectivelyi , j , k and l nodes, with t training examples and n epochs. The result was O(nt∗(ij+jk+kl)) .
We assumed the simplest form of matrix multiplication that has cubic time complexity. We used batch gradient descent algorithm. The results for stochastic and mini-batch gradient descent should be same. (Let me know if you think the otherwise: note that batch gradient descent is the general form, with little modification, it becomes stochastic or mini-batch)
Also, if you use momentum optimization, you will have same time complexity, because the extra matrix operations required are all element-wise operations, hence they will not affect the time complexity of the algorithm.
I'm not sure what the results would be using other optimizers such as RMSprop.
Sources
The following article http://briandolhansky.com/blog/2014/10/30/artificial-neural-networks-matrix-form-part-5 describes an implementation using matrices. Although this implementation is using "row major", the time complexity is not affected by this.
If you're not familiar with back-propagation, check this article:
http://briandolhansky.com/blog/2013/9/27/artificial-neural-networks-backpropagation-part-4
источник
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 haveO(w) where w is the number of weights, i.e., n∗ni , assuming full connectivity between your layers.
The back-propagation has the same complexity as the forward evaluation (just look at the formula).
So, the complexity for learningm examples, where each gets repeated e times, is O(w∗m∗e) .
The bad news is that there's no formula telling you what number of epochse you need.
источник
e
times for each ofm
examples. I didn't bother to compute the number of weights, I guess, that's the difference.w = ij + jk + kl
. basically sum ofn * n_i
between layers as you noted.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 which the time required to find a solution increases with the number of parameters (weights). In short, the time complexities of a range of different gradient-based methods (including second-order methods) seem to be similar.
Six different error functions exhibit a median run-time order of approximately O(N to the power 4) on the N-2-N encoder in this paper:
Lister, R and Stone J "An Empirical Study of the Time Complexity of Various Error Functions with Conjugate Gradient Back Propagation" , IEEE International Conference on Artificial Neural Networks (ICNN95), Perth, Australia, Nov 27-Dec 1, 1995.
Summarised from my book: Artificial Intelligence Engines: A Tutorial Introduction to the Mathematics of Deep Learning.
источник