next up previous contents
Nächste Seite: Neuronale Ansätze Aufwärts: Potentiell relevante nicht-neuronale Methoden Vorherige Seite: Genetische Algorithmen   Inhalt

Die Eimerkette für regelbasierte Systeme

Konzeptionelle Vorteile gegenüber den genetischen Algorithmen bietet Hollands bucket brigade Prinzip für regelbasierte Systeme. Es geht hierbei darum, viele einfache regelähnliche Entitäten (sogenannte Klassifikatoren ) in einer Weise zur Kooperation zu veranlassen, die zum erfolgreichen Verhalten des Gesamtsystems führt.

Botschaften in Form von Bitsequenzen der Länge $n$ können sowohl von der Umgebung eines lernenden Systems als auch von zu dem System gehörigen Klassifikatoren auf der globalen Botschaftentafel plaziert werden. Ein Klassifikator selbst ist eine zweigeteilte Zeichensequenz bestehend aus einer `Bedingungssequenz' und einer `Aktionssequenz'. Beide Teile sind Sequenzen aus $\left\{ 0,1,\_ \right\}^{n}$, wobei die Semantik des `_' im Falle des Auftretens in einer Bedingungssequenz besagt: `Ignoriere mich!'.

Eine positive reelle Variable ist mit jedem Klassifikator assoziiert und zeigt seine gegenwärtige `Stärke' an.

Im Laufe eines Zyklus (ein Zyklus entspricht einem Zeitschritt) werden alle Botschaften auf der Botschaftentafel mit den Bedingungssequenzen aller Klassifikatoren verglichen. Jeder Klassifikator, dessen Bedingungsteil mit wenigstens einer Botschaft übereinstimmt, berechnet seinen `Wetteinsatz', indem er seine Spezifizität (die Anzahl der Bits in seinem Bedingungsteil, die keine `_'s sind) mit dem Produkt seiner Stärke und einer kleinen Konstanten multipliziert.

Die höchstbietenden Klassifikatoren dürfen für den nächsten Zyklus nun ihren Aktionsteil auf die Botschaftentafel schreiben. (Tritt dabei das `_' in einer Aktionssequenz auf, so bewirkt es eine Durchreicheoperation: Das entsprechende Bit der `triggernden' Botschaft wird übernommen.)

Für das Schreibeprivileg müssen die Gewinner allerdings mit ihrem Wetteinsatz bezahlen, welcher unter denjenigen Klassifikatoren verteilt wird, die während des letzten Zyklus überhaupt erst die Vorraussetzungen für die Schreiboperationen der Gewinner schufen. Jeder in einer bestimmten Situation `aktive' Klassifikator wird also schwächer werden, wenn er seine Verluste im nächsten Zyklus nicht wieder ausgleichen oder gar mehr als wettmachen kann. So wie bei einer Eimerkette zum Feuerlöschen viele Eimer gleichzeitig von einer Station zur nächsten weitertransportiert werden, so werden bei Hollands Algorithmus Klassifikatorenstärken `durchgereicht'. Daher der Name `Eimerkette'.

Bestimmte Botschaften auf der Botschaftentafel werden von der Peripherie als Anweisung interpretiert, eine bestimmte Operation in der Umgebung auszuführen. Manche dieser Aktionen mögen von einem externen Kritiker als brauchbar angesehen werden. Der Kritiker verteilt in solchen Fällen eine Belohnung (Auszahlung) an die gegenwärtig aktiven Klassifikatoren, deren Stärke dadurch wächst.

Die zentrale Idee des ganzen Verfahrens ist: `Versteckte' Klassifikatoren, die zwar im Augenblick der externen Auszahlung nicht aktiv sind, die jedoch eine wichtige Rolle spielten, um überhaupt erst einmal die Vorbedingungen für die direkt belohnten Klassifikatoren zu schaffen, partizipieren am Lernprozeß durch ihre Einbindung in Eimerketten. Der Erfolg eines zu einem gegebenen Zeitpunkt aktiven Klassifikators hängt damit rekursiv von den Erfolgen seiner Nachfolger ab. Der externe Kritiker beendet die Rekursion. (Als ein zusätzliches Mittel zur Verbesserung der Performanz führt Holland genetische Algorithmen für die Konstruktion neuer Klassifikatoren ein.)

Die Kommunikation über die zentrale Botschaftentafel sowie der globale Wettbewerb aller Klassifikatoren machen das Verfahren weder lokal im Raum noch in der Zeit. Dennoch: Einer der Beiträge dieser Dissertation ist durch das Eimerkettenprinzip inspiriert und wendet es auf neuronale Netze an. Die Motivation dabei ist, den ersten wirklich lokalen Lernalgorithmus für neuronale Netze zu schaffen.


next up previous contents
Nächste Seite: Neuronale Ansätze Aufwärts: Potentiell relevante nicht-neuronale Methoden Vorherige Seite: Genetische Algorithmen   Inhalt
Juergen Schmidhuber 2003-02-20


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