Lernen in Neuronalen Agenten: Unterschied zwischen den Versionen
Sonne (Diskussion | Beiträge) |
Sonne (Diskussion | Beiträge) |
||
Zeile 93: | Zeile 93: | ||
* <math> R_t = \sum_{k=0}^\infty \gamma^k \cdot r_{t+k+1} </math> | * <math> R_t = \sum_{k=0}^\infty \gamma^k \cdot r_{t+k+1} </math> | ||
** <math> R_t </math> ... Langzeitreward | ** <math> R_t </math> ... Langzeitreward | ||
− | ** <math> \gamma </math> ... Discountfaktor [0,1] | + | ** <math> \gamma </math> ... Discountfaktor [0,1] ... schwächt den den Einfluss ferner Rewards ab |
** <math> r_t </math> ... reward zum Zeitpunkt t | ** <math> r_t </math> ... reward zum Zeitpunkt t | ||
* Durchführung: Ausführung einer Aktion und beobachten des Ergebnisses | * Durchführung: Ausführung einer Aktion und beobachten des Ergebnisses |
Version vom 10. Juli 2009, 10:20 Uhr
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
Lernprozesse
- Zweck der Informationsverarbeitung: situationsgerechtes Verhalten in der Umwelt
- Zwecke des Lernens: Veränderung des Verhaltens und damit Vergrößerung des Einsatzbereichs in dem Agent eingesetzt werden kann
- Realisierung des Lernprozesses: Umstrukturierung der Steuerarchitektur
Perception-Action-Cycle
- Wahrnehmungs-Handlungs-Zyklus
- Lernen erfordert eine sensorische Beobachtung der Umwelt und eine Aufgabe bzw. zielgerichtete Handlung, deren Erfolg/Misserfolg für den Agenten erkennbar sein muss
- Resultat: Selbstoptimierung des Verhaltens (um bestmöglich die gestellte Aufgabe zu erfüllen)
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
- "Gewusst WIE"
deklaratives Wissen
- deliberatives oder auch kognitives Wissen
- stellt Repräsentation der Umwelt dar
- dient der Planung von Verhalten
- "Gewusst WAS"
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.
Konditionierungslernen
- ein grundlegendes Lernprinzip im Perception-Action-Cycle
klassische Konditionierung
- ein unkonditionierter Stimulus (US) erzeugt immer eine sichtbare Reaktion (UR) und ist angeboren, wie ein Reflex
- z.B Nahrung -> Speichelfluss
- ein konditionierter Stimulus (CS) erzeugt zunächst keine sichtbare Reaktion (CR)
- z.B. Glockenschlag
- durch die kombinierte Anwendung von US und CS ist es möglich, ein CR auszubilden, welches dem UR ähnelt bzw. mit ihm identisch ist
- Folge: durch die alleinige Anwendung des CS kommt es zur sichtbaren Reaktion UR
- z.B. Die Fütterung eines Hundes (US) löst bei diesem zunächst Speichelfluss (UR) aus. Ertönt bei jeder Futtergabe ein Glockenschlag (CS) führt dies dazu, dass nach einiger Zeit der Glockenschlag allein ausreicht um den Speichelfluss zu aktivieren. (CR=UR)
-> Detektion von Beziehungen zwischen Ereignissen in der Umwelt
instrumentale Konditionierung
- Aktionen die in bestimmten Situationen zu Befriedigung führen werden häufiger ausgeführt als solche die zu Unzufriedenheit führen, d.h. unmittelbar auf eine Handlung folgt eine Konsequenz
- die Handlung fungiert somit als Instrument für die Konsequenz
- z.B. eine Ratte die eine Taste berührt und daraufhin Futter bekommt, wird dies wiederholt tun, wohingegen sie es vermeiden wird die Taste zu berühren, wenn sie daraufhin einen Stromschlag bekommt
-> Detektion von Beziehungen zwischen Verhalten und nachfolgendem Ereignis in der Umwelt
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). Diese akkumuliert sich über die Zeit. Ziel des Reinforcementlearnings ist es nun, durch Lernen solche Entscheidungsstrategien zu finden, so dass die akkumulierten Reinforcements optimal 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: lernen die Aktionen auszuführen, die zum größten Langzeit-Reward führen
-
- ... Langzeitreward
- ... Discountfaktor [0,1] ... schwächt den den Einfluss ferner Rewards ab
- ... 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
- suchen nur eine lokal optimale Policy
- 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 eines RL-Agenten
Policy
- Entscheidungsfunktion die 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 Agenten alleine
- Alle anderen Komponenten existieren nur damit die Policy verbessert und angepasst werden kann
Reinforcement 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
- Das Reward sagt dem Agenten WAS erreicht werden soll, aber nicht WIE
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 die angibt welchen Reward man erhalten würde wenn man sich im Zustand S befindet die Aktion a ausführt und dann der Policy folgt
- Reinforcements bestimmen wie erwünscht der aktuelle Zustand ist
- sie werden direkt aus der Umgebung bezogen
- Values hingegen geben die Langzeit-Erwünschtheit an, nachdem die, am wahrscheinlichsten erreichten, Zustände mit ihren jeweiligen Reinforcements errechnet wurden
- sie sind nur Schätzungen aus der Beobachtungsfolge, welche ein Agent über die gesamte Zeit macht
- 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 Value-Funktion durch Lernen effizient zu approximieren
Umgebungsmodell
- immitiert das Verhalten der Umgebung
- 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
- Umgebung gibt die möglichen Aktionen mit vor
State (Zustand)
- Alle notwendigen Parameter der Umgebung, die die Entscheidung beeinflussen 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, so dass der aktuelle Zustand nicht immer eindeutig beschrieben werden kann
- z.B. navigation mit IR oder Ultraschall Sensoren
Optimale Policies finden
Policy Iteration
- hier wird die optimale Policy gesucht, indem verschiedene Strategien direkt miteinander verglichen und bewertet werden
Value/Action-Value Iteration
- indirekte Suche nach der besten Policy durch die Value-Funktion
- dazu wird für jeden Zustand (oder jedes Zustands-Aktions-Paar) die Value-Funktion berechnet und das Maximum als beste Policy festgelegt
- bei komplexen Umgebungen führt dies aber schnell zu einem sehr großen Rechenaufwand und Speicherbedarf
Value/Action-Value Iteration
Das Bellman'sche Optimalitätsprinzip
- Der Teilplan eines optimalen Plans ist ebenfalls optimal!
- Eine optimale Policy hat die Eigenschaft, dass für einen beliebigen Zustand und beliebige Aktionen, alle nachfolgenden Entscheidungen wieder eine optimale Policy generieren -> Gebirgswanderung
Die Bellman'sche Gleichung
- Values sind Funktionen des Zustandes oder der Zustands-Aktions-Paare und schätzen wie gut es für einen Agenten ist, sich in diesem Zustand zu befinden oder diese Zustands-Aktions-Auswahl zu treffen (unter Berücksichtigung einer speziellen Policy)
Optimale Value-Funktionen
- Optimale Policies haben alle eine optimale Zustands-Value-Funktion bzw. Zustands-Aktions-Value-Funktion gemeinsam
- Idee (1): Der Zustands-Value, unter Berücksichtigung einer optimalen Policy, muss dem Erwartungswert für die beste Aktion ausgehend von diesem Zustand, unter Berücksichtigung der optimalen Policy, sein
- Idee (2): Der Aktions-Value eines Zustands-Aktions-Paares, unter Berücksichtigung einer optimalen Policy, muss dem Erwartungswert der besten Aktion des darauffolgenden Zustandes, unter Berücksichtigung der optimalen Policy, sein
- dies bildet die Vorraussetzung für Q-Learning
- Fazit: Wählt man immer die Aktion mit dem größten Aktions-Value, so sollte sich auch der long term Reward maximieren
Q-Learning
- Idee: Bellman'sche Gleichung in eine Updateregel umwandeln, indem zwei aufeinanderfolgende Zeitschritte betrachtet werden
- Policy Bewertung: Value-Funktion lernen
- Policy Verbesserung: Maximum-Suche bezüglich der gelernten Value-Funktion
- erneute Wiederholung führt zur optimalen Value-Funktion
Q-Learning-Algorithmus:
- 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:
- (s' zu neuem aktuellen Zustand machen)
- bis die Zustände erschöpfend durchsucht wurden, d.h. bis gegen konvergiert
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 Zustandes. Der Faktor 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 annimmt.
Exploration/Exploitation revisited
Wie schon mal angesprochen sollte man nicht immer nur exploren aber auch nicht nur exploiten
Zwei Verfahren besprochen, das Dilemma "schön" zu lösen:
Epsilon-Greedy:
- mit Wahrscheinlichkeit 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
- für ist die Auswahl unabhängig vom Q-Wert ( mit M - Anzahl der möglichen Aktionen)
- entspricht einem ausgeprägten Entdeckungsverhalten
- für werden Aktionen mit hohem Q-Wert ausgewählt und Aktionen mit kleinem Q-Wert vernachlässigt
- keinerlei Entdeckungsverhalten
- Mittelweg:
- es werden gelegentlich Aktionen ausgeführt, die nicht der Policy entsprechen
SARSA-Learning
- ähnlich dem Q-Learning
- Unterschied: nehme den Q-Wert des Weges den ich gegangen bin (Q-Learning nimmt den maximalen Q-Wert zum lernen)
- State -> Action -> Reinforcement -> State -> Action
- Die Update Regel der Q Werte lautet:
- mit einer Greedy-Policy konvergiert dieses Verfahren gegen das Q-Learning
On-Policy und Off-Policy
On-Policy:
- Policy, welche die Aktionsauswahl steuert, ist identisch mit der Policy, mit der gelernt werden soll
- typischer Vertreter: SARSA-Learning
Off-Policy:
- Policy, welche die Aktionsauswahl steuert, muss nicht identisch mit der Policy sein, mit der gelernt werden soll
- typischer Vertreter: Q-Learning (z.B. Stochastische Policy für Aktionsauswahl, Greedy-Policy zum Lernen)
- Vorteil: Lern-Policy kann "gierig" sein, wärend die Policy für die Aktionsauswahl die Möglichkeit hat, alle möglichen Aktionen auszuprobieren
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 alle durchlaufenen Zustände und Aktionen aktualisiert werden
- Die Updateregeln ändern sich zu:
Realisierungen des Traces
- erfordert geeignete Markierung aller durchlaufenen V- und Q-Values
Accumulating Trace:
- berücksichtigt Häufigkeit und Aktualität des Zustandes bzw. Zustands-Aktions-Paars
- Diese Version kann instabil werden da Werte >1 möglich sind
Replacing Trace:
- berücksichtigt nur Aktualität des Zustandes bzw. Zustands-Aktions-Paars (wird dadurch schneller und robuster)
Einfluss von :
- → TD(0): Alle Traces sind deaktiviert -> Normales TD Lernen
- : Normale abklingende Traces
- : Abklingen des Traces wird nur noch durch hervorgerufen
Besonderheiten:
- Bei der Ausführung von Off-Policy Aktionen muss der Trace deaktiviert werden, da der Zustand durch Befolgen einer anderen Policy erreicht wurde
Typische Probleme beim RL
POMDPs
- Partially Observable Markov Decision Process
- wird benötigt wenn Umgebung nur teilweise beobachtbar ist
- Lösungsansätze:
- Ignorieren und hoffen
- Hinzunahme von weiteren Beobachtungen (Geschwindigkeit, Beschleunigung)
- Benutzung impliziter interner Zeitinformationen (durch Traces)
- Hinzunahme fester/variabler Zeitfenster (zur Bewahrung der Sensorinformationen)
- Karte bauen (sollte aber eigentlich vermieden werden)
Komplexitätsproblem
- Lange Traninigszeiten der Agenten, selbst bei einfachen Aufgaben
- Ursache: Komplexität des Algo's
- hängt exponentiell von der Größe des Eingangsraumes und der Anzahl der auszuführenden Aktionen entsprechend der optimalen Policy ab
- Komplexität wird maximal bei delayed RL (Reinforcement erst nach Erreichen des Ziels) oder tabula rasa RL (Values mit 0 initialisiert)
- Lösungsansätze:
- Agent erhält für jede Aktion ein Reinforcement
- Value-Funktionen optimischtisch realisieren (etwas über dem maximal möglichen Return)
- angemessene Explorationsstrategien
- Änderung der Value-Funktion nach jeder Aktion (nicht erst nach Erreichen des Ziels)
- Eingangsraum zunächst eng um Zielzustand begrenzen und dann immer mehr erweitern
- Anlernen durch externen Experten (Experte agiert zunächst als Policy)
Neuronale Umsetzung von RL-Agenten
- State- und Action- Space ist immer reichlich groß -> effizienter die Funktion mittels neuronaler Verfahren zu approximieren
- Mapping vom State auf eine Action wird gelernt
- Zwei prinzipielle Ansätze:
- Partitionierung des Eingangsraumes mittels Vektorquanitsierern (self organizing feature maps, (growing) neural gas), dann wird mittels Q-Tabular - Learning weitergearbeitet
- Auch benachbarte Neuronen können mitlernen (hat Vor- und Nachteile!)
- alleiniger Einsatz von Funktionsapproximatoren (Multilayerperceptrons, Radiale Basisfunktionsnetze, Regressionsnetze...)
prinzipieller Aufbau
State Map
- empfängt Sensorwerte aus dem kontinuierlichen Input Space (IS) und wandelt sie mittels Vektorquanitisierer in einen diskreten State Space um. Jede Parzelle repräsentiert dann einen State, oder eine Stategruppierung.
Motor Map
- kodiert alle möglichen Aktionen des aktuell möglichen State in Form von einfachen Elementaraktionen (z.B. geradeausfahren, rechtsrum...)
- Hier sollte dann theoretisch auch irgendwie ein neuronaler Funktionsapproximator seine Arbeit verrichten. Dazu steht aber im Script nix gescheites.
- Eine Möglichkeit wäre, dass er das Mapping von den Partitionen der State Map auf eine Aktion der Motor Map macht.
- Dann gäbe es aber nur eine Motormap, in der ALLE überhaupt möglichen Aktionen stehen
- Eine andere Möglichkeit, welche so auch im Script angedeutet ist, ist, dass es pro Parzelle der State Map einen Funktionsapproximator gibt, welcher dann... ich hab keine Ahnung was macht - zumal im Abschnitt Q-Learning Algorithm auch kein NN vorkommt
Neuronale Value Approximation am Beispiel TD-Gammons
- nutzt TD-Lernen, daher der Name
- MLP oder RBF-Netz, mit einer oder mehreren Hidden-Schichten
- Input: speziell kodierte Brettsituation
- Output: erwarteter Value für jede angelegte Brettsituation
- Vorgehen:
- Vor dem Spiel: Netz lernt den Wert einer jeden Situation
- Während des Spiels: Netz bekommt alle möglichen Züge mittels Zuggenerator präsentiert und gibt geschätzten Wert dieser Züge zurück -> bester Zug ausgewählt
- Nach dem Spiel: Flasche Sekt aus dem Kühlschrank holen und sich ob seines Sieges freuen
Inputcodierung
- 198 Neuronen:
- 192 Neuronen für die Brettkonfiguration
- 24 Punkte * 2 Farben * 4 Neuronen für die Anzahl an Steinen auf dem Punkt
- Anzahl aktivierter Neuronen pro Punkt entspricht bis 3 der Anzahl an Steinen auf diesem Punkt - 4 aktivierte Neuronen heißt 4 oder mehr Steine auf diesem Punkt
- 2 Neuronen für die Barkonfiguration - Aktivierung von 1/2 je Stein und Farbe
- 2 Neuronen für die im Aus befindlichen Steine - Aktivierung von 1/15 je Stein und Farbe
- 2 Neuronen für aktiven Spieler
- 192 Neuronen für die Brettkonfiguration
Outputcodierung
- ursprünglich 1 Neuron -> Siegwahrscheinlichkeit/Value/Bewertung der Brettsituation
- später 4 Neuronen
- 1 Neuron für einfachen Sieg
- 1 Neuron für zweifachen Sieg
- 1 Neuron für weiß gewinnt
- 1 Neuron für schwarz gewinnt
- später 4 Neuronen
Aktivitätsausbreitung und Lernen
- Outputaktivität der Hidden-Neuronen:
- TD-Lernalgorithmus:
- Update der eligibility-Traces:
wobei ... Beitrag des Gewichtes w zu V
- gelernt wird alternierend beidseitig (das Netz spielt gegen sich selbst abwechselnd als schwarzer und weißer Spieler)
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
Multiagenten Systeme
Wesentliche Arten von Agenten
- Reaktiv
- feste Abbildung von Sensoren auf Aktoren
- Operand
- Verfügen über innere Zustände und können Wissen über folgen speichern
- Planend / deliberativ
- verfügen über Umweldmodell und wägen Folgen ihrer Handlung ab
- Hybride
- Kombinieren Reaktives und deliberatives Verhalten
- Kognitive
- Verfügen über komplexe Situationsbeschreibungen und können somit zwischen verschiedenen Zielen abwägen
Arten von Multi-Agenten Systemen
- Koordinierung mehrerer physischer Agenten (Rudel/Schwärme)
- Koordinierung mehrerer Agenten in einem Körper
MAS vs. Monolith
- MAS
- Vorteile:
- bessere Teilperformanze, skalierbar, Beherrschbar
- einfache Agenten
- einfache Erweiterbarkeit
- Nachteile
- Festlegung der Agenten
- geeignete Zerlegung des Problems muss gefunden werden
- geeignete Koordination der Agenten
- Reward-Dekomposition notwendig
- Vorteile:
- Monolith
- Vorteile:
- optimale Performanze
- notwendige Abbildung zwischen Sensoren und Aktoren wird selbst gefunden
- Teilaspekte und Koordinierung können durch Designer gewichtet werden
- Nachteile:
- kompliziertes Design und verteilen des Rewards
- kombinatorische Explosion des Zustandsraumes
- schlechte Erweiterbarkeit
- Vorteile:
"Mr. Smith, wo sind sie?" oder auch "Koordinierung der Agenten"
- Grundarten:
- Wettbewerb
- Kooperation
- Kombination von Kooperatiuon und Wettbewerb
Zentrale Kontrollstrategie
- Agenten haben kein Wissen über die Ziele der anderen Agenten
- nur eine Zentrale Struktur besitzt Wissen ober die Agenten (a.k.a. "M")
- Agenten liefern Aktionsvorschläge
- Zentrale Struktur realisiert die Auswahl der resultierenden Aktionen
Verteilte Kontrollstrategie
- Agenten haben Wissen über gegenseitige Existenz
- Agenten verhandeln über resultierende Aktion
- Koordination mittels Blackboard
- Agenten schreiben ihre Vorschläge auf das Blackboard
- Agenten können die Vorschläge der anderen Agenten einsehen und ihre Anpassen
- Selektion der auszuführenden Aktion erfolgt am Blackboard
Hierachische organisierte Agenten
- Subsumption Architektur
- strenge Hierachie vom Designer festgelegt
- Jeder Agent entscheidet anhand der aktuellen Situation, ob sein Aktionsvorschlag auszuführen ist
- indirekte Kommunikation zwischen den Agenten durch das Regelsystem
- starre Verhaltensgenerierung entsprechend dem Regelsystem
- Neudesign erforderlich wenn neue Agenten eingefügt werden sollen
Gleichberechtigte Agenten
- strenge lokale Kooperation zwischen den Agenten
- Überlagerung aller Aktionsvorschläge zu einer resultierenden Aktion
Adaptive Aktionsauswahl mittels W-Lernen
--> Siehe nächstes Kapitel
W-Lernen
- Wertesystem welches die zu erwartende Gesamt-Belohnung bzw -Verlust bei der Aktionsauswahl berücksichtigt
- Damit kann ein Agent einen kleinen Verlust tolerieren während er damit einen großen Verlust für das gesamte System verhindert
- Die Q-Werte werden genutzt um die W-Werte zu ermitteln
- Agenten sind selbständig
- es können Aktionen ausgewählt werden die kein Agent vorgeschlagen hat
- leicht um weitere Agenten erweiterbar
- höhere Robustheit gegenüber dem Ausfall von Angenten
- Je nach Policy erfolgt die Auswahl des gewinnenden Agenten, bzw. Aktionen anhand der W-Werte
- Praktisch immer Auswahl des maximalen W-Wert
- Ermittlung der W-Werte
- gleiche Aktionsräume => Berechnung der Werte aus den Q-Werten => statische W-Werte
- unterschiedliche Aktionsräume => RL-ähnlicher Lernprozess => dynamsiche W-Werte
statische W-Werte
- alle notwendigen Werte sind schon bekannt (da aus Q-Werte berechnet wird)
- kein Zeitaufwendiges Lernen notwendig
- leichte Auswertung
- Vier grundsätzliche realiserbare Auswahlstrategien
- Maximize best Happiness
- egositisches Konzept
- egositisches Konzept
- Maximize collective Happiness
- Suche nach dem größten Gesamtgewinn aller Agenten bei Auswahl einer bestimmten Aktion
- Suche nach dem größten Gesamtgewinn aller Agenten bei Auswahl einer bestimmten Aktion
- Maximize best Profit
- Suche nach dem größten Profit (maximaler Gewinn bei kleinstem Verlust)
- Minimize worst Unhappiness
- Suche nach dem größten Verlust um ihn zu Vermeiden
- Idee ist die Auswahl des Agenten, der durch seine Nichtausführung den größten Verlust einfahren würde (bzw. Gewinn entgeht)
- Maximize best Happiness
dynamische W-Werte
- Agent lernt die Folgen der Aktionsausführung eines anderen Experten
- Agent beobachtet, in welchen Folgezustand die Aktion eines anderen Agenten ihn gebracht hat un ermittelt den ihm dadurch entstandenen Verlust gegenüber seiner Aktion
- W-Werte werden aus realerzielten Rewards gelernt
- Lernen erfolgt nur für die Verlierer des Wettkampfs
- W-Lernen wählt damit den Agenten aus der den kleinsten Verlust für die anderen Agenten verursacht
- Vorteil:
- anwendbar auf beliebige Agenten mit unterschiedlichen Aktionsräumen
- beliebige Agentenanzahl
- Nachteil:
- iteratives Lernen der W-Werte bedingt wiederholtes Erleben von Aktionen