Maschinellen Lernen kann man in drei Klassen unterteilen: überwachtes Lernen (supervised learning), unüberwachtes Lernen (unsupervised learning) und bestärkendes Lernen (reinforcement learning). Diese drei Lernarten decken unterschiedliche Fragestellungen ab, auch wenn es natürlich Überschneidungen gibt. In diesem Blogartikel geht es um das reinforcement learning, aber klären wir zuerst die anderen beiden Arten.

Supervised Learning: Die populärste ML-Klasse

Supervised Learning, auf Deutsch überwachtes Lernen, fasst die Algorithmen zu einer Klasse zusammen, welche anhand eines gelabelten Datensatzes lernen. D.h. es steht ein Datensatz inklusive Ergebnisse zum Lernen zur Verfügung.

Machine Learning Funktion, welche als Input ein Bild bekommt und als Output ausgibt, ob ein Hund auf dem Bild ist.

Will man zum Beispiel der Computer beibringen, zu erkennen, ob ein Hund auf einem Bild ist. Dann füttert man den Algorithmus mit vielen Bildern, auf denen mal ein Hund und mal kein Hund abgebildet ist. Zusätzlich bekommt der Algorithmus noch zu jedem Bild die Information, ob eben dort ein Hund abgebildet ist oder nicht.

Die meisten Algorithmen des maschinellen Lernens gehören zur Klasse des überwachten Lernens. Aber das Problem ist der benötigte Datensatz. Denn ML-Algorithmen, allen voran neuronale Netze, sind datenhungrig. Da sie so viele Parameter haben, die eingestellt werden müssen, brauchen sie eine enorm große Menge an Trainingsdaten. Nun muss man also einen großen Datensatz bereitstellen, der eben auch die gewünschten Ergebnisse enthält. Und das auch noch möglichst ohne Fehler, denn der Algorithmus ist immer nur so gut wie der zugrundeliegende Trainingsdatensatz.

Bei Hundebildern kann man vielleicht noch mit einigem Aufwand einen Datensatz mit 1 Millionen Bildern bereitstellen. Bei Röntgenaufnahmen inklusive korrekter Diagnose ist das deutlich aufwändiger. Solch einen Datensatz zur Verfügung zu haben, ist viel wert und meist entscheidend, ob ein ML-Algorithmus erfolgreich eingesetzt werden kann. Das wird in Zukunft ein interessanter Markt sein, in dem viel Geld steckt. Mittlerweile gibt es für viele Themen schon einige große, gelabelte Datensätze. Viele sogar kostenlos, da sie aus Forschungsprojekten entstanden sind.

Anhand des Trainingsdatensatzes dreht der Algorithmus an seinen Parametern, um eine Kostenfunktion zu minimieren. Solch eine Kostenfunktion kann in unserem Hundebild-Beispiel einfach die Anzahl falsch klassifizierter Bilder sein.

Aber gibt es nicht auch Algorithmen, die die Labels nicht benötigen? Kommen wir zur Klasse des unüberwachten Lernens.

Unsupervised Learning: Datenstrukturen erkennen

Viele Unternehmen sammeln schon seit einiger Zeit jede Menge Daten, sei es über Produktionsabläufe oder Kundenverhalten. Wäre es nicht cool, diese einfach fürs maschinelle Lernen zu verwenden? Und zwar ohne umfangreiches händisches Labeln? Hier schlägt die Stunde der unsupervised learning Algorithmen. Denn diese benötigen zwar einen Datensatz, erkennen aber selbstständig Muster und Strukturen in den Daten.

Ein typisches Beispiel ist die Ausreißer-Erkennung (anomaly detection), die unter anderem bei der Betrugserkennung in Banken eingesetzt wird. Hierbei braucht der Algorithmus nicht unbedingt die zusätzliche Information, ob es sich um einen Betrug handelt oder nicht. In den Daten steckt, ob eine Transaktion aus dem Rahmen fällt und dementsprechend als auffällig markiert werden sollte.

Weitere wichtige Anwendungsgebiete von unüberwachtem Lernen sind die Gruppierung von Kunden oder Objekten (Clustering) sowie das Feature Engineering.

Reinforcement Learning: Aktion und Belohnung

