Conteúdo


Treine um agente de software para se comportar de forma racional com um aprendizado de reforço

Comments

O aprendizado de reforço é um subcampo do aprendizado de máquina que pode ser usado para treinar um agente de software para se comportar de forma racional em um ambiente. O agente é recompensado com base nas ações executadas no ambiente. Um exemplo vem de 1992, quando Gerry Tesauro da IBM usou o aprendizado de reforço para criar um jogador de gamão com autoaprendizagem. Este artigo explora o aprendizado de reforço, algumas áreas problemáticas em que ele pode ser aplicado e demonstra a tecnologia usando uma simulação simples.

Muitos algoritmos no aprendizado de máquina se encaixam em uma dessas duas categorias: aprendizagem não supervisionada ou supervisionada. No aprendizado não supervisionado, um algoritmo segrega os dados não rotulados em grupos com base em sua estrutura subjacente, o que torna os dados compreensíveis. Um exemplo de aprendizado não supervisionado é o algoritmo de clustering k-médias, que particiona dados em clusters com a média mais próxima. Do outro lado do espectro encontra-se o aprendizado supervisionado. No aprendizado supervisionado, um conjunto de variáveis de entrada é mapeado para um conjunto predefinido de variáveis de saída por meio de uma função de mapeamento (com o objetivo de aproximar os dados de entrada para predição). Esse processo é categorizado como supervisionado porque um algoritmo usa os dados de entrada e os de saída para treinar uma função de mapeamento. As redes neurais são um exemplo de aprendizado supervisionado.

O aprendizado de reforço é diferente de qualquer uma dessas abordagens de aprendizado, mas se aproxima mais da extremidade supervisionada do espectro. No aprendizado de reforço, o mapeamento do estado para a ação é aprendido por meio de uma recompensa ou punição acumulativa para suas ações. O mapeamento ocorre on-line, por meio de um equilíbrio entre exploração (tentando novas ações para um determinado estado) e explotação (usando o conhecimento existente do mapeamento do estado/ação). O resultado desejado é uma política ideal de estado para ação que maximiza alguma recompensa geral, conforme verificado a seguir.

A single line showing the spectrum of learning types, with     supervised learning on the left end, unsupervised learning on the right end,     and reinforcement learning just left of center
A single line showing the spectrum of learning types, with supervised learning on the left end, unsupervised learning on the right end, and reinforcement learning just left of center

Vamos começar com uma rápida história de aprendizado de reforço. A partir daí, mostrarei uma implementação de amostra de aprendizado de reforço, especificamente, a técnica de Q-learning.

Uma história do aprendizado de reforço

O aprendizado de reforço tem sua origem na psicologia animal: aprendizado por teste e erro. Os primeiros pesquisadores de inteligência artificial (IA) pensavam que esse mecanismo poderia ser implementado em máquinas e usado para aprender sobre como mapear estados (o ambiente) para ações. Marvin Minsky criou, em 1951, o exemplo mais antigo de aprendizado de reforço para imitar um rato aprendendo a encontrar a saída de um labirinto (implementado em tubos de vácuo que representavam os 40 neurônios do cérebro do rato simulado). À medida que o rato robótico achava a saída do labirinto, as sinapses eram reforçadas com base em sua capacidade de escapar.

Quarenta anos depois, o aprendizado de reforço obteve algum sucesso. Em 1992, o pesquisador Gerald Tesauro da IBM desenvolveu um jogador de gamão chamado TD-Gammon usando o aprendizado de reforço. Tesauro usou o aprendizado de diferença temporal (denominado TD lambda) para treinar uma rede neural composta por 80 unidades ocultas. O TD-Gammon aprendeu o jogo de gamão sem saber nada sobre ele, desenvolvendo seu conhecimento por meio do autojogo. O TD-Gammon jogou no nível dos melhores jogadores humanos e identificou novas estratégias de jogo.

A IBM aplicou o aprendizado de reforço no IBM Watson®, um sistema de pergunta e resposta que compreende e que pode responder na língua natural. Especificamente, a IBM aplicou o aprendizado de reforço na estratégia do IBM Watson jogando Jeopardy!, como tentar encontrar uma resposta para uma pergunta (com base em suas respostas formuladas e no grau de certeza), o quadrado a escolher no tabuleiro e como apostar no jogo (especificamente, nas duplas diárias). Em 2011, o IBM Watson derrotou campeões anteriores do Jeopardy!.

