Machine Learning – komplexe Probleme mithilfe von Q-Learning lösen

Wenn Informatikerinnen und Informatiker um Highscores in Videospielklassikern wie Space Invaders, Breakout oder Video Pinball wetteifern, kann das durchaus einen wissenschaftlichen Hintergrund haben. Auch wenn sie probieren, mit einem Roboterarm ein Kartenhaus zu bauen, steckt oft mehr dahinter als nerdiger Spieltrieb.

Was diese Aufgaben gemeinsam haben: Sie lassen sich mit dem sogenannten Reinforcement Learning lösen, dem verstärkenden Lernen. Das sind KI-Verfahren, bei denen ein Programm selbstständig lernen kann, durch bloßes Herumprobieren und anhand positiver und negativer Rückmeldungen Aufgaben zu lösen und Ziele zu erreichen. Eine prominente Spielart ist das Q-Learning mittels Q-Tabellen, das Ihnen Autor Pit Noack in diesem Artikel zeigt. Sie werden sehen, dass diese Art des Lernens erstaunliche Parallelen aufweist zu der Art und Weise, wie Menschen neue Fertigkeiten erwerben.

Die höchste Übereinstimmung gewinnt – Bilderkennung

Ein grundlegendes Anwendungsbeispiel der künstlichen Intelligenz ist die Bilderkennung mittels neuronaler Netze. Dabei geht es darum, eine Bilddatei korrekt einer Klasse zuzuordnen. Geradezu sprichwörtlich ist eine Anwendung, die Katzen- von Hundebildern unterscheiden kann.

Eine solche Bilderkennungsaufgabe ist schnell gelöst und mit einem einzigen Schritt abgeschlossen. Die Struktur ist dabei immer gleich: Eine Eingabe (das Bild) wird einer Ausgabe (der erkannten Klasse, also zum Beispiel Hund oder Katze) zugeordnet.
 

Doch wie lernt ein neuronales Netz, Katzen und Hundebilder zu unterscheiden? Letztlich funktioniert es nach dem Prinzip „Versuch und Irrtum“ (Trial and Error): Ein anfänglich zufällig eingestelltes Netz wird anhand von Beispielen trainiert, bei denen die korrekte Lösung bereits bekannt ist. Anhand der zunächst fehlerhaften Ausgaben wird das Netz in kleinen Schritten justiert, sodass die Fehler immer geringer werden. Nach dem Training sollte das Netz auch Bilder, die nicht Teil des Trainingsdatensatzes waren, korrekt zuordnen.

Verstärkendes Lernen – komplexe Probleme lösen

Es existiert allerdings eine Fülle von Problemen, die deutlich vertrackter sind als jenes der Bilderkennung, und für die das eben beschriebene Vorgehen nicht funktioniert. Diese können zum Beispiel sein:

• das Gewinnen einer Schachpartie,
• das Finden des kürzesten Weges durch einen Hindernisparcours,
• das Erreichen einer möglichst hohen Punktzahl bei einem Computerspiel wie Space Invaders, Breakout oder Video-Pinball.
   

Auch bei der Lösung dieser Probleme geht es letztlich darum, eine Zuordnung zwischen Eingaben und Ausgaben zu leisten. Die Eingabe ist jeweils der aktuelle Zustand – das ist im Falle des Schachprogramms die Stellung der Figuren auf dem Schachbrett. Die Ausgabe ist immer die nächste Aktion, sprich: der nächste Schachzug. Der Unterschied zur Bilderkennung ist allerdings gewichtig: Das Gewinnen einer Schachpartie erfordert eine Reihe von Schritten – im Gegensatz zur Bilderkennung, die mit einem einzigen Schritt abgeschlossen ist.

Um solche Probleme per „Versuch und Irrtum“ zu lösen, benötigen wir deshalb ein anderes Verfahren als bei der Bilderkennung. Dieses Verfahren nennen wir verstärkendes Lernen, oder auch bestärkendes Lernen bzw. Reinforcement Learning. Genauer gesagt handelt es sich dabei um eine ganze Klasse sehr unterschiedlicher Verfahren. Der Begriff stammt aus der Psychologie. Er bezieht sich auf den bekannten Umstand, dass jene Verhaltensweisen verstärkt werden, die ein positives Ergebnis bringen. Wir können in diesem Artikel nicht alle Varianten des verstärkenden Lernens vorstellen. Aber es gibt eine eindeutige Struktur, in die wir jedes konkrete Problem verpacken müssen, um es mittels des verstärkenden Lernens bearbeiten zu können. Wir schauen uns zunächst diese Struktur an und skizzieren anschließend ein grundlegendes Verfahren des verstärkenden Lernens: das Q-Learning mittels Q-Tabelle.

Q-Learning: Umwelt, Agent, Aktion und Belohnung

Eine Anwendung des Q-Learnings besteht grundsätzlich aus fünf wesentlichen Elementen: der Umwelt und ihrem jeweiligen Zustand, dem Agenten, den möglichen Aktionen und den Belohnungen.
 

Um zu verstehen, was es mit diesen Begriffen auf sich hat, schauen wir uns ein einfaches Problem an: die Suche nach dem kürzesten Weg durch einen überschaubaren Hindernisparcours.

• Das gesamte Bild repräsentiert die Umwelt.
• Das blaue Quadrat ist der Agent.
• Die möglichen Aktionen sind die Bewegungen, die der Agent ausführen kann: ein Schritt nach links, rechts, oben oder unten.
• Das grüne Quadrat ist das Ziel. Wenn der Agent es erreicht, erhält er eine Belohnung.
• Offensichtlich ist der Agent ein Teil der Umwelt. Und in unserem konkreten Beispiel ist die Position des Agenten die einzige veränderliche Eigenschaft der Umwelt. Somit bestimmt die Position des Agenten den Zustand der Umwelt.