Reinforcement Learning, auf Deutsch bestärkendes Lernen, funktioniert etwas anders als die beiden anderen Maschine Learning Algorithmen-Klassen. Denn es wird nicht aus einem Datensatz gelernt, sondern durch Aktionen in einer Umgebung und darauffolgende Belohnungen oder Bestrafungen.

Bestärkendes Lernen erscheint als eine sehr natürliche Art des Lernens. Denn Kinder lernen auf diese Weise: sie machen etwas und erfahren daraufhin ein Feedback, zum Beispiel dass ihr Lachen beim Gegenüber ebenfalls ein Lachen hervorzaubert.

Reinforcement Learning kann also immer dann zum Einsatz kommen, wenn ein Algorithmus/Agent in einer Umgebung (engl. Environment) handeln kann und diese Handlungen direkt oder auch später bewertet werden können. Je später das Feedback kommt, desto schwieriger ist es natürlich für den Agenten.

Machen wir ein einfaches Beispiel und stellen uns eine selbstlernende Schiebetür vor. Diese soll sich öffnen, wenn Menschen sich nähern und schließen, wenn keine Menschen in der Nähe sind. Die Tür hat vier Zustände: geschlossen, geöffnet, wird geschlossen, wird geöffnet. Zudem ist sie mit einem Sensor ausgestattet, der jede Sekunde überprüft, ob sich Menschen in einem 2m-Bereich vor oder hinter der Tür befinden. Daraus ergeben sich also insgesamt 8 Zustände:

Im Endeffekt ist hier ein ML-Algorithmus natürlich völlig übertrieben, denn die optimale Handlung kann man mit einfachen Wenn-Dann-Regeln programmieren, aber es geht ja ums Veranschaulichen. Das Belohnungssystem ist dementsprechend auch so ausgelegt, dass die richtige Handlung 100 Punkte bringt und die falschen Handlungen 0 Punkte. Der Algorithmus kann in diesem Fall einfach alle Handlungsmöglichkeiten durchprobieren und hat so nach einigen Versuchen die gewünschte Handlung gelernt.

AlphaGo Zero: Das Paradebeispiel für bestärkendes Lernen

In der Realität kommt Reinforcement Learning für deutlich komplexere Problemstellungen als die obige Schiebetür zum Einsatz. Gerade bei Brett- oder Computerspielen, welche klare Regeln haben, funktioniert Reinforcement Learning besonders gut und konnte beachtliche Erfolge erzielen.

Paradebeispiel ist Googles/DeepMinds AlphaGo Zero, ein Go-Programm, welches der Nachfolger von AlphaGo ist und diesen vernichtend schlagen konnte. AlphaGo war das erste Computerprogramm, welches 2016 den Go-Großmeister Lee Sedol, der als einer der stärksten menschliche Spieler galt, 4-1 besiegen konnte. Das war eine Sensation, denn Go hat durch das 19×19 große Spielfeld viel mehr (Faktor 10100) mögliche Spielzüge. Dadurch fällt das Durchprobieren aller möglichen Züge (Brute-Force) aus. Zudem gibt es keine gute Heuristik, um eine Stellung zu bewerten.

Während AlphaGo zwar auch schon Neuronale Netze einsetzte, ist die Besonderheit bei AlphaGo Zero, dass letzteres nur die Spielregeln einprogrammiert bekommen hat und Go nur durch das Spielen gegen sich selbst zur Meisterschaft gebracht hat. Nach 3 Tagen Lernen konnte AlphaGo Zero dann die Version von AlphaGo schlagen, die Lee besiegt hatte. Nach 40 Tagen schlug AlphaGo Zero auch die zu der Zeit beste Version von AlphaGo namens AlphaGo Master. Wobei Tage hier eigentlich nichts aussagen, denn es geht ja um die Rechenleistung, die verbraten wurde. Und davon hat Google ja fast unbegrenzt zur Verfügung.

Lernen im Simulator

Reinforcement Learning funktioniert durch Agieren in einer Umgebung. Das geht bei Spielen wie Go, aber nicht in der Wirklichkeit. Man kann nicht einfach ein Auto mit initialen zufälligen Aktionen in den Straßenverkehr stellen und tausende Handlungen abwarten, dass es sich mal etwas vernünftiger verhält und nicht gegen das nächste Auto fährt. Oder einen teuren Roboter in eine Fertigungsstraße einbauen und sehr lange nur Ausschuss produzieren.

