Der Algorithmus

In diesem Abschnitt wird die parallele Version des Algorithmus A2 (siehe auch [56] und [58] sowie die verbesserte Version in [52] ) detailliert aufgeschrieben. (Die sequentielle Version ergibt sich sofort aus der parallelen Version durch geringfügige Modifikationen.)

A2 unterscheidet sich von jedem der Algorithmen anderer Autoren in wenigstens einigen der folgenden Punkte: A2 verfügt über ein Potential zum `on-line'-Lernen, die parallele Version ist lokal in der Zeit, A2 erlaubt sowohl interne als auch externe Rückkopplung mit (wenigstens im Prinzip) beliebigen zeitlichen Verzögerungen, er kümmert sich nicht um Trainingsintervallgrenzen, er braucht lediglich Reinforcement-artige Information zum Lernen, er erlaubt verschiedene Arten von Reinforcement oder `Schmerz' bzw. `Lust', und er kann ein Modell aller Eingaben aus der wahrnehmbaren Umgebung konstruieren, um möglichst vollständige rückwärts in die Zeit gerichtete `Lernpfade' zur Verfügung zu stellen.

Mit anderen Worten, A2 ist tatsächlich ein sehr allgemeiner Algorithmus. A2 zielt darauf ab, das fundamentale Lernproblem in der `on-line' Lernsituation anzugreifen, soweit dies durch das Konzept des `raumzeitlichen Gradientenabstiegs' überhaupt möglich ist.

Die on-line-Version von Robinson und Fallsides `Infinite Input Duration' (IID-) Lernalgorithmus [40](siehe auch Kapitel 2) wird verwendet, um sowohl $C$ als auch $M$ zu trainieren. (Zur Erinnerung: Der IID-Algorithmus wurde zum ersten Mal durch Williams und Zipser getestet [80]). Wir konzentrieren uns erneut auf die Version für diskrete Zeit. Allerdings sollte es keine größeren Schwierigkeiten bereiten, A2's Prinzip mit Hilfe der Arbeiten von Pearlmutter [37] und Gherrity [10] auf kontinuierliche Zeit zu übertragen.

A2's Hauptschleife wird durch ein geeignetes domänenabhängiges Abbruchkriterium terminiert. Der Abbruch kann beispielsweise durch das Feststellen hinreichender Performanz ausgelöst werden.

Im 1. Schritt der Hauptschleife berechnet A2 die Aktionen der Effektoren des Systems. Dies geschieht einfach durch Ablesen der auf konventionelle Weise berechneten Aktivationen von $C$'s Ausgabeknoten und ihrer Interpretation als Steuersignale für die Motorik. Für alle neuen Aktivationen werden die entsprechenden Ableitungen bezüglich aller Steuernetzgewichte auf den neuesten Stand gebracht.

Im 2. Schritt werden die im 1. Schritt berechneten Aktionen ausgeführt, und ihre Effekte (oder auch die Effekte früherer Aktionen) werden sichtbar.

Im 3. Schritt werden in $M$'s Ausgabeknoten die Voraussagen für $C$'s neue Eingaben (hervorgerufen durch die externe Rückkopplung oder durch von den Effektoren unabhängige Umgebungsänderungen) berechnet, wobei $M$ $C$'s neue Eingaben nicht kennt. Wiederum wird relevante Gradienteninformation berechnet.

Im 4. Schritt werden $M$'s Gewichte sofort so verändert, daß in ähnlichem raumzeitlichen Kontext in Zukunft bessere Voraussagen zu erwarten sind. Für den Fall der Existenz von Trainingsintervallgrenzen wäre die von $M$ zu minimierende Fehlerfunktion

$$E_{M} = \sum_{t} \sum_{k \in I \cup P} (x_{{k}_{t}}-y_{{k}_{t}} )^{2},$$

wobei $y_{{k}_{t}}$ die Aktivation des $k$ten vorhersagenden Knotens von $M$ zur Zeit $t$ ist, $x_{{k}_{t}}$ die Aktivation der entsprechenden vorhergesagten Knotens von $C$ ist, und $t$ über alle Zeitschritte eines Trainingsintervalls rangierte. Jedes Gewicht $w_{ij}$ von $M$ ändert sich dabei proportional zu

$$\frac{\partial E_M }{\partial w_{ij}}.$$

Schließlich werden $C$'s Gewichte so geändert, daß die kumulativen Differenzen zwischen gewünschten und tatsächlichen Aktivationen der Schmerz- und Lustknoten minimiert werden unter der Annahme, daß $M$ bereits ein guter Prophet ist. Jedes Gewicht $w_{ij}$ von $C$ ändert sich proportional zu

$$\frac {\partial \sum_{t,i}(c_i - y_{i}(t))^2} {\partial w_{ij}}$$

unter der Annahme, daß die durch $W_M$ definierte Dynamik als Ersatz für die Umgebungsdynamik verwendet werden kann. (Das ist der Systemidentifikationsansatz.) Dabei ist $y_{i}(t)$ die tatsächliche und $c_i$ die gewünschte Aktivation des $i$ten R-Knotens zur Zeit $t$. Da es keine Trainingsintervallgrenzen mehr gibt (alle Episoden gehen ineinander über [80]), rangiert $t$ nun über alle vergangenen Zeitschritte. Im 4. Schritt wird auch sogenannter `Lehrerzwang' (`teacher forcing') [80] auf $M$ ausgeübt. Dies bedeutet, daß der Zustand von $M$'s Ausgabeknoten durch den neuen Zustand von $C$'s Eingabeknoten ersetzt wird. Um mathematisch korrekt zu bleiben, müssen anschließend alle Variablen, die für $M$'s Ausgabeknoten Gradienteninformation abspeichern, gleich Null gesetzt werden.

