Antes de começar a ler este texto peço que assista rapidamente o vídeo a seguir para saber quem serão os primeiros a ir para o paredão quando a revolução dos robôs iniciar.

Espero que você não tenha se perdido no Youtube. Este vídeo é uma compilação de vídeos da empresa Boston Dynamics em situações em que os robôs estão sendo treinados para executar tarefas. Aquelas pessoas (com um curto futuro pela frente) estão tentando dificultar as tarefas para que o robô possa adaptar a execução diante de diferentes obstáculos ou circunstâncias. Neste caso os robôs aprendem com a experiência e cada vez que atingem seu objetivo ganham uma recompensa, um “like virtual”. Com o passar do tempo o algoritmo que controla o robô percebe qual a melhor maneira de ganhar recompensas e executa as tarefas com maior perfeição. Esse processo é chamado de Aprendizado por Reforço (Reinforcement Learning) que pode ser positivo ou negativo. É mais ou menos o que acontece quando uma criança ganha um chocolate por fazer a tarefa do colégio (reforço positivo) ou fica de castigo se não a fizer (reforço negativo).

Bem, é claro que vamos falar de Machine Learning neste texto e em especial de uma técnica chamada Q-Learning. Esta é uma das técnicas de aprendizado por reforço que está dentro da categoria de Aprendizado Não-Supervisionado. O melhor de tudo é que disponibilizei um código para você verificar a mágica acontecendo.

Bom velhinho em apuros

Nosso personagem, Jonas, é motorista de taxi e gosta de trabalhar de madrugada (sim, ele mora em uma cidade pouco violenta). Em muitos momentos, quando está sem passageiros, ele estuda sobre inteligência artificial e coisas relacionadas. Seu objetivo é conseguir um emprego nesta área. Nos últimos dias ele se interessou por uma técnica chamada Q-Learning, um aprendizado por reforço, e esteve escrevendo alguns códigos no tempo livre sobre como ensinar um robô virtual a encontrar a saída de um labirinto com armadilhas.

Em determinado dia, por acaso a madrugada do dia 24 para 25 de dezembro, ele estava em seu carro estudando e esperando passageiros (sim, ele não tem família). Como era quase manhã, Jonas já pensava em ir para sua casa dormir no momento que viu um senhor correndo em direção ao seu carro. O homem era barrigudo, com uma grande barba branca, vestia roupas vermelhas e carregava um embrulho em suas mãos. Este abriu a porta do taxi, entrou e quase sem fôlego e gritou – Preciso de sua ajuda jovem, estamos quase sem tempo. Me leve a este local o mais rápido possível, VAMOS! – Foram momentos de confusão. Aquele senhor apontava para o horizonte onde o Sol dava indícios de aparecer e também para um endereço escrito no pacote de presente.

Jonas não queria acreditar que o Papai Noel havia aparecido diante dele e pedido sua ajuda, mas, de qualquer maneira, era um cliente que precisava de seus serviços. Ficou claro que deveria chegar ao destino antes que o Sol nascesse. O problema é que ele conhecia vários caminhos possíveis até o destino final e sua pouca experiência não o permitia saber qual o mais rápido (neste universo não existe google maps). Como, então, ele iria descobrir qual o menor caminho até lá (neste caso o menor caminho é também o mais rápido)? Eis que então surgiu uma expressão de esperança no rosto de nosso herói quando ele lembrou do assunto que vinha estudando. Rapidamente pegou seu notebook no banco de trás do carro, abriu e começou a digitar algumas coisas.

O senhor não acreditava no que o jovem estava fazendo e começou a gritar mais alto enquanto lágrimas de desespero corriam pelo seus rosto – Rapaz, isto é um assunto sério. Este presente foi esquecido e o natal será destruído se ele não for entregue antes do amanhecer, você é minha última esperança.

Alguns segundos foram suficientes para que Jonas rodasse um de seus códigos e, com um largo sorriso no rosto, arrancasse com seu carro – Não se preocupe, Papai Noel, não deixarei que isso aconteça.

Experimento virtual

O que Jonas fez em seu computador foi estabelecer uma espécie de modelo para a cidade indicando o destino. Representamos a cidade de maneira simplificada como mostra a figura abaixo. Cada um dos números representa um dos lugares em que está o taxi, chamaremos de células. Neste caso a movimentação permitida é apenas para cima, baixo, esquerda ou direita. A células com um “T” marcado são lugares em que há ruas em obras e Jonas ficaria preso se entrasse ali, já o “X” marca o destino, onde o presente final será entregue.