Daher wird zuerst in einer Simulation gelernt, in der nichts kaputt gehen kann. Das hat neben den geringeren Kosten und Risiken auch den entscheidenden Vorteil, dass das Lernen in Zeitraffer ablaufen kann und die Geschwindigkeit eigentlich nur von der Rechenpower beschränkt ist. Denn wenn wir neuronale Netze einsetzen, müssen tausende oder Millionen Parameter optimiert werden und das braucht normalerweise einen riesigen Datensatz bzw. im bestärkenden Lernen sehr viele Durchgänge.

Ist in der Simulation das Lernen ausgereizt, kann dieses Wissen genommen werden und in einen realen Roboter übertragen werden und dann in der Realität weiter verbessert werden. Dieses Vorgehen nennt man Transfer Learning, wobei der Begriff Transfer Learning weiter gefasst ist.

Die bekannteste Trainingshalle für künstliche Intelligenz mit anschaulichen Videoclips findet man bei OpenAI, die OpenAI Gym. Dafür gibt es auch zahlreiche Erweiterungen für andere Bereiche wie Recommendation Engines, Aktien-Trading, Kartenspiele und viele weitere.

Ein mathematisches Modell hinter Reinforcement Learning

Ein Basismodell hinter Reinforcement Learning ist das sogenannte Markov Entscheidungsproblem bzw. der Markov Entscheidungsprozess (engl. Markov decision process = MDP). Dieser besteht aus folgenden Zutaten:

  • Einer Menge von Zuständen S
  • Einer Menge von Aktionen A
  • Ein Aktionsmodell, welches eine Funktion T: S \times A \times S \rightarrow [0,1] ist. Diese ordnet jeder Kombination aus vorherigem Zustand, Aktion und Folgezustand eine Wahrscheinlichkeit zu.
  • Eine Belohnungsfunktion r: S \times A \times S \rightarrow \R, welche jeder Kombination aus letztem Zustand, Aktion und aktuellem Zustand einen Wert (reelle Zahl) zuweist.
  • Eine Startverteilung, wiederum als Funktion p_0: S \rightarrow [0,1]. Die Funktion bestimmt also die Wahrscheinlichkeit, in einem Zustand zu starten.

Eine Strategie (engl. policy) ist dann eine Funktion \pi: S \rightarrow A, die jedem Zustand eine Aktion zuweist. Man kann das auch nicht-deterministisch formulieren, d.h. der Agent entscheidet sich in einem Zustand für eine Aktion mit einer gewissen Wahrscheinlichkeit. Dann ist pi eine Funktion \pi: S \times A \rightarrow [0,1]. Als Lösung bzw. optimale Strategie wird eine Strategie bezeichnet, die die Summe der Belohnungen (engl. reward) maximiert. In der nicht-deterministischen Variante ist es der Erwartungswert der Summe der Belohnungen. Die Summe der Belohnungen kann man noch mit einem Diskontierungsfaktor (wie beim Zinseszins) versehen, um eine Gewichtung zwischen sofortiger und späterer Belohnung zu erreichen. Das ist zum Beispiel notwendig, wenn keine zeitliche Begrenzung vorliegt (denn dann könnte die Summe unendlich groß werden).

Dieses Modell kann man aber nicht für alle Problemstellungen verwenden, denn es hat die sogenannte Markov-Eigenschaft, dass es sich nicht erinnert. Der Zeitpunkt ist also egal, das Aktionsmodell und die Belohnungsfunktion hängen nur vom direkt vorherigen Zustand ab, nicht von dem vor zwei Zeiteinheiten oder dem bisherigen Verlauf.

Reinforcement Learning umgesetzt: Q-Learning

Der bekannteste Algorithmus des bestärkenden Lernens nennt sich Q-Learning. Man kann beweisen, dass Q-Learning für jeden endlichen Markov Entscheidungsprozess (also mit endlich vielen Zuständen und endlich vielen Handlungen) eine optimale Policy finden kann, sofern er unendlich viel Zeit dafür hätte. Aber auch in der Praxis funktioniert der Algorithmus meist ziemlich gut.

Es geht ja darum, eine Funktion Q: S \times A \rightarrow \R zu finden, die jede Zustand-Aktion-Kombination bewertet. Haben wir diese, dann kann sich der Algorithmus in einem Zustand einfach für die Aktion entscheiden, die die höchste Bewertung hat.