Der Ansatz des Lehrerzwangs ist ein natürlicher. Schließlich hängt der Fortgang von $C$'s Aktivationsausbreitung von den tatsächlichen neuen Eingaben ab und nicht von $M$'s Voraussagen. $M$'s Dynamik wird also der `realen' Umgebung angepaßt. Im Kontext des überwachten Lernens haben Williams und Zipser ein Experiment beschrieben, bei dem der `Lehrerzwang' geradezu notwendig war, um befriedigende Performanz zu erzielen.

$C$'s Fehler wird nicht durch die vorhergesagten Aktivationen von $C$'s Eingabeknoten, sondern durch die tatsächlichen Aktivationen bestimmt. Siehe dazu auch obigen Abschnitt über paralleles Lernen sowie einige nachfolgende Kommentare zur `on-line' Natur von A2.

A2 bietet ein Gerüst für ein sogar noch etwas allgemeineres Schema. Er basiert auf der logistischen Funktion $f(x)=\frac{1}{1+e^{-x}}$ als Aktivierungsfunktion für alle Nicht-Eingabeknoten. Die allgemeinere Form erlaubt verschiedene Aktivierungsfunktionen für jeden Knoten, verschiedene Fehlerfunktionen für sowohl $C$ als auch $M$, sowie probabilistische Ausgabeknoten für $C$. Zu den probabilistischen Ausgabeknoten werden gleich im Anschluß an die Beschreibung von A2 Details geliefert werden. (Weiterhin werden einige zusätzliche Kommentare folgen.) Für den Leser mag es hilfreich sein, mit dem in Kapitel 2 beschriebenen Verfahren für zeitlich lokales überwachtes Lernen zu vergleichen.

Notation :

$C$ ist die Menge aller Nicht-Eingabeknoten des Steuernetzwerkes,

$A$ ist die Menge seiner Ausgabeknoten,

