10 Verstärkendes Lernen

Neben den Klassifizierungs- und Prognosealgorithmen ist in den letzten Jahren besonders im Zusammenhang mit Spielstrategien und Routenplanung das Verstärkende Lernen (engl. reinforcement learning) immer wichtiger geworden. Ein wichtiger Algorithmus des Verstärkenden Lernens ist das Q-Learning.

Was ist das?
Das Q-Learning ist mit einer Dressur vergleichbar, wobei erwünschte Aktionen mit einer Belohnung und unerwünschte Aktionen mit einer Bestrafung bedacht werden. Das gute und richtige Verhalten soll also durch Belohnung verstärkt, das schlechte und falsche Verhalten durch Bestrafung geschwächt werden. Das ist nicht wörtlich zu nehmen, da eine Maschine nicht betraft werden kann. Daher wird beim ML Belohnung/Bestrafung als Punkte sammeln realisiert. Ist eine Handlung zielführend, gibt es Pluspunkte, z.B. +1; verfehlt die Handlung das vorgegebene Ziel, dann gibt es einen Punktabzug, also etwa -1. Das klingt erst mal ziemlich simpel, ist aber ziemlich mächtig, da es beliebig komplexe Situationen in aufeinanderfolgenden Schritten abarbeiten kann. Das heißt, es gibt nicht nur eine Belohnung für die nächste Handlung wie bei einem Hund, der Männchen macht und ein Leckerli kriegt. Beim Q-Learning geht es darum, sehr viele aufeinanderfolgende Schritte, die zu einem Ziel führen, mathematisch zu beschreiben, sodass am Ende eine große Belohnung steht.

Beispiel: Karina hat sich den Roboterhund Roby gekauft, der ihr das Handy bringen soll, wenn sie es in einem Raum vergessen hat. Roby soll nicht lange in der Wohnung herumsuchen, sondern den kürzesten Weg zum Handy finden und dann Karina das Handy bringen. Karinas Wohnung hat folgenden Grundriss. 

Roby ist nicht gerade die schlaueste KI, man muss ihm den Grundriss der Wohnung und was er machen soll, schon sehr detailliert beibringen. Wenn er alles gespeichert hat, dann trainiert man ihn. Danach verfügt er über ein internes Modell der Wohnung und der Aktionen, die er durchführen soll. Der Roby ist wirklich etwas schwerfällig, man muss ihm separat beibringen, von welchem Zimmer aus er in welches andere Zimmer gelangen kann, wo das Handy liegt, was er machen darf und was nicht. Die wichtigste Grundlage des Verstärkenden Lernens ist, dass wir eine maschinenlesbare Version der Situation der Umgebung in Roby einspeisen. Maschinenlesbar heißt, alles darf nur auf Zahlen beruhen. Aber das ist gar nicht so schwer. Wir verwenden eine 5 x 5-Matrix, in die wir alles nötige Wissen für Roby hineinschreiben.

Die Matrix ist so eine Art innere Landkarte, die Roby zeigt, was er machen darf und was nicht. Man liest sie folgendermaßen: Die Reihen bedeuten den Raum, in dem Roby gerade ist, und die Spalten die Aktionen, also die Räume, in die er als Nächstes gehen kann. Am Anfang ist die Matrix leer. Roby ist ziemlich ahnungslos in Bezug auf seine Umgebung und weiß nicht, was er machen soll. Aber das werden wir ihm jetzt beibringen. Dabei gehen wir folgendermaßen vor: Ist der Roboter in einem Raum, wo kein Handy liegt, so soll er das Zimmer verlassen, denn er ist im falschen Zimmer. Um ihm das klarzumachen, kriegt er eine Strafe von -1 Punkt, damit er nicht auf die Idee kommt, dass er einfach faul herumstehen soll. Ist er im richtigen Zimmer, da wo das Handy liegt, dann gibt es zur Belohnung 1 Punkt (also +1). Nehmen wir mal an, das Handy liegt in Zimmer 4. Wo Roby ist, ist zunächst egal. Wenn wir jetzt die Matrix ausfüllen, realisieren wir das Prinzip von Belohnung und Strafe und tragen Folgendes ein:

Von Raum 0 soll er nicht in Raum 0 gehen, das wäre ja Unsinn, also kriegt er -1 Punkt für diese Idee. Das Gleiche gilt für die Räume 1, 2 und 3. Nur in Raum 4 gibt es einen fetten Bonus von 1 Punkt, denn er hat das Ziel erreicht.

