Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

Autor Begriff Zusammenfassung/Zitate Quellen

KI-Forschung über Bestärkendes Lernen - Lexikon der Argumente

Norvig I 831
Bestärkendes Lernen/KI-Forschung/Norvig/Russell: In vielen komplexen Bereichen ist bestärkendes Lernen [durch Belohnung und Bestrafung] der einzig praktikable Weg, um ein Programm so auszubilden, dass es Leistungen auf hohem Niveau erbringt. Es ist z.B. für einen Menschen beim Spielen sehr schwer, genaue und konsistente Bewertungen einer großen Anzahl von Positionen zu liefern, was erforderlich wäre, um eine Bewertungsfunktion direkt anhand von Beispielen zu trainieren. Stattdessen kann dem Programm mitgeteilt werden, wann es gewonnen oder verloren hat. Dann kann es diese Information nutzen, um eine Bewertungsfunktion zu erlernen, die einigermaßen genaue Schätzungen der Gewinnwahrscheinlichkeit für eine bestimmte Stellung liefert. In ähnlicher Weise ist es äußerst schwierig, einen Software-Agenten so zu programmieren, dass er einen Hubschrauber fliegt; doch wenn man ihm angemessene negative Belohnungen für einen Absturz, ein Wackeln oder ein Abweichen von einem festgelegten Kurs gibt, kann ein Software-Agent lernen, selbst zu fliegen.
A. Passives bestärkendes Lernen
Situation: Ein Software-Agent befindet sich in einer Umgebung und muss lernen, sich dort erfolgreich zu verhalten.
Ein auf Nutzen basierender Software-Agent lernt eine Nutzenfunktion über Zustände und verwendet sie, um Aktionen auszuwählen, die den erwarteten Ergebnisnutzen maximieren.
Ein Q-lernender Software-Agent lernt eine Aktions-Nutzen-Funktion oder Q-Funktion, die den erwarteten Nutzen einer bestimmten Aktion in einem bestimmten Zustand angibt.
Ein Reflex-Software-Agent lernt eine Richtlinie (engl. Policy), die direkt von Zuständen auf Aktionen abbildet.
Erkundung: Ein Software-Agent muss so viel wie möglich von seiner Umgebung erfahren, um zu lernen, wie er sich in ihr verhalten soll. >Markov-Entscheidungsprozesse/Norvig.
Norvig I 833
Passives bestärkendes Lernen: Eine einfache Methode zur direkten Einschätzung des Nutzens wurde Ende der 1950er Jahre auf dem Gebiet der adaptiven Kontrolltheorie von Widrow und Hoff (1960)(1) erfunden. Die Idee ist, dass der Nutzen eines Zustands die erwartete Gesamtbelohnung von diesem Zustand ist (genannt die erwartete Belohnung "to-go"). Jeder Versuch liefert eine Stichprobe dieser Menge für jeden besuchten Zustand.
Nützlichkeit: Die Nützlichkeit von Zuständen ist nicht unabhängig! Der Nutzen jedes Zustands ist gleich seiner eigenen Belohnung plus dem erwarteten Nutzen seiner Nachfolgezustände. Das heißt, die Nutzenwerte folgen den Bellman-Gleichungen für eine festgesetzte Richtlinie. (>Werte/KI-Forschung).
Problem: Durch das Ignorieren der Verbindungen zwischen Zuständen verpasst die direkte Einschätzung des Nutzens Gelegenheiten zum Lernen.
Norvig I 834
Adaptive Dynamische Programmierung/ADP: Ein Software-Agent für die adaptive dynamische Programmierung (oder ADP) macht sich die Beschränkungen zwischen den Nutzwerten der Zustände zunutze, indem er das Übergangsmodell lernt, das sie verbindet und den entsprechenden Markov-Entscheidungsprozess mithilfe einer dynamischen Programmierungsmethode löst. Alternativ können wir den Ansatz der modifizierten "Policy-Iteration" (...) verwenden, wobei wir einen vereinfachten Wertiterationsprozess verwenden, um die Einschätzung des Nutzens nach jeder Änderung des gelernten Modells zu aktualisieren.
Norvig I 836
Temporal Difference Learning/TD: Alle TD-Methoden funktionieren, indem die Einschätzungen des Nutzens in Richtung des idealen Gleichgewichts angepasst werden, das lokal gilt, wenn die Einschätzungen des Nutzens korrekt sind.
Norvig I 839
B. Aktives bestärkendes Lernen:
Ein passiv-lernender Software-Agent hat eine feste Richtlinie, die sein Verhalten bestimmt. Ein aktiver Software-Agent muss entscheiden, welche Maßnahmen zu ergreifen sind. Zunächst muss der Software-Agent ein vollständiges Modell mit Ergebniswahrscheinlichkeiten für alle Aktionen lernen, (...). Als Nächstes müssen wir die Tatsache berücksichtigen, dass der Software-Agent eine Auswahl an Aktionen hat. Die Nutzwerte, die er lernen muss, sind diejenigen, die durch die optimale Richtlinie definiert sind; sie folgen den >Bellman-Gleichungen (...) Die letzte Frage ist, was bei jedem Schritt zu tun ist. Nachdem der Software-Agent eine Nutzenfunktion U erhalten hat, die für das gelernte Modell optimal ist, kann der Software-Agent durch einen vorausschauenden Blick in einem Schritt eine optimale Aktion extrahieren, um den erwarteten Nutzen zu maximieren. Alternativ dazu kann er, wenn er die "Policy-Iteration" verwendet, bereits die optimale Richtlinie verwenden, so dass er einfach die Aktion ausführen sollte, die die optimale Richtlinie empfiehlt.
Norvig I 843
Q-Lernen: Es gibt eine alternative Methode des "Temporal Difference Learning" (TD-Lernen), genannt Q-Lernen, die anstelle von Lernnutzwerten eine Aktions-Nutzwert-Darstellung lernt. Ein TD-Software-Agent, der eine Q-Funktion lernt, benötigt kein Modell der Form P(s'| s, a), weder für das Lernen noch für die Aktionsauswahl. Aus diesem Grund wird Q-Lernen als eine modellfreie Methode bezeichnet.
Norvig I 845
Funktionsapproximation: bedeutet einfach die Verwendung einer beliebigen Darstellung für die Q-Funktion, die nicht einer Nachschlagetabelle entspricht. Die Darstellung wird als Näherung (=Approximation) angesehen, weil es nicht unbedingt der Fall sein muss, dass die wahre Nutzenfunktion oder Q-Funktion in der gewählten Form dargestellt werden kann.
Norvig I 846
Verallgemeinerung: Die durch einen Funktions-Approximator erreichte Kompression erlaubt es dem Lernenden, von Zuständen, die er erreicht hat, zu Zuständen, die er nicht erreicht hat, zu verallgemeinern. Das heißt, der wichtigste Aspekt der Funktionsapproximation ist nicht, dass sie weniger Platz benötigt, sondern dass sie eine induktive Verallgemeinerung über Eingabezustände ermöglicht.
Norvig I 848
Richtlinien (engl. policies): eine Richtlinie π ist eine Funktion, die Zustände auf Aktionen abbildet. (...) wir könnten π durch eine Sammlung von parametrisierten Q-Funktionen darstellen, eine für jede Aktion und die Aktion mit dem höchsten vorhergesagten Wert durchführen (...). Wenn die Richtlinie durch Q-Funktionen dargestellt wird, dann führt die Richtlinien-Suche zu einem Prozess, der Q-Funktionen lernt. Dieser Prozess ist nicht dasselbe wie Q-Lernen! Beim Q-Lernen mit Funktionsapproximation findet der Algorithmus einen Wert von θ, so dass ˆQ θ "nahe" an Q ∗, der optimalen Q-Funktion, liegt.
Richtlinien-Suche: Die Richtlinien-Suche hingegen findet einen Wert von θ, der zu einer guten Leistung führt (...).
VsRichtlinien-Suche: Probleme: Ein Problem bei der Darstellung von Richtlinien dieser Art (...) ist, dass die Richtlinie eine diskontinuierliche Funktion der Parameter ist, wenn die Aktionen diskret sind.
Lösung: Das bedeutet, dass sich der Wert der Richtlinie auch diskontinuierlich ändern kann, was die gradientenbasierte Suche erschwert. Aus diesem Grund verwenden Richtlinien-Suchmethoden oft eine stochastische Richtlinien-Repräsentation πθ(s, a), die die Wahrscheinlichkeit der Auswahl einer Aktion a im Zustand s angibt.
Norvig I 854
Geschichte des bestärkenden Lernens: Turing (1948(2), 1950(3)) schlug den Ansatz des bestärkenden Lernens vor, obwohl er von dessen Wirksamkeit nicht überzeugt war und schrieb: "Der Einsatz von Strafen und Belohnungen kann bestenfalls ein Teil des Lehrprozesses sein". Arthur Samuels Werk (1959)(4) war wahrscheinlich die früheste erfolgreiche Forschung zum maschinellen Lernen. Etwa zur gleichen Zeit trainierten Forscher in der Theorie der adaptiven Steuerung (Widrow und Hoff, 1960)(1), aufbauend auf Arbeiten von Hebb (1949)(5), einfache Netzwerke mit Hilfe der Delta-Regel. Die cart-pole-Arbeit ("cart-pole" dt. inverses Pendel) von Michie und Chambers (1968)(6) kann ebenfalls als eine Methode des bestärkenden Lernens mit einem Funktions-Approximator angesehen werden. Die psychologische Literatur zum bestärkenden Lernen ist viel älter; Hilgard und Bower (1975)(7) geben einen guten Überblick.
Neurowissenschaften: Der neurowissenschaftliche Text von Dayan und Abbott (2001)(8) beschreibt mögliche neuronale Implementierungen des Temporal Difference Learning, während Dayan und Niv (2008)(9) die neuesten Erkenntnisse aus neurowissenschaftlichen und verhaltenswissenschaftlichen Experimenten zusammenfassen.
Markov-Entscheidungsprozess: Die Verbindung zwischen bestärkendem Lernen und Markov-Entscheidungsprozessen wurde erstmals von Werbos (1977)(10) hergestellt, jedoch geht die Entwicklung des bestärkenden Lernens in der KI auf Arbeiten an der University of Massachusetts in den frühen 1980er Jahren zurück (Barto et al., 1981)(11). Die Arbeit von Sutton (1988) bietet einen guten historischen Überblick.
Temporal Difference Learning (TD Lernen): Die Kombination des TD-Lernens mit der modellbasierten Generierung von simulierten Erfahrungen wurde in Suttons DYNA-Architektur vorgeschlagen (Sutton, 1990)(12). Die Idee des priorisierten "Sweepings" wurde unabhängig davon von Moore und Atkeson (1993)(13) eingeführt sowie von
Norvig I 855
Peng und Williams (1993)(14).
Q-Lernen: wurde in Watkins' Doktorarbeit (1989)(15) entwickelt, während SARSA (state-action-reward-state-action) in einem technischen Bericht von Rummery und Niranjan (1994)(16) erschien.
Funktionsapproximation: Die Funktionsapproximation beim bestärkenden Lernen geht auf die Arbeit von Samuel zurück, der sowohl lineare als auch nichtlineare Bewertungsfunktionen verwendete und auch Methoden zur Merkmalsauswahl einsetzte, um den Merkmals-CMAC-Raum zu reduzieren. Zu den späteren Methoden gehören das CMAC (Cerebellar Model Articulation Controller) (Albus, 1975)(17), das im Wesentlichen eine Summe sich überlappender lokaler Kernfunktionen ist und die assoziativen neuronalen Netze von Barto et al. (1983)(18). Neuronale Netze sind derzeit die populärste Form der Funktionsapproximation. Die bekannteste Anwendung ist TD-Gammon (Tesauro, 1992(19), 1995(20)), (...).
Richtlinien-Suche: Methoden zur Richtlinien-Suche wurden von Williams (1992(21)) in den Vordergrund gerückt, der die Algorithmenfamilie REINFORCE entwickelte. Spätere Arbeiten von Marbach und Tsitsiklis (1998)(22), Sutton et al. (2000)(23) und Baxter und Bartlett (2000)(24) verstärkten und verallgemeinerten die Konvergenzergebnisse für die Richtlinien-Suche. Die Methode der korrelierten Probeentahme für den Vergleich verschiedener Konfigurationen eines Systems wurde formal von Kahn und Marshall (1953)(25) beschrieben, scheint aber schon lange vorher bekannt gewesen zu sein. Seine Verwendung beim bestärkenden Lernen geht auf Van Roy (1998)(26) und Ng und Jordan (2000)(27) zurück; letztere führten auch den PEGASUS-Algorithmus ein und bewiesen seine formalen Eigenschaften.
Norvig I 857
Umgekehrtes bestärkendes Lernen: Russell (1998)(28) beschreibt die Aufgabe des umgekehrten bestärkenden Lernens und fand heraus, was die Belohnungsfunktion von einem Beispielpfad durch diesen Zustandsraum sein muss. Dies ist nützlich als Teil des Lernens in der Lehre oder als Teil der wissenschaftlichen Arbeit - wir können ein Tier oder einen Roboter verstehen, indem wir rückwärts von dem, was das Tier oder der Roboter tut, zu dem hinarbeiten, was seine Belohnungsfunktion sein muss.



1. Widrow, B. and Hoff, M. E. (1960). Adaptive switching circuits. In 1960 IRE WESCON Convention
Record, pp. 96–104.
2. Turing, A. (1948). Intelligent machinery. Tech. rep. National Physical Laboratory. reprinted in (Ince,
1992).
3. Turing, A. (1950). Computing machinery and intelligence. Mind, 59, 433–460.
4. Samuel, A. L. (1959). Some studies in machine learning using the game of checkers. IBM Journal of Research and Development, 3(3), 210–229.
5. Hebb, D. O. (1949). The Organization of Behavior. Wiley.
6. Michie, D. and Chambers, R. A. (1968). BOXES: An experiment in adaptive control. In Dale, E. and
Michie, D. (Eds.), Machine Intelligence 2, pp. 125–133. Elsevier/North-Holland.
7. Hilgard, E. R. and Bower, G. H. (1975). Theories of Learning (4th edition). Prentice-Hall.
8. Dayan, P. and Abbott, L. F. (2001). Theoretical Neuroscience: Computational and Mathematical Modeling of Neural Systems. MIT Press.
9. Dayan, P. and Niv, Y. (2008). Reinforcement learning and the brain: The good, the bad and the ugly.
Current Opinion in Neurobiology, 18(2), 185–196.
10. Werbos, P. (1977). Advanced forecasting methods for global crisis warning and models of intelligence. General Systems Yearbook, 22, 25–38.
11. Barto, A. G., Sutton, R. S., and Brouwer, P. S. (1981). Associative search network: A reinforcement learning associative memory. Biological Cybernetics, 40(3), 201–211.
12. Sutton, R. S. (1990). Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In ICML-90, pp. 216–224.
13. Moore, A. W. and Atkeson, C. G. (1993). Prioritized sweeping—Reinforcement learning with less data and less time. Machine Learning, 13, 103–130.
14. Peng, J. and Williams, R. J. (1993). Efficient learning and planning within the Dyna framework. Adaptive Behavior, 2, 437–454.
15. Watkins, C. J. (1989). Models of Delayed Reinforcement Learning. Ph.D. thesis, Psychology Department, Cambridge University.
16. Rummery, G. A. and Niranjan, M. (1994). Online Q-learning using connectionist systems. Tech.
rep. CUED/F-INFENG/TR 166, Cambridge University Engineering Department.
17. Albus, J. S. (1975). A new approach to manipulator control: The cerebellar model articulation controller (CMAC). J. Dynamic Systems, Measurement, and Control, 97, 270–277.
18. Barto, A. G., Sutton, R. S., and Anderson, C. W. (1983). Neuron-like adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man and Cybernetics, 13, 834–
846.
19. Tesauro, G. (1992). Practical issues in temporal difference learning. Machine Learning, 8(3–4), 257–
277.
20. Tesauro, G. (1995). Temporal difference learning and TD-Gammon. CACM, 38(3), 58–68.
21. Williams, R. J. (1992). Simple statistical gradient following algorithms for connectionist reinforcement learning. Machine Learning, 8, 229–256.
22. Marbach, P. and Tsitsiklis, J. N. (1998). Simulation based optimization of Markov reward processes.
Technical report LIDS-P-2411, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology.
23. Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Solla, S. A., Leen, T. K., andM¨uller, K.-R. (Eds.),
NIPS 12, pp. 1057–1063. MIT Press.
24. Baxter, J. and Bartlett, P. (2000). Reinforcement learning in POMDP’s via direct gradient ascent. In
ICML-00, pp. 41–48.
25. Kahn, H. and Marshall, A. W. (1953). Methods of reducing sample size in Monte Carlo computations. Operations Research, 1(5), 263–278.
26. Van Roy, B. (1998). Learning and value function approximation in complex decision processes. Ph.D. thesis, Laboratory for Information and Decision Systems, MIT.
27. Ng, A. Y. and Jordan, M. I. (2000). PEGASUS: A policy search method for large MDPs and POMDPs.
In UAI-00, pp. 406–415.
28. Russell, S. J. (1998). Learning agents for uncertain environments (extended abstract). In COLT-98, pp. 101–103.


_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.
KI-Forschung

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z