Agosto 2018
Volume 33 numero 8
Il presente articolo è stato tradotto automaticamente.
Esecuzione di test - Introduzione a domande E-Learning con c#
Dal James McCaffrey
.jpg "James McCaffrey")
(RL) di apprendimento per rinforzo è un ramo di machine learning che affronta i problemi in cui non sono presenti dati di training esplicita con valori di output corretta e noti. Q-learning è un algoritmo che può essere utilizzato per risolvere alcuni tipi di problemi RL. In questo articolo spiegare come funziona domande E-learning e fornire un programma di esempio.
Il modo migliore per vedere quale ha inizio in questo articolo è esaminiamo il labirinto semplice in figura 1 e il programma di dimostrazione associato Figura2. Il labirinto 3 x 4 contiene 12 celle, numerate da 0 a 11. L'obiettivo è ottenere dalla cella 8 nell'angolo in basso a sinistra, a 11 di cella nell'angolo in basso a destra nel minor numero spostamenti. È possibile spostare a sinistra, destra, alto o verso il basso, ma non in diagonale.
.png "Problema di semplice labirinto")
Figura 1 Maze semplice problema
.png "Programma di dimostrazione di Q-Learning")
Programma di dimostrazione Figura2 Q-Learning
Il programma demo imposta una rappresentazione del labirinto in memoria e quindi Usa l'algoritmo di Q-learning per trovare una matrice di domande E. Domande e è l'acronimo di qualità, in cui sono preferibili valori più grandi. Gli indici di riga sono le celle "from" e gli indici di colonna sono le celle "to". Se la cella inizia è 8, quindi l'analisi di tale riga mostra che il valore più grande di Q è 0,44 al 9 alla cella. Quindi dalla cella 9, il valore più grande nella riga è 1.08 dalla 5 alla cella. Il processo continua fino a quando il programma raggiunge lo stato dell'obiettivo in corrispondenza della cella 11.
Non è probabile che è necessario scrivere codice che risolve un labirinto, ma si tratta di Hello World per Q-learning perché il problema è facile comprensione. Spiegherò come possibile generalizzare Q-learning per i problemi più realistici più avanti in questo articolo.
Questo articolo presuppone che si dispone di intermedi o meglio le competenze di programmazione, ma non presume che si conosce Q-learning. Il programma demo è codificato tramite c#, ma si dovrebbe essere troppo difficile refactoring del codice in un altro linguaggio, ad esempio Visual Basic o Python. Il codice per il programma demo viene presentato nella sua interezza in questo articolo ed è anche disponibile nel download del file associato.
Mostra il codice
Per me almeno, Q-learning è un po' insolito perché ritengo che i concetti sono può essere illustrati meglio esaminando codice dimostrativo specifico anziché iniziando a usare i principi generali. La struttura generale del programma demo, con alcune modifiche di lieve entità per risparmiare spazio, è racchiusa figura 3.
Figura 3 struttura del programma Demo di Q-Learning
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
Per creare il programma di dimostrazione, avviato Visual Studio e creato un nuovo progetto applicazione di console c# denominato QLearning. Ho utilizzato Visual Studio 2017, ma la demo senza dipendenze significativi .NET in modo che tutte le versioni di Visual Studio funziona correttamente. Dopo aver caricato il codice del modello nell'editor sono rimosse tutte non necessari tramite le istruzioni, lasciando solo il riferimento allo spazio dei nomi System. Quindi ho aggiunto un riferimento allo spazio dei nomi Collections.Generic perché la demo utilizza un insieme List < int >.
Il programma demo è un oggetto Random con ambito di classe perché Q-learning richiede un componente di selezione casuale, come si vedrà a breve. Ns variabile è l'acronimo per il numero di stati, che è sinonimo con il numero di celle nel labirinto. Oggetto FT (transizioni fattibile) è una matrice di matrice di matrici di stile. Matrice di R è basato sulla matrice reward e matrice Q è la matrice di qualità.
L'algoritmo di Q-learning richiede learnRate e parametri gamma (noto anche come il fattore di sconto). Spiegherò più avanti. Q-learning è iterativa, pertanto la demo consente di impostare una variabile maxEpochs per controllare quanto tempo l'algoritmo può utilizzare per la matrice di domande e trovare.
Impostazione del Dedalo e i vantaggi
Il labirinto viene creato dal metodo CreateMaze, che viene definito come segue:
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;
}
Il metodo restituisce una matrice che definisce spostamenti consentiti. Ad esempio, è possibile spostare da 4 cella per cella 8, ma non è possibile spostare dalla cella 4 a 5 celle in quanto è una parete nel modo. È importante ricordare che c# consente di inizializzare matrici int su 0, quindi CreateMaze deve specificare solo gli spostamenti consentiti. Si noti che non è possibile spostare da una cella a se stesso, tranne la cella di obiettivo di 11.
La matrice di reward è definita da:
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 questo esempio, lo spostamento alla cella di obiettivo di 11 offre un premio di 10.0, ma qualsiasi altro passaggio offre un premio negativo-0.1. Questi valori sono una certa misura arbitrari. In generale, quando si lavora con RL, la struttura di reward è completamente dipendente dal problema. I benefici negativi piccoli punishes in questo caso, ogni potenziale spostamento un po', che ha l'effetto di preferendo i percorsi più brevi tramite percorsi più lunghi per l'obiettivo. Si noti che non è necessario impostare per gli spostamenti consentiti in quanto non si verificheranno mai un premio.
L'obiettivo di Q-learning è trovare il valore della matrice Q. Inizialmente, tutti i valori di domande e vengono impostati su 0.0 e la matrice di domande e viene creata come segue:
static double[][] CreateQuality(int ns) {
double[][] Q = new double[ns][];
for (int i = 0; i < ns; ++i)
Q[i] = new double[ns];
return Q;
}
Definizione degli stati successivi possibili
Come si vedrà a breve, l'algoritmo di Q-learning deve sapere che cosa indica che il sistema può eseguire la transizione, assegnato uno stato corrente. In questo esempio, uno stato del sistema è uguale a quella nel labirinto in modo che esistono solo 12 stati. Metodo GetPossNextStates viene definito come segue:
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;
}
Ad esempio, se lo stato corrente s è 5, GetPossNextStates restituisce un insieme List < int > che contiene (1, 9, 6). L'algoritmo di Q-learning è talvolta passa dallo stato corrente allo stato successivo casuale. Tale funzionalità è definita dal metodo GetRandNextState:
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];
}
Pertanto, se lo stato corrente s è 5, quindi GetRandNextState restituisce 1 o 6 o 9 con uguale probabilità (0,33).
L'algoritmo di Q-Learning
L'equazione di aggiornamento della chiave per Q-learning è basato sull'equazione matematica Fattorino d'albergo e viene visualizzata nella parte inferiore della figura 1. L'algoritmo viene implementato nel metodo Train. In generale pseudo-codice, l'algoritmo di Q-learning è:
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
L'algoritmo non è affatto ovvio e per me, risulta più comprensibile esaminando il codice. Inizio della definizione:
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);
...
Il numero di periodi di training deve essere determinato da tentativi ed errori. Una progettazione alternativa è eseguire l'iterazione fino a quando non modificare i valori della matrice di domande o fino a quando non sono stabilizzarsi a molto piccole modifiche per ogni iterazione. Il ciclo interno esegue l'iterazione finché lo stato corrente non è lo stato dell'obiettivo, cella 11 nel caso del dedalo demo:
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;
}
...
Si ipotizzi di in un labirinto. Noterete che è possibile passare a tre room differenti, A, B, C. Selezionare B, ma non vengono spostate ancora. Si richiede un elemento friend per analizzare la chat room B e friend indica che dalla chat B è possibile passare alla chat room X, Y, Z e quello di queste chat Y ha il valore di domande e ottimale. In altre parole, Y rappresenta lo stato successivo successivo migliore.
L'aggiornamento alla matrice di domande e viene eseguito:
...
Q[currState][nextState] =
((1 - lrnRate) * Q[currState][nextState]) +
(lrnRate * (R[currState][nextState] + (gamma * maxQ)));
currState = nextState;
if (currState == goal) break;
} // while
} // for
} // Train
L'equazione di aggiornamento costituita da due parti. La prima parte, ((1-lrnRate) * Q[currState][nextState]), viene chiamato il componente di exploit e aggiunge una frazione del valore precedente. La seconda parte, (lrnRate * (R [currState] [delle nextState] + (gamma * maxQ))), viene chiamato il componente di esplorazione. Valori più grandi dell'aumento di lrnRate l'influenza di premi correnti e futuri premi (Esplora) a scapito di premi precedenti (exploit). Il valore di gamma, il fattore di sconto influenza l'importanza dei premi future.
Utilizzando la matrice di domande e
Dopo la qualità di matrice è stato calcolato, può essere utilizzato per trovare un percorso ottima da qualsiasi stato inizia allo stato obiettivo. Metodo illustrato implementa questa funzionalità:
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");
}
Si noti che il metodo presuppone che lo stato dell'obiettivo raggiungibile dallo stato inizio. Il metodo Usa helper ArgMax per trovare lo stato successivo migliore:
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;
}
Ad esempio, se dispone di un vettore di valori (0,5, 0.3, 0,7, 0,2) ArgMax restituisce 2. La demo definisce un metodo di stampa per visualizzare la matrice di domande E. È possibile ottenere la versione di tipo pretty-print nel download del file associato. Una versione semplificata è:
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();
}
}
Conclusioni
Nell'esempio di Q-learning presentato in questo articolo fornisce una buona conoscenza dei principi fondamentali coinvolti. Lo scenario del problema presentato in questo articolo è un attributo con stati discreti, ma Q-learning è possibile lavorare con gli stati di continui, troppo. La sfida generale consiste nell'ottimizzare i benefici a lungo termine, quale ad esempio il labirinto equivale a ottenere lo stato dell'obiettivo nel minor numero di spostamenti. Q-learning può essere utile quando è possibile eseguire in modo sicuro il training di un sistema con molte versioni di valutazione, ad esempio un robot industriale di training come eseguire un'attività. Tuttavia, Q-learning non è applicabile a scenari come il training di un'automobili senza conducente come spostarsi tra il traffico. Q-learning e RL ricorda in qualche modo delle reti neurali nel 1980s: esistono applicazioni pratiche relativamente poche subito, ma sono disponibili le attività di ricerca complesse. Molti dei miei colleghi ritiene che in alcuni RL punto verrà explode in utilità in modo imprevisto.
Ripristino di emergenza. James McCaffreylavora per Microsoft Research Redmond, WA Ha lavorato su diversi prodotti Microsoft, tra cui Internet Explorer e Bing. Dr. È possibile contattarlo McCaffrey jamccaff@microsoft.com.
Grazie per i seguenti esperti tecnici Microsoft che ha esaminato in questo articolo: Asli Celikyilmaz, Chris Lee, Ricky Loynd, Amr Sharaf, Davide Tran