So, Schritt 1 ist getan, denn fürs Abchillen hat Karina den teuren Roby nicht gekauft. Als Nächstes müssen wir Roby mitteilen, was er auf gar keinen Fall machen kann oder darf. Nämlich z.B. von Raum 1 durch die Wand brechen, um in Raum 2 zu kommen. -1 Punkt heißt also: „Don’t even try, stupid!“ Das gibt -1 Punkt in der Zeile Raum 1 für die Aktion „gehe in Raum 2“. Der einzige Raum, der von Raum 1 erreichbar ist, ist der Raum 0. Da dort nicht das Handy liegt, soll Roby weder belohnt noch bestraft werden, also kriegt er dafür 0 Punkte. 0 Punkte heißt: „Kann man machen.“ Alle anderen Räume sind von Raum 1 nicht direkt erreichbar, also gibt es dafür -1 Punkte, weil es Unsinn wäre, wenn Roby versuchen würde, direkt von Raum 1 in diese Räume zu gelangen.

Nach diesen Schritten sieht die Matrix schon etwas anders aus:

Ach, jetzt haben wir ja den Raum 0 fast vergessen, die Räume 1, 2 und 4 sind direkt von 0 erreichbar, der Raum 3 nicht. Also kriegt die Aktion „gehe in Raum 3“ für die Zeile von Raum 0 eine Strafe von -1 Punkt. Beim Übergang von Raum 0 zu den Räumen 1, 2 und 4 müssen wir aufpassen. Geht es von 0 in 1 und 2, erhält Roby 0 Punkte. Geht es von 0 nach 4, dann ist das ja genau richtig, denn in 4 liegt das Handy, also gibt es 1 Punkt Belohnung.

Nach diesen Schritten sieht die Matrix so aus:

Weiter geht es mit Raum 2 und 3. Von 2 kann ich nicht nach 1 und 3 gelangen (-1 Punkt), aber nach 0 (0 Punkte) und 4 (1 Punkt). Von 3 kann ich nur nach 4 gelangen, dafür gibt es auch 1 Punkt. Ansonsten komme ich von 3 nirgendwo hin, daher gibt es für alle anderen Versuche -1 Punkt. So, unsere Karte der Wohnung und die Lage des Handys sind für den Roboter nun verständlich in die Matrix eingetragen.

Nun weiß der Roboterhund, wie die Wohnungsstruktur ist und wie das Belohnungsschema funktioniert. Jetzt muss er noch lernen, dass man manchmal auch längere Wege gehen muss. Er muss lernen, nicht gleich aufzugeben, wenn es nicht sofort eine Belohnung gibt. Dafür verwendet man das sogenannte Q-Learning. In diesen Algorithmus speisen wir unsere Matrix ein und erhalten dann eine neue Matrix, die es Roby ermöglicht, auch längere Wege zu gehen, wenn am Ende eine Belohnung winkt.

Der Q-Learning-Algorithmus macht dabei Folgendes: Er lässt den Roboter per Zufall immer wieder durch die Wohnung laufen und rechnet dabei zusammen, welche Belohnung es am Ende gibt. Jede Situation ergibt sich dadurch aus dem Ergebnis aller vorherigen Aktionen. Wer sich für die Mathematik dahinter interessiert, kann unten in den Medienhinweisen nachsehen.

Wir erhalten durch das Q-Learning also eine neue Matrix, die Q-Matrix. Diese Matrix ist das perfekte Modell, das Roby genau sagt, wie er am besten in Zimmer 4 kommt, egal von welchem Raum aus er startet. Was auch nett ist – alle Bestrafungen sind abgeschafft, jetzt gibt es nur noch Belohnungen oder gar nichts. Roby wird immer das machen, was ihm die höchste Belohnung bringt.

Spielen wir das Ganze nun einmal durch. Nehmen wir an, Roby ist in Raum 0. Er sieht jetzt nur noch die Zeile für Raum 0. Da ist eine Null drin, da kriegt er nichts, geht er in Raum 1, gibt es 0,9025 Punkte, für Raum 2 gibt es 0,95 Punkte, aber für Raum 4 gibt es 1 vollen Punkt. Da ist klar, was er macht. Ab in Raum 4, und schon hat er das Ziel erreicht. Bingo!

Okay, das klingt jetzt nicht so richtig komplex für den Riesenaufwand mit der Matrix und dem Q-Learning-Algorithmus. Aber das Besondere an der Q-Matrix ist, dass dadurch mehrere Aktionen hintereinander ausgeführt werden können, und das ist genau das, was wir für die Navigation, ob drinnen oder draußen oder in einer Spielewelt, brauchen.

