DRITTE METHODE: EIN $O(n^3)$ VERFAHREN

Dieser Abschnitt präsentiert den ersten originären Beitrag der vorliegenden Arbeit. Wie oben gesehen, beträgt RTRLs Berechnungskomplexität^2.2pro Zeitschritt $O(n^4)$. Im folgenden werden wir die Gradientenkalkulation so umarrangieren, daß die Speicherkomplexität des neuen Verfahrens dieselbe Ordnung wie die von RTRL aufweist, die Berechnungskomplexität aber in Proportion zur Zahl der Knoten im Netzwerk sinkt. Im Gegensatz zu der in [156] vorgestellten ad-hoc Methode bestimmt das neuartige Verfahren den exakten Gradienten, nicht etwa nur eine Approximation desselben [109].

Alle $O(n)$ Zeitschritte benötigt die neue Methode $O(n^4)$ Operationen, bei allen dazwischenliegenden Zeitschritten sind allerdings nur $O(n^2)$ Operationen erforderlich. Dies drückt die durchschnittliche Zeitkomplexität pro Zeitschritt auf $O(n^3)$.

Eine Trainingssequenz mit $s+1$ Zeitschritten startet wieder zum Zeitschritt 0 und endet zum Zeitschritt $s$. Der nachfolgende Algorithmus ist von Interesse, falls $s >> n$ (sonst sei BPTT empfohlen).

Der Algorithmus^2.3 ist ein Hybrid zwischen BPTT und RTRL [109]. Die folgende Beschreibung enthält sowohl die Herleitung als auch einige Kommentare zur Komplexität der einzelnen Schritte. Die wesentliche Idee ist: Zerlege die Gradientenberechnung in mehrerere Blöcke, von denen jeder $O(n)$ Zeitschritte umfaßt. Führe für jeden Block $n+1$ BPTT-ähnliche Berechnungsphasen durch. Eine davon dient zur Bestimmung gewisser Fehlergradienten, die restlichen $n$ Phasen dienen zur Berechnung der partiellen Ableitungen der Netzeingaben jedes internen Knotens am Ende jedes Blocks. Führe schließlich $n+1$ RTRL-ähnliche Berechnungsphasen durch, um die Resultate der BPTT-Phasen mit den aus früher abgearbeiteten Blocks gewonnenen Resultaten zu verrechnen. Siehe Abbildung 2.3.

Abbildung: Zur Illustration des $O(n^3)$-Verfahrens. Die Aktivationsausbreitungsphase des rekurrenten Netzes aus Abbildung 2.1 wird in zeitliche Blöcke der Länge $O(n)$ zerlegt.

Für alle $w_{ij}$ und für alle $l \in U, t \geq 0$ definieren wir

$$q_{ij}^l(t) = \frac{\partial net_l(t) } {\partial w_{ij}} = ... ...tau =1}^{t} \frac{\partial net_l(t) } {\partial w_{ij}(\tau)}.$$

Zu Beginn des Algorithmus setzen wir die Variable $t_0 \leftarrow 0$. $t_0$ bezeichnet den ersten Zeitschritt des gegenwärtigen Blocks. Man beachte, daß für alle in Frage kommenden $l,w_{ij}$ gilt:

$$q_{ij}^l(0) = 0,~ \frac{\partial E^{total}(0,0) } {\partial w_{ij}} = 0.$$

Die Hauptschleife des Algorithmus umfaßt 5 Schritte.

1. SCHRITT: Setze $h \leftarrow O(n)$ (es sei empfohlen: $h \leftarrow n$).

Die Größe $\frac{\partial E^{total}(0,t_0) } {\partial w_{ij}}$ ist für alle $w_{ij}$ bereits bekannt. Dasselbe gilt für $q_{ij}^l(t_0)$ für alle in Frage kommenden $l,i,j$. Gesucht ist eine effiziente Methode zur Bestimmung des Beitrags von $E^{total}(0,t_0+h)$ zur Änderung von $w_{ij}$,