Das Ganze funktioniert iterativ, d.h. zuerst wird Q zufällig oder mittels Vorwissen initialisiert und anschließend in jedem Schritt optimiert. In dem Optimierungsschritt i wird ein neuer Wert Q_i(s_t, a_t) gebildet, der sich aus dem alten Wert Q_{i-1}(s_t, a_t) und geschätzten Gesamtbelohnung B zusammensetzt. Diese zwei werden mit der Lernrate \alpha gewichtet, also Q_i(s_t, a_t) = (1-\alpha) * Q_{i-1}(s_t, a_t) + \alpha * B. Die Lernrate bestimmt, wie wichtig neue Information ist. Bei \alpha = 0 lernt der Agent nichts, bei \alpha = 1 werden nur die neuesten Informationen berücksichtigt. \Alpha = 1 ist sinnvoll, wenn die Umgebung deterministisch ist, also kein Zufall bezüglich des nächsten Zustands im Spiel ist. In der Praxis wird also ein Wert zwischen 0 und 1 gewählt, der sich ggf. auch über die Zeit verändert.

Die Belohnung wiederum setzt sich aus der sofortigen Belohnung r(s_t, a_t) und der maximalen Belohnung in Zustand s_{t+1}, noch mit einem Diskontierungsfaktor gamma versehen, zusammen. Der Diskontierungsfaktor \gamma bestimmt, wie gierig der Agent ist. Ist die jetzige Belohnung (kleiner Faktor nahe 0) oder zukünftige Belohnungen (Faktor nahe 1) wichtiger? Häufig wird auch mit einem kleinen Diskontierungsfaktor angefangen, der dann im Laufe der Zeit erhöht wird.

Die komplette Formel lautet dann:

    \[Q_i(s_t, a_t) = (1-\alpha) * Q_{i-1}(s_t, a_t) + \alpha * \bigl( r(s_t, a_t) + \gamma \max_{a \in A} Q(s_{t+1}, a) \bigr)\]

 

Q-Learning und neuronale Netze

AlphaGo und all die anderen erfolgreichen Reinforcement Learning Programme basieren aber auf neuronalen Netzen. Wie kommen diese jetzt ins Spiel? Die Idee ist einfach, die Funktion Q durch ein neuronales Netz lernen zu lassen. Wir füttern es also mit dem aktuellen Zustand und ggf. weiteren Informationen der Umgebung und es spuckt die Aktion bzw. für jede Aktion eine Bewertung aus.

Das Problem mit dem ursprünglichen Algorithmus ist nämlich, dass er einfach zu viel Rechen- und Speicherkapazität benötigt, wenn die Zustandsmenge S und die Aktionsmenge A größer sind. Das neuronale Netz approximiert die Funktion Q.

Der erste bekannte Algorithmus dieser Art heißt DQN für Deep-Q-Network und wurde von DeepMind entwickelt, um dem Computer das Computer-Spielen (genauer gesagt Atari 2600). Das Original-Paper Playing Atari with Deep Reinforcement Learning von 2013 ist auf arXiv zu finden.

Mittlerweile gilt A3C (Asynchronous Advantage Actor Critic), ebenfalls aus der Schmiede von DeepMind, als überlegener Algorithmus, da er schneller und robuster ist. Dabei heißt asynchronous hier, dass mehrere Agenten parallel losgeschickt werden und so von den Erfahrungen der anderen profitieren können. Advantage meint, dass nicht die diskontierte Belohnung betrachtet wird, um Aktionen zu bewerten, sondern wieviel besser die Belohnung gegenüber der erwarteten Belohnung ist. Und schließlich bedeutet Actor Critic, dass sowohl die Policy als auch die Value Function, welche einen Zustand bewertet, benutzt werden. Auch darüber könnt ihr auf arXiv im Artikel Asynchronous Methods for Deep Reinforcement Learning von 2016 nachlesen.

Dieser Blogartikel kratzt natürlich nur an der Oberfläche der faszinierenden Machine Learning-Klasse Reinforcement Learning. Willst Du mehr darüber wissen, dann hinterlasse doch einen Kommentar oder schreib mir auf Twitter.

Seid bestärkt Freunde,

Euer Holger