Die Umwelt befindet sich zu jedem Zeitpunkt in einem definierten Zustand. Die Anzahl dieser Zustände ist endlich. Dem Agenten steht eine ebenfalls endliche Anzahl an Aktionen zur Verfügung, um mit der Umwelt zu interagieren. Aktionen können den Zustand der Umwelt verändern. Manche Zustände sind mit einer Belohnung für den Agenten verknüpft. Die Belohnungen sind Teil der Umwelt. Wenn der Agent einen der vorher festgelegten Endzustände erreicht, ist eine Episode abgeschlossen.

Ein schlauer Agent sollte seine Aktionen also in sinnvoller Weise vom Zustand der Umwelt abhängig machen. Seine Aktionen aber wiederum verändern den Zustand der Umwelt. Agent und Umwelt stehen also in einem zirkulären Verhältnis.

Die Q-Tabelle – Das Q steht für Qualität

Das Q-Learning mittels Q-Tabelle ist ein grundlegender Vertreter des Q-Learnings. Dabei geht es letztlich darum, eine Tabelle mit Werten zu füllen:

• Die Zeilen der Tabelle stehen für die möglichen Umweltzustände.
• Die Spalten repräsentieren die möglichen Aktionen.

Damit eine solche Tabelle überhaupt konstruiert werden kann, müssen die Umweltzustände und Aktionen aufzählbar sein. Das erreichen wir durch einfaches Durchnummerieren der Felder unseres Hindernisparcours (Zustände) und der vier Bewegungsrichtungen (Aktionen).

Die Werte, die in der Tabelle stehen, drücken dabei aus, wie sinnvoll eine Aktion in einem bestimmten Zustand ist, und zwar in Hinblick auf zukünftige Belohnungen. Das sind die Q-Werte.

Die Abbildung zeigt eine vereinfachte Variante. Hier steht in jeder Zeile eine 1, alle anderen Felder sind mit einer 0 gefüllt. Die 1 markiert die jeweils vielversprechendste Aktion.

Wie aber füllt der Agent die Tabelle? Zu Beginn des Lernprozesses hat er keine Ahnung, wo das Ziel sich befindet, und führt eine rein zufällige Suchbewegung aus und findet das Ziel irgendwann durch bloßes Herumprobieren. Dann passiert vereinfacht gesagt Folgendes: Der Agent schaut, von welcher Position (sprich: von welchen Zustand) aus er das Ziel mit welcher Aktion erreicht hat. Und in der Tabelle trägt er dann in das entsprechende Feld eine 1 ein. Im übertragenen Sinne können wir sagen: Der Agent zeichnet einen Pfeil vom zuletzt besuchten Feld Richtung Ziel.
 

Anschließend startet der Agent erneut von einer zufälligen Position und sucht erneut das Ziel in einem zufälligen Zickzack-Kurs – bis es entweder das Ziel erreicht oder ein Feld, das bereits mit einem Pfeil versehen ist.
 

Dieser Vorgang wird so lang wiederholt, bis alle Zeilen der Tabelle einen Eintrag haben, es also für jeden Umweltzustand eine bevorzugte Aktion gibt.
 

Sie sehen die Veränderung des Spielfelds im weiteren Verlauf des Programms. Zum Ende hin sind alle Zellen mit Pfeilen versehen, die den Weg Richtung Ziel weisen. Die Zellen sind dabei mit unterschiedlich hellen Graustufen eingefärbt. Die Helligkeit einer Zelle steht für deren Q-Wert: Je näher eine Zelle dem Ziel ist, umso heller leuchtet sie. Die Pfeile zeigen jeweils auf diejenige benachbarte Zelle, die den höchsten Q-Wert besitzt.

Die unterschiedlichen Helligkeitsstufen weisen auf einen fundamentalen Unterschied zur vereinfachten Q-Tabelle in der Abbildung hin: Dort nämlich können die Einträge nur zwei unterschiedliche Werte annehmen, 0 oder 1 – wobei die jeweils bevorzugte Aktion mit 1 gekennzeichnet ist.

Diese kurze Darstellung zeigt den Prozess des Q-Learnings mittels Q-Tabelle erheblich vereinfacht. Dennoch verstehen Sie nun, wie eine KI-Anwendung vorgehen muss, um Probleme zu bearbeiten, deren optimale Lösung eine Vielzahl von Schritten erfordert.

Mehr zum Thema Künstliche Intelligenz erfahren Sie im → Buch »Künstliche Intelligenz verstehen. Eine spielerische Einführung in die KI« von Pit Noack und Sophia Sanner. Das hier beschriebene Beispielprogramm wird auch im Buch behandelt und kann direkt online ausprobiert werden: → www.maschinennah.de/ki-buch.
 

Die Inhalte und Bilder auf dieser Seite stammen zum Teil aus dem Buch »Künstliche Intelligenz verstehen«. | Bilder: © Rheinwerk Verlag (1-11)
 

Steigen Sie ein in die Welt der KI

Mit diesen Büchern werden Sie schnell die Prozesse hinter Künstlicher Intelligenz verstehen und lernen, diese in Ihrem Alltag effizient einzusetzen. Unsere Experten zeigen Ihnen, welche Technologien, Konzepte und Methoden Sie unbedingt kennen müssen, um in der digitalen Welt up to date zu bleiben.