close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Einführung Was ist Reinforcement Learning? Überwachtes - TAMS

EinbettenHerunterladen
Universität Hamburg
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Einführung
Was ist Reinforcement Learning?
Künstliche Intelligenz
• Lernen aus Interaktion
• Ziel-orientiertes Lernen
• Lernen durch, von, und während der Interaktion mit
einer externen Umgebung
• Lernen “was zu tun ist” — wie man Situationen auf
Aktionen abbildet — um ein numerisches RewardSignal zu maximieren
Steuerungs- und
Regelungstechnik
Psychologie
Maschinelles Lernen
Fachbereich Informatik
Reinforcement
Learning (RL)
Neurowissenschaft
Künstliche Neuronale Netze
181
AB TAMS
Tim Baier
tbaier@informatik.uni-hamburg.de
Technische Aspekte Multimodaler Systeme
Universität Hamburg
182
AB TAMS
Tim Baier
tbaier@informatik.uni-hamburg.de
Technische Aspekte Multimodaler Systeme
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Überwachtes Lernen
Reinforcement Learning
Trainings Info = gewünschte (Soll-) Ausgabe
Eingaben
Überwacht lernendes
System
Maschinelles Lernen
Fachbereich Informatik
Trainings Info = Bewertungen (“rewards” / “penalties”)
Ausgaben
Eingaben
183
Technische Aspekte Multimodaler Systeme
Ausgaben (“Aktionen”)
Ziel: erreiche soviel Reward wie möglich
Fehler = (Soll-Ausgabe – Systemausgabe)
AB TAMS
RL
System
Tim Baier
tbaier@informatik.uni-hamburg.de
184
AB TAMS
Technische Aspekte Multimodaler Systeme
Tim Baier
tbaier@informatik.uni-hamburg.de
1
Universität Hamburg
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Reinforcement Learning
•
•
Key Features von RL
Ziel: Möglichst „erfolgreich“ in der Umgebung agieren
Entspricht Maximierung der Belohnungssequenz Rt
• Lerner bekommt nicht gesagt welche Aktionen zu wählen
sind
• Trial-and-Error Suche
• Möglichkeit eines verspäteten (“delayed”) Reward
– Aufgeben von kurzfristigem Ertrag um höheren
langfristigen Ertrag zu erhalten
• Das Dilemma “exploration” vs. “exploitation”
• Betrachte das komplette Problem eines ziel-orientierten
Agenten in Interaktion mit einer unsicheren Umgebung
Agent
st
rt
Maschinelles Lernen
Fachbereich Informatik
at
Umgebung
185
AB TAMS
Tim Baier
tbaier@informatik.uni-hamburg.de
Technische Aspekte Multimodaler Systeme
Universität Hamburg
186
AB TAMS
Technische Aspekte Multimodaler Systeme
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Maschinelles Lernen
Fachbereich Informatik
Der vollständige Agent
•
•
•
•
Tim Baier
tbaier@informatik.uni-hamburg.de
Elemente des RL
Zeitlich situiert
Beständiges Lernen und Planen
Beeinflusst die Umgebung
Umgebung ist stochastisch und ungewiss
Policy
Reward
Value
Modell der
Umgebung
Umgebung
Zustand
Reward
•
•
•
•
Aktion
Policy: was ist zu tun
Reward: was ist gut
Value: was ist gut, da es Reward vorhersagt
Modell: was folgt auf was
Agent
187
AB TAMS
Technische Aspekte Multimodaler Systeme
Tim Baier
tbaier@informatik.uni-hamburg.de
188
AB TAMS
Technische Aspekte Multimodaler Systeme
Tim Baier
tbaier@informatik.uni-hamburg.de
2
Universität Hamburg
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Ein erweitertes Beispiel: Tic-Tac-Toe
X
X
O X
O X
X
X
X
O X
O
O X
O
X O X
X O X
O X
O X
X
O
O
Ein RL Ansatz für Tic-Tac-Toe
1. Erstelle eine Tabelle mit einem Eintrag pro Zustand:
Zustand
x
x
} x’s Zug
...
x
x
x
...
...
...
x
} o’s Zug
Setzt einen nicht perfekten Gegner
voraus:
— er/sie macht manchmal Fehler
Tim Baier
tbaier@informatik.uni-hamburg.de
Universität Hamburg
RL-Lernregel für Tic-Tac-Toe
Zug des Gegners
Unser Zug
unentschieden
*
Verschiedene mögliche
nächste Zustände
Nehme den nächsten Zustand mit der höchsten
geschätzten Gewinnwahrscheinlichkeit — das
höchste V(s); ein greedy Zug.
Aber in 10% aller Fälle wähle einen
zufälligen Zug; ein explorierender Zug.
AB TAMS
Technische Aspekte Multimodaler Systeme
190
Tim Baier
tbaier@informatik.uni-hamburg.de
a
{
{
{
{
{
{
b
Explorierender Zug
c* c
s – Zustand vor dem greedy Zug
s ′ – Zustand nach dem greedy Zug
d
e*
Wir inkrementieren jedes V(s) zu V( s ′) – ein „backup“
:
e
f
kleiner positiver Wert, z.B. α = 0.1
g* g
der „Schrittweitenparameter“
191
AB TAMS
Technische Aspekte Multimodaler Systeme
Fachbereich Informatik
Maschinelles Lernen
Verbesserung des T.T.T Spielers
Startposition
Unser Zug
0
Momentaner Zustand
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Zug des Gegners
o x o
o x x
x o o
Um einen Zug zu wählen,
schaue einen Schritt nach vorne:
verloren
189
Technische Aspekte Multimodaler Systeme
Unser Zug
0
gewonnen
} x’s Zug
x o
x
x o
AB TAMS
Zug des Gegners
x o
o
o
...
...
1
...
...
} x’s Zug
x x x
o
o
...
o x
x
...
} o’s Zug
...
o
V(s) – geschätzte Wahrscheinlichkeit für den Gewinn
.5
2. Jetzt spiele viele Spiele.
.5
...
...
x o
...
...
Maschinelles Lernen
Fachbereich Informatik
Tim Baier
tbaier@informatik.uni-hamburg.de
• Beachten von Symmetrien
– Darstellung/Generalisierung
– Wie kann dies fehlschlagen?
• Braucht man “Zufallszüge”? Warum?
– Braucht man immer die 10%?
• Kann man von “Zufallszügen” lernen?
• Kann man offline lernen?
– Vor-Lernen durch Spielen gegen sich selbst?
– Verwendung von gelernten Modellen des Gegners?
• ...
AB TAMS
Technische Aspekte Multimodaler Systeme
192
Tim Baier
tbaier@informatik.uni-hamburg.de
3
Universität Hamburg
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
z.B. Generalisierung
Tabelle
Zustand
Maschinelles Lernen
Fachbereich Informatik
Warum ist Tic-Tac-Toe einfach?
Generalisierender Funktionsapproximator
V
Zustand
• Endliche, kleine Anzahl an Zuständen
• Es ist immer möglich einen Schritt nach
vorne zu gucken (one-step look ahead)
• Zustände komplett wahrnehmbar
• ...
V
s1
s2
s3
.
.
.
Trainiere
hier
sN
AB TAMS
Technische Aspekte Multimodaler Systeme
193
Tim Baier
tbaier@informatik.uni-hamburg.de
Universität Hamburg
Fachbereich Informatik
194
AB TAMS
Tim Baier
tbaier@informatik.uni-hamburg.de
Technische Aspekte Multimodaler Systeme
Universität Hamburg
Maschinelles Lernen
Maschinelles Lernen
Fachbereich Informatik
Einige namhafte RL Anwendungen
TD-Gammon
Tesauro, 1992–1995
• TD-Gammon: Tesauro
• weltbestes Backgammon Programm
Value
• Aufzugssteuerung: Crites & Barto
Aktionsauswahl
durch 2–3 Lagensuche
TD Fehler
• High Performance “down-peak” Aufzugscontroller
Vt+1 −Vt
• Lagerverwaltung: Van Roy, Bertsekas, Lee & Tsitsiklis
• 10–15% Verbesserung gegenüber standard Industriemethoden
Starte mit zufälligem Netzwerk
Spiele sehr viele Spiele gegen dich selbst
• Dynamische Kanalzuordnung: Singh & Bertsekas, Nie &
Haykin
Lerne eine Wertefunktion anhand dieser simulierten Erfahrung
• High Performance Zuordnung von Funkkanälen zu
Mobiltelefonaten
Dies produziert wohl den besten Spieler der Welt
195
AB TAMS
Technische Aspekte Multimodaler Systeme
Tim Baier
tbaier@informatik.uni-hamburg.de
196
AB TAMS
Technische Aspekte Multimodaler Systeme
Tim Baier
tbaier@informatik.uni-hamburg.de
4
Universität Hamburg
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Maschinelles Lernen
Fachbereich Informatik
Aufzugseinteilung
Performance Vergleich
Crites and Barto, 1996
10 Stockwerke, 4 Kabinen
800
80
Zustände: Knopfzustände; Positionen,
Richtungen, und
Bewegungszustände der Kabinen;
Personen in Kabinen & in Etagen
60
Aktionen: halte an X, oder fahre nach
Y, nächste Etage
22
1
Durchschn.
quadrierte 400
Wartezeit
0
0
% Wartezeit
>1 Minute
0
Rewards: geschätzt, –1 pro Zeitschritt
für jede wartende Person
Vorsichtige Schätzung: ca. 10
600
2
Durchschn.
Warte- 40
und
System-20
zeiten
Lastenverteiler
200
Lastenverteiler
Lastenverteiler
Zustände
197
AB TAMS
198
AB TAMS
Tim Baier
tbaier@informatik.uni-hamburg.de
Technische Aspekte Multimodaler Systeme
Tim Baier
tbaier@informatik.uni-hamburg.de
Technische Aspekte Multimodaler Systeme
Universität Hamburg
Universität Hamburg
Maschinelles Lernen
Fachbereich Informatik
Maschinelles Lernen
Fachbereich Informatik
RL Geschichte
MENACE (Michie 1961)
Temporal-difference
learning
Optimal control,
value functions
“Matchbox Educable Noughts and Crosses Engine”
Secondary
reinforcement (Ψ
Ψ)
Hamilton (Physics)
1800s
Trial-and-Error
learning
Thorndike (Ψ
Ψ)
1911
Shannon
Samuel
Minsky
Bellman/Howard (OR)
Holland
Klopf
Witten
Barto et al.
Technische Aspekte Multimodaler Systeme
xox
x
o
x x
oo
ox
xo o
xx
o
x x
oox
xox
oox
x
x x
xo
o
x
ox
o
ox
xo
o
o
oxo
x
x
xo
xo
xo
o
oo x
ox
ox
ox
o
ox
oo
x
o
x
o
ox
o
xox
o
oox
oo x
x
ox
x
o
o
o
oxx
o
ox
o
o
x
ox
o
o
o
x
o
o
x
x
o
xo
o
oxo
o
o
x
o
o
ox
o
Werbos
Sutton
Watkins
AB TAMS
xo
xoo
x
199
Tim Baier
tbaier@informatik.uni-hamburg.de
200
AB TAMS
Technische Aspekte Multimodaler Systeme
Tim Baier
tbaier@informatik.uni-hamburg.de
5
Document
Kategorie
Internet
Seitenansichten
2
Dateigröße
142 KB
Tags
1/--Seiten
melden