Em 2016, a Google aplicou o aprendizado de reforço para criar um programa para jogar o Go. O Go é notoriamente difícil de desenvolver, por causa da escala dos possíveis movimentos (um tabuleiro 19x19 com dois tipos de pedras). Um movimento inicial no xadrez tem 20 possibilidades, mas o Go tem 361 movimentos iniciais possíveis. O AlphaGo do Google aprendeu analisando os movimentos de jogadores profissionais e, então, jogou sozinho para aumentar seu conhecimento (embora agora seja totalmente treinado pelo autojogo). Usando o aprendizado de reforço profundo, o AlphaGo derrotou um grão-mestre de Go coreano.

Q-learning

Agora, vamos dar uma olhada em um tipo de aprendizado de reforço chamado Q-learning e, então, vamos criar uma simples simulação para demonstrá-lo.

Imagine um agente em um mundo bidimensional. O ambiente é composto de casas que o agente pode ocupar (os estados). Em cada estado encontram-se as ações que cada agente pode executar,—ou seja, o movimento em uma de quatro direções para uma nova casa. Quando o agente se movimenta, ele pode receber uma recompensa (ou uma recompensa no futuro que foi recebida com base no movimento inicial). Dada essa recompensa, ele pode designar uma preferência à ação para um estado, de forma que o estado seja preferido no futuro (visto que o objetivo do agente é maximizar essa recompensa). O processo de aprendizado é, então, identificar a ação ideal para cada estado que fornece a maior recompensa. Identificar as políticas de ações para determinados estados é o processo de aprendizado.

No Q-learning, a cada par estado-ação é atribuído um Q-value, que representa a soma de reforços calculada por uma função de Q-value. Esse trabalho é realizado à medida que o agente explora o ambiente. Quando uma ação específica é executada em um determinado estado, uma recompensa é recebida e ela atualiza o Q-value do par estado-ação para que se lembre disso. À medida que o agente vagueia, os Q-values para os pares estado-ação são refinados para que posteriormente (aprendizado posterior) o agente possa aplicar a melhor ação para um determinado estado (dado seu Q-value). Observe que, durante o aprendizado, o agente pode, de maneira probabilística, escolher uma ação para um determinado estado (como uma função de cada Q-value da ação em relação à soma dos Q-values). Esse processo permite que o agente prefira uma ação para um determinado estado (para usar seu conhecimento aprendido), mas, ocasionalmente, ele escolhe uma ação menos ideal para exploração, conforme verificado a seguir.

Process diagram showing the process loop between the site/feedback      and action for the agent and environment based on the environment,      state, action, and Q-value
Process diagram showing the process loop between the site/feedback and action for the agent and environment based on the environment, state, action, and Q-value

A função do Q-value incorpora dois fatores que podem ser usados para adaptar essa operação. O primeiro é uma taxa de aprendizado (alfa), que define quanto de um novo Q-value substituirá o antigo. Um valor de 0 significa que o agente não aprenderá nada (o que importa são as informações antigas), em que um valor de 1 significa que as informações recém-descobertas são as únicas que importam. O fator seguinte é denominado fator de desconto (gama) e define a importância de futuras recompensas. Um valor de 0 significa que apenas recompensas de curto prazo são levadas em consideração, em que um valor de 1 dá mais importância a recompensas de longo prazo. Depois de um movimento ser selecionado (ação para um determinado estado), o Q-value para essa ação é atualizado usando o Q-value atual, a recompensa e o max Q-value do estado-alvo, como apresentado a seguir.

Q-learning equation showing the learning and discount      factors, the reward, the new and current values, and the future      value estimate
Q-learning equation showing the learning and discount factors, the reward, the new and current values, and the future value estimate

As políticas dos pares estado-ação são criadas em episódios. Quando o agente atinge o estado final, o episódio é concluído e um novo episódio pode ser iniciado. O treinamento também pode ser vinculado por épocas (etapas realizadas pelo agente no ambiente). Observe que os estados não inseridos e as ações não tentadas não são registrados na tabela de estado-ação. Se um agente não explorar alguma parte do estado-espaço, ele não terá nenhuma ideia do benefício (ou prejuízo) que o aguarda ali. Em problemas com estados-espaços massivos é possível encontrar uma solução sem explorar todo o estado-espaço. O fluxo simples na figura a seguir ilustra o processo de aprendizado no Q-learning.

Flow chart showing the Q-learning process
Flow chart showing the Q-learning process