$$\triangle w_{ij}(t_0+h) = - \alpha \frac{\partial E^{total}(... ... \frac{\partial E^{total}(0,t_0+h) } {\partial w_{ij}(\tau)},$$

wobei $\alpha$ wieder eine positive konstante Lernrate bezeichnet.

2. SCHRITT: Führe eine Aktivationsausbreitungsphase für die Zeitschritte $t_0$ bis einschließlich $t_0+h$ gemäß der in Gleichung (2.1) spezifizierten Aktivierungsdynamik durch. Stellt sich zur Laufzeit heraus, daß die gegenwärtige Trainingssequenz weniger als $t_0+h$ Zeitschritte umfaßt (i.e., $h > s-t_0$), dann setze $h \leftarrow s-t_0$. Falls $h=0$, terminiere den Algorithmus.

3. SCHRITT: Führe zur Berechnung von Fehlerableitungen folgende Kombination einer BPTT-ähnlichen Berechnungsphase mit einer RTRL-ähnlichen Berechnungsphase durch. Wir schreiben

$$\frac{\partial E^{total}(0,t_0+h) } {\partial w_{ij}} = \f... ...ij}} + \frac{\partial E^{total}(t_0,t_0+h) } {\partial w_{ij}}$$

$$= \frac{\partial E^{total}(0,t_0) } {\partial w_{ij}} + \sum... ...\frac{\partial E^{total}(t_0,t_0+h) } {\partial w_{ij}(\tau)}$$

$$= \frac{\partial E^{total}(0,t_0) } {\partial w_{ij}} + \sum... ...\frac{\partial E^{total}(t_0,t_0+h) } {\partial w_{ij}(\tau)}$$ (2.7)

Wir kennen bereits den ersten Term des Ausdrucks (2.7). Man konzentriere sich auf den dritten Term:

$$\sum_{\tau =t_0 + 1}^{t_0+h} \frac{\partial E^{total}(t_0,t_... ...} = - \sum_{\tau = t_0+1}^{t_0+h} \delta_i(\tau) x_j(\tau -1),$$

wobei

$$\delta_i(\tau) = - \frac{\partial E^{total}(t_0,t_0+h) } {\partial net_i(\tau)}.$$

Für gegebenes $t_0$ kann $\delta_i(\tau)$ für alle $i \in U, t_0 \leq \tau \leq t_0+h$ mittels einer einzigen BPTT-Phase der Länge $h$ und der Ordnung $O(hn^2)$ bestimmt werden:

$$\delta_i(\tau) = f_i'(net_i(\tau))e_i(\tau) ~~falls~~\tau = t_0+h$$

$$\delta_i(\tau) = f_i'(net_i(\tau))(e_i(\tau) + \sum_{l \in U} w_{li}\delta_l(\tau +1)) ~~falls~~t_0 \leq \tau < t_0+h$$

Was bleibt, ist die Berechnung des zweiten Terms in (2.7) für alle $w_{ij}$, was $O(n^3)$ Operationen kostet:

$$\sum_{\tau =1}^{t_0} \frac{\partial E^{total}(t_0,t_0+h) } ... ...t_k(t_0)} \frac{\partial net_k(t_0) } {\partial w_{ij}(\tau)}$$

$$= \sum_{k \in U} - \delta_k(t_0) \sum_{\tau =1}^{t_0} \frac{... ... w_{ij}(\tau)} = - \sum_{k \in U} \delta_k(t_0) q_{ij}^k(t_0).$$

4. SCHRITT: Um $q_{ij}^l(t_0+h)$ für alle möglichen $l,i,j$ zu berechnen, führe $n$ BPTT/RTRL-Kombinationen (eine solche Kombination für jedes $l$) aus:

$$q_{ij}^l(t_0+h)= \frac{\partial net_l(t_0+h) } {\partial w_... ...^{t_0+h} \frac{\partial net_l(t_0+h) } {\partial w_{ij}(\tau)}$$

$$= \sum_{\tau=1}^{t_0} \frac{\partial net_l(t_0+h) } {\partia... ...{t_0+h} \frac{\partial net_l(t_0+h) } {\partial w_{ij}(\tau)}$$

$$= \sum_{\tau=1}^{t_0} \sum_{k \in U} \frac{\partial net_l(t_... ...i(\tau)} \frac{\partial net_i(\tau)}{\partial w_{ij}(\tau)}$$

$$= \sum_{k \in U} \gamma_{lk}(t_0) h^k_{ij}(t_0) + \sum_{\tau = t_0+1}^{t_0+h} \gamma_{li}(\tau) x_j(\tau -1),$$ (2.8)

wobei

$$\gamma_{lk}(\tau) = \frac{\partial net_l(t_0+h)} {\partial net_k(\tau)}.$$

Für gegebenes $t_0$ und gegebenes $l \in U$ läßt sich $\gamma_{li}(\tau)$ für alle $i \in U, t_0 \leq \tau \leq t_0+h$ mittels einer einzigen BPTT-Phase der Länge $h$ und der Ordnung $O(hn^2)$ bestimmen:

$$falls~~\tau = t_0+h:~~falls~~l=i,~~dann~~\gamma_{li}(\tau) = 1,~~sonst~~ \gamma_{li}(\tau) = 0$$

$$falls~~t_0 \leq \tau < t_0+h:~~ \gamma_{li}(\tau) = f_i'(net_i(\tau)) \sum_{a \in U} w_{ai} \gamma_{la}(\tau + 1)$$

Für gegebenes $l$ kostet die Berechnung von (2.8) für alle $w_{ij}$ $O(n^3+hn^2)$ Operationen. Der 3. und der 4. SCHRITT brauchen zusammen also $(n+1)O(hn^2 + n^3)$ Operationen, die sich allerdings über $h$ Zeitschritte verteilen. Da wir zu Beginn $h =O(n)$ gesetzt haben, verstreuen sich demzufolge $O(n^4)$ Operationen über $O(n)$ Zeitschritte. Dies zieht eine durchschnittliche Berechnungskomplexität der Ordnung $O(n^3)$ nach sich.

Der 5. Schritt schließt die Hauptschleife des Algorithmus ab:

5. SCHRITT: Setze $t_0 \leftarrow t_0+h$ und springe zum 1. SCHRITT.

So wie er oben formuliert wurde, führt der Algorithmus bei jedem $n$-ten Zeitschritt zu einen Spitzenberechnungsaufwand von $O(n^4)$ Operationen. Nichts hält uns jedoch davon ab, diese $O(n^4)$ Berechnungen gleichmäßig über $n$ Zeitschritte zu verteilen. Man könnte zum Beispiel zu jedem Zeitschritt des $k$-ten Blocks eine der $n$ BPTT-Phasen des 4. SCHRITTs des $(k-1)$-ten Blocks durchführen. Dies würde auch den Spitzenberechnungsaufwand pro Zeitschritt auf $O(n^3)$ drücken.

Die off-line Version des Algorithmus führt die Gesamtgewichtsänderung nach Abschluß der Präsentation aller Trainingssequenzen aus.

Die korrespondierende on-line-Version ändert die Gewichte jeweils nach dem 4. SCHRITT (also jeweils nach der Abarbeitung eines Blockes der Zeitdauer $n$). Die im nächsten Abschnitt (sowie in den Arbeiten der anderen in diesem Kapitel aufgeführten Autoren) beschriebenen Experimente verwenden für alle Versionen aller drei oben betrachteten Algorithmen gewöhnlich Lernraten zwischen 0.01 und 1.0.

Related links in English: Recurrent networks - Fast weights - Subgoal learning - Reinforcement learning and POMDPs - Unsupervised learning and ICA - Metalearning and learning to learn
Deutsche Heimseite