HERLEITUNG DES ALGORITHMUS

Mit der Kettenregel berechnen wir Gewichtsinkremente für die Initialgewichte $w_{ab}(1)$ gemäß

$$w_{ab}(1) \leftarrow w_{ab}(1) - \eta \frac{\partial E^{total}(n_rn_s)} {\partial w_{ab}(1)} ,$$ (8.12)

wobei $\eta$ eine konstante positive Lernrate bezeichnet. Damit erhalten wir einen exakten gradientenbasierten Algorithmus zur Minimierung von $E^{total}$ unter der `selbstreferentiellen' durch (8.8) bis (8.11) gegebenen Dynamik. Um den Schreibaufwand zu reduzieren, seien folgende (teilweise durch [148] inspirierte) Kurzschreibweisen eingeführt:

Für alle Knoten $u$ und alle Gewichte $w_{ab}$ schreiben wir

$$p_{ab}^u(t)= \frac{\partial u(t)} {\partial w_{ab}(1)} .$$ (8.13)

Für alle Verbindungspaare $(w_{ij}, w_{ab})$ schreiben wir

$$q^{ij}_{ab}(t) = \frac{\partial w_{ij}(t)} {\partial w_{ab}(1)} .$$ (8.14)

Man beachte zunächst, daß

$$\frac{\partial E^{total}(1) } {\partial w_{ab}(1)} = 0,~~\... ... {\partial w_{ab}(1)} - \sum_k eval_k(t+1) p_{ab}^{o_k}(t).$$ (8.15)

Das verbleibende Problem besteht also in der Berechnung der $p_{ab}^{o_k}(t)$, welche sich durch inkrementelle Berechnung aller $p_{ab}^{z_k}(t)$ und $q^{ij}_{ab}(t)$ vollziehen läßt, wie wir gleich sehen werden.

Für den Zeitpunkt 1 gilt

$$p_{ab}^{z_k}(1)= 0.$$ (8.16)

Für $t \geq 1$ erhalten wir die Rekursion

$$p_{ab}^{x_k}(t+1) = 0,$$ (8.17)

$$p_{ab}^{eval_k}(t+1) = - p_{ab}^{o_k}(t), ~falls~d_k(t)~existiert,~und~0~sonst,$$ (8.18)

$$p^{val}_{ab}(t+1) = \sum_{i,j} \frac{\partial} {\partial w_{ab}(1)} [~ g(\Vert ana(t) - adr(w_{ij})\Vert^2)w_{ij}(t) ~] =$$

$$\sum_{i,j} \{~~ q^{ij}_{ab}(t) g[\Vert ana(t) - adr(w_{ij})\Vert^2) ]~+$$

$$w_{ij}(t)~ [~~ g'(\Vert ana(t) - adr(w_{ij})\Vert^2 ) 2 \sum_m (ana_m(t) - adr_m(w_{ij})) p_{ab}^{ana_m}(t) ~~]~ ~~\}$$ (8.19)

(wobei $adr_m(w_{ij})$ das $m$-te Bit der Adresse von $w_{ij}$ bezeichnet),

$$p_{ab}^{y_k}(t+1)= f_{y_k}'(net_{y_k}(t+1)) \sum_l \frac{\partial} {\partial w_{ab}(1)} [ l(t)w_{y_kl}(t) ] =$$

$$f_{y_k}'(net_{y_k}(t+1)) \sum_l w_{y_kl}(t) p_{ab}^{l}(t) + l(t) q_{ab}^{y_kl}(t) ,$$ (8.20)

wobei

$$q^{ij}_{ab}(1) = 1~falls~w_{ab}=w_{ij},~und~0~sonst,$$ (8.21)

$$\forall t>1:~~ q^{ij}_{ab}(t) = \frac{\partial} {\partial ... ...angleup(\tau)g(\Vert mod(\tau) - adr(w_{ij})\Vert^2) \right] =$$

$$q^{ij}_{ab}(t-1) + \frac{\partial} {\partial w_{ab}(1)} \bigtriangleup(t-1)g(\Vert mod(t-1) - adr(w_{ij})\Vert^2) =$$

$$q^{ij}_{ab}(t-1) + p_{ab}^{\bigtriangleup}(t-1) g(\Vert mod(t-1) - adr(w_{ij})\Vert^2) +$$

$$2 \bigtriangleup(t-1)~ g'(\Vert mod(t-1) - adr(w_{ij})\Vert^2 ) \sum_m [mod_m(t-1) - adr_m(w_{ij})] p_{ab}^{mod_m}(t-1) .$$ (8.22)

Die $p^j_{ab}(t)$ und $q^{ij}_{ab}(t)$ lassen sich gemäß den Gleichungen (8.16)-(8.22) inkrementell zu jedem Zeitschritt aktualisieren, was bedeutet, daß auch (8.15) und (8.12) inkrementell berechnet werden können. Die Speicherkomplexität beträgt unabhängig von der Sequenzlänge $O(n_{conn}^2)$. Der Berechnungsaufwand pro Zeitschritt beträgt unabhängig von der Sequenzlänge $O(n_{conn}^2 log n_{conn})$. Dies übertrifft bedauerlicherweise sogar die Berechnungskomplexität von RTRL (siehe Kapitel 2), welche gleich $O(n_{conn}^2)$ ist.

Ein weiterer Nachteil (neben der hohen Komplexität) ist die hohe Anzahl lokaler Minima der ungewöhnlich komplexen Zielfunktion. Der Zweck dieses letzten Kapitels der Arbeit besteht jedoch nicht in der Auffindung des effizientesten oder praktikabelsten gradientenbasierten `selbstreferentiellen' Lernalgorithmus, sondern in der Demonstration, daß solche Algorithmen überhaupt theoretisch möglich sind.

Offenbar gerät der Algorithmus nicht in eine endlose Rekursion. Er verwendet Gradientenabstieg, um Gewichtsänderungsalgorithmen zu finden, die zwar nicht notwendigerweise Gradientenabstieg betreiben (sondern möglicherweise etwas Raffinierteres), aber dennoch dazu beitragen, $E^{total}$ zu minimieren. Damit läßt sich das Gesamtsystem als eine `selbstreferentielle' Erweiterung der `konventionelleren' Algorithmen aus Kapitel 2 ansehen. Beschleunigungsverfahren à la Kapitel 2 sind möglich, für die Zwecke des vorliegenden Kapitels jedoch nicht von Belang.

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