EXPERIMENT: VERZÖGERUNGEN MIT MEHR ALS 1000 ZEITSCHRITTEN

Wir konstruieren eine stochastische Grammatik, i.e. eine Grammatik, bei der die Anwendung jeder Produktionsregel mit einer von vornherein festgelegten Wahrscheinlichkeit stattfindet. Produziert Zeichenkette $\alpha$ die Zeichenkette $\beta$ mit Wahrscheinlichkeit $q$, so schreiben wir formal

$$\alpha \rightarrow^q \beta .$$

$N$ bezeichnet die Menge der Nichtterminalzeichen, $T$ steht für die Menge der Terminalzeichen, $\lambda$ stellt die leere Zeichenkette dar, $S$ repräsentiert das Startsymbol.

Die Grammatik $T_3$ sei wie folgt definiert (Regeln werden durchnumeriert):

$$T = \{a, b, x, y, 1, 2 \},$$

$$N = \{S, S',S'', A, A', A'', B, B', B'', C, C', C'', D, D', D'' \},$$

$$(1)~~S \rightarrow^{0.25} xCCCS'1, ~~ (2)~~S \rightarrow^{0.25} yCCCS'2, ~~$$

$$(3)~~S \rightarrow^{0.25} xDDDS''1, ~~ (4)~~S \rightarrow^{0.25} yDDDS''2, ~~$$

$$(5)~~S' \rightarrow^{0.5} C, ~~ (6)~~S' \rightarrow^{0.5} \lambda ,~~$$

$$(7)~~S'' \rightarrow^{0.5} D, ~~ (8)~~S'' \rightarrow^{0.5} \lambda, ~~$$

$$(9)~~C \rightarrow^{1.0} ABABABABABABABABABABC', ~~$$

$$(10)~~C' \rightarrow^{0.5} ABC', ~~ (11)~~C' \rightarrow^{0.5} \lambda, ~~$$

$$(12)~~D \rightarrow^{1.0} BABABABABABABABABABAD', ~~$$

$$(13)~~D' \rightarrow^{0.5} BAD',~~ (14)~~D' \rightarrow^{0.5} \lambda,~~$$

$$(15)~~A \rightarrow^{1.0} abababababababababababA',~~$$

$$(16)~~A' \rightarrow^{0.5} abA',~~ (17)~~A' \rightarrow^{0.5} \lambda,~~$$

$$(18)~~B \rightarrow^{1.0} babababababababababaB',~~ \end{di... ...ghtarrow^{0.5} baB',~~ (20)~~B' \rightarrow^{0.5} \lambda.~~$$ (7.5)

$T_3$ erzeugt eine unendliche Menge von Zeichenreihen, von denen jede mindestens die Länge $3*20*20+1+1=1202$ aufweist. Das erste Terminalsymbol jeder Zeichenkette ist entweder $x$ oder $y$. Dann folgt eine sehr lange aus $a$'s und $b$'s bestehende Unterkette. Das letzte Terminalzeichen ist 1, falls das erste Terminalzeichen $x$ war, und 2 sonst.

Wir nennen die am Ende jeder Zeichenreihe auftretenden Symbole $1$ und $2$ `Sequenzklassifikatoren'. Ziel unseres Systems soll die richtige Vorhersage der Sequenzklassifikatoren sein, ohne sie tatsächlich beobachtet zu haben. Um dies zu erreichen, muß das System Ereignisse berücksichtigen, die zumindest 1200 Zeitschritte in der Vergangenheit zurückliegen.

Zunächst wurde wieder ein konventionelles rekurrentes Netz getestet. Die 6 verschiedenen Terminalzeichen wurden jeweils durch einen Bitvektor der Länge 6 mit einer einzigen Komponente $\neq 0$ repräsentiert. Auch die Netzwerkausgaben (die Vorhersagen) waren demgemäß 6-dimensional.

Dem konventionellen Netzwerk war es mit verschiedenen Anzahlen versteckter Knoten, verschiedenen Lernraten, und verschiedenen Gewichtsinitialisierungen zwischen -0.5 und 0.5 (wie nach den Experimenten aus dem letzten Unterabschnitt erwartet) nicht möglich, innerhalb von $10^6$ Trainingssequenzpräsentationen die Sequenzklassifikatoren korrekt vorherzusagen. Ich vermute, daß auch $10^9$ Trainingssequenzpräsentationen nicht ausgereicht hätten - mangelnde Rechenzeit verhinderte allerdings die Bestätigung dieses Verdachts.

Ein Multiebenensystem hingegen traf bei der Lösung der Aufgabe auf keine nennenswerten Schwierigkeiten. Es wurde eine aus drei Ebenen bestehende Prediktorenhierarchie verwendet. Alle drei Prediktoren $P_1$, $P_2$, $P_3$ ließen sich als rekurrente Netze implementieren, die durch `abgeschnittenes BPTT' (siehe Kapitel 2) trainiert wurden, wobei die zu jedem Zeitschritt jeder Zeitskala auftretenden Fehlersignale lediglich 3 Zeitschritte (!) `in die Vergangenheit' zurückpropagiert wurden (mehr waren bei diesem Experiment nicht nötig). Alle 3 Prediktoren besaßen jeweils 6 Eingabeknoten, je einen für die 6 verschiedenen Terminalzeichen (für das Experiment waren keine eindeutigen Zeitschrittrepräsentationen erforderlich). Als deterministische Ausgabe jedes Prediktors $P_i$ wurde derjenige Bitvektor der Länge 1 angesehen, der der eigentlich reellwertigen Ausgabe von $P_i$ am nächsten war. Jeder Prediktor verfügte über 3 versteckte Knoten. Alle Gewichte wurden zufällig zwischen -0.1 und 0.1 initialisiert.

Zunächst wurde $P_1$ mittels 333 gemäß (7.6) generierter Trainingssequenzen trainiert (weniger hätten auch gereicht). Nach Einfrieren von $P_1$'s Gewichten fand $P_2$'s Trainingsphase mit ebenfalls 333 Sequenzpräsentationen statt. Schließlich dienten 333 Sequenzen zur Adjustierung von $P_3$'s Gewichten. Alle drei Netze verwendeten eine Lernrate von 0.333. Die insgesamt 999 Sequenzpräsentationen genügten, dem System beizubringen, die Sequenzklassifikatoren korrekt vorherzusagen.

$P_1$ lernte im wesentlichen, daß $a$ normalerweise von $b$ gefolgt wird, und umgekehrt. Dies entspricht der lokalen in den Regeln (15) - (20) enthaltenen Struktur. Da allerdings dank der Regeln (1) - (14) die von $P_1$ vorhergesagten Werte glegentlich falsch sind (manchmal treten 2 $b$'s oder 2 $a$'s in Folge auf, oder auch eines der Zeichen $x, y, 1, 2$), bekam $P_2$ durchschnittlich alle 21 Zeitschritte (auf $P_1$'s Skala) eine von $P_1$ unerwartete Eingabe. $P_2$ lernte nun seinerseits die in seinen Eingaben enthaltene durch die Regeln (9) - (14) gegebene `globalere Struktur'. Die einzigen von $P_2$ unerwarteten Ereignisse bestanden nun in die Anfängen und Enden der präsentierten Sequenzen. Für $P_3$ war es schließlich einfach, die nach den Regeln (1) - (8) existierende Beziehung zwischen Sequenzanfängen und -enden zu entdecken und die Sequenzklassifikatoren korrekt vorherzusagen. Weitere vergleichbare Experimente finden sich in [37].

Testaufgaben wie die soeben beschriebene zeigen, daß auf dem Prinzip der Geschichtskompression basierende Systeme in gewissen Trainingsumgebungen mindestens 1000 mal schneller lernen können als konventionelle rekurrente Netze. Dabei ist dies noch eine sehr vorsichtige Abschätzung - aufgrund mangelnder Rechnerzeit war es nicht möglich, herauszufinden, wie lange ein konventionelles Netz zur Lösung obiger Aufgabe braucht. Weiterhin kann es sein, daß (wie im obigen Experiment) die an der Hierarchie beteiligten Prediktoren wesentlich weniger Operationen pro Zeitschritt benötigen als ein konventionelles rekurrentes Netzwerk - einfach deswegen, weil sie auf ihrer gedehnten Zeitskala Fehler häufig nur relativ wenige Zeitschritte in die Vergangenheit zurückpropagieren müssen. In gewissen Umgebungen reichen also lokale Lernalgorithmen aus, um in der Hierarchie beliebig lange Zeitspannen zu überbrücken. In solchen Fällen lassen sich demnach zwei Fliegen mit einer Klappe schlagen.

Es sollte nun klar sein, daß man durch Wahl komplexerer Grammatiken als (7.6) die Vorteile einer Prediktorenhierarchie im Vergleich zu den `konventionellen' Verfahren aus Kapitel 2 beliebig deutlich herausstellen kann - die hier an einem speziellen Beispiel demonstrierte mindestens 1000-fache Überlegenheit der neuen Methodik stellt bei weitem keine obere Schranke dar.

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