Apa kompleksitas waktu untuk melatih jaringan saraf menggunakan back-propagation?

Misalkan NN berisi $n$ lapisan tersembunyi, contoh pelatihan $m$ , $x$ fitur, dan $n_i$ node di setiap lapisan. Apa kompleksitas waktu untuk melatih NN ini menggunakan back-propagation?

Saya punya ide dasar tentang bagaimana mereka menemukan kompleksitas waktu dari algoritma, tetapi di sini ada 4 faktor yang berbeda untuk dipertimbangkan di sini yaitu iterasi, layer, node di setiap layer, contoh pelatihan, dan mungkin lebih banyak faktor. Saya menemukan jawaban di sini tetapi tidak cukup jelas.

Apakah ada faktor lain, selain dari yang saya sebutkan di atas, yang mempengaruhi kompleksitas waktu dari algoritma pelatihan NN?

Saya belum melihat jawaban dari sumber tepercaya, tetapi saya akan mencoba menjawabnya sendiri, dengan contoh sederhana (dengan pengetahuan saya saat ini).

Secara umum, perhatikan bahwa melatih MLP menggunakan propagasi balik biasanya diterapkan dengan matriks.

Kompleksitas waktu dari perkalian matriks

Kompleksitas waktu dari perkalian matriks untuk $M_{ij} * M_{jk}$ hanyalah $\mathcal{O}(i*j*k)$ .

Perhatikan bahwa kita mengasumsikan algoritma multiplikasi paling sederhana di sini: ada beberapa algoritma lain dengan kompleksitas waktu yang lebih baik.

Algoritma umpan maju

Algoritma propagasi feedforward adalah sebagai berikut.

Pertama, untuk beralih dari layer $i$ ke $j$ , Anda lakukan

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

Kemudian Anda menerapkan fungsi aktivasi

$$Z_j = f(S_j)$$

Jika kita memiliki $N$ layer (termasuk layer input dan output), ini akan berjalan $N-1$ kali.

Contoh

Sebagai contoh, mari kita hitung kompleksitas waktu untuk algoritma pass maju untuk MLP dengan $4$ lapisan, di mana $i$ menunjukkan jumlah node dari layer input, $j$ jumlah node di lapisan kedua, $k$ jumlah node di lapisan ketiga dan $l$ jumlah node di lapisan output.

Karena ada $4$ lapisan, Anda perlu $3$ matriks untuk mewakili bobot antara lapisan-lapisan ini. Mari kita menandakannya dengan $W_{ji}$ , $W_{kj}$ dan $W_{lk}$ , di mana $W_{ji}$ adalah sebuah matriks dengan $j$ baris dan kolom $i$ ( $W_{ji}$ dengan demikian berisi bobot pergi dari layer $i$ ke layer $j$ ).

Asumsikan Anda memiliki $t$ contoh pelatihan. Untuk merambat dari layer $i$ ke $j$ , kita harus terlebih dahulu

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

dan operasi ini (yaitu perkalian matriks) memiliki kompleksitas waktu $\mathcal{O}(j*i*t)$ . Kemudian kami menerapkan fungsi aktivasi

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

dan ini memiliki kompleksitas waktu $\mathcal{O}(j*t)$ , karena ini adalah operasi elemen-bijaksana.

Jadi, secara total, kita punya

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

Menggunakan logika yang sama, untuk menjalankan $j \to k$ , kita memiliki $\mathcal{O}(k*j*t)$ , dan, untuk $k \to l$ , kita memiliki $\mathcal{O}(l*k*t)$ .

Secara total, kompleksitas waktu untuk perbanyakan feedforward akan

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

Saya tidak yakin apakah ini dapat disederhanakan lebih lanjut atau tidak. Mungkin hanya $\mathcal{O}(t*i*j*k*l)$ , tapi saya tidak yakin.

Algoritma back-propagation

The back-propagation algorithm proceeds as follows. Starting from the output layer $l \to k$, we compute the error signal, $E_{lt}$, a matrix containing the error signals for nodes at layer $l$

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

where $\odot$ means element-wise multiplication. Note that $E_{lt}$ has $l$ rows and $t$ columns: it simply means each column is the error signal for training example $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}$$

For $l \to k$, we thus have the time complexity $\mathcal{O}(lt + lt + ltk + lk) = \mathcal{O}(l*t*k)$.

Now, going back from $k \to j$. We first have

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

Then

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

And then

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

$W_{kl}$$W_{lk}$$k \to j$$\mathcal{O}(kt + klt + ktj + kj) = \mathcal{O}(k*t(l+j))$

$j \to i$$\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.