Schauen wir uns das noch einmal an einem letzten Beispiel an: Roby ist in Raum 1. Die einzige Belohnung, die er kriegen kann, ist 0,95 Punkte, wenn er in Raum 0 geht. Da er aber erst aufhört, wenn er die volle Belohnung von 1 Punkt bekommt, macht er nun weiter, indem er von Raum 0 in Raum 4 geht, denn dann gibt es die volle Punktzahl. Der Weg ist also: Raum 1 -> Raum 0 -> Raum 4, yeah!

Okay, auch das ist ja erst einmal nicht so richtig superschlau, aber es funktioniert. Der richtige Knüller am Q-Learning ist, dass das mit 5 Räumen, mit 50 Räumen oder auch mit 50.000 Räumen funktioniert. 50.000 Räume? Welches Haus hat 50.000 Räume? Das mit den Räumen ist nicht wörtlich zu nehmen, denn der Q-Learning-Algorithmus funktioniert auch draußen ;-).

 Anstelle von Räumen nehmen wir jetzt mal Adressen, und davon gibt es in vielen Städten mehr als 50.000. Der Roboter ist jetzt kein Handyholer, sondern ein Lieferroboter, der Waren ausliefern soll. Dabei soll er den kürzesten Weg zur Zieladresse finden. Wie in dem Zimmerbeispiel gibt es Straßen, durch die er fahren kann, und andere, die er nicht durchfahren darf, z.B. Fußgängerzonen oder Einbahnstraßen. Auch darf er an einigen Kreuzungen vielleicht nicht links oder rechts abbiegen. Genauso wie im Zimmerbeispiel wird man eine Matrix erstellen, die die Gesamtstruktur der Möglichkeiten abbildet. Dann lässt man den Q-Learning-Algorithmus darüber laufen und erhält eine Belohnungsmatrix, die der Roboter nur noch abarbeiten muss. Und schon kann er die Pizza warm anliefern :-).

Selbstcheck: Überlege noch einmal, wie wir vorgegangen sind. War das jetzt ein Beispiel für Supervised Learning oder Unsupervised Learning?

Antwort: Da wir dem Roboter alles haarklein vorgeben mussten, haben wir hier ein klares Beispiel von Supervised Learning. Es gibt aber auch die Möglichkeit, Verstärkendes Lernen unbeaufsichtigt (unsupervised) durchzuführen. Schau dir mal das folgende Beispiel an. Hier erkundet der Roboter in einer Trainingsphase mit einem Laser und einer Kamera selber den Grundriss der Wohnung und erstellt danach seine Navigationsmatrix.

 Video mit Verstärkendem Lernen ohne Supervisor (englisch):

Das ist ja nun mal wirklich clever: Erst wird das Terrain erkundet und die Matrix mit der Belohnung automatisch erstellt, sodann wird die Q-Matrix berechnet und dann die Aufgabe gelöst. So bringt sich der Roboter selber bei, das Optimale zu tun. Genauso würde das in einem Spiel funktionieren: Der Roboter geht alle Spielmöglichkeiten durch und erhält immer dann eine Belohnung, wenn er ein Spiel gewinnt.

Wirtschaft
Aus dem Beispiel mit dem Lieferroboter ergibt sich schon die wirtschaftliche Bedeutung des Verstärkenden Lernens. Überall da, wo in einer bestimmten Umgebung navigiert werden muss, kann diese Technik eingesetzt werden; bei der Optimierung von Lieferrobotern, in einem Warenlager oder in der Prozesssteuerung in einer Fabrik. Und natürlich in vielen Spielen. Vielleicht hast du dich schon mal gefragt, warum die automatischen Gegner in digitalen Spielen immer schlauer werden. Na? Höchstwahrscheinlich wurden sie mit Q-Learning trainiert, um in der Lage zu sein, komplexe Strategien gegen uns durchzuziehen.

Gesellschaft
Durch die Übertragung von strategischen Aufgaben an Roboter werden Arbeitsfelder erschlossen, die vorher nur Menschen besetzt haben. Es stellt sich die Frage: Wenn immer mehr komplexe Abläufe automatisiert werden, was passiert dann mit diesen Jobs? Wenn der Roboter besser planen kann als der Mensch, was heißt das für das Führungspersonal in einer Fabrik oder einem Warenlager? Und wenn diese Mechanismen immer mehr in Spielen eingesetzt werden und diese am Ende immer besser sind als der menschliche Spieler – warum sollte man dann überhaupt noch spielen?