August 2018
Jahrgang 33, Nummer 8
Test Run: Einführung in Q-Learning mithilfe von C#
Durch James McCaffrey
.jpg "James McCaffrey")
Vertiefendes lernen (RL) ist ein nebenzweig des maschinellen Lernens, die beschäftigt sich mit Problemen, wenn keine explizite Trainingsdaten mit bekannten, richtigen Ausgabewerten vorhanden ist. Q-Learning ist ein Algorithmus, der verwendet werden kann, um einige Arten von RL Probleme zu lösen. In diesem Artikel, wenn ich Erläutern der Funktionsweise von Q-Learning und ein Beispielprogramm bereitstellen.
Die beste Möglichkeit, worauf ich in diesem Artikel wird auf einen Blick auf den einfachen Irrgarten in Abbildung1 und das zugeordnete Demoprogramm in abbildung2. Im 3 x 4-Dschungel hat 12 Zellen, die von 0 bis 11 nummeriert. Das Ziel ist, über Zelle 8 in der unteren linken Ecke zur Zelle 11 in der Ecke unten rechts in der geringste wechselt zu erhalten. Sie können nach links, rechts, oben oder unten, aber nicht diagonal.
.png "Einfaches Problem")
Abbildung 1 – einfaches Problem
.png "Q-Learning-Demoprogramm")
Abbildung 2, Q-Learning-Demo-Programm
Das Demoprogramm richtet eine Darstellung des Labyrinths im Arbeitsspeicher, und klicken Sie dann den Q-Learning-Algorithmus verwendet, um eine Matrix Fragen zu finden. F steht für Qualität und, in dem sind größere Werte besser. Die Zeilenindizes sind die Zellen "von" und die Spaltenindizes werden die Zellen "zu". Wenn die Anfangszelle 8 ist, zeigt Überprüfung klicken Sie dann auf die Zeile der größte Wert von f 0,44 9 zu Zelle. Zelle 9 ist der größte Wert in der Zeile klicken Sie dann 1,08 5 zu der Zelle. Der Prozess wird fortgesetzt, bis das Programm den Zielzustand Zelle 11 erreicht.
Es ist unwahrscheinlich, Sie müssen Code schreiben, der ein Labyrinths gelöst, aber dies ist das Hello World für Q-Learning, da das Problem leicht zu verstehen ist. Ich werde erläutern, wie Q-Learning realistischer Probleme weiter unten in diesem Artikel generalisieren kann.
In diesem Artikel wird vorausgesetzt, Sie über mittlere oder fortgeschrittene Programmierkenntnisse verfügen, aber nicht voraus, dass Sie irgendetwas über Q-Learning-wissen. Das Demoprogramm wurde mit c# programmiert, aber Sie sollten keine allzu große schwierigkeiten refactoring des Codes in einer anderen Sprache, z. B. Visual Basic oder Python haben. Der Code für das Demoprogramm wird in diesem Artikel in seiner Gesamtheit vorgestellt und ist auch im begleitenden Dateidownload verfügbar.
Informationen zum Code
Für mich ist zumindest Q-Learning etwas ungewöhnlich, da ich, dass die Konzepte verstanden werden am besten denke anhand von bestimmten Democode statt über die allgemeinen Prinzipien ab. Die Gesamtstruktur des Demoprogramms (mit ein paar kleinen Änderungen, um Platz zu sparen) ist in Abbildung 3 zu sehen.
Abbildung 3: Struktur des Q-Learning-Demoprogramms
using System;
using System.Collections.Generic;
namespace QLearning
{
class QLearningProgram
{
static Random rnd = new Random(1);
static void Main(string[] args)
{
Console.WriteLine("Begin Q-learning maze demo");
Console.WriteLine("Setting up maze and rewards");
int ns = 12;
int[][] FT = CreateMaze(ns);
double[][] R = CreateReward(ns);
double[][] Q = CreateQuality(ns);
Console.WriteLine("Analyzing maze using Q-learning");
int goal = 11;
double gamma = 0.5;
double learnRate = 0.5;
int maxEpochs = 1000;
Train(FT, R, Q, goal, gamma, learnRate, maxEpochs);
Console.WriteLine("Done. Q matrix: ");
Print(Q);
Console.WriteLine("Using Q to walk from cell 8 to 11");
Walk(8, 11, Q);
Console.WriteLine("End demo");
Console.ReadLine();
}
static void Print(double[][] Q) { . . }
static int[][] CreateMaze(int ns) { . . }
static double[][] CreateReward(int ns) { . . }
static double[][] CreateQuality(int ns) { . . }
static List<int> GetPossNextStates(int s,
int[][] FT) { . . }
static int GetRandNextState(int s, int[][] FT) { . . }
static void Train(int[][] FT, double[][] R, double[][] Q,
int goal, double gamma, double lrnRate,
int maxEpochs) { . . }
static void Walk(int start, int goal, double[][] Q) { . . }
static int ArgMax(double[] vector) { . . }
} // Program
} // ns
Um das Demoprogramm zu erstellen, ich Visual Studio gestartet und erstellt ein neues C#-Konsolenanwendungsprojekt mit dem Namen QLearning. Ich habe Visual Studio 2017 verwendet, aber die Demo hat keine nennenswerten .NET Abhängigkeiten aus, sodass jede Version von Visual Studio funktionieren sollte. Nach dem Laden des Vorlagencodes in nicht benötigte ich alle entfernt Editor using-Anweisungen, lassen nur den Verweis auf den System-Namespace. Dann fügte ich einen Verweis auf den Namespace "Collections.Generic", weil das Demoprogramm eine List < Int >-Auflistung verwendet.
Das Demoprogramm hat ein klassenweit zufällig ausgewählten Objekts, da Q-Learning auf eine zufällige Auswahl-Komponente umfasst, wie Sie bald sehen werden. Variable ns steht für die Anzahl von Status, wenn Sie die ist ein Synonym für die Anzahl der Zellen in den Irrgarten. Objekt FT (mögliche Übergänge) ist ein Array-von-Arrays-Style-Matrix. Matrix R ist die Matrix Reward und Matrix F ist die Qualität-Matrix.
Der Q-Learning-Algorithmus erfordert Parameter Gamma (auch bekannt als die Faktor Rabatt) und "learnrate". Ich werde später erläutern. Q-Learning ist iterativ und, damit die Demo zu steuern, wie lange der Algorithmus verwenden kann, finden Sie die Matrix Q MaxEpochs-Variable eingerichtet.
Einrichten des Labyrinths und die Boni
Labyrinths wird von der Methode CreateMaze, erstellt die wie folgt definiert ist:
static int[][] CreateMaze(int ns) {
int[][] FT = new int[ns][];
for (int i = 0; i < ns; ++i) FT[i] = new int[ns];
FT[0][1] = FT[0][4] = FT[1][0] = FT[1][5] = FT[2][3] = 1;
FT[2][6] = FT[3][2] = FT[3][7] = FT[4][0] = FT[4][8] = 1;
FT[5][1] = FT[5][6] = FT[5][9] = FT[6][2] = FT[6][5] = 1;
FT[6][7] = FT[7][3] = FT[7][6] = FT[7][11] = FT[8][4] = 1;
FT[8][9] = FT[9][5] = FT[9][8] = FT[9][10] = FT[10][9] = 1;
FT[11][11] = 1; // Goal
return FT;
}
Die Methode gibt eine Matrix, die zulässige Verschiebungen definiert. Beispielsweise können nicht können Sie der Zelle 8 von Zelle 4 verschieben wechseln, jedoch Sie vom Zelle 4 Zelle 5 da eine Wand in die Methode vorhanden ist. Denken Sie daran, dass C#-Int-Arrays, die 0 (null) initialisiert, damit CreateMaze nur zulässige Verschiebungen angeben muss. Beachten Sie, dass Sie aus einer Zelle auf sich selbst, mit Ausnahme der Ziel-Zelle 11 verschieben nicht möglich.
Die Matrix Reward wird definiert durch:
static double[][] CreateReward(int ns) {
double[][] R = new double[ns][];
for (int i = 0; i < ns; ++i) R[i] = new double[ns];
R[0][1] = R[0][4] = R[1][0] = R[1][5] = R[2][3] = -0.1;
R[2][6] = R[3][2] = R[3][7] = R[4][0] = R[4][8] = -0.1;
R[5][1] = R[5][6] = R[5][9] = R[6][2] = R[6][5] = -0.1;
R[6][7] = R[7][3] = R[7][6] = R[7][11] = R[8][4] = -0.1;
R[8][9] = R[9][5] = R[9][8] = R[9][10] = R[10][9] = -0.1;
R[7][11] = 10.0; // Goal
return R;
}
In diesem Beispiel ist das Verschieben in Ziel-Zelle, 11 bietet eine Belohnung von 10.0, aber alle anderen verschieben, bietet eine negative Reward von-0.1. Diese Werte sind einigermaßen willkürlich. Im Allgemeinen ist die Struktur Reward bei der Arbeit mit RL vollständig problemabhängige. Hier punishes der kleinen negative nutzen jede einzelne Verschiebung etwas, das hat den Effekt kürzere Pfade über längere Pfade vorzieht, um das Ziel. Beachten Sie, dass Sie keine, eine Belohnung für Verschiebungen festlegen, die nicht zulässig, da sie niemals eintreten werden.
Das Ziel des Q-Learning wird zum Auffinden des Werts der F-Matrix. Zunächst alle Q-Werte sind auf 0,0 festgelegt und die F-Matrix erstellt wird wie folgt:
static double[][] CreateQuality(int ns) {
double[][] Q = new double[ns][];
for (int i = 0; i < ns; ++i)
Q[i] = new double[ns];
return Q;
}
Definieren die nächsten Zustände möglich
Wie Sie bald sehen werden, muss der Q-Learning-Algorithmus wissen was besagt, dass das System, übergehen kann aufgrund einer aktuellen Status. In diesem Beispiel ist ein Status des Systems identisch mit die Position in der Maze, daher gibt es nur 12 Zustände. Methode GetPossNextStates ist definiert wie folgt:
static List<int> GetPossNextStates(int s, int[][] FT) {
List<int> result = new List<int>();
for (int j = 0; j < FT.Length; ++j)
if (FT[s][j] == 1) result.Add(j);
return result;
}
Beispielsweise ist der aktuelle Status s 5, gibt GetPossNextStates eine List < Int >-Auflistung, die mit (1, 6, 9). Der Q-Learning-Algorithmus wird manchmal auch aus dem aktuellen Zustand in einen zufälligen nächsten Zustand. Diese Funktionalität wird durch die Methode GetRandNextState definiert:
static int GetRandNextState(int s, int[][] FT) {
List<int> possNextStates = GetPossNextStates(s, FT);
int ct = possNextStates.Count;
int idx = rnd.Next(0, ct);
return possNextStates[idx];
}
Daher zurück der aktuelle Status s 5 ist, wenn GetRandNextState entweder "1" oder "6" oder "9 mit gleicher Wahrscheinlichkeit (mit 0.33).
Der Q-Learning-Algorithmus
Die Schlüssel aktualisieren Gleichung für Q-Learning basiert auf die mathematische Gleichung Bellman und wird am unteren Rand der Abbildung 1 dargestellt. Der Algorithmus ist in Train-Methode implementiert. In abstraktem Pseudocode ist der Q-Learning-Algorithmus:
loop maxEpochs times
set currState = a random state
while currState != goalState
pick a random next-state but don't move yet
find largest Q for all next-next-states
update Q[currState][nextState] using Bellman
move to nextState
end-while
end-loop
Der Algorithmus überhaupt nicht offensichtlich ist, und für mich ist es am besten anhand des Codes erläutern. Die Definition beginnt:
static void Train(int[][] FT, double[][] R, double[][] Q,
int goal, double gamma, double lrnRate, int maxEpochs)
{
for (int epoch = 0; epoch < maxEpochs; ++epoch) {
int currState = rnd.Next(0, R.Length);
...
Die Anzahl der trainingsepochen muss durch Versuch und Irrtum ermittelt werden. Ein alternativer Entwurf besteht durchlaufen, bis die Werte in der Matrix Q nicht ändern, oder sie auf sehr kleine Änderungen pro Iteration stabilisieren. Die innere Schleife durchläuft, bis der aktuelle Status den Zustand "Ziel" Zelle 11 im Fall der Demo Maze wird:
while (true) {
int nextState = GetRandNextState(currState, FT);
List<int> possNextNextStates = GetPossNextStates(nextState, FT);
double maxQ = double.MinValue;
for (int j = 0; j < possNextNextStates.Count; ++j) {
int nns = possNextNextStates[j]; // short alias
double q = Q[nextState][nns];
if (q > maxQ) maxQ = q;
}
...
Angenommen Sie, Sie sich in einem Irrgarten befinden. Sie sehen, dass Sie auf drei verschiedenen Räume, A, B, C. zugreifen können Sie wählen B, aber noch nicht zu verschieben. Sie stellen einen Freund in Platz B wechseln und Freundes besagt, dass aus B Sie Räume X wechseln können, Y, Z und der Räume Y hat den besten F-Wert. Das heißt, ist Y den besten nächsten-Next-Status.
Die Aktualisierung der F-Matrix wird ausgeführt:
...
Q[currState][nextState] =
((1 - lrnRate) * Q[currState][nextState]) +
(lrnRate * (R[currState][nextState] + (gamma * maxQ)));
currState = nextState;
if (currState == goal) break;
} // while
} // for
} // Train
Die Update-Formel besteht aus zwei Teilen. Der erste Teil, ((1-lrnRate) * Q[currState][nextState]), die Exploit-Komponente aufgerufen wird, und fügt Sie einen Bruchteil der alte Wert. Der zweite Teil (LrnRate * (R [CurrState] [NextState] + (Gamma * MaxQ))), die Durchsuchen-Komponente aufgerufen wird. Größere Werte von der LrnRate Anstieg der Einfluss von aktuellen Boni und zukünftige Rewards Durchsuchen () auf Kosten der letzten Rewards (Exploit). Der Wert der Gammafunktion, der Rabatt Faktor ist, wirkt sich auf die Bedeutung von zukünftigen Boni.
Mithilfe der F-Matrix
Nach der Qualität wurde Matrix berechnet, kann sie verwendet werden kann, um einen optimalen Weg von einem beliebigen Zustand ab, die den Zielstatus zu finden. Methode durchlaufen wird diese Funktion implementiert:
static void Walk(int start, int goal, double[][] Q) {
int curr = start; int next;
Console.Write(curr + "->");
while (curr != goal) {
next = ArgMax(Q[curr]);
Console.Write(next + "->");
curr = next;
}
Console.WriteLine("done");
}
Beachten Sie, dass die Methode wird davon ausgegangen, dass der Zielzustand aus dem ursprünglichen Status erreichbar ist. Die Methode verwendet Helper ArgMax, um den besten nächsten Status suchen:
static int ArgMax(double[] vector) {
double maxVal = vector[0]; int idx = 0;
for (int i = 0; i < vector.Length; ++i) {
if (vector[i] > maxVal) {
maxVal = vector[i]; idx = i;
}
}
return idx;
}
Beispielsweise verfügt ein Vektor Werte (0.5, 0,3, 0,7, 0,2) klicken Sie dann ArgMax gibt 2 zurück. Die Demo definiert eine Print-Methode, um der F-Matrix angezeigt. Sie können die Version Schöndruck im begleitenden Dateidownload abrufen. Eine vereinfachte Version ist:
static void Print(double[][] Q) {
int ns = Q.Length;
Console.WriteLine("[0] [1] . . [11]");
for (int i = 0; i < ns; ++i) {
for (int j = 0; j < ns; ++j) {
Console.Write(Q[i][j].ToString("F2") + " ");
}
Console.WriteLine();
}
}
Zusammenfassung
Das hier vorgestellte Q-Learning-Beispiel erhalten Sie ein gutes Verständnis der wichtigsten Prinzipien beteiligt. Die in diesem Artikel vorgestellten Problemszenario ist ein URI mit diskreten Status kann, aber Q-Learning mit fortlaufenden Status zu. Die allgemeine Herausforderung ist, den langfristige nutzen, zu maximieren, der für das Maze-Beispiel ist identisch mit dem Zielstatus in die geringste Anzahl von Verschiebungen abrufen. Q-Learning kann nützlich sein, wenn Sie ein System mit der viele der Testversionen, z. B. Schulungen von einer gewerblichen Roboter Gewusst wie: Ausführen einer Aufgabe sicher trainieren können. Aber Q-Learning ist nicht in Szenarios wie Trainieren eines fahrerlose Autos das Navigieren durch Datenverkehr angewendet. Q-Learning und RL erinnere mich ein wenig neuronaler Netzwerke in den 1980er – jetzt relativ wenige praktische Anwendungen stehen, aber es gibt Intensives Forschungszwecken verwenden. Viele meiner Kollegen sind der Meinung, dass an einigen Punkt RL in Nützlichkeit auf unerwartete Weise aufzulösen ist.
Dr. James McCaffreyist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jamccaff@microsoft.com.
Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Asli Celikyilmaz, Chris Lee, Ricky Loynd, Amr-Sharaf, Ken Tran