EXPERIMENTE MIT KLAMMERBALANCIERENDER TURINGMASCHINE

Das folgende Problem wurde erstmals von Williams und Zipser beschrieben [150]. Es geht darum, einem rekurrenten Netz beizubringen, das Zustandsübergangsdiagramm einer Turingmaschine zu simulieren, deren Aufgabe es ist, balancierte Zeichenreihen bestehend aus öffnenden und schließenden Klammern von unbalancierten Klammerfolgen zu unterscheiden.

Auf jedem Feld des Bandes der Turingmaschine kann eines von 4 möglichen Symbolen stehen: `(', `)', `*' und ` ' (`Blank'). Die entsprechenden Eingabevektoren für das Netzwerk sind $(0,1)^T$, $(1,0)^T$, $(1,1)^T$ und $(0,0)^T$. Der endliche Automat, der das Zustandsübergangsdiagramm der Turingmaschine beschreibt, ist durch Tabelle 2.1 definiert. Er besitzt 4 Zustände: 0, 1, 2 und 3. Aus einem gegebenen Zustand geht der Automat nach dem Lesen des Zeichens unter dem Lese- und Schreibkopf der Turingmaschine gemäß der Zustandsübergangstabelle in einen neuen Zustand über und schreibt gleichzeitig vor, ob der Lese- und Schreibkopf nach rechts, nach links, oder überhaupt nicht bewegt werden soll (`nix'). Die entsprechenden gewünschten Ausgabevektoren für zwei der Ausgabeknoten des Netzwerkes sind $(0,1)^T$, $(1,0)^T$ und $(0,0)^T$. Weiterhin wird eine von vier Aktionen ausgeführt: 1. Schreibe `*', 2. Zeige an, daß die Klammerstruktur balanciert ist, 3. Zeige an, daß die Klammerstruktur nicht balanciert ist, 4. Tue nichts (`nix'). Die entsprechenden gewünschten Ausgabevektoren für zwei zusätzliche Ausgabeknoten des Netzwerkes sind $(1,1)^T$, $(0,1)^T$, $(1,0)^T$ und $(0,0)^T$. Dem Netzwerk wird zu keinem Zeitpunkt Information über den gegenwärtigen Zustand der Turingmaschine geliefert. Es muß daher eigene geeignete interne Zustände `erfinden'.

Tabelle: Zustandsübergangsdiagramm einer Turingmaschine, die balancierte Klammerfolgen von unbalancierten Klammerfolgen unterscheidet.

Zustand	Eingabe	Neuer Zustand	Aktion	Bewegung
0	Blank	1	nix	nix
0	(	1	nix	nix
0	) (unmöglich)
0	* (unmöglich)
1	Blank	3	nix	links
1	(	1	nix	rechts
1	)	2	schreibe `*'	links
1	*	1	nix	rechts
2	Blank	0	unbalanziert	nix
2	(	1	schreibe `*'	rechts
2	)	2	nix	links
2	*	2	nix	links
3	Blank	0	balanziert	nix
3	(	0	unbalanziert	nix
3	)	3	nix	links
3	*	3	nix	links

Während der Trainingsphase wurde sowohl zu Beginn als auch nach jeder Abarbeitung einer aus maximal 30 Klammern bestehenden Zeichenreihe eine neue Klammernfolge gemäß einer exponentiellen Bandlängenverteilung generiert und die Anfangsposition des Kopfes der Turingmaschine auf das erste Zeichen des frisch generierten Bandes zurückgesetzt. Ein frisches Trainingsband wurde dabei wie folgt erstellt: Zunächst wurde auf zufällige Weise eine balancierte Klammernfolge generiert. In zwei Dritteln aller Fälle wurde diese durch zufällige `Mutationen' modifiziert, wobei die Wahrscheinlichkeit dafür, daß $k$ Klammern durch ihr Gegenstück ersetzt wurden, $0.5^k$ betrug.

Dem rekurrenten Netzwerk wurden jeweils zwei Zeitschritte zur Verarbeitung einer neuen Eingabe zugestanden. Zwischen dem Ende der Abarbeitung eines Bandes und dem Beginn der Abarbeitung des neuen Bandes wurde das Netz nicht von neuem initialisiert - Ereignisse, die während der Verarbeitung alter Bänder auftraten, konnten somit im Prinzip einen störenden Einfluß auf die Verarbeitung eines neuen Bandes nehmen. Die Trainingsphase wurde nach 100000 Turingmaschinenzyklen beendet. Eine anschließende Testphase galt als erfolgreich beendet (das Problem galt als gelernt), wenn das Netzwerk für die Zeitdauer von 50000 Turingmaschinenzyklen keinen Fehler machte, wobei ein Fehler durch eine 0.5 übersteigende Differenz zwischen der gewünschten und der tatsächlichen Ausgabe eines beliebigen Ausgabeknotens definiert war.

Bei 5 Testläufen mit RTRL lernte ein rekurrente Netz mit 15 versteckten Knoten und mit zwischen -1.0 und 1.0 initialisierten Gewichten bei einer Lernrate von 0.5 dabei stets, die Turingmaschine korrekt zu simulieren. Diese Resultate sind mit den in [150] berichteten Ergebnissen verträglich.

Bei 5 Testläufen mit dem neuartigen $O(n^3)$-Verfahren aus Abschnitt 2.5 lernte dasselbe rekurrente Netz bei gleicher Gewichtsinitialisierung ebenfalls in allen Fällen, die Aufgabe zu lösen. Dies ist nicht verwunderlich, da ja beide Verfahren den gleichen Gradienten berechnen (numerische Probleme durch die unterschiedliche Art der Gradientenberechnung traten nicht auf). Das neuartige Verfahren benötigte allerdings nur etwa ein Achtel der Rechenzeit des RTRL-Verfahrens. Natürlich stellt der Beschleunigungsfaktor 8 hier keine obere Schranke für die Überlegenheit der $O(n^3)$-Methode dar - je größer das Netzwerk, desto stärker fällt der Proportionalitätsfaktor $O(n)$ ins Gewicht.

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