A partir daqui, veremos uma simples implementação do Q-learning, na qual um agente aprende a navegar em um ambiente cheio de obstáculos para localizar uma recompensa.

Implementação de amostra

Esta implementação de amostra pode ser encontrada no GitHub. Nesta simples implementação, é criado um ambiente de 20x20 casas. Cada casa pode conter um obstáculo (como uma parede ou um objeto impenetrável), um espaço aberto (com um valor de recompensa de 0) e a casa objetivo (com um valor de recompensa de 1). O agente começa na casa superior esquerda e, então, usa o Q-learning para encontrar um caminho ideal até o objetivo, que é exibido ao final do processo de aprendizado.

Vamos começar com as importantes estruturas que usei para essa implementação de Q-learning. A primeira é a estrutura de estado-ação, que contém Q-values para as ações de um determinado estado. O símbolo MAX_ACTIONS representa as quatro ações que um agente pode executar em qualquer estado fornecido (0 = Norte, 1 = Leste, 2 = Sul, 3 = Oeste). O QVal representa os Q-values para cada uma das quatro ações e oQMax é o maior Q-value (usado para determinar o melhor caminho quando o agente usa seu conhecimento aprendido). Essa estrutura é instanciada para cada célula no ambiente. Um ambiente também é criado, que é representado por caracteres (|, +, -, # como obstáculos;‘ ‘ como espaço aberto e $ como o estado-alvo):

typedef struct {
   double QVal[ MAX_ACTIONS ];  // Q-value para cada ação.
   double QMax;                 // Q-value máximo.
} stateAction_t;
stateAction_t stateSpace[ Y_MAX ][ X_MAX ];
char environment [ Y_MAX ][ X_MAX ]={};

Vamos começar do início, com a função main . Essa função implementa o loop de Q-learning, em que o agente experimenta ações aleatoriamente, atualiza os Q-values e, após algumas épocas, mostra o melhor caminho encontrado para o objetivo:

int main()
{
   pos_t agent = start;

   srand( time( NULL ) );

   // Init the state/action Q data
   initStateSpace( );

   // Iterar um número máximo de etapas.
   for ( int epochs = 0 ; epochs < MAX_EPOCHS ; epochs++ )
   {
      // Selecionar uma ação para o agente com base na política desejada.
      int action = ChooseAgentAction( &agent, EXPLORE );

      // Atualizar o agente com base na ação.
      UpdateAgent( &agent, action );
   }

   // Mostrar o caminho do agente
   ExecuteAgent( );

   return 0;
}

Em seguida, a função ChooseAgentAction seleciona a próxima ação para o agente com base na política desejada (explorar versus explotar). Para a política de explotação, a função identifica a ação com o maior Q-value e a retorna. Essa opção representa a melhor ação para esse estado e imita o agente explotando seu conhecimento para chegar rapidamente ao objetivo. Para a política de exploração, eu simplesmente pego uma ação aleatória e, então, retorno-a se ela for uma ação legal (se move o agente até o objetivo ou espaço aberto e não até um obstáculo). Outra abordagem para exploração é selecionar a ação probabilisticamente como uma função do QVal (usando o QVal como uma probabilidade sobre a soma de Q-values para o estado):

int ChooseAgentAction( pos_t *agent, int actionSelection )
{
   int action;

   // Escolher a melhor ação (maior Q-value)
   if ( actionSelection == EXPLOIT )
   {
      for ( action = 0 ; action < MAX_ACTIONS ; action++ )
      {
         if ( stateSpace[ agent->y ][ agent->x ].QVal[ action] ==
              stateSpace[ agent->y ][ agent->x ].QMax )
         {
            break;
      }
      }
   }
   // Escolher uma ação aleatória.
   else if ( actionSelection == EXPLORE )
   {
      do
      {
        action = getRand( MAX_ACTIONS );
      } while ( !legalMove( agent->y, agent->x, action ) );
   }

   return action;
}

A última função desta simulação que examino é chamada de UpdateAgente implementa o núcleo do algoritmo de Q-learning. Observe que essa função é fornecida com a ação desejada (uma direção para o movimento) que eu uso para identificar o próximo estado a inserir. A recompensa deste estado é extraída do ambiente e, então, usada para calcular o Q-value atualizado a partir do estado atual (e armazenar em cache o valor QMax , no caso de ter sido alterado). Se o novo estado inserido for o estado-alvo, eu coloco o agente de volta no estado inicial para reiniciar o processo de aprendizado:

void UpdateAgent( pos_t *agent, int action )
{
   int newy = agent->y + dir[ action ].y;
   int newx = agent->x + dir[ action ].x;
   double reward = (double)getReward( environment[ newy ][ newx ] );

   // Avaliar o Q-value
   stateSpace[ agent->y ][ agent->x ].QVal[ action ] +=
     LEARNING_RATE *
      ( reward + ( DISCOUNT_RATE * stateSpace[ newy ][ newx ].QMax) -
                 stateSpace[ agent->y ][ agent->x ].QVal[ action ] );

   CalculateMaxQ( agent->y, agent->x );

   // Avaliar a posição do agente
   agent->x += dir[ action ].x;
   agent->y += dir[ action ].y;

   // Se o agente atingiu o objetivo, coloque-o de volta no estado inicial
   if ( ( agent->x == goal.x ) && ( agent->y == goal.y ) )
   {
      agent->x = start.x; agent->y = start.y;
   }

   return;
}

Essa pequena quantidade de códigos (e algumas outras que podem ser examinadas no GitHub) implementa o Q-learning para esta demonstração. É possível criar o código usandomake e, então, executá-lo usando o nome do programa qlearn. A ilustração a seguir mostra a saída do código e o caminho selecionado como . caracteres. Eu executei isso no contexto da função ExecuteAgent (não mostrada), que usa a política de explotação para escolher o melhor caminho:

$ ./qlearn 

+ - - - - - - - - - - - - - - - - - - + 
| . .             # # #   # # # # #   | 
|   .   # # #     # # #   # # # # #   | 
| # .     # # #           #   # #     | 
| # .       # # # # # # # #           | 
| # .       # # # # # # # #   # #     | 
|   .   # # #         # #     # # #   | 
|   . # # # # #       # #     # # #   | 
|   . # #                       # #   | 
|   . . . . . . . .   # # #   # # #   | 
|   #       # # # .   # # #   # # # # | 
| # # #     # # # . . . # #   # $ . . | 
| # # #   # # # #     . . . . # # # . | 
| # # #     # # #   # # # # . # # # . | 
| # # #       # #   # # #   . . # # . | 
| # #           #   #       # . # # . | 
| #       # #           # # # . # # . | 
|       # # # #         # # # . . . . | 
|       # # # # #                     | 
+ - - - - - - - - - - - - - - - - - - + 

$

Indo além

O aprendizado de reforço, inspirado na psicologia comportamental, é uma técnica útil de aprendizado de máquina que você pode usar para identificar ações para estados em um ambiente. A abordagem pode permitir que um agente aprenda a interagir no ambiente para obter alguma recompensa cumulativa. Este artigo explorou o Q-learning, em que o algoritmo não requer nenhum modelo para compreender o ambiente e cria uma política de seleção de ação. Você pode usar essa abordagem para solucionar uma ampla gama de problemas.

Outra abordagem para o aprendizado de reforço é o Estado-Ação-Recompensa-Estado-Ação, que apresenta muitas semelhanças com o Q-learning. Ambos apresentam semelhanças para aprender sistemas classificadores, que desenvolvem regras dependentes de contexto para espaços de solução complexos.

O aprendizado de diferença temporal é um método de predição dentro do aprendizado de reforço que também trabalha com a ideia de que as predições podem ser aprendidas a partir de observações em um ambiente. Mas as variantes de aprendizado de diferença temporal podem atualizar os Q-values de estado-ação anteriores em vez de apenas o atual.

O aprendizado de diferença temporal começou com o trabalho de Arthur Samuel (que notavelmente desenvolveu a IA para um programa para jogadores de xadrez na IBM na plataforma IBM ® 701) e continuou na área de jogos com o TD-Gammon de Gerald Tesauro na IBM em 1992. O Google continuou essa tendência com o DeepMind, usando o aprendizado de reforço profundo para jogar e derrotar pontuações de jogadores humanos para 23 de 49 jogos Atari 2600 (como o Breakout da Atari)). Nesse modelo, a imagem do videogame visualizada pelo jogador é aplicada no algoritmo de aprendizado de máquina e o algoritmo lança a jogada seguinte (como movimentar o jogador) para o jogo.


Recursos para download


Comentários

Acesse ou registre-se para adicionar e acompanhar os comentários.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=80
Zone=Cognitive computing
ArticleID=1054408
ArticleTitle=Treine um agente de software para se comportar de forma racional com um aprendizado de reforço
publish-date=12042017