Keine Rückkopplung

Stochastische Lernautomaten sind abstrakte Maschinen, die ausgehend von einer Wahrscheinlichkeitsverteilung möglicher Aktionen Ausgaben produzieren. Keine Eingaben kommen von der Umgebung. Abhängig von der Bewertung eines evaluativen Kritikers werden bestimmte Aktionen jeweils wahrscheinlicher oder unwahrscheinlicher gemacht. Für diesen Zweck eignen sich viele einfache Lernalgorithmen, unter anderem die vielgestaltigen Belohnungs-/Bestrafungsalgorithmen (reward-penalty-algorithms). Wird eine spezifische Aktion ausgewählt und als erfolgreich bewertet, so soll ihre Auswahlwahrscheinlichkeit auf Kosten der Auswahlwahrscheinlichkeiten anderer Aktionen erhöht werden. Führt sie jedoch zum Mißerfolg, so soll ihre Auswahlwahrscheinlichkeit in Zukunft niedriger sein. Es gibt umfassende mathematische Literatur zu solchen stochastischen Lernautomaten (siehe [33]).

Assoziative Stochastische Lernautomaten (der Begriff stammt von Williams [78]) sind für uns wesentlich interessanter, da sie zumindest schon einmal Reaktionen auf Eingaben von der Umgebung erlauben. Von den assoziativen stochastischen Lernautomaten interessiert uns zunächst die quasilineare stochastische Einheit. Die Wahrscheinlichkeit, daß solch eine Einheit (im folgenden auch `Knoten' genannt) mit der Nummer $i$ die Ausgabe $y_{i}$ produziert, hängt von einer Wahrscheinlichkeitsverteilung ab, deren Dichtefunktion nur einen Parameter $p_i = f_i (\sum_{j}w_{ij}x^{i}_{j})$ besitzt. Dabei ist $w_{ij}$ die $j$-te Komponente des Gewichtsvektors $w_i$ des Knotens $i$, $x^{i}_{j}$ die $j$-te Komponente seines Eingabevektors $x^{i}$, und $f_{i}$ eine mit $i$ assoziierte sigmoide Funktion. Als Spezialfall erwähnen wir den quasilinearen Bernoulliknoten $i$: Für ihn ist $y_i \in \{0, 1 \}$, mit $P(y_i = 0 \mid w_i, x^{i}) = 1 - p_i$ und $P(y_i = 1 \mid w_i, x^i) = p_i$.

Barto und Anandan [3] nennen Lernaufgaben, bei denen es dem lernenden System möglich ist, Aktionen mit kontextueller Zusatzinformation (gewonnen aus Eingaben von der Umgebung) zu assoziieren, assoziative Reinforcement Lernaufgaben (associative reinforcement learning tasks). Barto und Anandan entwarfen den Assoziativen Belohnungs-/Bestrafungsalgorithmus (associative reward-penalty algorithm) für den Fall binären Reinforcements $r \in \{0, 1 \}$:

$$\triangle w_{ij} = \alpha (y_i - p_i) x^i_j ~~ falls~~r=1, ~... ... w_{ij} = \alpha \lambda (1 - y_i - p_i) x^i_j ~~ falls~~r=0.$$

Dabei ist $\triangle w_{ij}$ wie immer die Gewichtsänderung von $w_{ij}$, $\alpha$ eine Lernrate, und $0 \leq \lambda \leq 1$. Barto und Jordan haben auch eine Verallgemeinerung für kontinuierliches Reinforcement vorgeschlagen [4].

Williams setzte mehrere quasilineare Knoten zu einem azyklischen Netzwerk zusammen. Eine Aktivationsausbreitungsphase in solch einem Netz läuft analog zu der Aktivationsausbreitungsphase in einem Back-Propagation Netz ab. Der wesentliche Unterschied besteht in der stochastischen Natur der Aktivierungsfunktionen.

Das Reinforcementsignal $r$ ist wieder ein - diesmal allen Knoten zugänglicher - skalarer Wert. Vorausgesetzt wird nun, daß für alle $\xi \in Y_i$ (der Menge aller möglichen Ausgaben von $i$)

$$\frac{\partial P\{ y_i = \xi \mid w_i, x^i \} }{\partial w_{ij}}$$

existiert, und daß die Gewichte der Änderungsregel

$$\triangle w_{ij} = \alpha_{ij} (r - b_{ij}) e_{ij}$$

gehorchen. Dabei ist $\alpha_{ij}$ eine positive Lernrate, $b_{ij}$ ein Offset, welches für gegebenes $w$ und $x^i$ unabhängig von $y_{i}$ ist, und $e_{ij}$ die charakteristische Eligibilität

$$e_{ij} := \frac{\partial ln~P\{ y_i = \xi \mid w_i, x^i \} }{\partial w_{ij}} .$$

Unter diesen Voraussetzungen bewies Williams eine interessante sich auf die Performanzverbesserung solcher Netzwerke beziehende Aussage [78]: Das innere Produkt

$$\frac{\partial E\{ r \mid w \} }{\partial w} E\{ \triangle w \mid w \}$$

ist positiv, solange der zweite Faktor nicht Null ist.

Was bedeutet dieses Resultat? Es zeigt, daß man für eine große Klasse von Lernalgorithmen im Mittel erwarten kann, daß sich die Gewichte in Richtung des Gradienten des Erwartungswerts des Reinforcements ändern.

Das ist ein sehr allgemeines und sehr wünschenswertes Ergebnis. Allerdings sind die von Williams so getauften `REINFORCE'-Algorithmen (`REward Increment = Nonnegative Factor * Offset Reinforcement * Characteristic Eligibility') nur dann zweckmäßig, wenn die Umgebung außer Reinforcementsignalen keine Zusatzinformation über wünschenswerte Ausgaben bereitstellt. Zwar sind REINFORCE-Algorithmen bei weitem allgemeiner als etwa Back-Propagation. Wo jedoch beide Paradigmen anwendbar sind, zieht man überwachte Gradientenabstiegsverfahren wegen ihrer erfahrungsgemäß weit schnelleren Konvergenz vor.

Die Lernregel für die REINFORCE-Algorithmen erlaubt eingeschränkte Lokalität in Zeit und Raum: Kein Analogon zur Fehlerpropagierungsphase beim überwachten Lernen ist notwendig. Jeder Knoten erhält nach der Aktivationsausbreitung dasselbe Reinforcementsignal. Allerdings müssen auch bei REINFORCE-Algorithmen Aktivationsausbreitung und Gewichtsänderung durch eine globale Instanz zeitlich getrennt werden.

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