Methoden der zeitlichen Differenzen

Dieser Abschnitt behandelt einen für uns sehr wichtigen Spezialfall überwachten Lernens. Es geht dabei darum, Voraussagen über Aspekte des zukünftigen Verhaltens eines sich zeitlich ändernden Systems zu treffen. Während reine Gradientenabstiegsverfahren Gewichtsänderungen anhand von Unterschieden zwischen vorausgesagten und tatsächlichen Zuständen durchführen, verwenden Methoden der zeitlichen Differenzen (kurz `TD-Methoden', `TD' steht für `Temporal Differences' ) Unterschiede zwischen aufeinanderfolgenden Vorhersagen. Erstaunlicherweise kommen TD-Methoden dort, wo sie anwendbar sind, nicht nur mit weniger Spitzenberechnungsaufwand als konventionelle Techniken aus, sondern produzieren unter bestimmten Voraussetzungen auch genauere Vorhersagen. Wo sind sie anwendbar? Zum Beispiel dort, wo es darum geht, den Endzustand eines dynamischen Prozesses vorherzusagen.

Für einige der in späteren Kapiteln vorgestellten Problembereiche bieten sich Methoden der zeitlichen Differenzen an, um bestimmte Eigenschaften einer dynamischen Umgebung zu modellieren. Das durch TD-Methoden gewonnene Modell dieser Eigenschaften kann für die adaptive Konstruktion zielgerichteter Programme ausgenützt werden. Dieser Abschnitt liefert die nötigen Grundlagen.

Es liege eine Sequenz von Beobachtungen $x_{t}, t \in \left\{ 1 \ldots n \right\}$ eines dynamischen Systems zu aufeinanderfolgenden Zeitpunkten $t$ vor. Das Problem besteht darin, zu jedem Zeitpunkt $t \leq n$ eine Vorhersage $P_{t}$ über den finalen Zustand $x_{n} = P_{n}$ zu treffen. Purer Gradientenabstieg würde bedeuten:

$$\triangle w^T = -\alpha \sum_{t = 1}^{ n-1} (P_{n} - P_{t}) \frac{\partial P_{t}}{\partial w} .$$

Dabei ist $w$ wieder der Gewichtsvektor des Netzes, $\alpha$ eine positive Lernrate, und $\triangle w$ die von der Lernregel induzierte Gewichtsänderung.

TD$(\lambda)$-Methoden werden im Gegensatz dazu nun wie folgt definiert:

$$\triangle w^T = -\alpha \sum_{t = 1}^{ n-1} (P_{t+1} - P_{... ..._{k = 1}^{t} \lambda^{t-k} \frac{\partial P_{k}}{\partial w} .$$

Hierbei ist $0 \leq \lambda \leq 1$ ein `Schwundfaktor', welcher bestimmt, wie stark vergangene Voraussageänderungen in die Gewichtsänderung mit einfließen.

Bei den TD$(\lambda)$-Methoden handelt es sich um eine Generalisierung des Gradientenabstiegs. Für $\lambda = 1$ ergibt sich mit etwas Hin- und Herschaufeln von Indizes nämlich exakt der pure Gradientenabstieg.

Für $\lambda \neq 1$ allerdings bekommt man etwas, was kein Gradientenabstieg ist. Ist das, was man da erhält, nun gut, oder ist es schlecht? Es läßt sich zeigen, daß TD$(\lambda)$ mit $\lambda \leq 1$ zumindest für spezielle Arten von dynamischen Systemen bessere Voraussagen ermöglicht als der pure Gradientenabstieg TD$(1)$: Unter der Voraussetzung, daß das vorherzusagende System sich als ein absorbierender Markov-Prozeß beschreiben läßt, konnte Sutton demonstrieren, daß lineare TD$(0)$ zu den optimalen Voraussagen (im Sinne der `maximum likelihood estimates') konvergiert [67]. (Wiederholung: Ein Markov-Prozeß ist ein Prozeß, bei dem die Weiterevolution von einem gegebenen Zustand zur Zeit $t$ nicht von früheren Zuständen abhängt. Ein absorbierender Markov-Prozeß ist einer, bei dem die Wahrscheinlichkeit der Terminierung $1$ ist.)

Ein weiterer wichtiger Vorteil der TD$(\lambda)$-Methoden ist ihre Zugänglichkeit für inkrementelle Gewichtsänderungen und dem damit verbundenen niedrigen Spitzenberechnungsaufwand. Am deutlichsten wird das für den Fall, der uns im weiteren am meisten interessieren soll, nämlich TD$(0)$. Man führt für jeden Zeitpunkt $t < n$ einen Wert $\triangle w_{t}$ ein, welcher sich wie folgt berechnet:

$$\triangle w_{t}^T = -\alpha (P_{t+1} - P_{t}) \frac{\partial P_{t}}{\partial w} .$$

$\triangle w = \sum_{t}\triangle w_{t}$ liefert die Gesamtgewichtsänderung, welche stattfindet, nachdem alle Beobachtungen gemacht wurden. Schon während das dynamische System beobachtet wird, kann man in akkumulativen Variablen die Summe der bisher berechneten Gewichtsänderungen für jedes Gewicht inkrementell auf den neuesten Stand bringen. Daher ist der Spitzenberechnungsaufwand pro Zeitschritt und Gewicht $O(1)$.

Will man ein Verfahren, das komplett `on-line' arbeitet, so kann man jede Gewichtsänderung in dem Moment durchführen, in dem sie berechnet wird. Für den TD$(0)$-Fall bedeutet das:

$$\triangle w_{t}^T = - \alpha (P_{x_{t+1}, w_{t}} - P_{x_{t}, w_{t}} ) \frac{\partial P_{x_{t}}}{\partial w} .$$

Dabei ist $P_{x_{t}, w_{t}}$ die entsprechende Voraussage basierend auf $x_{t}$ und $w_{t}$.

Auch für Voraussagen kumulativer Art sind TD-Methoden geeignet. Später wird es zum Beispiel darauf ankommen, zu jedem Zeitpunkt $t$ eine Summe noch ausstehender Reinforcementsignale $R_{k}$ zu allen späteren Zeitpunkten $k$ vorherzusagen. Nach der Lernphase soll für alle $t$ gelten:

$$P_{t} = \sum_{k = 0}^{m} \gamma^{k} R_{t+k+1} .$$

Hierbei kann $m$ für angemessenes $\gamma$ unendlich sein, denn $0 < \gamma \leq 1$ ist wieder eine `Discountrate', welche bestimmt, wie stark Erwartungen über verschieden weit in der Zukunft liegende Ereignisse die Gewichtsänderung mit beeinflussen sollen. Da nach obiger Gleichung

$$P_{t} = R_{t+1} + \gamma P_{t+1} ,$$

gelten soll, muß $\triangle w_{t}$ im Fall TD$(0)$ nun wie folgt berechnet werden:

$$\triangle w_{t}^T = -\alpha (R_{t+1} + \gamma P_{t+1} - P_{t}) \frac{\partial P_{t}}{\partial w} .$$

Für den `on-line' Fall muß man Voraussagen wiederum mit Indizes versehen, die Gewichtsvektoren zu verschiedenen Zeitpunkten anzeigen.

Man sollte nicht vergessen, daß die vorausgesetzte Markov-Eigenschaft in der Praxis oft nicht gegeben ist. Für den Fall, daß die Umgebung (oder zumindest die für ein lernendes System wahrnehmbare Umgebung) nicht vom Markov-Typ ist, kann man allerdings TD-Methoden und generelle Gradientenabstiegsverfahren für rekurrente Netze in sinnvoller Weise kombinieren, wie sich in Kapitel 6 zeigen wird.

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