Com este “ambiente” pronto, a técnica utilizada faz uma espécie de experimento virtual que funciona da seguinte maneira: um robô taxista, chamado de agente, é colocado aleatoriamente em qualquer uma das células e ele se move também aleatoriamente para uma das células vizinhas, a posição dele é chamada de estado. O movimento vai se repetindo e termina em três ocasiões: quando chega nas células 8, 13 ou 16. Se chegar em 8 ou 13 recebe um reforço negativo e chegando em 16 recebe um reforço positivo. É como se fosse concedida uma gorjeta extra por chegar em 16 e uma multa por chegar em 8 ou 13. Quando uma das condições é satisfeita a tentativa acaba, chamamos isso de episódio. O agente então guarda em sua memória informações sobre o caminho que fez, por exemplo, se ele começou em 7 e foi para 8, ele sabe agora que o caminho 7→8 fornece uma recompensa negativa e tentará evitar está ação (ir de 7 para 8). Todo esse processo é repetido diversas vezes (vários episódios) e o agente vai melhorando sua memória, ou seja, vai aprendendo sobre os melhores caminhos da cidade para chegar na célula 16.

Antes de continuar lembremos de alguns termos vistos aqui e mais alguns que fazem parte do contexto de Q-Learning:

• Agente – o próprio robô, aquele que executa as ações e interage com o ambiente;
• Estado (s) – a situação ou o lugar onde o agente se encontra em determinado instante. Ex: se o agente ocupa a célula 1 no segundo turno ele tem estado igual a 1 (s₂=1);
• Ação (a) – uma possível atitude que o agente pode tomar. Ex: se o agente está na célula 1 ele só pode ter como ação ir para a célula 2 ou 5;
• Ambiente – a cidade;
• Recompensa (R) – algum modo de dizer que o agente está se saindo bem, fazemos isso através de números;
• Memória (Q) – algo que permita o agente lembrar e escolher sua ação. Também se usa o termo Qualidade, pois este determina a qualidade de uma ação (se é boa ou ruim).

Claro que não vai ocorrer nenhuma mágica aqui, há uma equação por trás deste aprendizado:

Há duas coisas novas nesta equação: α é um número chamado de taxa de aprendizado e γ é chamado de fator de exploração. Tipicamente estes dois são valores entre zero e um.

Você pode encontrar esta equação em vários trabalhos que envolvem psicologia cognitiva, física, matemática, economia e é claro é também utilizada pelo time do Elon Musk que joga Dota2, mas em cada um desses lugares ela tem uma carinha um pouco diferente.

Ok, chega de jogar conversa fora e vamos ver o que essa belezinha pode fez pelo natal. O procedimento é o seguinte:

• Sorteamos uma posição de início aleatória para o taxista: se ele cair em um bloqueio “perde uma vida” e a tentativa acaba; caso contrário ele escolhe aleatoriamente uma das células vizinhas e muda de posição (estado); isso é repetido até encontrar a saída.
• Quando ele muda de estado está aprendendo sobre a cidade e atualiza sua memória (Q^novo) com a equação acima. Exemplo: se ele foi para a célula 4 ele “olha” para as células vizinhas (3 e 8), procura nas suas experiências passadas qual das ações “ir de 4 para 3” e “ir de 4 para 8” retornou uma recompensa maior. Isso é representado pelo termo MAX(Q(s_t+1,a_t+1)), se ele nunca executou as ações antes, esta quantidade é zero. A recompensa que o ambiente gera para ele está armazenada em R_t, são valores que nós definimos. Então o agente faz as contas, soma tudo à memória anterior e avança aleatoriamente para a célula 3 ou 8.

Em cada episódio de nosso experimento virtual, o agente descobre o mundo ao seu redor. É como jogar o mesmo estágio de um jogo sem parar, morrendo ou chegando ao fim. Quer um exemplo muito bom? Experimente Dead Cells, cada vez que você morre deve começar desde o início e cada vez que avança mais do que nas vezes anteriores seu cérebro enche você de recompensa (dopamina).