$I$ ist die Menge seiner `normalen' Eingabeknoten,

$P$ ist die Menge seiner Lust- und Schmerzknoten,

$M$ ist die Menge aller Knoten des Modellnetzwerkes,

$O$ ist die Menge seiner Ausgabeknoten,

$O_{P} \subset O$ ist die Menge aller Knoten, die Schmerz oder Lust voraussagen,

$W_{M}$ ist die Menge der Variablen für die Gewichte von $M$,

$W_{C}$ ist die Menge der Variablen für die Gewichte von $C$,

$y_{k_{new}}$ ist die Variable für die auf den neuesten Stand gebrachte Aktivation des $k$ten Knotens von $M \cup C \cup I \cup P$,

$y_{k_{old}}$ ist die Variable für den letzten Wert von $y_{k_{new}}$,

$w_{ij}$ ist die Variable für das Gewicht der gerichteten Verbindung vom Knoten $j$ zum Knoten $i$,

$p_{ij_{new}}^{k}$ ist die Variable für den gegenwärtigen angenäherten Wert von $\frac{\partial y_{k_{new}} }{\partial w_{ij}}$,

$p_{ij_{old}}^{k}$ ist die Variable für den letzten Wert von $p_{ij_{new}}^{k}$,

falls $k \in P$, dann ist $c_k$ $k$'s unveränderliche gewünschte Aktivation,

falls $k \in I \cup P$, dann ist $kpred$ der Knoten aus $O$, welcher $k$'s Aktivationen voraussagt,

$\alpha_C$ ist die Lernrate des Steuernetzwerkes,

$\alpha_M$ ist die Lernrate des Modellnetzwerkes.

$\mid I \cup P \mid = \mid O \mid$,

$\mid O_{P} \mid = \mid P \mid$.

Von jedem Knoten aus $I \cup P \cup A$ führt eine Vorwärtsverbindung zu jedem Knoten aus $M \cup C$,

jeder Knoten aus $M$ ist bidirektional mit jedem anderen Knoten aus $M$ vernezt,

jeder Knoten aus $C$ ist bidirektional mit jedem anderen Knoten aus $C$ vernezt,

jede Verbindung, die auf einen Knoten aus $M$ weist, gehört zu $W_{M}$,

jede Verbindung, die auf einen Knoten aus $C$ weist, gehört zu $W_{C}$,

jedes Gewicht $w_{ij} \in W_{M}$ benötigt $p_{ij}^{k}$-Variablen für alle $k \in M$,

jedes Gewicht $w_{ij} \in W_{C}$ benötigt $p_{ij}^{k}$-Variablen für alle $k \in M \cup C \cup I \cup P$.

Die parallele Version des Algorithmus sieht wie folgt aus:

INITIALISIERUNG:

Für alle $w_{ij} \in W_{M} \cup W_{C}$:

$w_{ij} \leftarrow$ Zufallsgenerator,

für alle möglichen $k$: $p_{ij_{old}}^{k} \leftarrow 0, p_{ij_{new}}^{k} \leftarrow 0$ .

Für alle $k \in M \cup C : y_{k_{old}} \leftarrow 0, y_{k_{new}} \leftarrow 0.$

Für alle $k \in I \cup P$ :

Bestimme $y_{k_{old}}$ durch Wahrnehmung aus der Umgebung, $y_{k_{new}} \leftarrow 0.$

WIEDERHOLE, BIS ABBRUCHKRITERIUM ERFÜLLT:

1. Für alle $i \in C: y_{i_{new}} \leftarrow \frac{1}{1 + e^{- \sum_{j} w_{ij} y_{j_{old}} }}$.

Für alle $w_{ij} \in W_{C}, k \in C$:

$p_{ij_{new}}^{k} \leftarrow y_{k_{new}}(1 - y_{k_{new}}) ( \sum_{l } w_{kl} p_{ij_{old}}^{l} + \delta_{ik} y_{j_{old}}) .$

Für alle $k \in C$:

$y_{k_{old}} \leftarrow y_{k_{new}}$,

für alle $w_{ij} \in W_{C}$ : $p_{ij_{old}}^{k} \leftarrow p_{ij_{new}}^{k}$ .

2. Führe alle auf Aktivationen der Knoten aus $A$ basierenden motorischen Aktionen aus.

Für alle $i \in I \cup P$:

Bestimme $y_{i_{new}}$ durch Wahrnehmung aus der Umgebung.

3. Für alle $i \in M: y_{i_{new}} \leftarrow \frac{1}{1 + e^{- \sum_{j} w_{ij} y_{j_{old}} }}$.

Für alle $w_{ij} \in W_{M} \cup W_C, k \in M$:

$p_{ij_{new}}^{k} \leftarrow y_{k_{new}}(1 - y_{k_{new}}) ( \sum_{l } w_{kl} p_{ij_{old}}^{l} + \delta_{ik} y_{j_{old}}) .$

Für alle $k \in M$:

$y_{k_{old}} \leftarrow y_{k_{new}}$,

für alle $w_{ij} \in W_{C} \cup W_M$ : $p_{ij_{old}}^{k} \leftarrow p_{ij_{new}}^{k}$ .

4. Für alle $w_{ij} \in W_{M}$:

$w_{ij} \leftarrow w_{ij} + \alpha_{M} \sum_{k \in I \cup P} (y_{k_{new}} - y_{kpred_{old}}) p_{ij_{old}}^{kpred} .$

Für alle $w_{ij} \in W_{C}$:

$w_{ij} \leftarrow w_{ij} + \alpha_{C} \sum_{k \in P} (c_k - y_{k_{new}}) p_{ij_{old}}^{kpred} .$

Für alle $k \in I \cup P$:

$y_{k_{old}} \leftarrow y_{k_{new}}$, $y_{kpred_{old}} \leftarrow y_{k_{new}}$,

für alle $w_{ij} \in W_{M}: p_{ij_{old}}^{kpred} \leftarrow 0$,

für alle $w_{ij} \in W_{C}: p_{ij_{old}}^{k} \leftarrow p_{ij_{old}}^{kpred}$ .

Related links in English: Recurrent neural networks - Subgoal learning - Reinforcement learning and POMDPs - Reinforcement learning economies - Selective attention
Deutsche Heimseite