Qual é a complexidade de tempo para treinar uma rede neural usando retropropagação?

Suponha que um NN contenha $n$ camadas ocultas, $m$ exemplos de treinamento, $x$ recursos e $n_i$ nós em cada camada. Qual é a complexidade de tempo para treinar esse NN usando a propagação traseira?

Eu tenho uma idéia básica sobre como eles encontram a complexidade do tempo dos algoritmos, mas aqui há quatro fatores diferentes a serem considerados aqui, como iterações, camadas, nós em cada camada, exemplos de treinamento e talvez mais fatores. Encontrei uma resposta aqui, mas não estava clara o suficiente.

Existem outros fatores, além dos mencionados acima, que influenciam a complexidade de tempo do algoritmo de treinamento de uma NN?

Não vi uma resposta de uma fonte confiável, mas tentarei responder a mim mesmo, com um exemplo simples (com meu conhecimento atual).

Em geral, observe que o treinamento de um MLP usando a propagação traseira é geralmente implementado com matrizes.

Complexidade temporal da multiplicação da matriz

A complexidade temporal da multiplicação de matrizes para $M_{ij} * M_{jk}$ é simplesmente $\mathcal{O}(i*j*k)$ .

Observe que estamos assumindo o algoritmo de multiplicação mais simples aqui: existem outros algoritmos com uma complexidade de tempo um pouco melhor.

Algoritmo de avanço de feedforward

O algoritmo de propagação de feedforward é o seguinte.

Primeiro, para passar da camada $i$ para $j$ , você precisa

$$S_j = W_{ji}*Z_i$$

Então você aplica a função de ativação

$$Z_j = f(S_j)$$

Se tivermos $N$ camadas (incluindo as camadas de entrada e saída), isso será executado $N-1$ vezes.

Exemplo

Como exemplo, vamos calcular a complexidade do tempo para o algoritmo de encaminhamento para um MLP com $4$ camadas, em que $i$ indica o número de nós da camada de entrada, $j$ o número de nós na segunda camada, $k$ o número de nós na terceira camada e $l$ o número de nós na camada de saída.

Como existem $4$ camadas, você precisa de $3$ matrizes para representar pesos entre essas camadas. Vamos denotá-los por $W_{ji}$ , $W_{kj}$ e $W_{lk}$ , onde $W_{ji}$ é uma matriz com $j$ linhas e colunas $i$ ( $W_{ji}$ contém os pesos que vão da camada $i$ à camada $j$ ).

Suponha que você tenha $t$ exemplos de treinamento. Para propagação da camada $i$ a $j$ , temos primeiro

$$S_{jt} = W_{ji} * Z_{it}$$

e esta operação (isto é, multiplicação de matrizes) tem complexidade de tempo $\mathcal{O}(j*i*t)$ . Então aplicamos a função de ativação

$$Z_{jt} = f(S_{jt})$$

e este tem $\mathcal{O}(j*t)$ complexidade de tempo, porque é uma operação de elemento a elemento.

Então, no total, temos

$$\mathcal{O}(j*i*t + j*t) = \mathcal{O}(j*t*(t + 1)) = \mathcal{O}(j*i*t)$$

Usando a mesma lógica, para ir $j \to k$ , temos $\mathcal{O}(k*j*t)$ e, para $k \to l$ , temos $\mathcal{O}(l*k*t)$ .

No total, a complexidade do tempo para propagação de feedforward será

$$\mathcal{O}(j*i*t + k*j*t + l*k*t) = \mathcal{O}(t*(ij + jk + kl))$$

Não tenho certeza se isso pode ser simplificado ainda mais ou não. Talvez seja apenas $\mathcal{O}(t*i*j*k*l)$ , mas eu não tenho certeza.

Algoritmo de propagação traseira

O algoritmo de retropropagação prossegue da seguinte maneira. Partindo da camada de saída $l \to k$ , calculamos o sinal de erro, $E_{lt}$ , uma matriz que contém os sinais de erro para nós na camada $l$

$$E_{lt} = f'(S_{lt}) \odot {(Z_{lt} - O_{lt})}$$

onde $\odot$ significa multiplicação por elementos. Note-se que $E_{lt}$ tem $l$ linhas e $t$ colunas: ele simplesmente significa que cada coluna é o sinal de erro para treinar exemplo $t$ .

We then compute the "delta weights", $D_{lk} \in \mathbb{R}^{l \times k}$ (between layer $l$ and layer $k$)

$$D_{lk} = E_{lt} * Z_{tk}$$

where $Z_{tk}$ is the transpose of $Z_{kt}$.

We then adjust the weights

$$W_{lk} = W_{lk} - D_{lk}$$

Para $l \to k$ , temos, assim, a complexidade do tempo $\mathcal{O}(lt + lt + ltk + lk) = \mathcal{O}(l*t*k)$ .

Agora, voltando de $k \to j$ . Primeiro temos

$$E_{kt} = f'(S_{kt}) \odot (W_{kl} * E_{lt})$$

Então

$$D_{kj} = E_{kt} * Z_{tj}$$

And then

$$W_{kj} = W_{kj} - D_{kj}$$

where $W_{kl}$ is the transpose of $W_{lk}$. For $k \to j$, we have the time complexity $\mathcal{O}(kt + klt + ktj + kj) = \mathcal{O}(k*t(l+j))$.

And finally, for $j \to i$, we have $\mathcal{O}(j*t(k+i))$. In total, we have

$$\mathcal{O}(ltk + tk(l + j) + tj (k + i)) = \mathcal{O}(t*(lk + kj + ji))$$

which is same as feedforward pass algorithm. Since they are same, the total time complexity for one epoch will be

$$O(t*(ij + jk + kl)).$$

This time complexity is then multiplied by number of iterations (epochs). So, we have

$$O(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 respectively $i$, $j$, $k$ and $l$ nodes, with $t$ training examples and $n$ epochs. The result was $\mathcal{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 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 (just look at the formula).

So, the complexity for learning $m$ examples, where each gets repeated $e$ times, is $\mathcal{O}(w*m*e)$.

The bad news is that there's no formula telling you what number of epochs $e$ you need.

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.