Para definir a recompensa ganha em cada ação, façamos o seguinte: queremos que taxista entenda que a célula 16 contém o destino final, então estar nesta e ali permanecer deve fornecer a maior recompensa, e ir para ela através das ações “12→16” e “15→16” deve fornecer recompensas um pouco menores. Representamos isso, na matriz R_t, da seguinte maneira:

Na matriz R_t as colunas (zero = célula 1, …, 15 = célula 16) representam o estado e as linhas representam a ação. Ex: se o agente estiver na célula 12 (S=12), e for para a célula 16 (a=12→16), olhamos no destaque em vermelho que receberá uma recompensa igual a 20. Os valores -1 representam ações proibidas. Ex: no destaque em azul, a partir da célula 5, as únicas ações possíveis são a={5→1, 5→ 6, 5→ 9}. Neste caso com valor zero, ou seja, nenhuma recompensa.

A memória do agente é parecida com essa matriz R_t. Ela precisa associar um valor alto para as ações boas e baixo para ações ruins. No primeiro episódio, a cidade é completamente nova para taxista então não há memórias (a matriz contém apenas zeros). Depois de muito treino podemos ver como ele se sai tomando suas próprias decisões.

Colocando o treino em prática

Parece tudo meio confuso, não? Talvez seja melhor fazermos um teste como exemplo. Algumas coisas que foram ditas serão repetidas para melhorar o entendimento. Se você tem curiosidade de verificar por si mesmo, pode verificar aqui os passos de um código completo em Python.

Em cada momento do treinamento vemos o estado do labirinto com o agente assim:

Cada “_” representa uma das posições do labirinto, o “o” representa onde está o agente, “T” representam os bloqueios nas células 8 e 13 e por fim “X” é o destino.

Definimos os valores das matrizes Rt e Q, usaremo como dito acima e vamos usar α=1 e γ=0.95.

Eis o resultado da simulação de um episódio:

Análise:

• A célula 11 foi sorteada como estado inicial;
• O taxista tem quatro opções de ação 11→7, 11→10, 11→15 e 11→ Sorteia a última opção e faz a conta

Qnovo(s=11,a=12) = (1-1)*Q(s=11,a=12) + 0.5*(0 + 1*0) = 0

• A matriz Q continua com o valor zero para esta ação;
• Na ação seguinte ele vai ao acaso para a saída e recebe uma boa recompensa

Qnovo(s=12,a=16) = (1-1)*Q(s=12,a=16) + 0.5*(20 + 1*0) = 10

• Agora sim! Nosso robô sabe que, se ele fizer a ação 12→16, receberá uma recompensa. A matriz de memória agora não tem apenas zeros, possui um valor 10 na posição que representa esta ação.
• Após vários episódios a memória estará repleta de números, como esta:

Verificando a memória vemos, por exemplo, que, se o agente estiver na célula 11 (linha 10 da tabela), o próximo movimento é escolhido com base no maior número (recompensa) nesta linha; que corresponde ao valor 111 e a ação é ir para a célula 12 (coluna 11 da tabela). Assim, ele se move para 12 e, de lá, a maior recompensa diz a ele para ir para o destino final. Como resultado de tudo isso, não importa onde o agente inicia sua jornada, ele sempre chega ao destino final através do menor caminho existente.

Conclusão

Com esse treino baseado em reforço positivo, quando o agente é recompensado por uma determinada ação, foi possível construir uma memória das experiências passadas. Note que, mesmo se o agente estiver longe da saída, a memória permite que ele chegue lá. Uma característica desta técnica é que, se a configuração do ambiente mudar, é preciso formar uma nova memória. Isso pode ser resolvido se adicionarmos uma nova dimensão, o tempo, nas matrizes R e Q. Para os mais aficionados é possível verificar que a equação de aprendizado é utilizada na física em um outro formato, o de uma equação de campo (pode verificar aqui), que pode ser vista como uma equação que descreve a transmissão de informação, no nosso caso a informação armazenada na memória do agente.

Se quiser aprender mais sobre o assunto recomendo o livro Reinforcement Learning dos autores Richard S. Sutton e Andrew G Barto.

Feliz Natal!

Junior “Ninja” Koch é Bacharel em Física, Doutor em Ciência e Engenharia de Materiais, Pós-doutorando em Gravidade Quântica e Cientista de Dados. Adora criar modelos matemáticos para tudo que vê e colocar machine learning no meio. Seu lema é “Tudo é matemática”.