Agosto de 2018

Volume 33 – Número 8

Execução de Teste - Introdução ao Aprendizado Q Usando C#

Por James McCaffrey

Reforço (RL) de aprendizado é uma ramificação de aprendizado de máquina que soluciona problemas em que não há nenhum dado de treinamento explícito com os valores de saída corretos conhecidos. Perguntas E-learning é um algoritmo que pode ser usado para resolver alguns tipos de problemas RL. Neste artigo, explicarei como funciona o aprendizado Q e fornecer um programa de exemplo.

A melhor maneira de o rumo que este artigo tomará é examinar o Labirinto simple no figura1 e o programa de demonstração associado na Figura 2. O labirinto de 3 x 4 tem 12 células, numeradas de 0 a 11. O objetivo é obter de 8 de célula no canto inferior esquerdo, a célula 11 no canto inferior direito, o menor número é movido. Você pode mover para a esquerda, direita, para cima ou para baixo, mas não na diagonal.

Figura 1 simples com Labirintos problema

Figura 2 programa de demonstração de perguntas E-Learning

O programa de demonstração configura uma representação de Labirinto na memória e, em seguida, usa o algoritmo de aprendizado Q para localizar uma matriz de Q. O Q significa a qualidade, onde os valores maiores são melhores. Os índices de linha são as células "from" e os índices de coluna são as células "para". Se a célula inicial for 8, em seguida, a verificação de que a linha mostra que o maior valor de p é 0,44 em 9 de célula. Em seguida, da célula 9, o maior valor na linha é 1,08 em 5 a célula. O processo continua até que o programa atingir o estado de meta na célula 11. 

Não é provável que você precisará escrever código que resolve um Labirinto, mas isso é o Hello World para o aprendizado Q porque o problema é fácil de entender. Explicarei como aprendizado Q pode generalizar a mais realistas problemas neste artigo.

Este artigo pressupõe que você tenha habilidades de programação intermediárias ou melhores, mas não pressupõe que conheça nada sobre aprendizado Q. O programa de demonstração é codificado usando c#, mas você não deve ter muita dificuldade para refatorar o código em outra linguagem, como Visual Basic ou Python. O código para o programa de demonstração é apresentado em sua totalidade neste artigo e também está disponível no download do arquivo que acompanha este artigo.

Mostre-me o código

Para mim, pelo menos, aprendizado Q é um pouco incomum pois acho que os conceitos são mais bem compreendidos, examinando o código de demonstração específica em vez de a partir de princípios gerais. A estrutura geral do programa de demonstração, com algumas edições secundárias para economizar espaço, é mostrada na Figura 3.

Figura 3 estrutura do programa de demonstração de perguntas E-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

Para criar o programa de demonstração, iniciei o Visual Studio e criado um novo console aplicativo projeto c# chamado QLearning. Eu usei o Visual Studio 2017, mas a demonstração tem sem dependências significativas do .NET, portanto, qualquer versão do Visual Studio funcionará bem. Depois que o código de modelo carregado no editor, removi todas as desnecessários usando instruções, deixando somente a referência ao namespace System. Em seguida, adicionei uma referência ao namespace Collections Generic porque a demonstração usa uma coleção List < int >.

O programa de demonstração tem um objeto aleatório de escopo de classe como aprendizado Q envolve um componente de seleção aleatória, como você verá em breve. Variável ns significa o número de estados, que é o número de células no Labirinto um sinônimo. Objeto FT (transições viáveis) é uma matriz de matrizes. Matriz de R é a matriz de recompensa e matriz p é a matriz de qualidade.

O algoritmo de aprendizado Q exige gama de parâmetros (também conhecido como o fator de desconto) e learnRate. Explicarei posteriormente. Aprendizado Q é iterativo, portanto, a demonstração configura uma variável maxEpochs para controlar quanto tempo o algoritmo pode usar para localizar a matriz de P.

Configurando o Labirinto e as recompensas

O Labirinto é criado pelo método CreateMaze, que é definido da seguinte maneira:

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;
}

O método retorna uma matriz que define as movimentações permitidas. Por exemplo, você pode mover de célula 4 a 8 de célula, mas não é possível mover de 4 da célula a célula 5 porque há uma parede da forma. Lembre-se de que c# inicializa matrizes de inteiro como 0, portanto, CreateMaze deve especificar somente permitido move. Observe que você não pode mover de uma célula a mesmo, exceto para a célula de meta de 11.

A matriz de recompensa é definida por:

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;
}

Neste exemplo, mover a célula de meta 11 fornece uma recompensa de 10.0, mas qualquer outro movimento fornece uma recompensa negativa de-0.1. Esses valores são um tanto arbitrários. Em geral, ao trabalhar com RL, a estrutura de recompensa é totalmente dependente do problema. Aqui, a recompensa negativa pequeno punishes cada movimento sendo que um pouco, que tem o efeito de preferindo caminhos mais curtos a meta ao longo de caminhos mais longos. Observe que você não precisa definir um prêmio para movimentações que não são permitidos porque eles nunca acontecerá.

A meta de aprendizado Q é encontrar o valor da matriz Q. Inicialmente, todos os valores de p são definidos como 0.0 e a matriz de Q é criada da seguinte forma:

static double[][] CreateQuality(int ns) {
  double[][] Q = new double[ns][];
  for (int i = 0; i < ns; ++i)
    Q[i] = new double[ns];
  return Q;
}

Definindo estados de Avançar possível

Como você verá em breve, o algoritmo de aprendizado Q precisa saber o que indica que o sistema pode fazer a transição, dado um estado atual. Neste exemplo, um estado do sistema é o mesmo que o local no Labirinto para que há somente 12 estados. Método GetPossNextStates é definido da seguinte forma:

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;
}

Por exemplo, se o estado atual s for 5, GetPossNextStates retorna uma coleção de List < int > mantendo (1, 6, 9). O algoritmo de aprendizado Q, às vezes, passa do estado atual para um próximo estado aleatório. Essa funcionalidade é definida pelo método 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];
}

Dessa forma, se o estado atual s for 5, em seguida, GetRandNextState retorna 1 ou 6 ou 9 com a mesma probabilidade (cada 0,33).

O algoritmo de aprendizado Q

A equação de atualização de chave para aprendizado Q se baseia na equação matemática Bellman e é mostrada na parte inferior da Figura 1. O algoritmo é implementado no método Train. Em pseudocódigo de alto nível, o algoritmo de aprendizado Q é:

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

O algoritmo não é óbvio, e para mim, ele é mais bem compreendido, examinando o código. A definição começa:

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);
...

O número de épocas de treinamento deve ser determinado por tentativa e erro. Um design alternativo é a iteração até que os valores na matriz de perguntas e não alteram, ou até que eles se estabilizar para alterações muito pequenas por iteração. O loop interno itera até que o estado atual se torne o estado de meta, a célula 11 no caso do labirinto de demonstração:

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;
  }
...

Imagine que você está em um labirinto. Você verá que você pode ir para três quartos diferentes, A, B, C. Escolher B, mas não mover ainda. Você pedir um amigo para entrar em sala de B e o amigo informa que de sala B, você pode ir para salas de X, Y, Z e que esses quartos Y tem o melhor valor P. Em outras palavras, Y é o melhor estado de Avançar de Avançar.

A atualização para a matriz de Q será executada:

...
      Q[currState][nextState] =
        ((1 - lrnRate) * Q[currState][nextState]) +
        (lrnRate * (R[currState][nextState] + (gamma * maxQ)));
      currState = nextState;
      if (currState == goal) break;
    } // while
  } // for
} // Train

A equação de atualização tem duas partes. A primeira parte, ((1-lrnRate) * Q[currState][nextState]), é chamado do componente de exploração e adiciona uma fração do valor antigo. A segunda parte, (lrnRate * (R [currState] [nextState] + (gama * maxQ))), é chamado o componente de explorar. Valores maiores de aumento lrnRate a influência de remunerações atuais e futuras recompensas (exploram) às custas de remunerações últimos (exploração). O valor de gama, o fator de desconto, influencia a importância de remunerações futuras.

Usando a matriz de Q

Após a qualidade da matriz tiver sido calculado, ele pode ser usado para localizar um caminho ideal de qualquer estado inicial para o estado de meta. Método orientam implementa essa funcionalidade:

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");
}

Observe que o método pressupõe que o estado de meta é acessível do estado inicial. O método usa auxiliar ArgMax para localizar o próximo estado melhor:

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;
}

Por exemplo, se um vetor tem valores (0,5, 0.3, 0,7, 0,2) ArgMax retorna 2. A demonstração define um método de impressão para exibir a matriz de Q. Você pode obter a versão de impressão bonita no download do arquivo que acompanha este artigo. Uma versão simplificada é:

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();
  }
}

Conclusão

O exemplo de aprendizado Q apresentado aqui deve lhe dar uma boa compreensão dos principais princípios envolvidos. O cenário de problema apresentado neste artigo é uma com estados discretos, mas, aprendizado Q também pode trabalhar com os estados contínuos. O desafio geral é maximizar a recompensa de longo prazo, que, para o exemplo de Labirinto é igual a introdução para o estado de meta no menor número de movimentos. Perguntas E-learning pode ser útil quando você pode treinar com segurança um sistema com várias versões de avaliação, como treinamento de um robô industrial como executar uma tarefa. Mas, aprendizado Q não é aplicável em cenários como treinar um carros sem motorista como navegar por meio de tráfego. Aprendizado Q e RL lembrar-me um pouco de redes neurais na década de 1980 — há relativamente poucos aplicativos práticos no momento, mas há os esforços de pesquisa intensa. Muitos dos meus colegas acreditam que em algum ponto RL será explodir em utilidade de maneiras inesperadas.

Dr. James McCaffreytrabalha para a Microsoft Research em Redmond, Washington. Ele trabalhou em vários produtos da Microsoft, incluindo Internet Explorer e Bing. Entre em contato com o Dr. McCaffrey pelo email jamccaff@microsoft.com.

Agradecemos aos seguintes especialistas técnicos da Microsoft pela revisão deste artigo: Asli Celikyilmaz, Chris Lee, Ricky Loynd, Kenneth Tran, Amr Sharaf

Discuta esse artigo no fórum do MSDN Magazine