Ein Experiment mit `verzögertem XOR'

In diesem Abschnitt wird experimentell demonstriert, daß der aus Lokalitäts- und Simplizitätsgründen eingeführte lineare Kritiker nicht notwendigerweise ein Hindernis für die Lösung von Problemen des nicht linear separablen Typs darstellt. Dabei werden auch die Unterschiede zu Andersons viel komplizierterem System aufgezeigt.

Beim `verzögerten XOR' mit statischen Eingaben' geht es darum, ein rekurrentes Netzwerk zur Lösung eines XOR-Problems mit verzögerter Bewertung der Netzausgaben zu veranlassen. Es existiert keine externe Rückkopplung.

Für die Dauer eines Trainingsintervalls wurden zwei der drei Eingabeknoten des vollständig bidirektional vernetzten Hauptnetzwerkes $C$ mit zufällig gewählten binären Werten besetzt. Der dritte Eingabeknoten war ein `wahrer' Knoten, seine Aktivation war stets gleich 1, um allen Nicht-Eingabeknoten einen modifizierbaren Schwellwert zur Verfügung zu stellen. $C$ verfügte über $h$ versteckte Knoten.

$C$'s Aufgabe bestand darin, eine vordefinierte Anzahl $k$ von Zeitschritten lang zu laufen, und im letzten Zeitschritt das XOR der Aktivationen des ersten und des zweiten Eingabeknoten in einem einzelnen Ausgabeknoten sichtbar zu machen.

Für verschiedene Anzahlen versteckter Knoten sowie für verschiedene Verzögerungszeitdauern fand der lokale Algorithmus Lösungen für seine Aufgabe. So waren zum Beispiel bei einer Gewichtsinitialisierung zwischen -0.1 und 0.1 und unter den Voraussetzungen $h=3$, $k = 3$ sowie $\eta = \alpha = 0.2$ in 7 von 10 durchgeführten Testläufen durchschnittlich 2000 Präsentationen pro Muster notwendig, um mehr als 97 Prozent korrekter Klassifikationen zu erzielen. Bei 4 Läufen war die Rate korrekter Klassifikationen größer als 99 Prozent.

Daß die Rate nicht immer 100 Prozent betrug, lag natürlich an der stochastischen Natur der Aktivierungsfunktionen von $C$'s Knoten. Es war jedoch möglich, perfekte Klassifikation aller Muster zu erzwingen: Man mußte lediglich nach der Lernphase aus dem nicht-deterministischen Netzwerk ein deterministisches machen. Dies erforderte nichts weiter, als daß jeder Knoten von $C$ stets die wahrscheinlichste Aktivation (abhängig von seinen Gewichten und seiner gegenwärtigen Eingabe) wählte. Schon relativ wenige Trainingszyklen reichten aus, um eine deterministische Lösung des Problems zu finden.

Wie ist es möglich, daß ein linearer Kritiker ausreicht, obwohl doch die Aufgabe vom nicht linear separablen Typ ist? Dieses kontraintuitive Faktum läßt sich dadurch erklären, daß die Aufgabe des Kritikers in der Regel einfacher ist als die Aufgabe des rekurrenten nicht-linearen Hauptnetzwerkes $C$. $C$ muß in seinen rekurrenten Verbindungen das Programm für die XOR-Abbildung implementieren, während der Kritiker lediglich die Abbildung von Netzwerkzuständen auf zukünftiges Reinforcement zu implementieren braucht. Im allgemeinen (insbesondere zu Beginn der Lernphase) kann die Abbildung von Netzwerkzuständen auf zukünftiges zu erwartendes Reinforcement selbst eine linear nicht separable Funktion darstellen. Hat jedoch $C$ schon gelernt, auf eine Untermenge der möglichen Eingaben mit der korrekten verzögerten Antwort zu reagieren, so vereinfacht sich die Aufgabe des Kritikers. In der Tat wird seine Aufgabe nach dem Auffinden einer perfekten Lösung trivial: Dann muß er nämlich nur noch für alle Netzwerkzustände den immer gleichbleibenden Wert des finalen Reinforcements vorhersagen, welcher 1 ist.

Eine derartige abschließende triviale Abbildung kann durch eine schwergewichtige Verbindung vom `wahren' Knoten auf den Kritiker implementiert werden. Tatsächlich war diese Art von Verbindung in manchen Fällen genau das, was nach dem Training beobachtet werden konnte.

Die wesentlichsten Unterschiede zu Andersons System [2] seien hier noch einmal aufgelistet. Im Gegensatz zu dem in Andersons Arbeit beschriebenen Algorithmus wurde kein BP-Netzwerk, sondern ein einzelner linearer Knoten als Kritiker verwendet. Weiterhin wurde kein statisches azyklisches mehrlagriges Netzwerk für die Berechnung von Ausgabeaktionen verwendet, sondern ein dynamisches vollständig zyklisches Netzwerk. Auch wurden versteckte Knoten nicht wie bei Andersons Methode mit anderen Lernregeln behandelt als die Ausgabeknoten.

Auch das Konzept der diskreten Zeitschritte war ein anderes: Während Andersons Zeitschritte zwei mehrlagige Aktivationsausbreitungs- und Fehlerrückpropagierungsphasen umfaßten, führt das oben beschriebene Verfahren in jedem Zeitschritt lediglich Ein-Lagen-Operationen aus. (Dabei sehen wir den `update'-Schritt des rekurrenten Netzes als eine Ein-Lagen-Operation an.) Man beachte, daß ein `update'-Schritt des Steuernetzes auch eine Änderung der Eingabeaktivationen aufgrund der externen Rückkopplung bedeutet. Dies hat eine Verzögerung von mindestens zwei Zeitschritten zwischen nicht-linear zu transformierenden Eingaben und entsprechenden Ausgabeaktionen zur Folge. Eine neue Eingabe kann unter Umständen bereits anliegen, bevor die Antwort auf die alte Eingabe berechnet ist.

Es muß darauf hingewiesen werden, daß ein linearer Kritiker nicht in allen Fällen ausreichend sein muß. Hieraus erwächst Motivation für die folgenden Abschnitte.

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