XOR-Varianten

Statische Probleme können als Spezialfall der sequentiellen Probleme aufgefaßt werden. Um die prinzipiellen Fähigkeiten des Eimerkettenalgorithmus zu illustrieren, wurde er zunächst anhand eines Problems vom nicht linear separablen Typ getestet. Das klassische Beispiel für solch ein Problem ist das XOR-Problem.

Minsky und Papert zeigten 1969, daß dieses Problem mit den damaligen Lernverfahren für neuronale Netze nicht lösbar war. Neuronale Netze erlebten ihre große Renaissance erst Mitte der 80er Jahre, als Methoden bekannt wurden, mit deren Hilfe gerade das XOR-Problem (und andere Probleme verwandten Typs) lösbar wurden.

Die verschiedenen bei den in diesem Unterabschnitt beschriebenen Experimenten verwendeten Netzwerke waren von der azyklischen Art. Im ersten Experiment wurde eine Lage mit drei Eingabeknoten vollständig mit einer drei `versteckte' Knoten umfassenden `versteckten' WTA-Einheit und einer zwei Ausgabeknoten umfassenden WTA-Einheit `vorwärtsvernetzt'. Auch die `versteckte' WTA-Einheit hatte vorwärtsgerichtete Verbindungen zu den Ausgabeknoten.

Zu Beginn eines `Zyklus' wurden alle Knotenaktivationen mit $0$ initialisiert, und eines der vier binären Eingabemuster wurde zufällig ausgewählt. Ein Zyklus dauerte sechs Zeitschritte, während derer das Muster den beiden ersten Eingabeknoten präsentiert wurde. Die Aktivation des dritten Eingabeknotens (des sogenannten wahren Knotens) war immer gleich $1$, um eine modifizierbare `Schwelle' für jeden Nicht-Eingabeknoten zu bieten. (`Wahre' Knoten sind für viele konnektionistische Ansätze gang und gäbe. Sowohl BP-Netze als auch die Boltzmann-Maschine werden häufig mit `wahren' Eingabeknoten ausgestattet.)

Die Aufgabe für das Netzwerk bestand darin, den ersten bzw. den zweiten Ausgabeknoten anzuschalten, je nachdem, ob die Anwendung der XOR-Funktion auf das Eingabemuster $1$ oder $0$ ergab. Das Problem war dabei als Reinforcement-Lernaufgabe definiert: Zu jedem Zeitpunkt $t$ vergab ein externer Kritiker genau dann Gewichtssubstanz $Ext_{ij}(t) = \eta c_{ij}(t)$ an ein Gewicht $w_{ij}$, wenn $j$ ein Ausgabeknoten und noch dazu korrekt angeschaltet war. In allen anderen Fällen galt $Ext_{ij}(t) = 0$.

Ein Eingabemuster galt als vom System korrekt klassifiziert, wenn bei ausgeschaltetem Gewichtsänderungsmechanismus während der letzten drei Zeitschritte eines Zyklus der richtige Ausgabeknoten aktiviert war. Um dieses Kriterium zu testen, wurde der Änderungsalgorithmus während sogenannter Prüfzyklen abgeschaltet. Das diente zur Verhinderung der Möglichkeit, daß das Netzwerk während eines Prüfzyklus noch aus einer falschen Klassifikation eine richtige machen konnte.

Die Aufgabe galt als vom System gelöst, wenn es alle vier Eingabemuster korrekt klassifizierte. Um herauszufinden, ob das Netzwerk schon eine Lösung gefunden hatte, wurde der Eimerkettenmechanismus nach jedem Trainingszyklus suspendiert und die Klassifikationsfähigkeit des Netzes anhand der vier Eingabemuster getestet.

Bei 20 verschiedenen Testläufen mit unterschiedlichen Anfangsbedingungen waren jeweils durchschnittlich 619 Musterpräsentationen nötig, um eine Lösung zu finden. Das bedeutet, daß jedes der vier Eingabemuster ungefähr $155$ mal präsentiert werden mußte. Dies entspricht dem in der Literatur häufig verwendeten Begriff von $155$ `Epochen'.

Die meisten der 20 Lösungen waren unstabil insofern, als weiteres Training sie nicht notwendigerweise fixierte. So konnten zum Beispiel nach dem Finden einer Lösung $5$ weitere Trainingszyklen dazu führen, daß die Performanz sich wieder verschlechterte. Daher wurden in weiteren Experimenten auch die Zyklenzahlen gemessen, die für eine stabile Lösung notwendig waren.

Eine Lösung wurde als `stabil' angesehen, wenn $100$ zusätzliche Musterpräsentationen die Klassifikationsperformanz nicht störten. Die exakte Testprozedur lief wie folgt ab: Nach jedem Trainingszyklus wurde der Gewichtsänderungsmechanismus abgeschaltet. Daraufhin wurde geprüft, ob das Netz ein neues zufällig ausgewähltes Muster richtig klassifizierte. Schließlich wurde der Eimerkettenalgorithmus wieder angeworfen. Dieses Verfahren wurde iteriert, bis das Netzwerk bei 100 aufeinanderfolgenden Prüfzyklen 100 korrekte Klassifikationen produzierte. Bei 10 verschiedenen Testläufen stellte sich heraus, daß jedes Muster durchschnittlich $674$ mal angeboten werden mußte, um dem obigen Kriterium Genüge zu tun.

Verwendete man zwei anstelle von drei `versteckten' Knoten, so waren durchschnittlich 160 Präsentationen pro Muster zum Auffinden einer Lösung notwendig. Es schien jedoch nicht möglich, unter diesen Bedingungen stabile Lösungen (im Sinne des obigen Kriteriums) zu finden.

Das XOR-Problem wurde auch mit einer anderen Netzwerkarchitektur getestet. Statt direkte vorwärtsgerichtete Verbindungen von den Eingabeknoten zu den Ausgabeknoten zuzulassen, wurden die Eingabeknoten lediglich mit zwei WTA-Einheiten verbunden, von denen jede zwei `versteckte' Knoten enthielt. Die versteckten' WTA-Einheiten besaßen ihrerseits Verbindungen zu den Ausgabeknoten.

Bei zehn Testläufen verfehlte es der Algorithmus unter diesen Umständen zweimal, in weniger als 4000 Trainingszyklen eine Lösung zu finden. In den verbliebenen 8 Fällen waren durchschnittlich 263 Musterpräsentationen zum Auffinden einer Lösung erforderlich. 911 Präsentationen waren für die Ausprägung einer stabilen Lösung (siehe obiges Kriterium) notwendig.

Verglichen mit der Boltzmann-Maschine [14] schneidet das Verfahren vom Gesamtrechenaufwand her gut ab, verglichen mit BP-Netzen erweist es sich als langsam. Wie schon in der Einleitung erwähnt, geht es uns jedoch nicht um die Lerngeschwindigkeit, sondern um den experimentellen Nachweis, daß vollständig lokales Lernen auch in Netzen mit versteckten Knoten möglich ist. Sowohl die Boltzmann Maschine als auch BP sind nicht stark lokal.

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