Lernen in Neuronalen Agenten
Begriffliche Grundlagen
Verhalten
Entspricht dem natürlichsprachlichen Begriff des Verhaltens und umfasst alle strukturierten Interaktionen mit der Umwelt. Dabei kann man, sofern man das möchte, zwischen komplexem Verhalten und Basisverhalten unterscheiden (wobei sich komplexes Verhalten aus Basisverhalten zusammensetzt)
Agent
Ein Agent ist eine physische oder virtuelle Entität (Ferber 2001),
- die selbständig in einer Umwelt agieren kann
- die direkt mit anderen Agenten kommunizieren kann
- die durch eine Menge von Absichten angetrieben wird (in Form von individ. Zielen, Befriedigungs-/Überlebensfunktionen, die sie versucht zu optimieren)
- die eigene Ressourcen besitzt
- die fähig ist, ihre Umwelt wahrzunehmen (nur in einem best. Ausmaß!)
- die nur eine partielle Repräsentation der Umwelt (Modell) besitzt
- die bestimmte Fähigkeiten besitzt (oder erwirbt) und Dienste offerieren kann
- die sich ggf. selbst reproduzieren kann
- deren Verhalten darauf ausgerichtet ist, ihre Ziele unter Berücksichtigung der ihr zur Verfügung stehenden Ressourcen und Fähigkeiten zu befriedigen und die dabei auf ihre Wahrnehmung, ihre internen Modelle und ihre Kommunikation mit anderen Agenten (oder Menschen) angewiesen ist
Stability-Plasticity Dilemma
Ist das Problem auf neue Situationen reagieren zu können und diese zu lernen, dabei aber bereits angesammeltes Wissen zu bewahren.
Exploration-Exploitation Dilemma
Ebenfalls ein Standardproblem von lernenden Systemen. Um neues Wissen über meine Umwelt zu erlangen müsste ich ständig explorieren, andererseits sollte ich aber auch ständig bekannte Aktionen ausführen um bereits gelerntes Wissen anzuwenden (exploitation) Lösungsansätze kommen später
Ebenen des Lernens und der Wissensrepräsentation
prozedurales Wissen
- Verhaltenswissen bzw. Sensomotorische Intelligenz.
- Beschreibt für eine ganz konkrete sensorische Situation die möglichen Aktionen des Agenten
deklaratives Wissen
- deliberatives oder auch kognitives Wissen
- Stellt Repräsentation der Umwelt da
- dient der Planung von Verhalten
Aus deklarativem Wissen können Subziele einer Handlungsstrategie festgelegt werden, welche dann mit Hilfe des prozeduralen Wissens abgearbeitet werden. Zum Beispiel könnte ein, mittels deklarativem Wissen erstelltes, Subziel, auf dem Weg ein Wasserglas zu greifen, sein, den Arm auszustrecken. Das prozedurale Wissen beschreibt dann wie die Muskeln anzusteuern sind, um den Arm nach vorne zu bekommen.
Reinforcement Learning
Grundidee des RL
Für jede Ausgeführte Handlung (Oder auch am Ende eines Handlungsstranges) erhält ein Agent eine Belohnung oder Bestrafung (Reinforcement). Dieses Akkumuliert sich über die Zeit. Ziel Des Reinforcementlearning ist es nun, durch Lernen solche Entscheidungsstrategien zu finden, dass die akkumulierten Reinforcements optimiert werden.
Charakterisierung des RL
- Lernparadigma:
- irgendwo zwischen überwachtem Lernen und unüberwachtem Lernen
- nutzt ebenfalls ein Feedback, aber nur zur Bewertung des Verhaltens
- alleinige Aussage, ob das Verhalten gut war oder schlecht, aber nicht, wie es hätte sein müssen
- Grundsatz (noch mal in einem Satz):
- autonomes Lernen komplexer Wahrnehmungs-Verhaltens-Muster basierend auf einem unspezifischen skalaren Signal, welches das Systemverhalten bewertet
- Findet Anwendung in: Robotik, Optimaler Regelung, Spielen uvm.
General RL-Task
<graphviz> digraph G { Umgebung -> Agent [label="Zustand (State)"]; Umgebung -> Agent [style=dotted,label="Reinforcement"]; Agent -> Umgebung [label="Aktion"]; } </graphviz>
- Ziel: Zu lernen die Aktionen auszuführen die zum größten Lanzeit reward führen
-
- ... Langzeitreward
- ... Discountfaktor [0,1]
- ... reward zum Zeitpunkt t
- Durchführung: Ausführung einer Aktion und beobachten des Ergebnisses
- Anpassen der Policy, welche die Aktion ausgewählt hat, je nach dem ob das Reward positiv oder negativ ausgefallen ist, damit die Aktion öfter ausgeführt wird oder weniger oft, wenn der selbe Zustand wieder erreicht werden sollte.
- Die beste Aktion in einem Zeitschritt führt nicht immer zum besten Langzeitergebnis!
schwache und starke RL-Verfahren
- schwache RL-Verfahren
- Haben nur eine begrenzte Zeitliche Sicht
- Wählen immer die für ihre Sicht optimale Aktion aus
- starke RL-Verfahren
- besitzen zeitlich unbegrenzte Sicht
- Versuchen eine global optimale Policy zu erlernen
- Maximierung der Summe aller rewards
RL als MDP
- MDP (Makrov Decision Processes)
- Annahmen
- es gibt nur eine endliche Menge an Zuständen
- es gibt eine endliche Menge an ausführbaren Aktionen
- Der Zustand kann zu jeden Zeitpunkt beobachtet werden und es ist möglich eine Aktion auszuwählen für den Zustand anhand einer Policy
- Nach der Ausführung der Aktion gibt es ein reward
- Der Zustand wird durch die Aktion in den nächsten Zustand überführt
- Markov Annahme
- Der nächste Zustand wird ausschließlich durch den aktuellen Zustand und die auszuführende Aktion bestimmt
- Damit kann der zu erwartende Reward anhand des aktuellen Zustandes berechnet werden
Basiskomponenten einses RL-Agenten
\\ Bild Folie 3a-16
Policy
- Entscheidungsfunktion welche Angibt welche Aktion ausgeführt werden soll wenn sich der Agent in einem bestimmten Zustand befindet
- Die Policy bestimmt das verhalten und die Performance des Agent alleine
- Alle anderen Komponenten existieren nur damit die Policy verbessert und angepasst werden kann
Reinforcment Funktion
- Definiert die Ziele des Agenten
- Wird vom Entwickler vorgegeben
- Ist eine Funktion die den Zustand bewertet und angibt wie erwünscht er ist
- => Definiert was gut und was schlecht ist
- Darf während des Lernens nicht geändert werden, sonst kann man keine Policy erreichen
Value/Action Funktion
- Value V(S) ist eine Funktion welche angibt welchen Reward man erhalten würde wenn man sich im Zustand S befindet und der Policy folgt
- Action-Value Q(s,a) ist eine Funktion welche angibt welchen Reward man erhalten würde wnn man sich im Zustand S befindet die Aktion a ausführt und dann der Policy folgt
- Somit kann nicht nur kurzsichtig agiert werden sondern auch langfristig
- Kann approximiert werden durch Lookup Tabellen oder MLP/RBF- Netzwerke
- Eine der Hauptaufgaben des RL ist es die Funktion durch lernen effizient zu approximieren
Umgebungsmodell
- Kann durch den Entwickler vorgegeben werden oder selbst erlernt werden
- Hilft den neuen Zustand vorherzusagen wenn man eine bestimmte Aktion ausführt
- Nicht jeder RL-Agent besitzt ein Umgebungsmodell aber es erhöt die Geschwindigkeit mit der ein Agent die optimale Policy lernt
- Modellfreie RL-Agenten finden die selbe Lösung ... es dauert nur länger
Umgebung
- Muss wenigstens teilweise Beobachtbar sein
- Siehe: State vs. Situation
- Umgebung gibt die möglichen Aktionen mit vor
State vs. Situation
- State (Zustand)
- Alle notwendigen Parameter um eine Umgebung zu beschreiben und eine Aktion auszuwählen sind dem Agenten zugänglich
- wie z.B. globale Positionsinformation
- Situation
- Der Agent hat nur Zugriff auf einen Teil der Parameter. Somit kann er den aktuellen Zustand nicht immer eindeutig beschreiben.
- z.B. navigation mit IR oder Ultraschall Sensoren
Q-Learning
Q-Values oder auch Action-State-Values sind ein Maß dafür, welchen Reward man durch die Ausführung einer bestimmten Aktion (a) in einem bestimmten State (s) erwartet. Wählt man immer die Aktion mit dem größten Q-Wert, so sollte sich auch der long term reward maximieren. Dazu müssen die korrekten Q-Values angelernt werden. Funktioniert folgendermaßen:
- Initialisierung aller geschätzten mit 0 [Anm.: Bei unendlich häufiger Ausführung des Algorithmus nähern sich die geschätzen den optimalen (welche den long-term reward maximieren) an.]
- beobachte den aktuellen State
- Wiederhole:
- Wähle eine Aktion im aktuellen Zustand entsprechend der policy (z.B. greedy Auswahl der Aktionen mit maximalem Q-Wert oder Bolzmann Auswahl) und führe sie aus
- Erhalte den sofortigen reward
- Beobachte den neuen Zustand
- Update des geschätzten nach folgender Update-Gleichung
- Bis die Zustände erschöpfend durchsucht wurden
Die Updateregel ist wie folgt zu interpretieren:
Die neue Schätzung des Q-Values einer Aktion a (welche soeben durchgeführt wurde) im vorigen Zustand s (Der Zustand vor dem Ausführen der Aktion a) setzt sich aus der alten Schätzung dieses Wertes zusammen plus einen Anpassungsterm, welcher mit einer skalaren Größe gewichtet ist, welche die Lerngeschwindigkeit beeinflusst. Der Anpassungsterm ist der, durch Ausführung von a, erhaltene Reward + dem maximal möglichen Q-Value des Zustandes in dem ich mich aktuell befinde minus dem Q-Value des vorigen Stuzandes. Der Faktor Gamma sorgt dafür, dass die Q-Werte mit steigender Entfernung (im Sinne von aufeinander folgenden Zuständen) zu einem Zustand, in welchem es einen großen Reward gibt, stetig fallen. Damit kann eine Art Q-Value Gradientenaufstieg in Richtung von besonders positiven Zuständen erfolgen (oder eben eine Abwendung von besonders negativen). Die Subtraktion des Q-Values am Ende sorgt nur dafür, dass diese nicht ins Endlose steigen. Sieht man gut, wenn man beta als 1 annimmt.
Exploration/Exploitation revisited
Wie schon mal angesprochen sollte man nicht immer nur exploren aber auch nicht nur exploiten *räusper*
Zwei Verfahren besprochen, das Dilemma "schön" zu lösen:
- Epsilon-Greedy:
- Mit Wahrscheinlichkeit von wird die Aktion ausgewählt, welche den höchsten Reward verspricht (welcher der höchste Q-Wert anhängt)
- Mit Wahrscheinlichkeit wird eine zufällige Aktion ausgewählt
- Boltzmann-Aktionsauswahl:
- Boltzmann Temperatur bestimmt den Grad der Zufälligkeit der Aktionsauswahl.
- geht T gegen unendlich ist die Auswahl unabhängig vom Q-Wert ( mit M - Anzahl der möglichen Aktionen)
- bei kleinerem T werden eher Aktionen mit hohem Q-Wert ausgewählt.
SARSA-Learning
- SARSA ist keine Krankheit sondern ein TD-Lernverfahren ähnlich dem Q-Learning
- Die Update Regel der Q Werte lautet:
- Typischer Vertreter für ein On-Policy verfahren
- mit einer Greedy-Policy Konvergiert dieses Verfahren gegen das Q-Learning
Eligibility Traces
- Ziel: Rückverteilung der temporealen Differenz von bzw. auf alle Zustände bzw. Zustands-Aktionspaare die zu der aktuellen Situation beigetragen haben
- Einsatz: Vor allem bei Delayed RL-Problemen
- Zielanfahrten
- Spiele
- erhöhen die Lerngeschwindigkeit des RL-Verfahrens da alles durchlaufenen Zustande und Aktionen aktualisiert werden
- Die Updateregeln ändern sich zu:
- Beispiel für Realisierungen des Traces
- Accumulating Trace
- Diese Version kann Instabil werden da Werte >1 möglich sind
- replacing trace
- → TD(0) Alle Traces sind deaktiviert => Normales TD Lernen
- Normale abklingende Traces
- Abklingen des Traces wird nur noch durch hervorgerufen
- Accumulating Trace
- Bei der Ausführung von off-policy Aktionen muss der Trace deaktiviert werden
- Da der Zustand nicht durch befolgen der Policy erreicht wurde
Neuronale Umsetzung von RL-Agenten
Learning Classifier Systems
- LCS kommen aus der Symbolischen KI
- Sind entstanden dadurch das Expertensysteme mit Genetischen Algortihmen verbunden wurden um Regeln schneller zu erlernen.
- Ein LCS besteht aus drei Hauptkomponenten
- Ein Regel und Nachrichten System
- Regelt die Interaktion mit der Umgebung
- Übersetzt die reellen Zahlen der Umgebung in abstrakte Nachrichten
- Repräsentiert die aktuelle Policy welche in Form von Klassifizierern vorliegt
- Ein Credit Aufteilungssystem (zum Bewerten der Wissensbasis)
- Verteil die eingehenden Rewards auf alle Regeln
- Realisiert die Lern-Policy
- Ein System zum entwickeln von Klassifizieren
- Aufgabe ist das explorieren und spezialisieren der Zustand-Aktionsraum Repräsentation
- Ein Regel und Nachrichten System
- Detektoren
- erkennen Features in complexen reellwertigen eingaben von der Umgebung
- Übersetzen diese Eingaben in einen Vektor aus {1,0}
- Classifier
- Jeder Classifier beschreibt eine Regel
- Jede Regel besteht aus einer Menge von Bedingungen (Vektor von {0,1,#} # ... Joker)
- Eine Aktion ein Vektor von {0,1}
- Eine Stärke
- Jeder Classifier beschreibt eine Regel
- Effektors
- Übersetzen Nachrichten in Aktionen die Ausgeführt werden sollen
- Aktionsauswahl
- Alle Nachrichten der Umgebung werden gegen alle classifier geprüft
- Auf einen Zustand können mehrere Regeln zutreffen
- Alle Classifier auf die eine Nachricht zutrifft nehmen an einer Auktion teil
- Jeder passende Classifier muss dafür ein gebot abgeben das sich nach seiner Stärker und seiner spezifizität richtet
- Jeder passende Classifier muss dafür ein gebot abgeben das sich nach seiner Stärker und seiner spezifizität richtet
- Creditverteilung
- Alle Clasifier müssen ihr Gebot bezahlen
- Jeder Classifier muss eine Kopfsteuer Zahlen
- Der Gewinnende Klassifier muss sein Gebot bezahlen und bekommt das Reward sowie einen Anteil des folgenden Gebotes
- Alle Clasifier müssen ihr Gebot bezahlen
- Anpassung der Classifier
- Deterministisch
- Wenn kein Classifier auf die Nachricht passt wird einfach ein neuer angelegt mit einer zufälligen Aktion
- Die Stärke wird auf den Durchschnitt aller bereits vorhandenen Regeln gesetzt
- Genetischer Algorithmus
- Die Stärksten Classifiert werden ausgewählt
- Werden gemischt (Übernehmen von Teilen aus dem einen und dem anderen CLassifier um einen neuen zu erstellen)
- Und Mutiert (Werte werden zufällige geändert)
- Deterministisch