Was ist die zeitliche Komplexität für das Training eines neuronalen Netzwerks mit Backpropagation?

16

Angenommen, ein NN enthält n ausgeblendete Ebenen, m Trainingsbeispiele, Features und Knoten in jeder Ebene. Was ist die zeitliche Komplexität, um dieses NN mithilfe von Backpropagation zu trainieren?xni

Ich habe eine grundlegende Vorstellung davon, wie sie die zeitliche Komplexität von Algorithmen finden, aber hier sind 4 verschiedene Faktoren zu berücksichtigen, z. B. Iterationen, Ebenen, Knoten in jeder Ebene, Trainingsbeispiele und möglicherweise weitere Faktoren. Ich habe hier eine Antwort gefunden, aber es war nicht klar genug.

Gibt es andere Faktoren als die oben genannten, die die zeitliche Komplexität des Trainingsalgorithmus eines NN beeinflussen?

DuttaA
quelle
Siehe auch https://qr.ae/TWttzq .
Nr.

Antworten:

9

Ich habe keine Antwort von einer vertrauenswürdigen Quelle gesehen, aber ich werde versuchen, dies selbst mit einem einfachen Beispiel zu beantworten (mit meinem aktuellen Wissen).

Im Allgemeinen ist zu beachten, dass das Trainieren eines MLP unter Verwendung von Backpropagation normalerweise mit Matrizen implementiert wird.

Zeitliche Komplexität der Matrixmultiplikation

Die zeitliche Komplexität der Matrixmultiplikation für MijMjk ist einfach O(ijk) .

Beachten Sie, dass wir hier von einem einfachsten Multiplikationsalgorithmus ausgehen: Es gibt einige andere Algorithmen mit etwas besserer Zeitkomplexität.

Feedforward-Pass-Algorithmus

Der Feedforward-Ausbreitungsalgorithmus ist wie folgt.

Zuerst müssen Sie von Schicht i nach j wechseln

Sj=WjiZi

Dann wenden Sie die Aktivierungsfunktion an

Zj=f(Sj)

Wenn wir N Ebenen (einschließlich Eingabe- und Ausgabeebene) haben, wird dies N1 Mal ausgeführt.

Beispiel

Als Beispiel berechnen wir die Zeitkomplexität für den Vorwärtsdurchlaufalgorithmus für einen MLP mit 4 Schichten, wobei i die Anzahl der Knoten der Eingangsschicht, j die Anzahl der Knoten in der zweiten Schicht und k die Anzahl der Knoten in der Eingangsschicht bezeichnet dritte Schicht und l die Anzahl der Knoten in der Ausgabeschicht.

Da es 4 Ebenen gibt, benötigen Sie 3 Matrizen, um die Gewichte zwischen diesen Ebenen darzustellen. Bezeichnen wir sie mit Wji , Wkj und Wlk , wobei Wji eine Matrix mit j Zeilen und i Spalten ist ( Wji enthält also die von Schicht i zu Schicht j gehenden Gewichte ).

Angenommen , Sie haben t Trainingsbeispiele. Für die Ausbreitung von Schicht i nach j haben wir zuerst

Sjt=WjiZit

und dieser Vorgang (dh Matrix multiplcation) aufweist O(jit) Zeitkomplexität. Dann wenden wir die Aktivierungsfunktion an

Zjt=f(Sjt)

und dies hat O(jt) Zeitkomplexität, da es sich um ein Element weise Betrieb ist.

Insgesamt haben wir also

O(jit+jt)=O(jt(t+1))=O(jit)

Mit derselben Logik für das Gehen jk , haben wir O(kjt) , und für kl , haben wir O(lkt) .

Insgesamt wird die Zeitkomplexität für die Vorwärtskopplung sein

O(jit+kjt+lkt)=O(t(ij+jk+kl))

Ich bin nicht sicher, ob dies weiter vereinfacht werden kann oder nicht. Vielleicht ist es nur O(tijkl) , aber ich bin nicht sicher.

Backpropagation-Algorithmus

Der Backpropagation-Algorithmus geht wie folgt vor. Ausgehend von der Ausgangsschicht lk berechnen wir das Fehlersignal Elt , eine Matrix, die die Fehlersignale für Knoten auf Schicht l

Elt=f(Slt)(ZltOlt)

wo Mittel elementweise Multiplikation. Beachten Sie, dass Elt hat l Zeilen und t Spalten: Es bedeutet einfach , jede Spalte ist das Fehlersignal beispielsweise die Ausbildung t .

We then compute the "delta weights", DlkRl×k (between layer l and layer k)

Dlk=EltZtk

where Ztk is the transpose of Zkt.

We then adjust the weights

Wlk=WlkDlk

For lk, we thus have the time complexity O(lt+lt+ltk+lk)=O(ltk).

Now, going back from kj. We first have

Ekt=f(Skt)(WklElt)

Then

Dkj=EktZtj

And then

Wkj=WkjDkj

where Wkl is the transpose of Wlk. For kj, we have the time complexity O(kt+klt+ktj+kj)=O(kt(l+j)).

And finally, for ji, we have O(jt(k+i)). In total, we have

O(ltk+tk(l+j)+tj(k+i))=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(nt(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 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

M.kazem Akhgary
quelle
Your answer is great..I could not find any ambiguity till now, but you forgot the no. of iterations part, just add it...and if no one answers in 5 days i'll surely accept your answer
DuttaA
@DuttaA I tried to put every thing I knew. it may not be 100% correct so feel free to leave this unaccepted :) I'm also waiting for other answers to see what other points I missed.
M.kazem Akhgary
3

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 O(w) where w is the number of weights, i.e., nni, 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 O(wme).

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

maaartinus
quelle
From the above answer don't you think itdepends on more factors?
DuttaA
1
@DuttaA No. There's a constant amount of work per weight, which gets repeated e times for each of m examples. I didn't bother to compute the number of weights, I guess, that's the difference.
maaartinus
I think the answers are same. in my answer I can assume number of weights w = ij + jk + kl. basically sum of n * n_i between layers as you noted.
M.kazem Akhgary