Pós-Graduação em Ciência da Computação
APLICAÇÃO DE MINERAÇÃO DE DADOS PARA
REDUZIR A DIMENSÃO DO ESPAÇO DE
CARACTERÍSTICAS E AÇÕES EM
APRENDIZAGEM POR REFORÇO: CENÁRIO DO
DRIBLE DA ROBOCUP
Por
DAVI CARNAÚBA DE LIMA VIEIRA
Dissertação de Mestrado
Universidade Federal de Pernambuco
[email protected]
www.cin.ufpe.br/~posgraduacao
RECIFE, 09/2010
UNIVERSIDADE FEDERAL DE PERNAMBUCO
CENTRO DE INFORMÁTICA
PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
DAVI CARNAÚBA DE LIMA VIEIRA
APLICAÇÃO DE MINERAÇÃO DE DADOS PARA REDUZIR A
DIMENSÃO DO ESPAÇO DE CARACTERÍSTICAS E AÇÕES EM
APRENDIZAGEM POR REFORÇO: CENÁRIO DO DRIBLE DA
ROBOCUP
ESTE TRABALHO FOI APRESENTADO À PÓS-GRADUAÇÃO EM
CIÊNCIA DA COMPUTAÇÃO DO CENTRO DE INFORMÁTICA DA
UNIVERSIDADE FEDERAL DE PERNAMBUCO COMO REQUISITO
PARCIAL PARA OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIA
DA COMPUTAÇÃO.
ORIENTADOR(A): Paulo Jorge Leitão Adeodato
Recife, SETEMBRO/2010
Vieira, Davi Carnaúba de Lima
Aplicação de mineração de dados para reduzir a dimensão
do espaço de características e ações em aprendizagem por
reforço: cenário do drible da RoboCup / Davi Carnaúba de Lima
Vieira - Recife: O Autor, 2010.
xix, 125 folhas : il., fig., tab.
Dissertação
(mestrado)
Universidade
Federal
Pernambuco. CIn. Ciência da computação, 2010.
de
Inclui bibliografia e apêndice.
1. Inteligência artificial. 2. Mineração
Aprendizagem por reforço. I. Título.
006.3
CDD (22. ed.)
de
dados.
MEI2010 – 0172
3.
Aos meus pais,
José Antonio Cruz Vieira e
Maria Nazaré Carnaúba de Lima Vieira
Agradecimentos
Primeiramente a Deus por ter me concedido inteligência suficiente para finalizar esse trabalho.
A todos os membros da banca. É uma grande honra poder contar com a contribuição de todos.
Aos professores Aluízio Araújo, Flávia Barros, Francisco Carvalho, Patrícia
Tedesco, Paulo Adeodato e Teresa Ludermir. Foi muito prazeroso estar em contato
com professores tão dedicados.
Novamente ao professor Paulo Adeodato pela orientação e confiança depositada no meu trabalho de dissertação.
Aos meus pais pelo apoio incondicional e pelo exemplo de força e determinação.
A minha esposa Carine, companheira de todas as horas, por tudo que tem feito por mim.
Aos meus amigos Antonio Zarth, Daniel Melo, Eric Rommel, Orivaldo Vieira,
Paulemir Campos, Paulo Gonçalves e Rubens Bernante, por me fazerem sentir em
casa mesmo estando longe dela. Sentirei saudades dos nossos debates intelectuais
que aconteciam nos botecos da Várzea.
Ao meu professor e agora amigo, Ulisses Dias, pelo incentivo e orientação para continuar minha vida acadêmica.
Ao Centro de Informática pela ótima estrutura e a FACEPE pelo apoio financeiro.
“History has proven that human predictive
powers have never been good beyond a decade. A
few examples are in place here. On the 17th of December 1903, Orville Wright made the first mancarrying powered flight in an aircraft built by himself
and his brother Wilbur Wright. The flight covered
about 120 feet and lasted for 12 seconds. If at that
point someone would have claimed that roughly 66
years later the first man would set foot on the moon,
he would surely have been diagnosed as mentally
insane. However, on the 20th of July 1969, Neil
Armstrong stepped out of the Apollo-11 Lunar Module and onto the surface of the moon.”
(Boer & Kok, 2002)
Resumo
A aprendizagem por reforço é usada em cenários nos quais não se dispõe de um
resultado associado a cada estado nem a cada ação tomada por um agente
inteligente. Essa forma de aprendizagem; portanto, mantém uma forte dependência
da exploração dos espaços de estados e de ações que produz uma explosão de
dados cujo armazenamento se torna um problema em muitas situações. Por outro
lado, tem-se a mineração de dados como uma área da inteligência artificial que
busca extrair informações ou padrões de grandes quantidades de dados, ou
armazenados em um banco de dados ou trafegando em um fluxo contínuo de dados.
A principal contribuição deste trabalho é mostrar como as técnicas de
mineração de dados podem ser utilizadas para selecionar as variáveis e ações mais
relevantes dos ambientes da aprendizagem por reforço. O objetivo desta seleção é
reduzir a complexidade do problema e a quantidade de memória usada pelo agente,
que podem acelerar a convergência da aprendizagem. A dificuldade em utilizar as
técnicas de mineração de dados em ambientes da aprendizagem por reforço devese ao não armazenamento dos dados provenientes da exploração dos espaços de
estados e de ações em um banco de dados. Este trabalho também contribui
propondo um esquema de armazenamento para os estados visitados e as ações
executadas pelo agente.
Neste estudo, o método de seleção de atributos e de ações foi validado
experimentalmente em um problema no qual a aprendizagem por reforço é a
abordagem mais adequada; o drible no futebol de robôs – RoboCup-2D. Este
problema é composto de 23 variáveis contínuas e 113 ações disponíveis para o
agente que consome cerca de 18MB de memória quando utilizado o algoritmo
combinado com a técnica de tile-coding. Os resultados dos experimentos
mostraram que a quantidade de variáveis do ambiente pode ser reduzida em até
56% e a quantidade de ações em até 85%, com uma redução do uso da memória de
95% e um aumento no desempenho de aproximadamente 10% de acordo com a
distribuição da freqüência relativa de sucesso do agente. A abordagem proposta é
simples de usar e eficiente.
Palavras-chave: Aprendizagem por Reforço, Agentes Inteligentes, RoboCup, Mineração de Dados, Seleção de Atributos e Ações.
Abstract
Reinforcement learning is used in scenarios when there is no outcome associated
with the states or actions taken by an intelligent agent. Therefore, this form of learning keeps it as a strong dependence of the operation of state spaces and actions that
produce an explosion on data which becomes a problem in many situations. On the
other hand, we have the Data mining which can be seen as an area of artificial intelligence that seeks to extract information or patterns from large amounts of data either
stored in databases or flowing in streams.
The main contribution of this work is to show how the techniques of data mining can be used to select the most relevant features and actions from reinforcement
learning environments. The objective of this selection is to reduce the complexity of
the problem and the amount of memory used by the agent thus leading to faster convergence. The difficulty in using data mining techniques in reinforcement learning
environments is due to the lack of states and actions explored by the agent stored in
a database. This work also contributes by proposing a storage schema for the visited
states and actions performed by the agent.
In this study, the method of selection of attributes and actions was validated
experimentally on an issue where the reinforcement learning is the most appropriate
approach; the dribble in robot soccer - RoboCup 2D. This problem is composed of 23
continuous variables and 113 actions available to the agent which results in a memory consumption of approximately 18MB when the traditional
is used com-
bined with the tile-coding technique. The experiments’ results show that the amount
of variables in the environment were reduced by 56% and the amount of actions by
85%, which resulted in a reduction in memory consumption of 95% and an increase
in performance of up to 10% according to the relative frequency distribution of
agents’ success. The approach proposed here is both easy to use and efficient.
Keywords: Reinforcement Learning, Intelligent Agents, RoboCup, Data Mining, Feature and Action Selection.
Sumário
CAPÍTULO 1 INTRODUÇÃO ............................................................................................................................... 1
1.1
APRENDIZAGEM POR REFORÇO E A ROBOCUP............................................................................... 1
1.2
MOTIVAÇÃO ................................................................................................................................... 3
1.3
CONTEXTUALIZAÇÃO ...................................................................................................................... 5
1.4
OBJETIVOS..................................................................................................................................... 7
1.5
CONTRIBUIÇÕES ............................................................................................................................ 8
1.6
DESCRIÇÃO DA DISSERTAÇÃO ....................................................................................................... 9
1.7
ORGANIZAÇÃO DA DISSERTAÇÃO ................................................................................................... 9
CAPÍTULO 2 MODELO COMPUTACIONAL ........................................................................................................11
APRENDIZADO POR DIFERENÇA TEMPORAL...................................................................................12
2.1
2.1.1
Rastro de Elegibilidade ..........................................................................................................13
2.1.1.1 Sarsa( ) .............................................................................................................................................. 14
2.1.1.2 Método Q( )........................................................................................................................................ 16
2.2
CONTROLE COM APROXIMADOR DE FUNÇÕES ...............................................................................17
2.3
TILE CODING (CMAC) ..................................................................................................................19
CAPÍTULO 3 AMBIENTE DE TESTE ....................................................................................................................23
3.1
VISÃO GERAL DO SIMULADOR .......................................................................................................23
3.2
VISÃO GERAL DO AGENTE.............................................................................................................25
3.2.1
Sensor Visual .........................................................................................................................26
3.2.2
Sensores Auditivos ................................................................................................................28
3.2.3
Sensores Corporais ...............................................................................................................29
MODELAGEM DO AMBIENTE DO DRIBLE .........................................................................................30
3.3
3.3.1
Treinador ................................................................................................................................34
3.3.2
Comportamento dos Oponentes ...........................................................................................34
3.3.2.1 Time UvA Trilearn .............................................................................................................................. 35
3.3.3
Implementação do Agente ....................................................................................................36
xi
CAPÍTULO 4 MINERAÇÃO DE DADOS NA APRENDIZAGEM POR REFORÇO .......................................................39
SELEÇÃO DE ATRIBUTOS ...............................................................................................................40
4.1
4.1.1
LVF - Las Vegas Filter ...........................................................................................................42
4.1.2
Taxa de Ganho.......................................................................................................................45
4.1.3
Regressão Linear e o Coeficiente de Correlação................................................................46
4.2
SELEÇÃO DE AÇÕES .....................................................................................................................47
4.3
APRENDIZAGEM POR REFORÇO E A MINERAÇÃO DE DADOS ..........................................................48
4.3.1
Armazenamento e Seleção dos dados ................................................................................50
CAPÍTULO 5 EXPERIMENTOS E ANÁLISE ESTATÍSTICA DOS DADOS ..................................................................52
5.1
TREINAMENTO DO AGENTE ...........................................................................................................52
5.2
SELEÇÃO DE ATRIBUTOS ...............................................................................................................55
5.2.1
Treinamento com Todos os Atributos...................................................................................56
5.2.1.1 Análise da Correlação dos Atributos ................................................................................................. 61
5.2.2
Taxa de Ganho.......................................................................................................................63
5.2.3
Las Vegas Filter .....................................................................................................................68
5.3
SELEÇÃO DE AÇÕES .....................................................................................................................72
5.3.1
Análise das Ações com Todos os Atributos.........................................................................73
5.3.2
Análise das Ações com Atributos Eliminados por Taxa de Ganho ....................................75
5.3.3
Análise das Ações com Atributos Eliminados por LVF .......................................................76
5.3.4
Remoção das Ações nos Modelos Discutidos .....................................................................77
5.4
COMPARAÇÃO DOS MODELOS .......................................................................................................80
5.4.1
Teste do Desempenho ..........................................................................................................80
5.4.2
Uso da Memória .....................................................................................................................82
5.5
QUALIDADE DO DRIBLE .................................................................................................................84
CAPÍTULO 6 CONCLUSÃO ................................................................................................................................86
6.1
RESULTADOS E DISCUSSÕES ........................................................................................................87
6.2
CONTRIBUIÇÕES E RELEVÂNCIA ....................................................................................................90
6.3
TRABALHOS FUTUROS ..................................................................................................................91
APÊNDICE A APRENDIZAGEM POR REFORÇO ..................................................................................................93
A.1
A.1.1
A.2
A.2.1
INTRODUÇÃO.................................................................................................................................93
Política Ótima .........................................................................................................................96
PROGRAMAÇÃO DINÂMICA ............................................................................................................97
Processo de Aprendizagem ..................................................................................................98
A.2.1.1 Policy Evaluation ....................................................................................................................98
A.2.1.2 Policy Improvement ................................................................................................................99
A.2.1.3 Policy Iteration ...................................................................................................................... 100
xii
A.2.1.4 Value Iteration ....................................................................................................................... 102
A.3
A.3.1
ALGORITMOS DA APRENDIZAGEM POR REFORÇO ........................................................................ 103
Monte Carlo .......................................................................................................................... 104
A.3.1.1 Monte Carlo On-Policy ......................................................................................................... 105
A.3.1.2 Monte Carlo Off-Policy ......................................................................................................... 107
APÊNDICE B MODELOS BASEADOS NO GRADIENTE DESCENDENTE ...............................................................110
B.1
B.1.1
B.2
INTRODUÇÃO............................................................................................................................... 110
Algoritmo do Mínimo Quadrado Médio............................................................................... 112
REDES NEURAIS MULTILAYER PERCEPTRON .............................................................................. 114
REFERÊNCIAS BIBLIOGRÁFICAS .....................................................................................................................118
xiii
Lista de Figuras
Visão mecânica da técnica de elegibility traces. Fonte: (Sutton & Barto, 1998) .................... 14
Alguns tilings sobrepostos. Nesta figura cada tile é endereçado por duas variáveis, e . A
generalização é obtida entre as regiões sobrepostas. A sobreposição dos tiles torna possível
a experiência obtida em uma região ser compartilhada entre seus vizinhos. ....................... 21
Monitor. .............................................................................................................................. 24
Estrutura do Agente. ............................................................................................................ 25
Posições de todas as linhas e bandeiras do campo. .............................................................. 25
Campo de visão do agente. Os objetos são representados pelos círculos pretos, onde a, e, c,
d e f são jogadores, g é o goleiro e b é a bola. Os objetos são vistos pelo agente se estiverem
dentro do seu ângulo de visão determinado por view_angle, o jogador a, no entanto, pode
ser sentido pelo agente. O goleiro g e a bola b não são vistos pelo agente. Unum_far_length,
unum_too_far_length, team_far_length e team_too_far_length são constantes que
representam a distância de um objeto e, por padrão, são definidos como 20, 30, 40 e 60
(metros), respectivamente. Fonte: (Stone, 1998). ................................................................ 27
Estados finais de um episódio. (a) Agente passou o oponente, mas o estado final não
aparenta ser um drible. (b) Agente passou o oponente deixando-o atrás do seu corpo. Neste
caso, o estado final aparenta mais ser um drible. ................................................................. 31
Ambiente de treinamento .................................................................................................... 32
Busca exaustiva pelo espaço de atributos. O ponto de partida pode iniciar sem nenhum
atributo (visualização top-down) ou com todos atributos (visualização bottom-up). ............ 40
Esquema Snowflake de armazenamento do treinamento do agente. Os Dados de
treinamento estão armazenados em duas tabelas principais: Resultado e ResultadoTemAção.
............................................................................................................................................ 51
xiv
Decaimento exponencial da taxa de aprendizado. ............................................................... 56
Curvas de desempenho (média de dez execuções) do agente com todas as variáveis,
mudando apenas o parâmetro alpha (taxa de aprendizado). ............................................... 57
Curvas de desempenho (média de dez execuções) do agente com todas as variáveis,
mudando apenas o parâmetro E. ......................................................................................... 58
Curvas de desempenho (média de dez execuções) do agente com todas as variáveis,
mudando apenas o parâmetro lambda (elegibility traces).................................................... 59
Curvas de desempenho (média de dez execuções) do agente com todas as variáveis,
mudando apenas a quantidade de tilings. ............................................................................ 59
Curvas de desempenho (média de dez execuções) do agente com todas as variáveis e com a
combinação dos melhores valores para os parâmetros gamma, alpha, E, lambda e
quantidade de tilings. .......................................................................................................... 60
Correlação entre as variáveis com coeficiente maior que sete décimos. Dados retirados do
treinamento com todas as variáveis. .................................................................................... 62
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
Alpha após a remoção das variáveis segundo a taxa de ganho. ............................................ 65
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
E após a remoção das variáveis segundo a taxa de ganho. ................................................... 65
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
Lambda após a remoção das variáveis segundo a taxa de ganho.......................................... 66
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
Tilings após a remoção das variáveis segundo a taxa de ganho. ........................................... 66
Curvas de desempenho (média de dez execuções) do agente com a combinação dos
melhores valores para os parâmetros gamma, alpha, E, lambda e tilings após a remoção das
variáveis irrelevantes de acordo com a taxa de ganho e a redundância (correlação). ........... 67
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
alpha após a remoção das variáveis irrelevantes pelo algoritmo LVF.................................... 69
xv
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
E após a remoção das variáveis irrelevantes pelo algoritmo LVF. ......................................... 70
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
Lambda após a remoção das variáveis irrelevantes pelo algoritmo LVF. ............................... 71
Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro
Tilings após a remoção das variáveis irrelevantes pelo algoritmo LVF. ................................. 71
Curvas de desempenho (média de dez execuções) do agente com a combinação dos
melhores valores para os parâmetros gamma, alpha, E, lambda e tilings após a remoção das
variáveis irrelevantes pelo algoritmo LVF. ............................................................................ 72
Confiança das ações extraídas do treinamento do agente com todas as variáveis para dois
níveis de exploração............................................................................................................. 74
Suporte das ações extraídas do treinamento do agente com todas as variáveis para dois
níveis de exploração............................................................................................................. 74
Confiança das ações extraídas do treinamento do agente após remoção das variáveis
segundo a taxa de ganho para dois níveis de exploração...................................................... 75
Suporte das ações extraídas do treinamento do agente após remoção das variáveis segundo
a taxa de ganho. ................................................................................................................... 75
Confiança das ações extraídas do treinamento do agente após a remoção das variáveis
irrelevantes pelo algoritmo LVF para dois níveis de exploração. ........................................... 76
Suporte das ações extraídas do treinamento do agente após a remoção das variáveis
irrelevantes pelo algoritmo LVF para dois níveis de exploração. ........................................... 76
Curvas de desempenho (média de dez execuções) de todas as abordagens relativas as
seleções de ações variando o parâmetro
. ........................................................................ 78
Comparação do desempenho no teste dos modelos (média de dez execuções) com todas as
variáveis. .............................................................................................................................. 80
Comparação do desempenho dos modelos (média de dez execuções) no teste com as
variáveis selecionadas segundo a Taxa de Ganho e a Redundância. ..................................... 81
xvi
Comparação do desempenho dos modelos (média de dez execuções) no teste com as
variáveis selecionadas pelo algoritmo LVF. ........................................................................... 82
Comparação do uso da memória dos modelos (média de dez execuções) com todas as
variáveis. .............................................................................................................................. 83
Comparação do uso da memória dos modelos (média de dez execuções) com as variáveis
selecionadas pelo algoritmo Taxa de Ganho. ....................................................................... 83
Comparação do uso da memória dos modelos com as variáveis selecionadas pelo algoritmo
LVF (média de dez execuções). ............................................................................................. 84
Interação agente-ambiente. Traduzido da fonte: (Sutton & Barto, 1998) ............................. 94
Modelo linear. ................................................................................................................... 113
Rede Neural Multilayer Perceptron. ................................................................................... 114
xvii
Lista de Tabelas
Possíveis valores para os parâmetros view_width_factor e view_quality_factor. ................. 27
Descrição dos sensores corporais do agente. ....................................................................... 29
Ações realizáveis pelo agente............................................................................................... 32
Representação do ambiente em 23 variáveis contínuas ....................................................... 33
Resultado das competições German Open e RoboCup realizadas entre 2001 e 2004. O time
UvA Trilearn obteve 3 vitórias no torneio German Open e uma vitória no torneio da
RoboCup. ............................................................................................................................. 35
Valores iniciais para os parâmetro do modelo. ..................................................................... 54
Espaço de busca. .................................................................................................................. 54
Variação inicial dos parâmetros do modelo. ......................................................................... 54
Taxa de ganho para as variáveis do ambiente. ..................................................................... 64
Quantidade de variáveis removidas. .................................................................................... 77
xviii
Lista de Algoritmos
Sarsa( )................................................................................................................................ 15
Q( ) ..................................................................................................................................... 17
Versão adaptada do algoritmo
para o gradiente descendente linear. .................. 22
Interceptação da bola .......................................................................................................... 35
Implementação do Agente: Função startEpisode(). .............................................................. 37
Implementação do Agente: Função step(). ........................................................................... 38
Implementação do Agente: Função endEpisode(). ................................................................ 38
LVF (Las Vegas Filter) ........................................................................................................... 44
Algoritmo policy iteration................................................................................................... 101
Algoritmo value iteration. .................................................................................................. 102
Monte Carlo on-policy ........................................................................................................ 106
Monte Carlo off-policy ....................................................................................................... 108
Combinação do algoritmo Q-Learning com as redes neurais artificiais multilayer perceptron.
.......................................................................................................................................... 117
xix
Lista de Siglas
instante de tempo discreto
instante de tempo final de um episódio
recompensa recebida no instante de tempo
estado sucessor
estado no instante de tempo
próxima ação
ação executada no instante de tempo
ação ótima
política ótima
probabilidade de transição do estado
para o estado
se executado a
ação
recompensa imediata esperada com a transição do estado
do
para o esta-
se executado a ação
quantidade de tillings
desconto
taxa de aprendizado
taxa de decaimento do rastro
probabilidade de executar uma ação aleatória em uma política
-ésimo retorno recebido no estado
xx
probabilidade de executar uma ação
ação executada com probabilidade
quando o estado é
no estado
eligibility trace de um estado
eligibility trace do par estado-ação
função valor estado de uma política
função valor estado ótima
função valor estado-ação de uma política
função valor estado-ação ótima
xxi
Capítulo 1
Introdução
By mid-21st century, a team of fully autonomous humanoid robot soccer
players shall win a soccer game, complying with the official rules of the
FIFA, against the winner of the most recent world cup for human players.
-H. KITANO
1.1
Aprendizagem por Reforço e a RoboCup
A aprendizagem por reforço (Sutton & Barto, 1998) tem sido amplamente utilizada
em problemas nos quais outras abordagens de aprendizado não podem ser aplicadas; problemas cujas tarefas não oferecem o suporte de um professor que possa
disponibilizar as respostas desejadas ou comportamentos esperados. Modelos que
necessitam de um professor são conhecidos como modelos supervisionados e utilizam a aprendizagem supervisionada como base de seu treinamento (Haykin, 1994).
Os modelos baseados neste tipo de aprendizagem dispõem de um conjunto de entrada e respostas desejadas na sua amostra de dados para treinamento. O objetivo
dos modelos supervisionados é aproximar a saída estimada - gerada pelo modelo da resposta desejada. Sucessivas passagens da amostra de treinamento pelo modelo são feitas até que algum critério de parada seja satisfeito. Normalmente os critérios de parada dos métodos iterativos estão associados ao erro gerado pelo modelo e são satisfeitos quando o erro é menor que algum valor especificado previamente
ou se este erro não se reduz ao longo das iterações.
Outro
tipo
de
aprendizado
é
conhecido
como
aprendizagem
não-
supervisionada. Neste tipo de aprendizagem os modelos não dispõem de um professor para disponibilizar as respostas desejadas. O processo de aprendizagem
consiste em encontrar semelhanças entre os dados, agrupando-os em grupos para
posteriormente serem rotulados.
1
1.1 Aprendizagem por Reforço e a RoboCup
2
O termo aprendizagem por reforço consiste em programar modelos para que
possam ser treinados por interação com o ambiente, e tem como objetivo aumentar
sua recompensa ao longo do tempo (Sutton & Barto, 1998). Este tipo de aprendizado foi inspirado principalmente no comportamento do aprendizado animal, cujo treinamento tem como base tentativa e erro. Explicitamente, este tipo de aprendizado
não possui um professor, mas existem informações sobre a relevância de suas ações codificadas em um sinal numérico1 chamado recompensa.
O conceito de aprendizado por reforço pode ser aplicado em tudo que possa
monitorar e atuar no ambiente, tais como um agente. A área de Inteligência Artificial
define um agente como uma entidade que funciona de forma contínua e autônoma,
que seja capaz de sentir e atuar no ambiente em que se situam, por meio de atuadores e sensores (Russell & Norvig, 2003). Em um robô pode-se, por exemplo, considerar como atuador um motor de passo que permite realizar o movimento de um
braço mecânico e, como sensor, uma câmera de vídeo que permite a visualização
do ambiente.
Widrow e colegas (1973) utilizaram o termo “aprendendo com um crítico” (learning with a critical) para diferenciar o processo de aprendizagem por reforço dos
modelos que aprendem com um professor. É de responsabilidade do crítico avaliar e
codificar o efeito das ações realizadas pelo agente em um sinal numérico que indica
o quanto é “promissor” realizar uma ação particular em um estado. O agente deve
selecionar as ações que maximizem o acumulado do sinal de recompensa que recebe ao longo do tempo, pois ações que o levam para estados que aparentemente dão
a maior recompensa em um dado momento podem levar a outros que não dão
(Sutton & Barto, 1998).
Dentre todas as tarefas em que a aprendizagem por reforço é utilizada podese destacar o campeonato de futebol de robôs. De acordo com Kitano e colegas
(1995), a iniciativa do campeonato de futebol de robôs ou RoboCup é uma tentativa
criada com o intuito de prover um ambiente complexo e padronizado, onde pesquisadores da área de inteligência artificial e áreas relacionadas possam avaliar e examinar novas tecnologias. Seu objetivo final é desenvolver, até o ano de 2050, um
time de futebol completo composto por robôs humanóides (Kitano & Asada, 1998).
1
O sinal numérico deve ser um número que represente a satisfação do agente em um estado. Normalmente
este número assume valores negativos para punição e positivos para recompensa.
1.2 Motivação
3
O campeonato de futebol de robôs cobre diversas áreas da Inteligência Artificial e robótica, tais como, projeto de agentes autônomos, colaboração entre agentes,
raciocínio em tempo real, sensores em tempo real, aprendizado, visão, controle motor, controle inteligente de robô e outras (Kitano et al., 1997). O escopo do presente
trabalho, no entanto, está restrito ao ambiente de um simulador 2D que abstrai questões mais complexas ligadas à robótica, como movimentação de membros e visão
computacional. Formalmente, o ambiente proporcionado pelo simulador de futebol
de robôs (RoboCup) é definido como: Parcialmente Observável, Estocástico, Episódico2, Dinâmico, Contínuo e Multi-Agente (Russell & Norvig, 2003).
Como apresentado em detalhes por Stone (1998), o simulador de futebol de
robôs é um ambiente totalmente distribuído, multi-agente que possui os jogadores
de um time e os oponentes do outro. O simulador opera em tempos discretos, em
que cada passo de tempo representa 100ms e, se o agente não realizar uma ação
neste intervalo de tempo, o agente perde a chance de executar a ação, tornando o
ciclo perdido (Cheny et al., 2003).
Ainda no simulador de futebol de robôs, estados ocultos são incluídos. Cada
agente tem uma visão parcial do mundo a todo momento: por padrão, a visão de
cada agente é limitada em um ângulo de 90 graus, e a precisão dos objetos vistos
pelo agente diminui com o aumento da distância. Os agentes tem ruído nos sensores e atuadores; o que não permite que eles percebam o mundo exatamente como
ele é (sim como eles vêem), como também não permite que possam afetar o mundo
exatamente como queiram. Adicionalmente, os ciclos de percepção e ações são assíncronos, proibindo o uso de paradigmas tradicionais da IA clássica que utilizam a
percepção como entrada para a ativação de determinadas ações. As oportunidades
de comunicação entre os agentes são limitadas e o agente deve tomar suas decisões em tempo real, o que impede a utilização de algoritmos de busca exaustiva.
Estas características tornam o simulador de futebol de robôs realístico e desafiador.
1.2
Motivação
O simulador de futebol de robôs apresenta desafios para modelos de aprendizagem,
disponibilizando um ambiente estocástico com variáveis de estado contínuas, que
2
Seqüência finita de percepção-ação do agente.
1.2 Motivação
4
inclui a ação do vento, incerteza, ruídos nos sensores e outras que justificam e motivam a utilização do ambiente proporcionado pelo futebol de robôs no teste de novas
abordagens de aprendizado. Estas e outras complexidades tornam o futebol de robôs um simulador de tempo real capaz de prover um ambiente desafiador, ideal para
o teste de novos modelos computacionais.
De posse da bola, um jogador da linha tem fundamentalmente quatro opções:
chutar a gol, conduzir a bola, dar um passe para um companheiro ou dar um drible
no adversário. O chute a gol é um problema tipicamente supervisionado (Oliveira et
al., 2009) enquanto os outros três não produzem resultados diretamente associados
às ações. O interesse pela habilidade do drible deve-se ao fato de que, em uma partida real de futebol, a habilidade de driblar é considerada uma das mais difíceis de
executar e uma das mais eficientes em um movimento de ataque. Com esta habilidade, os jogadores serão capazes de aumentar o desempenho do ataque, permitindo jogadas individuais que podem aumentar as chances de gol.
A aprendizagem por reforço tem sido aplicada com sucesso em ambientes
com grandes quantidades de estados (Tesauro,1994; Crites & Barto, 1996; Bagnell
& Schneider, 2001; Braga & Araújo, 2002; Barto et al., 1990; Stone et al., 2005). Sua
tolerância a ruídos e sua capacidade de generalização em ambientes estocásticos
tornam os modelos de aprendizado por reforço atrativos em ambientes como o proporcionado pelo futebol de robôs (Stone et al., 2005; Riedmiller et al., 2001). Assim
como na aprendizagem supervisionada e não-supervisionada, a qualidade dos dados é de grande importância para a convergência e generalização destes modelos
(Coons et al., 2008).
A Mineração de Dados é uma das aplicações de inteligência artificial que busca extrair informações ou padrões de grandes quantidades de dados armazenados
em bancos de dados, ou trafegando em um fluxo contínuo de dados (Han & Kamber,
2006). Pesquisas recentes mostram que algumas técnicas da mineração de dados
podem ser aplicadas com sucesso na aprendizagem por reforço para (Alhajj & Kaya,
2003; Kheradmandian & Rahmati, 2009), mas estas técnicas não têm sido utilizadas
para determinar quais atributos e ações são relevantes para que o agente consiga
atingir seu objetivo. Contudo, existem casos de sucesso para esta finalidade em outros paradigmas da aprendizagem que incentivam pesquisas nesta área (Matoušek
& Aubrecht, 2006; Lu et al., 1996).
1.3 Contextualização
1.3
5
Contextualização
Recentemente, grande parte das pesquisas, relacionadas com a aprendizagem por reforço, procuram desenvolver algoritmos mais eficientes, porém isso requer o pré-processamento dos dados antes da aplicação dos algoritmos (Lu et al.,
1996; Han & Kamber, 2006). O pré-processamento dos dados é uma etapa da mineração de dados que consiste em tratar os dados contidos em uma base de dados
para que seja alcançado um ganho na eficiência do aprendizado, entre outros aspectos. Na aprendizagem por reforço, a inexistência de bases de dados representa
uma dificuldade para a aplicação de técnicas de mineração de dados.
Apesar das pesquisas com mineração de dados estarem mais relacionadas
na literatura com os paradigmas da aprendizagem supervisionada e nãosupervisionada, Cohen e Maimon (2005) mostram que existem relações entre a aprendizagem por reforço e a mineração de dados. Vieira e colegas (2010) mostraram que é possível a utilização das técnicas de mineração de dados para seleção de
atributos e ações em ambientes da aprendizagem por reforço. A seleção de atributos
e ações permitiu a redução da dimensionalidade do problema, redução no tempo de
convergência e no uso da memória.
Dentre as técnicas de pré-processamento encontradas na mineração de dados, a seleção de atributos feature selection (Han & Kamber, 2006) é uma das mais
importantes. Com a seleção de atributos é possível reduzir a complexidade do problema, aumentar a capacidade de generalização, acelerar o processo de aprendizado, melhorar a interpretabilidade do modelo e reduzir a quantidade de memória e
processamento utilizados. De acordo com a lógica da navalha de Occam (Occam’s
Razor) (Liu & Motoda, 1998), modelos complexos tendem a ser menos eficiente que
os de menor complexidade. Esta lógica expõe a importância em realizar uma análise
qualitativa dos atributos.
Na mineração de dados, a qualidade dos atributos pode ser medida calculando-se o ganho de informação de cada variável. O ganho de informação é uma medida que mede a capacidade de um atributo em classificar os dados de treinamento
(Mitchell, 1997). Outras técnicas de mineração de dados para esta finalidade já foram descritas na literatura (Hall, 1999; Liu & Setiono, 1996).
Na aprendizagem por reforço, a escolha dos atributos do ambiente e ações do
agente é de fundamental importância para seu aprendizado, pois atributos desne-
1.3 Contextualização
6
cessários aumentam o espaço de busca, tornando difícil encontrar uma solução ótima (Coons et al., 2008). Com a remoção das variáveis de menor relevância, de acordo com alguma métrica usada pelas técnicas de seleção de atributos, é possível
obter um ganho significativo no desempenho do modelo (Han & Kamber, 2006).
Na literatura há trabalhos (Cavazos & Moss, 2004; 2006; Stepheson et al.,
2002) que utilizam especialistas no problema para auxiliarem na tarefa de seleção
de atributos. Porém, vale ressaltar que a disponibilidade de um especialista nem
sempre é possível, e em alguns casos o especialista pode não ajudar. Hipoteticamente, se fosse perguntado a um jogador de futebol em quais características do
campo, da bola e do oponente ele está preocupado no momento de um drible, entre
outras, possivelmente a distância do oponente seria uma das principais características. Entretanto, para um robô, a distância da bola poderia ser sua principal característica, pois sem esta variável o robô seria incapaz de realizar um chute já que, no
futebol de robôs, existe uma margem que define uma distância máxima entre o agente e a bola para que seja possível realizar um chute. Se neste ponto as variáveis
mais relevantes do ambiente recebessem um peso maior no treinamento do agente,
os modelos construídos provavelmente teriam desempenhos diferentes.
Outro aspecto de suma importância nos ambientes da aprendizagem por reforço é o espaço de ações disponíveis para o agente. Agentes que possuem grandes quantidades de ações, não necessariamente redundantes, podem prejudicar o
aprendizado tornando a convergência do modelo mais lenta (Riedmiller, 1999). Uma
das soluções para este tipo de problema consiste na transformação das ações de
forma a reduzir o espaço de ações do agente (Stone & Sutton, 2001). Basicamente
esta técnica baseia-se na abstração de um conjunto de ações, geralmente de baixo
nível, em uma única ação de alto nível. No entanto, a desvantagem desta técnica é a
necessidade de um especialista com conhecimentos avançados do problema. Uma
alternativa, naturalmente, seria avaliar todas as ações realizáveis pelo agente, para,
então, remover as ações que não contribuem para o agente alcançar seu objetivo.
A seleção de atributos e ações são apenas algumas das melhorias que podem ser alcançadas com a aplicação de técnicas de mineração de dados em ambientes da aprendizagem por reforço. Outras que podem ser realizadas são:
 Transformação das variáveis - Estas também fazem parte da etapa
de pré-processamento, e são intensamente utilizadas em problemas da a-
1.4 Objetivos
7
prendizagem supervisionada e não-supervisionada. As técnicas para transformação das variáveis buscam meios para modificar (transformar) as variáveis de entrada de um modelo, com o objetivo de obter atributos de melhor
qualidade (Han & Kamber, 2006).
 Eliminação de atributos correlacionados (Agakov et al., 2006; Cavazos & Moss, 2006) - Esta técnica evita a utilização de atributos redundantes
no aprendizado do modelo. Na aprendizagem por reforço, atributos redundantes podem prejudicar a generalização, aumentar o tempo de convergência e o
consumo de memória e processamento.
A maior dificuldade da seleção automática de atributos, sem o uso das técnicas de mineração de dados, é o crescimento exponencial do tempo necessário para
encontrar um conjunto ótimo de atributos, uma vez que não seria possível encontrar
a seleção ótima sem o teste de todas as possíveis combinações dos
levantes escolhidos de todos os
vezes. Se a quantidade dos
atributos re-
atributos, i.e., aplicando o critério
atributos relevantes não é conhecida, o tempo total
necessário para encontrar a melhor combinação de atributos será proporcional a
.
1.4
Objetivos
O principal objetivo deste trabalho é propor a utilização de técnicas de mineração de
dados para a seleção de atributos e ações dos ambientes da aprendizagem por reforço, visando a melhorar o desempenho dos modelos utilizados e reduzir o consumo de memória e processamento.
Outro objetivo considerado é a utilização da aprendizagem por reforço no futebol de robôs para a realização do drible. Como forma de incorporar conhecimento,
os agentes utilizam as ações de nível intermediário disponíveis pelo time CMUnited99 (Boer & Kok, 2002), ao invés das ações primitivas do simulador. As ações utilizadas são:
 Hold_BALL() - Posiciona a bola em um ângulo em relação ao corpo do
agente que mantenha a bola o mais distante possível do oponente.
1.5 Contribuições
8
 Conduzir(ângulo, velocidade) - Conduz a bola com um ângulo entre
graus em 3 possíveis velocidades: devagar, normal e rápido. O
ângulo de condução deve ser múltiplo de 5 graus para diminuir a complexidade do problema.
 Intercept() - Procura e intercepta a bola. Esta função é chamada
quando a bola está a uma distância maior que a permitida para realizar um
chute.
Através destas ações deseja-se criar uma nova ação de alto-nível chamada
drible() que possibilite o agente driblar o oponente.
1.5
Contribuições
Este trabalho contribui demonstrando que a aprendizagem por reforço pode ser aplicada com sucesso na realização do drible, um problema de grande complexidade e
pouco abordado na literatura. A complexidade citada diz respeito ao tamanho do espaço de busca que é aumentado proporcionalmente em função da quantidade de
ações e estados do ambiente. Por exemplo, em um ambiente episódico de
dos e
esta-
ações, considerando-se que um estado não seja revisitado no mesmo epi-
sódio, o tempo necessário para o agente encontrar a melhor solução no pior caso é
. Riedmiller (1999) investigou a utilização das redes neurais em ambientes da
aprendizagem por reforço, constatando um aumento no tempo de convergência destes modelos, cerca de 400% (144.000s), devido ao aumento da quantidade de ações. Os experimentos realizados acerca desta etapa investigarão a capacidade de
convergência do modelo utilizado por este trabalho em ambientes complexos com
grande quantidade de ações e estados. O ambiente do drible é composto de 23 variáveis de estado contínuas e, 113 ações realizáveis, o que torna o espaço de busca
do agente alto e desafiador.
A principal contribuição mostra que as técnicas de mineração de dados podem, também, ser utilizadas com sucesso em problemas da aprendizagem por reforço. Uma das vantagens da utilização das técnicas de mineração de dados para a
identificação dos atributos e ações mais relevantes de um determinado problema é a
realização de uma análise estatística das variáveis de forma independente do espe-
1.6 Descrição da Dissertação
9
cialista no domínio. Identificando e selecionando as melhores variáveis e ações de
acordo com alguma métrica estabelecida previamente, é possível melhorar a capacidade de generalização, diminuindo o tempo de convergência, aumentando a interpretabilidade e reduzindo o consumo de processamento e memória.
1.6
Descrição da Dissertação
Neste trabalho será apresentado o desenvolvimento de um modelo baseado na aprendizagem por reforço para o controle de um agente inserido no ambiente provido
pelo simulador de futebol de robôs (RoboCup). Este modelo será utilizado no treinamento do agente para aprender a realizar o drible.
O modelo utilizado possui características temporais e foi combinado com um
aproximador linear, conhecido como tile-coding (Sutton & Barto, 1998), para permitir
a sua utilização em ambientes de estados infinitos. O treinamento do modelo ocorre
mediante o cálculo das estimativas de recompensa para cada estado visitado, e tem
convergência garantida para uma política ótima, se o agente visitar os estados infinitamente (Sutton & Barto, 1998). Terminado o treinamento, as estimativas de recompensa de cada estado estarão armazenadas na memória do agente e, portanto, as
próximas ações do agente serão determinadas por uma busca gulosa (Mitchell,
1997) pelas entradas da tabela de estimativas (Sutton & Barto, 1998).
O agente será treinado contra o oponente do time UvA Trilearn (Boer & Kok,
2002). Este time foi escolhido devido a sua reputação, e disponibilização do código
fonte e do código binário.
O presente trabalho avaliará 3 métodos para identificar e selecionar os atributos mais relevantes e 2 medidas, confiança e suporte, normalmente utilizadas na
avaliação de regras de associação, para identificar e selecionar as ações mais relevantes.
1.7
Organização da Dissertação
Esta dissertação está organizada em seis capítulos, incluindo esta introdução.
1.7 Organização da Dissertação
10
O Capítulo 2 está relacionado ao desenvolvimento do modelo utilizando o método de aprendizagem temporal combinado com a técnica de tile-coding para permitir a generalização.
O Capítulo 3 mostra como o ambiente de teste foi modelado para um problema da aprendizagem por reforço e como o modelo criado foi estruturado para solucioná-lo. Ainda neste capítulo serão mostradas informações importantes para a
construção do ambiente de treinamento, tais como as características técnicas dos
jogadores, do campo, do técnico e da bola.
O Capítulo 4 descreve as técnicas de mineração de dados, e como estas podem ser utilizadas em ambientes da aprendizagem por reforço.
O Capítulo 5 mostra os experimentos, seus resultados e sua interpretação
baseada em análise estatística do modelo utilizando o problema do drible como estudo de caso.
O Capítulo 6 apresenta as conclusões da dissertação, suas limitações e ressalta as perspectivas de trabalhos futuros.
O Apêndice A revisa o conceito de programação dinâmica, enfatizando aspectos importantes para a consolidação dos principais métodos da aprendizagem por
reforço.
O Apêndice B revisa os modelos baseados no gradiente descendente e como
podem ser combinados com os algoritmos da aprendizagem por reforço.
Capítulo 2
Modelo Computacional
Os tradicionais modelos da aprendizagem por reforço baseados em tabelas são incapazes de generalizar (Sutton & Barto, 1998). Algumas técnicas vêm sendo combinadas em problemas de domínios de larga escala para possibilitar a generalização.
O jogo de gamão (Tesauro, 1994), controle de elevadores (Crites & Barto, 1996),
controle de helicóptero (Bagnell & Schneider, 2001), balanceamento da polia (Barto
et al., 1990), navegação de robôs (Braga & Araújo, 2002) e o KeepAway da RoboCup (Stone et al., 2005) são exemplos de combinações.
Este trabalho utilizou um aproximador linear, conhecido como Tile Coding
(CMAC) (Albus, 1975), construído com base no funcionamento do cerebelo, para
obter a generalização desejada. A motivação do uso deste aproximador deve-se à
teoria que o cerebelo é responsável pelo controle de membros. O funcionamento do
cerebelo tem características semelhantes ao aproximador linear chamado Perceptron (Albus, 1975) que é a base para o funcionamento do CMAC.
Este capítulo divide-se em quatro seções com os conceitos colocados de forma seqüencial: A Seção 2.1 apresenta dois dos principais algoritmos da aprendizagem por reforço. A Seção 2.2 realiza uma revisão na literatura e introduz o conceito
de aproximação de funções. A Seção 2.3 mostra a variante do algoritmo LMS para
construir o modelo linear utilizado.
11
2.1 Aprendizado por Diferença Temporal
2.1
12
Aprendizado por Diferença Temporal
O método de aprendizagem por Diferença Temporal, também chamado de TD
(Temporal Difference) (Sutton, 1988), surgiu com a combinação de idéias retiradas
de dois métodos da aprendizagem por reforço: Monte Carlo e a programação dinâmica (Sutton & Barto, 1998).
A vantagem dos métodos temporais deve-se ao seu processo de aprendizagem incremental. Diferente do método Monte Carlo, neste tipo de aprendizagem o
valor de um estado, ou de um par estado-ação, é atualizado imediatamente após a
ação do agente. Da mesma forma que a programação dinâmica, o aprendizado por
diferença temporal atualiza o valor de um estado utilizando o valor do seu estado
sucessor e da recompensa imediata. Sendo assim, não é preciso esperar até o fim
do episódio para que a aprendizagem aconteça. Esta característica possibilita utilizar
os métodos temporais em ambientes que não sejam episódicos. Isto traz uma grande vantagem em relação ao método Monte Carlo, pois em alguns problemas os episódios podem ser longos tornando a aprendizagem lenta. Em outras palavras a atualização da função valor-estado para um estado
pode ser definida como:
( 2.1)
onde
e
prendizado,
são respectivamente o valor dos estados
é o estado sucessor a
e
e
,
é a taxa de a-
é o desconto. O valor do parâmetro
de-
ve ser maior que zero e menor que um. De acordo com Sutton & Barto (1998),
de-
ve diminuir com o tempo para impedir que as estimativas continuem variando em
resposta as recompensas mais recentes recebidas.
O termo desconto apresentado na Equação 2.1 refere-se a um termo que determina a importância das recompensas futuras (Sutton & Barto, 1998). Se
for igual
a zero tornará o agente mais oportunista, considerando apenas as recompensas imediatas. Desta forma o agente aprenderá a escolher
o que pode diminuir o retorno. À medida que
para maximizar apenas
se aproxima de um, o agente dará
mais importância às recompensas futuras de forma a maximizar o retorno.
A Equação 2.1 tem uma semelhança com a Equação A.14 como mostrado a
seguir:
2.1 Aprendizado por Diferença Temporal
13
(2.2)
Uma possível forma de interpretar a Equação A.17 é dada a seguir:
( 2.3)
onde
para o método Monte Carlo é
. Para
e
enquanto que para o método TD é
a convergência é garantida pela lei dos
grandes números, mas não para o caso em que
é uma constante e
. No entanto, Dayan (1992) provou que para qualquer política fixa , o método TD também converge para
com probabilidade
se o parâmetro
decair
com o tempo.
Antes de apresentar a variação do algoritmo TD para os métodos on-policy e
off-policy, a Subsubseção 2.1.1 apresenta um mecanismo chamado de eligibility traces que se combinado com os algoritmos TD pode proporcionar um aumento na eficiência do aprendizado.
2.1.1 Rastro de Elegibilidade
A técnica eligibility trace (rastro de elegibilidade) torna possível retornar para os estados passados uma parcela da recompensa recebida em um estado sucessor. A
Figura 2.1 ilustra a mecânica da técnica.
2.1 Aprendizado por Diferença Temporal
14
Figura 2.1 Visão mecânica da técnica de elegibility traces. Fonte: (Sutton & Barto,
1998)
Este método utiliza uma memória adicional associada a cada estado
tado por
râmetros
deno-
, onde em cada interação seu valor é diminuído, em função de dois pae
e, incrementado em
placing traces) quando
nir a atualização de
(accumulating traces) ou substituído por
(re-
é o estado sucessor de . Em outros termos, pode-se defiem um instante de tempo , como segue:
(accumulating traces)
( 2.4)
ou (replacing traces)
( 2.5)
onde
é o fator de desconto e
parâmetro
é o parâmetro para redução gradual de
. O
determina a contribuição dos estados passados para que ao agente
resultar-se em um estado
.
2.1.1.1 Sarsa( )
Nesta seção é apresentado o método on-policy combinado com a técnica de elegibility traces, chamado Sarsa( ) (Rummery, 1995). Conforme visto nas seções anteriores os métodos on-policy seguem uma política flexível e a atualização da política é a
mesma utilizada para o controle do agente. A política utilizada pode ser qualquer
uma, mas deve garantir que todos os estados sejam visitados infinitamente.
2.1 Aprendizado por Diferença Temporal
início:
para cada
15
faça
;
;
fim
para cada
faça
inicialize
;
repita
realize a ação e observe e ;
escolha uma ação
seguindo uma política
;
; // Para accumulating traces ou
; // Para replacing traces
para todo
faça
;
;
fim
;
;
até
;
fim
fim
Algoritmo 2.1 Sarsa( )
O Algoritmo 2.1 segue uma política
derivada de Q;
(Seção A.3) para garantir que
os estados não greedy tenham probabilidade de serem selecionados. Um exemplo
de política
babilidade
para o Algoritmo 2.1 é selecionar uma ação greedy com proe com probabilidade
uma ação qualquer. O Algoritmo 2.1 mostra o
pseudocódigo do algoritmo modificado. Conforme apresentado, a estimativa
passa a ser atualizada por:
( 2.6)
onde
( 2.7)
e (accumulating traces)
2.1 Aprendizado por Diferença Temporal
16
( 2.8)
ou (replacing traces)
( 2.9)
O algoritmo Sarsa( ) segue a mesma propriedade do algoritmo TD( ), ou seja, fixando uma política
é possível estimar o valor de
agente siga uma política
ma
e, garantindo que o
assegura a convergência para uma política óti-
.
2.1.1.2 Método Q( )
Q-Learning (Watkins, 1989) é um algoritmo off-policy, baseado na aprendizagem por
diferença temporal, normalmente utilizado em tarefas de controle. Este algoritmo
trabalha com uma matriz de estado-ação que armazena as estimativas de recompensa em se realizar uma ação
em um estado .
Seguindo o conceito da aprendizagem por diferença temporal, a atualização
da estimativa de recompensa de um par estado-ação, dá-se por:
( 2.10)
onde
é a estimativa de recompensa de realizar uma ação
é um parâmetro que define a taxa de aprendizado,
é o fator de desconto e
é a estimativa de recompensa de realizar uma ação
sor a .
em um estado ,
em um estado suces-
2.2 Controle com Aproximador de Funções
início:
para cada
17
faça
;
;
fim
para cada
faça
inicialize
;
repita
realize a ação e observe e ;
escolha uma ação
seguindo uma política
;
;
; // Para accumulating traces ou
; // Para replacing traces
para todo
faça
;
se
então
;
senão
;
fim
;
;
até
Algoritmo 2.2 Q( )
fim
fim
derivada de Q;
O Algoritmo 2.2 mostra o método Q-Learning com a técnica de eligibility traces. Este
método segue uma política de comportamento flexível (e.g.
que a política de estimação continua gulosa (
2.2
) enquanto
).
Controle com Aproximador de Funções
Nas tarefas de controle em ambientes da aprendizagem por reforço, obter a generalização desejada pode ser problemático, pois em grande parte das tarefas alguns
estados nunca serão vivenciados exatamente como antes. Estas tarefas incluem
sensores complexos, como os de uma imagem visual. A solução para este tipo de
problema é a generalização de estados já visitados pelo agente, para estados nunca
vistos anteriormente.
A generalização a partir de exemplos é largamente utilizada em outros paradigmas da aprendizagem, como, por exemplo, a aprendizagem supervisionada. Este
2.2 Controle com Aproximador de Funções
18
tipo de aprendizagem é freqüentemente chamado de aproximação por função, pois
são utilizados exemplos de uma função desconhecida para construir um aproximador de toda função.
Os tradicionais algoritmos da aprendizagem por reforço (Apêndice A) são representados como uma tabela na qual cada entrada representa o valor de estimativa
do par estado-ação. Este tipo de abordagem é limitado em tarefas com pequenos
números de estados e ações devido ao alto consumo de memória e tempo de processamento para preencher a tabela de estimativas. Cada entrada da tabela mantida por estes modelos não compartilha o conhecimento com seus vizinhos, o que não
permite a generalização.
A generalização em ambientes da aprendizagem por reforço é de grande valia, pois em ambientes com variáveis de estado contínuo a quantidade de estados
torna-se infinita, tornando o treinamento dos agentes impraticável devido ao alto
consumo de memória e tempo de processamento para preencher a tabela de estimativas, visto que o agente deve revisitar cada estado infinitamente (ver Apêndice
A). A principal característica da generalização em ambientes da aprendizagem por
reforço é possibilitar que os agentes possam se basear em experiências passadas
para realizar determinadas ações em estados nunca vistos anteriormente pelo agente.
Basicamente, os modelos utilizados na aprendizagem supervisionada e nãosupervisionada, tais como uma rede neural artificial, podem ser combinados com a
aprendizagem por reforço para obter a generalização desejada. Como exemplo desta combinação pode-se citar o trabalho de Tesauro (1994) que consistiu na combinação de uma Rede Neural Artificial Multilayer Perceptron (Rumelhart et al., 1986)
com o algoritmo
para estimar os valores de
. A grande vantagem deste
modelo consiste na capacidade das Redes Neurais Multilayer Perceptron aproximarem qualquer função computável. No entanto, segundo Haykin (1994), a aplicação
das redes neurais artificiais em ambientes da aprendizagem por reforço é problemática devido à facilidade de este aproximador cair em ótimos locais. Boyan & Moore
(1995) e Riedmiller (2005) propõem estratégias para o treinamento da rede neural
em ambientes da aprendizagem por reforço para diminuir as chances de a rede neural cair em ótimos locais.
Barto e colegas (1990) utilizaram elementos adaptativos baseados no funcionamento do neurônio biológico (Perceptron). Neste trabalho o sistema de aprendiza-
2.3 Tile Coding (CMAC)
19
do consiste em dois elementos principais, são eles: ASE (Associative Search Element) e ACE (Adaptive Critic Element). Este modelo possibilita a generalização em
ambientes complexos. Entretanto, assume a existência de um decodificador para
dividir o espaço de estados em regiões (Boxes) representadas por um vetor binário
de
componentes. A desvantagem destes modelos deve-se ao número de regiões
obtidas em problemas de grande complexidade, o que ocasiona um uso excessivo
de memória para armazenar as estimativas de cada região. Outra desvantagem é
que as regiões não compartilham sua experiência com as regiões vizinhas, impedindo a generalização.
Uma alternativa para o modelo de Barto e colegas (1990) é a integração da
técnica CMAC (Cerebellar Model Articulation Controller) proposta por Lin e Kim
(1991). A técnica CMAC (Albus, 1975) distribui o aprendizado entre células de memória ao invés de manter o aprendizado limitado em uma região. Esta técnica utiliza
as variáveis de estado como endereços para células de memórias, o que possibilita
o compartilhamento do aprendizado entre as regiões visitadas.
O trabalho realizado por Stone e colegas (2005) tornou possível verificar a
combinação do algoritmo
com o modelo descrito por Lin e Kim (1991). As
células de memória neste modelo são organizadas em grades (tilings) de dimensão
e tamanho
, sobrepostas com um deslocamento
entre cada, onde
é um
parâmetro que define a quantidade de grades existentes. Stone e colegas (2005)
validaram o modelo experimentalmente aplicando-o no ambiente do futebol de robôs
em um problema específico chamado Keepaway. Neste problema, os jogadores devem manter a posse de bola pelo maior tempo possível sem perder a bola para os
oponentes. Os resultados dos experimentos apresentados foram satisfatórios, já que
em média, os jogadores permaneceram com a posse de bola por 15 segundos contra 8 segundos de uma solução hand-coded.
2.3
Tile Coding (CMAC)
Uma parte do cérebro que parece ser intimamente envolvida nos processos de controle de membros é o cerebelo (Brindley, 1964). A anatomia e os estudos neurofísicos desta parte do cérebro têm sustentado esta teoria (Albus, 1971; Grossman,
1967).
2.3 Tile Coding (CMAC)
20
Segundo Albus (1971), a ativação do cerebelo chega sob a forma de um feedback sensorial e proprioceptiva3 dos músculos, articulações e pele junto com os
comandos de nível superior dos centros do motor que indicam o movimento que é
para ser realizado. De acordo com a teoria, esta entrada consiste em um endereço
no qual o conteúdo contido nestes endereços contém sinais apropriados para os
músculos realizarem o movimento desejado.
O resultado do movimento gera uma nova entrada (estado) e o processo é
repetido, resultando em uma trajetória de um membro pelo espaço. A cada ponto
desta trajetória, o estado do membro é enviado para o cerebelo como entrada e a
memória cerebelar respondem com sinais atuadores para os músculos que movimentam o membro para o próximo ponto da trajetória (Albus, 1975).
O CMAC é um sistema adaptativo utilizado em tarefas de controle. Inspirado
no funcionamento do cerebelo, a aproximação para uma política ótima é computada
pela referência a uma tabela ao invés de soluções matemáticas, tais como as redes
neurais artificiais (Albus, 1975). Este sistema combina as ações com as variáveis de
estado em um vetor de entrada utilizado para endereçar fisicamente posições na
memória onde serão armazenados os valores de estimativa de cada par estadoação.
A vantagem da combinação deste aproximador linear com os tradicionais métodos da aprendizagem por reforço deve-se à possibilidade de este aproximador
permitir o compartilhamento do conhecimento de uma região entre suas vizinhas,
possibilitando a generalização. Determinada a região em que um estado se encontra, as estimativas de suas regiões vizinhas são combinadas por meio de uma soma,
de forma similar ao perceptron.
3
Termo utilizado para nomear a capacidade em reconhecer a localização de um membro no espaço que inclui
sua posição e orientação, a força exercida pelos músculos e a posição de cada parte do corpo às demais, sem
utilizar a visão.
2.3 Tile Coding (CMAC)
21
Figura 2.2 Alguns tilings sobrepostos. Nesta figura cada tile é endereçado por duas
variáveis, e . A generalização é obtida entre as regiões sobrepostas. A sobreposição dos tiles torna possível a experiência obtida em uma região ser compartilhada
entre seus vizinhos.
A técnica de tile-coding consiste em separar o espaço de entrada em regiões
chamadas de tiles. Basicamente, um conjunto de vários tiles é chamado de tiling e
pode haver vários tilings sobrepostos com um deslocamento de
entre si, onde
é a quantidade utilizada. A Figura 2.2 ilustra este conceito.
Cada tile contém uma estimativa daquela região. O valor da estimativa
pas-
sa a ser obtido pela Equação 2.11.
(2.11)
onde
corresponde à estimativa contida no tile dos tilings de
limita, e
no qual o estado
se
é a quantidade de tilings. A atualização de cada tile é dada pela Equação
2.1 com apenas uma alteração no valor de
realizada pelo agente em um estado
que passa a ser
. A ação a ser
é definida por:
(2.12)
A Equação 2.12 garante que o agente sempre realize as ações que aparentemente o levam a uma melhor recompensa ao longo do tempo. Para garantir que o
agente explore uma maior quantidade de estados, uma ação aleatória deve ser selecionada com probabilidade
e uma ação gulosa com probabilidade
, desta
forma é possível diminuir a probabilidade de o agente cair em máximos locais (Seção A.3 na página 103). O Algoritmo A.1 mostra o pseudo-código do CMAC combinado com o algoritmo
.
2.3 Tile Coding (CMAC)
22
início:
;
;
para cada
faça
;
para cada
faça
;
fim
escolha uma ação
repita
;
para cada
faça
seguindo uma política
;
fim
realize a ação , observe a recompensa, , e o próximo estado, ;
;
para cada
faça
;
fim
escolha uma ação
seguindo uma política
;
;
;
;
até
fim
fim
;
Algoritmo 2.3 Versão adaptada do algoritmo
te linear.
para o gradiente descenden-
Capítulo 3
Ambiente de Teste
O ambiente de teste utilizado nos experimentos deste trabalho é descrito neste capítulo. Antes da apresentação do ambiente de teste as características mais elementares do simulador e do agente são apresentadas nas Seções 3.1 e 3.2, respectivamente.
A Seção 3.3 mostra como o ambiente de teste foi modelado. Ainda nesta seção, será apresentado o comportamento dos oponentes utilizados no treinamento e
como o agente foi implementado para treinar o drible. Também é mostrada a importância do treinador (agente responsável em coordenar o time) no treinamento da habilidade de driblar.
3.1
Visão Geral do Simulador
O simulador da RoboCup-2D4 consiste em três componentes principais, são elas
(Boer & Kok, 2002): servidor, logplayer e monitor. O servidor tem papel principal em
uma partida de futebol da RoboCup. Esta componente proporciona um campo de
futebol virtual e é responsável pela simulação de todos os movimentos dos objetos
contidos no campo, que incluem os jogadores, treinadores, bola e ainda um juiz que
controla a partida de acordo com as regras do jogo.
Os jogadores são controlados por programas cliente (cérebro dos jogadores)
que se conectam ao servidor via protocolo UDP/IP5. Estas conexões são individuais
e estão associadas a um único jogador. Usando esta conexão é possível enviar solicitações ao servidor para executar uma ação específica (e.g. chutar a bola), como
também receber informações do estado do ambiente. Contudo, a comunicação dire4
Disponível em: http://sourceforge.net/projects/sserver/develop
Protocolo de comunicação não orientado para conexão. Este protocolo não garante a entrega dos dados para
o destino.
5
23
3.1 Visão Geral do Simulador
24
ta entre os jogadores não é permitida. Para isto, o agente deve se comunicar com os
outros agentes através dos comandos say (falar) e hear (escutar) enviados diretamente para o servidor que restringe esta comunicação. O servidor controla a partida
em instantes de tempo discreto. Cada instante de tempo, ou ciclo, possui 100ms e,
devido à característica de comunicação assíncrona, o servidor não espera pela ação
de um cliente para passar para o próximo instante de tempo. Sendo assim, se neste
intervalo de tempo o cliente não executar nenhuma ação, o ciclo será perdido.
O simulador também inclui um monitor para visualizar a partida de futebol. O
monitor e o servidor são conectados via protocolo UDP/IP. Depois de realizada a
conexão, o monitor passa a atualizar graficamente as informações do estado do ambiente enviadas pelo servidor. A Figura 3.1 mostra a execução do monitor.
Figura 3.1 Monitor.
A última componente do simulador da RoboCup é o logplayer. O logplayer é
responsável em reproduzir uma partida de futebol da RoboCup armazenada em disco. Esta ferramenta é útil para analisar as jogadas de um time em questão. Entre as
funções disponíveis pela ferramenta pode-se destacar a redução e o aumento da
3.2 Visão Geral do Agente
25
velocidade de reprodução, avanço na reprodução para uma jogada específica e repetição.
Figura 3.2 Estrutura do Agente.
Figura 3.3 Posições de todas as linhas e bandeiras do campo.
3.2
Visão Geral do Agente
Cada jogador é composto de um corpo e um pescoço, e são controlados de forma
independente pelo programa cliente. A representação gráfica de um jogador é mostrada na Figura 3.2. O pescoço determina para onde o agente está olhando em um
dado momento e a posição do corpo é a orientação do agente.
Os sensores dos agentes estão divididos em sensores visuais, corporais e
auditivos (Boer & Kok, 2002). Estes sensores são detalhados nos tópicos a seguir.
3.2 Visão Geral do Agente
26
3.2.1 Sensor Visual
O sensor visual detecta as informações visuais do campo como distância e direção
dos objetos. Estas informações são enviadas pelo servidor automaticamente a cada
send_step ms. Send_step é um parâmetro do servidor que determina a freqüência
com que o servidor envia as informações dos objetos (jogadores e bola) ao agente.
O sensor visual também funciona como um sensor de proximidade, vendo os objetos
que estão atrás do agente, mas só se estiverem a uma distância máxima visible_distance. Visible_distance é uma constante definida antes do inicio da partida.
Por padrão, visible_distance tem valor 3 (metros).
A informação sensorial enviada para o agente, como distância e ângulo, são
relativas ao agente. A informação relativa deve ser convertida em informação global
pelo agente. Para facilitar esta conversão, foram colocadas bandeiras e linhas dentro e nos limites do campo. A Figura 3.3 mostra o campo com todas as bandeiras e
linhas. Combinando a posição global das bandeiras no campo com a posição relativa dos objetos, o agente pode determinar sua posição global e a dos outros objetos
no campo.
É permitido para o agente controlar a freqüência de atualização, qualidade e
limite de visão do seu sensor visual. A freqüência de atualização é obtida em função
dos parâmetros view_width_factor, send_step e view_quality_factor. O cálculo realizado para determinar a nova freqüência é (Boer & Kok, 2002):
(3.1)
onde
é o novo intervalo de tempo no qual o servidor envia as infor-
mações
visuais
do
agente,
é
o
intervalo
de
tempo
normal,
determina a largura do campo de visão do agente e
indica a qualidade da visão do agente.
Os parâmetros
e
devem assumir va-
lores pré-determinados pelo simulador. Estes valores são apresentados na tabela a
seguir:
3.2 Visão Geral do Agente
27
Tabela 3.1 Possíveis valores para os parâmetros view_width_factor e view_quality_factor.
Parâmetro
Valor
0.5
Visão estreita (45o)
1
Visão normal (90o)
2
Visão larga (180o)
view_width_factor
view_quality_factor
Descrição
0.5
1
Qualidade baixa
Qualidade alta
Figura 3.4 Campo de visão do agente. Os objetos são representados pelos círculos
pretos, onde a, e, c, d e f são jogadores, g é o goleiro e b é a bola. Os objetos são
vistos pelo agente se estiverem dentro do seu ângulo de visão determinado por view_angle, o jogador a, no entanto, pode ser sentido pelo agente. O goleiro g e a bola b não são vistos pelo agente. Unum_far_length, unum_too_far_length, team_far_length e team_too_far_length são constantes que representam a distância
de um objeto e, por padrão, são definidos como 20, 30, 40 e 60 (metros), respectivamente. Fonte: (Stone, 1998).
Modificando o parâmetro
afeta diretamente a sensibilidade
da visão do agente da seguinte forma:

Se
for 0.5, o agente consegue somente enxergar, inde-
pendente da distância, apenas o nome do objeto e a direção do objeto.

Se
for 1, o agente consegue enxergar mais detalhes dos
objetos, mas com a seguinte restrição: com o aumento da distância entre o
agente e um dado objeto, a quantidade de detalhes vistos pelo agente é re-
3.2 Visão Geral do Agente
duzida. Seja
28
a distância entre o agente e um objeto e
,
,
,
constantes que
discretizam a distância entre os objetos e o agente conforme ilustrado na Figura 3.4, os detalhes enxergados pelo agente são determinados como segue:
- Se
, então o agente é capaz de visualizar o
número do uniforme do jogador e o nome do time ao qual pertence o
jogador. Ainda é possível visualizar: distância, direção, variação da direção do corpo e pescoço e, a direção do corpo e pescoço.
- Se
, então o agente é
capaz de saber a distância e direção do jogador com probabilidade 1.
No entanto, a probabilidade com que o agente consegue notar a variação da direção do corpo e pescoço diminui linearmente de 1 até 0 a
medida que
aumenta.
- Se
, então o agente não pode determinar
a variação da direção do corpo e pescoço do jogador, mas pode determinar a distância e direção do jogador.
3.2.2 Sensores Auditivos
O sensor auditivo do agente detecta mensagens enviadas pelo treinador ou pelos
outros jogadores do mesmo time ou do time adversário. As mensagens são limitadas
por padrão em 512 bytes, e é o único meio de comunicação entre os agentes. O simulador restringe a capacidade auditiva de cada agente. Agentes não conseguem
escutar mensagens originadas de jogadores que estão a uma distância máxima indicada pela constante audio_cut_distance.
Outra restrição deste sensor limita a quantidade de mensagens que um agente pode escutar em um intervalo de tempo. Cada vez que o agente recebe uma
mensagem, sua capacidade auditiva é diminuída pela constante hear_decay. O servidor mantém uma variável
agente. Inicialmente
que conta a quantidade de mensagens recebidas pelo
é igual ao seu valor máximo (hear_max). Esta variável indica
sua capacidade auditiva e quando
atinge seu valor mínimo (zero) o agente fica
impossibilitado de receber novas mensagens. A cada ciclo de tempo, a variável
é
3.2 Visão Geral do Agente
29
incrementada hear_inc vezes e o agente pode voltar a receber mensagens quando
.
3.2.3 Sensores Corporais
Os sensores corporais detectam a informação física do agente, tais como energia,
velocidade do agente, ângulo do pescoço e outros. Uma descrição de todas as informações obtidas através dos sensores corporais é resumida na Tabela 3.2. As informações dos sensores corporais são enviadas ao agente a cada sense_body_step
ms (por padrão sense_body_step é igual a 100 ms).
Tabela 3.2 Descrição dos sensores corporais do agente.
Sensor
view_quality
Descrição
Qualidade da visão do agente. Pode assumir os valores high (alta) ou low (baixa).
Valor Padrão
high
Largura do cone que representa a visão do
view_width
agente. Pode assumir valores narrow (es-
normal
treito), normal ou wide (largo)
stamina
effort
amountOfSpeed
Número real positivo representando a energia atual do agente.
Número real positivo representando o esforço atual do agente.
Representa a velocidade atual do agente.
directionOfSpeed Representa a direção do agente.
neckAngle
Representa o ângulo do pescoço em relação ao seu corpo.
-
-
Dois sensores apresentados na Tabela 3.2 merecem atenção, são eles: stamina e effort. O simulador impede que os jogadores fiquem correndo constantemente no campo na sua velocidade máxima. Para controlar o quanto um jogador pode
correr, o servidor implementa o conceito de stamina (energia) e effort (esforço). Agentes que correm o tempo todo gastam sua energia (stamina) mais rapidamente do
que aqueles que correm somente quando necessário.
3.3 Modelagem do Ambiente do Drible
30
No inicio da partida o valor de stamina é igual à stamina_max. A cada ciclo de
tempo o valor de stamina é recuperado de acordo com a seguinte equação:
(3.2)
onde stamina_inc_max é uma constante que determina a taxa de recuperação da
energia (stamina) e recovery é uma variável que diminui quando o valor de stamina
é menor que
, onde recover_dec_thr é uma cons-
tante do simulador. É importante citar que o valor de recovery não é recuperado durante a partida. Se recovery é decrementada, o tempo de recuperação de stamina
será maior.
Apesar de a variável stamina representar a energia do agente, é a variável
effort que determinará o esforço que o agente pode aplicar em uma corrida. As variáveis stamina e effort estão relacionados como segue:
1. effort somente será decrementado quando
, onde
stamina for menor que
é uma constante do si-
mulador.
2. effort
somente
será
incrementado
quando
, onde
stamina
for
maior
que
é uma constante do si-
mulador.
3.3
Modelagem do Ambiente do Drible
Neste trabalho o drible é definido como a habilidade de o jogador conduzir a bola
entre os oponentes sem perder a posse até um ponto específico do campo. Durante
o processo de drible o agente deve aprender a selecionar entre as possíveis ações,
as com maior probabilidade de sucesso, cujo objetivo é induzir o oponente a uma
determinada posição que favoreça a realização do drible.
Em alguns artigos encontrados na literatura o drible é tratado como a habilidade do jogador apenas conduzir a bola o que não é verdade. Em outras palavras
um movimento é considerado como sendo um drible se:
(3.3)
e
3.3 Modelagem do Ambiente do Drible
31
(3.4)
onde
é a posição em metros do jogador no eixo ,
eixo
do oponente, é o instante de tempo, e entre e
é a posição em metros no
deve existir uma se-
quência de ações que torne possível o agente realizar o drible.
O agente deve iniciar um episódio em uma posição onde
considerado um drible, se em um instante de tempo
sar seu oponente, i.e., se sua posição no eixo
). A constante
. Será
, o agente conseguir pas-
for maior (
(50cm) define uma distância mínima que o agente deve manter
do seu oponente após o drible.
Figura 3.5 Estados finais de um episódio. (a) Agente passou o oponente, mas o estado final não aparenta ser um drible. (b) Agente passou o oponente deixando-o atrás do seu corpo. Neste caso, o estado final aparenta mais ser um drible.
A Figura 3.5a mostra o estado final de um episódio que satisfaz apenas a Equação 3.3. Neste caso, a figura dá a impressão de que o agente correu do oponente passando-o sem driblar. A Equação 3.4 garante que casos como este não ocorram freqüentemente. Assim, para ser recompensado, é necessário que o agente enfrente o oponente “encarando a marcação”. A Figura 3.5b mostra o estado final de
um episódio que satisfaz as Equações 3.3 e 3.4.
As seguintes equações asseguram a posse de bola do agente:
(3.5)
onde
é a norma euclidiana,
é a margem de chute e
,
e
são vetores
com as coordenadas relativas ao campo em metros da bola, do agente e do oponente, respectivamente.
O ambiente de treinamento é modelado conforme apresentado na Figura 3.6.
3.3 Modelagem do Ambiente do Drible
32
Figura 3.6 Ambiente de treinamento
O objetivo do agente é satisfazer as Equações 3.3 e 3.4 sem que o mesmo ultrapasse os limites da região de drible, representados pelas linhas mais claras na
Figura 3.6. A linha mais escura é considerada como o fim da região de drible e se o
agente ultrapassá-la deverá ser recompensado mesmo não satisfazendo as Equações 3.3 e 3.4 do drible. A localização da região de drible é escolhida aleatoriamente
no inicio do drible. Isto garante que o agente não se limite apenas a uma região do
campo para realizar o drible.
O episódio é reiniciado e o agente é punido se exceder os limites da região
representada pelas linhas brancas ou, se a Equação 3.5 for
. A posição do o-
ponente é aleatorizada a cada episódio, e a posição do agente é fixa no inicio da
região do drible.
A representação do ambiente para o agente é dado através de 23 variáveis
descritas na Tabela 3.4. As 110 ações realizáveis pelo agente são descritas na Tabela 3.3.
Tabela 3.3 Ações realizáveis pelo agente.
Ação
Descrição
Conduzir(ângulo,
Conduz a bola com um ângulo entre -90 e 90 em 3 possíveis
velocidade)
velocidades: lento, normal e rápido. O ângulo de condução
deve ser múltiplo de 5 incluindo o zero.
Hold_BALL( )
Coloca a bola próximo ao corpo do agente em um ângulo que
mantenha a bola o mais distante do oponente.
Intercept( )
Intercepta a bola.
3.3 Modelagem do Ambiente do Drible
33
Tabela 3.4 Representação do ambiente em 23 variáveis contínuas
Variável
Descrição
aVelX
Velocidade do agente em relação ao eixo x.
aVelY
Velocidade do agente em relação ao eixo y.
bVel
Velocidade relativa da bola.
oVelX
Velocidade do oponente em relação ao eixo x.
oVelY
Velocidade do oponente em relação ao eixo y.
bDist
Distância entre o agente e a bola em metros.
oDist
Distância entre o agente e o oponente em metros.
oBDist
Distância entre o oponente e a bola em metros.
aSD
Distância entre a posição inicial do agente e o agente em metros.
oSD
Distância entre a posição inicial do agente e o oponente em metros.
bAngle
oBAngle
oAngle
Ângulo da bola em relação ao corpo do agente.
Ângulo da bola em relação ao corpo do oponente.
Ângulo do oponente em relação ao corpo do agente.
aSA
Ângulo da posição inicial do agente em relação ao agente.
oSA
Ângulo da posição inicial do agente em relação ao oponente
aBodyA
Ângulo da posição inicial do agente em relação ao corpo do agente.
ballDir
Ângulo que indica a direção da bola.
bPosX
Posição da bola no eixo x.
bPosY
Posição da bola no eixo y.
oPosX
Posição do oponente no eixo x.
oPosY
Posição do oponente no eixo y.
aPosX
Posição do agente no eixo x.
aPosY
Posição do agente no eixo y.
O espaço de ações
do agente para um estado
foi definido como segue:
(3.6)
onde
é a margem de chute definido nos parâmetros do servidor da RoboCup.
Neste trabalho, a cada passo de tempo, o agente foi recompensado por
no fim de cada episódio por
conseguiu realizar o drible.
se o agente realizou o drible e por
e
se o agente não
3.3 Modelagem do Ambiente do Drible
34
3.3.1 Treinador
O simulador da RoboCup permite a utilização de um agente especial chamado de
treinador. O treinador possui habilidades especiais, como movimentação de jogadores, visualização do campo e objetos sem ruído em seus sensores, capacidade em
parar e iniciar a partida, substituição dos jogadores e outras.
Existem dois tipos de treinadores, on-line e o off-line. Os treinadores do tipo
on-line são os únicos permitidos em uma partida real da RoboCup. Este tipo de treinador possui algumas limitações se comparado com o treinador off-line. O treinador
on-line tem como única finalidade a coordenação do time com a realização de substituições e no envio de mensagens com instruções para os jogadores. O treinador
ainda pode manter estatísticas do jogo para uma mudança rápida na estratégia do
time.
O treinador off-line é utilizado no treinamento de jogadas ensaiadas do time
ou no treinamento de alguma habilidade específica, como o drible. Neste trabalho o
treinador off-line faz o papel do crítico. É ele o responsável em informar ao agente se
o episódio terminou ou não em sucesso. Ao fim de cada episódio o treinador é responsável em mover os jogadores para suas posições iniciais, conforme descrito na
Seção 3.3.
3.3.2 Comportamento dos Oponentes
Os dois times utilizados como oponentes, no treinamento do agente, são descritos
nos próximos tópicos. O time UvA Trilearn contém uma detalhada documentação da
implementação de suas funcionalidades básicas. Esta documentação é apresentada
na dissertação de mestrado de Boer & Kok (2002).
A Tabela 3.5 mostra o resultado classificatório do times UvA Trilearn nas competições German Open e Robocup.Os resultados apresentados mostram que os times
utilizados possuem uma boa estratégia de jogo, se comparado com os outros times
existentes.
3.3 Modelagem do Ambiente do Drible
35
Tabela 3.5 Resultado das competições German Open e RoboCup realizadas entre
2001 e 2004. O time UvA Trilearn obteve 3 vitórias no torneio German Open e uma
vitória no torneio da RoboCup.
Torneio
Classificação
Ano
German Open
5o
2001
RoboCup
4o
2001
German Open
1o
2002
RoboCup
4o
2002
German Open
1o
2003
RoboCup
1o
2003
German Open
1o
2004
RoboCup
7o
2004
3.3.2.1 Time UvA Trilearn
A habilidade de interceptar a bola do time UvA Trilearn baseia-se no método analítico apresentado em (Stone, 1998).
intercept( )
inicio
;
se
então retorne
;
;
repita
;
;
;
até
ou
se
retorne
;
então
;
senão retorne
fim
;
Algoritmo 3.1 Interceptação da bola
3.3 Modelagem do Ambiente do Drible
36
O Algoritmo 3.1 mostra o pseudocódigo da habilidade de interceptar a bola
implementada pelo time UvA Trilearn.
No método analítico a estimativa da velocidade da bola é realizada através de
métodos preditivos que utilizam as posições passadas da bola. Os futuros movimentos da bola são previstos baseando-se em sua velocidade estimada. Os métodos
preditivos utilizados no Algoritmo 3.1 (predictGlobPosAfterNrCycles e predictNrCyclesToPoint) são utilizados para prever o futuro estado dos objetos dinâmicos contidos no campo, estes objetos incluem a bola e os oponentes. O time UvA Trilearn
não utiliza a previsão para determinar as futuras ações dos oponentes, concentrando apenas na previsão da posição da bola.
Os métodos preditivos utilizados no Algoritmo 3.1 são: predictGlobPosAfterNrCycles e predictNrCyclesToPoint. O primeiro método, predictGlobPosAfterNrCycles, realiza a predição da posição de um objeto após uma determinada
quantidade de ciclos. O segundo método preditivo, predictNrCyclesToPoint, realiza
a previsão de quantos ciclos serão necessário para o agente mover-se para a posição especificada.
3.3.3 Implementação do Agente
Os algoritmos da aprendizagem por reforço apresentados no Apêndice A assumem
que a interação entre o agente e o ambiente é síncrona. Em interações síncronas, o
agente e o ambiente estão em perfeita sincronia, tanto que o ambiente somente é
atualizado após a ação do agente. Enquanto esta ação não é realizada nada acontece, o tempo para. Por exemplo, se a interação entre os jogadores e o simulador de
futebol de robôs fosse síncrona, o simulador só iria avançar para o próximo instante
de tempo após a ação de todos os jogadores.
Em uma interação assíncrona, o agente e o ambiente não estão em perfeita
sincronia, o tempo nunca é parado como acontece na interação síncrona. Neste tipo
de interação o simulador é quem dá o tempo e o agente deve acompanhar. Este tipo
de interação é problemático em problemas multiagentes ou onde a dinâmica do ambiente depende do tempo. Isto porque o ambiente sofre constantes modificações
devido à ação dos outros agentes, ou da existência de objetos que variam com o
tempo (e.g. aceleração da bola).
3.3 Modelagem do Ambiente do Drible
37
Como descrito na Seção 3.1 o simulador recebe as ações do agente de forma
assíncrona operando em instantes de tempo discretos de 100ms, onde a cada instante de tempo o agente pode realizar uma ação. Se neste intervalo de tempo o agente não executar nenhuma ação, o ciclo é perdido e o agente perderá a chance de
executar sua ação. Devido a estas características a implementação do modelo foi
dividido em 3 funções principais: startEpisode(), step() e endEpisode().
A função startEpisode() é chamada no inicio do episódio. Esta função apenas
seleciona a primeira ação do episódio seguindo uma política
. A imple-
mentação desta função é apresentada a seguir:
Após o primeiro instante de tempo do episódio, a função step() é chamada a
cada ciclo do simulador. Esta função recebe a recompensa da última ação, escolhe
a próxima ação seguindo uma política
e atualiza a política que está sen-
do seguida. O Algoritmo 3.3 apresenta a implementação da função step().
O último instante de tempo do episódio não deve ser executado na função
step(), pois o agente não deve selecionar uma próxima ação (característica da função step()). Sendo assim, a função endEpisode() é chamada ao invés da função
step(). Na função endEpisode() o agente recebe a recompensa da última ação realizada e atualiza a política seguida. Esta última função é apresentada no Algoritmo
3.4.
startEpisode( )
;
;
para toda
faça
;
fim
;
;
fim
Algoritmo 3.2 Implementação do Agente: Função startEpisode().
3.3 Modelagem do Ambiente do Drible
38
step( )
;
;
;
para toda
faça
;
fim
;
para todo tile
faça
;
fim
;
para todo tile faça
;
;
fim
;
;
;
fim
Algoritmo 3.3 Implementação do Agente: Função step().
endEpisode( )
se
;
senão
então
;
;
para todo tile faça
;
fim
fim
Algoritmo 3.4 Implementação do Agente: Função endEpisode().
Capítulo 4
Mineração de Dados na Aprendizagem por Reforço
A seleção de atributos é um processo para identificar e remover atributos irrelevantes e/ou redundantes. Este processo reduz a dimensionalidade do problema fazendo
com que os algoritmos de aprendizagem possam operar de maneira eficiente e rápida. Em alguns casos, a precisão dos algoritmos de aprendizagem pode ser aumentada; em outros casos, o modelo torna-se mais compacto e, portanto, são mais rápidos e fáceis de interpretar.
Pesquisas mostram que o desempenho da maioria dos algoritmos de aprendizagem de máquina são afetados por informações irrelevantes e redundantes durante o treinamento. Por exemplo, o algoritmo do vizinho mais próximo (nearest neighbour) é sensível a atributos irrelevantes – o número de exemplos necessários para que o algoritmo alcance uma precisão especificada aumenta exponencialmente
com o aumento de atributos irrelevantes (Langley & Sage, 1994b; Aha et al., 1991).
Outros algoritmos como as árvores de decisão e o C4.5 (Quinlan, 1993; Quinlan,1986) também são sensíveis a atributos irrelevantes e redundantes. Em muitos
casos, removendo os atributos redundantes e irrelevantes é possível aumentar significativamente a eficiência destes algoritmos (Kohavi & John, 1996).
Na aprendizagem por reforço os atributos irrelevantes e redundantes aumentam a dimensionalidade dos dados e o espaço de busca do agente. Se o espaço de
busca do agente é muito grande é possível que o algoritmo nunca 6 convirja para
uma solução. Desta forma, fica evidente a importância da seleção de atributos em
ambientes da aprendizagem por reforço. Sendo assim, deseja-se explorar a política
do agente através do comportamento do agente armazenado em um banco de dados para encontrar as variáveis mais relevantes. Espera-se que as variáveis mais
6
Em um espaço de busca muito grande pode levar anos para encontrar uma solução. Neste caso é considerado
que o algoritmo não converge para uma solução.
39
4.1 Seleção de Atributos
40
relevantes para uma política ( ) também sejam relevantes para outra política ( ), tal
que
.
Neste capítulo são apresentados os princípios de funcionamento dos algorit-
mos de seleção de atributos considerados neste trabalho (Seção 4.1 e as Subseções 4.1.1, 4.1.2 e 4.1.3). A abordagem proposta para a seleção de ações é apresentada na Seção 4.2. A Seção 4.3 mostra a correlação existente entre a aprendizagem por reforço e a mineração de dados. Nesta última seção também é mostrado
como o armazenamento e as transformações dos dados de treinamento do agente
são realizados.
Figura 4.1 Busca exaustiva pelo espaço de atributos. O ponto de partida pode iniciar sem nenhum atributo (visualização top-down) ou com todos atributos (visualização bottom-up).
4.1
Seleção de Atributos
De acordo com Genari et al. (1989), os atributos serão relevantes se seus valores
variam sistematicamente de acordo com o atributo que determina a classe. Em outras palavras, um atributo será útil ou relevante se estiver correlacionado com o atributo que determina a classe das instâncias; caso contrário o atributo é considerado
irrelevante.
4.1 Seleção de Atributos
41
Evidências experimentais encontradas na literatura mostram que é preciso eliminar atributos irrelevantes e redundantes (Langley & Sage, 1994a; Kohavi & John,
1996; Kohavi & Sommerfield, 1995). Desta forma, é possível obter uma melhora na
eficiência dos algoritmos de aprendizagem. Um atributo é dito redundante se existem um ou mais atributos que possuem alto grau de similaridade com ele (intercorrelação). Um conjunto de atributos ideal é aquele cujos atributos possuem um
alto grau de correlação com o atributo classe e uma inter-correlação baixa (Hall,
1999). Deve-se, portanto, maximizar a correlação dos atributos com o atributo classe
e minimizar a inter-correlação entre eles:
(4.1)
e
(4.2)
onde
é um operador que mede a correlação entre dois atributos,
qualquer e
é um atributo
é o atributo classe.
Os algoritmos para a seleção de atributos buscam identificar no conjunto de
atributos um subconjunto de atributos relevantes e não-redundantes. Segundo Langley (1994c), existem quatro operações básicas que afetam a natureza desta busca:
1. Ponto de partida (ver Figura 4.1). A Seleção de um subconjunto inicial de atributos como ponto de partida pode afetar a eficiência da pesquisa. Uma opção
é começar com nenhum atributo e sucessivamente adicioná-los. Neste caso,
a pesquisa segue naturalmente através do espaço de busca (forward through
the search space) (Langley, 1994c). Por outro lado, a pesquisa pode começar
com todos os atributos e, sucessivamente, removê-los. Neste caso, a pesquisa é dita ser retrógrada através do espaço de busca (backward through the
search space) (Langley, 1994c). Outra alternativa é começar em algum lugar
no meio do espaço de busca e passar para o exterior a partir deste ponto.
2. Organização da pesquisa (Langley, 1994c). Uma busca exaustiva pelo espaço de atributos é computacionalmente caro (ver Figura 4.1). Se inicialmente
existir
atributos, então existem
subconjuntos possíveis. Estratégias de
busca heurística são mais viáveis computacionalmente do que os exaustivos,
embora eles não garantam encontrar sempre um subconjunto ótimo de atributos.
4.1 Seleção de Atributos
42
3. Estratégia de avaliação. Como os subconjuntos de atributos são avaliados é o
principal fator dos algoritmos de seleção de atributos. Um paradigma chamado de filtro (Kohavi & John, 1996; Kohavi, 1995) funciona independente de
qualquer algoritmo de aprendizado; atributos indesejáveis são filtrados antes
do inicio da aprendizagem. Estes algoritmos usam heurísticas baseadas em
características gerais dos dados - ao invés de algoritmos de aprendizagem para avaliar os subconjuntos de atributos (Hall, 1999).
4. Critério de parada. Dependendo da estratégia de avaliação, um algoritmo que
seleciona atributos pode parar de adicionar ou remover atributos quando nenhuma das alternativas melhora o desempenho do algoritmo de aprendizagem. Alternativamente, o algoritmo poderá continuar a rever os subconjuntos
de atributos, enquanto não for alcançado um desempenho estabelecido previamente. Outra opção poderia ser a de continuar gerando subconjuntos de
atributos até atingir o extremo oposto do espaço de busca e em seguida, escolher o melhor (Langley, 1994c).
4.1.1 LVF - Las Vegas Filter
Las Vegas é um algoritmo aleatório que sempre retorna os resultados corretos, ou
informa sobre uma possível falha (Liu & Setiono, 1996). Em outras palavras, o algoritmo Las Vegas não se arrisca com a veracidade dos resultados; ele só arrisca nos
recursos utilizados para a computação dos resultados (a casa sempre vence). Os
algoritmos Las Vegas usam a aleatoriedade para guiar sua busca de tal forma que a
solução correta é sempre garantida mesmo quando as piores escolhas são feitas
(Brassard & Bratley, 1996).
O algoritmo LVF (Las Vegas Filter) é uma variação do algoritmo Las Vegas
para a seleção de atributos (Liu & Setiono, 1996). Seu funcionamento é descrito a
seguir: considerando um conjunto de dados que possuam
atributos, o algoritmo
LVF deve gerar um subconjunto aleatório de atributos, , a cada ciclo de execução
do algoritmo. Se o número de atributos ( ) do subconjunto de atributos,
que a quantidade de atributos do subconjunto
possuem os atributos selecionados em
(
, é menor
), então os dados ( ) que
são checados de acordo com o critério de
inconsistência. Se a taxa de inconsistência é menor que , então
.
4.1 Seleção de Atributos
43
O critério de inconsistência é a principal componente do algoritmo LVF (Liu &
Setiono, 1996). O critério indica se o conjunto de atributos reduzidos pode ser aceito.
Isto é, quando a taxa de inconsistência está abaixo de um valor especificado previamente. A taxa de inconsistência é calculada em um processo de três passos. Primeiro, uma contagem dos padrões inconsistentes é realizada. Se dois padrões combinam, exceto pelo rótulo da classe, estes padrões são considerados inconsistentes.
Os padrões inconsistentes devem ser agrupados por suas respectivas classes. Após o agrupamento, deve-se contar separadamente a quantidade de padrões
inconsistentes em cada grupo. O total de padrões inconsistentes será a soma de
todas as instâncias inconsistentes. Por exemplo, para um subconjunto de atributos
selecionados aleatoriamente de um conjunto de treinamento que possui 3 classes,
onde a classe 1 tem
padrões inconsistentes, a classe 2 tem
tentes e a classe 3 tem
( ) será
padrões inconsis-
padrões inconsistentes, o total de padrões inconsistentes
.
No segundo passo determina-se a inconsistência do subconjunto de atributos
escolhido. Esta inconsistência é calculada da seguinte forma. Subtrai do total de padrões inconsistentes ( ) o grupo de classe que obteve o maior número de padrões
inconsistentes, i.e.,
. No terceiro passo deve-se calcular a taxa
de inconsistência definida por:
Liu e Setiono (1996) utilizaram o algoritmo LVF em dois problemas de alta dimensionalidade – o primeiro tinha 65.000 instâncias descritas por 59 atributos; o segundo tinha 5.909 instâncias descritas por 81 atributos. Segundo os autores, o algoritmo LVF foi capaz de reduzir o número de atributos em ambos os problemas em
mais que a metade. Os autores também relatam que, devido à natureza aleatória do
algoritmo, quanto maior o valor do parâmetro MAX melhor serão os resultados obtidos.
As três principais vantagens do algoritmo LVF, são:
1. Simples de implementar;
2. Eficiente, isto é, rápido em obter o resultado;
3. Resultado não é afetado por algoritmos de aprendizagem;
4.1 Seleção de Atributos
44
O Algoritmo 4.1 mostra a implementação do algoritmo LVF.
Entrada:
– Número de tentativas,
– Conjunto de instâncias,
– Número de atributos,
– Taxa de inconsistência mínima permitida
Saída: conjunto de atributos que satisfazem o critério de inconsistência
inicio:
para
até
faça
;
;
se
se
então
então
;
;
;
senão (
)e(
) então
;
fim
fim
Algoritmo 4.1 LVF (Las Vegas Filter)
A principal desvantagem do algoritmo LVF é a impossibilidade do seu uso em
problemas que apresentem variáveis contínuas. No entanto, esta desvantagem pode
ser eliminada aplicando algoritmos que discretizem as variáveis contínuas (Fayyad &
Irani, 1993; Kononenko, 1995).
Um problema em potencial a respeito da utilização da inconsistência como critério para selecionar atributos é que apenas um atributo sozinho pode garantir que
não exista inconsistência nos dados. Um exemplo deste tipo de atributo é o CPF.
Segundo Liu e Setiono (1996), este problema pode ser resolvido deixando este atributo fora do processo de seleção de atributos.
4.1 Seleção de Atributos
45
4.1.2 Taxa de Ganho
Para selecionar as variáveis mais relevantes é possível utilizar a taxa de ganho (Gain Ratio) de cada variável, mas para isto antes é necessário calcular o ganho de informação. O uso do ganho de informação como medida para estimar a qualidade
dos atributos foi primeiramente proposto por Hunt e colegas (1966) e depois por
Quinlan (1986) para construir árvores de decisão. Esta medida é baseada no trabalho pioneiro de Claude Shannon (1948) sobre a teoria da informação que estuda o
valor, ou o “conteúdo da informação”, das mensagens (Han & Kamber, 2006). A Equação 4.3 mostra como calcular o ganho de informação de um atributo
do conjun-
to de instâncias .
(4.3)
onde
é a quantidade de informação necessária para identificar a classe de
uma instância em ,
atributo
,
é o conjunto de todos os possíveis valores para o
é um subconjunto de
cujo atributo
possui valor
,
é a
quantidade de instâncias. A entropia é calculada pela equação definida por:
(4.4)
onde
é a quantidade de classes em ,
pertencer a classe e é estimada por
é a probabilidade de uma instância em
.
A taxa de ganho aplica uma normalização ao ganho de informação utilizando
a informação de separação (SplitInfo) similar a Equação 4.4 da entropia:
(4.5)
onde a única diferença entre as Equações 4.4 e 4.5 é o somatório. A taxa de ganho
finalmente é calculada por:
(4.6)
4.1 Seleção de Atributos
46
O calculo da taxa de ganho não elimina as variáveis menos relevantes, ao
invés disto, apenas associa um valor que representa a capacidade da variável em
particionar as instâncias de
segundo suas respectivas classes. Fica a cargo do
usuário decidir quais variáveis devem ser eliminadas. Geralmente as variáveis eliminadas são as que possuem o menor ganho de informação. Nesta técnica, assim
como no algoritmo LVF, não é possível utilizá-la em problemas que possuam atributos contínuos. No entanto, esta limitação pode ser eliminada aplicando algoritmos
que discretizem as variáveis contínuas. Outra desvantagem desta medida é a impossibilidade de detectar atributos redundantes.
4.1.3 Regressão Linear e o Coeficiente de Correlação
A regressão linear é um método para se estimar um valor esperado de uma variável
y, dados os valores de outra variável x (Han & Kamber, 2006). A regressão é chamada de linear por considerar que a relação entre as variáveis é dada por uma função linear. Se a distribuição dos valores de x e y puder ser representada por uma
função linear, diz-se que estas duas variáveis estão correlacionadas ou que existe
uma relação entre elas. A função linear que descreve o comportamento dos dados
pode ser obtida através das seguintes equações:
(4.7)
e
(4.8)
onde
é o tamanho da amostra que consiste no par
da reta e,
e
são as médias das variáveis
,
e
são os coeficientes
e , respectivamente. Finalmente, a
reta pode ser obtida substituindo os valores obtidos de
e
em:
(4.9)
Determinar a correlação existente entre duas variáveis pode ser útil para determinar e avaliar a relação existente entre duas variáveis. A correlação pode ser
positiva ou negativa. Na correlação positiva as variáveis x e y crescem no mesmo
sentido, i.e., se x cresce, y também tende a crescer. Já na correlação negativa as
variáveis x e y crescem em sentido contrário, i.e., se x cresce, y decresce. Quanto
4.2 Seleção de Ações
47
maior o valor absoluto da correlação entre as variáveis maior é a redundância existente entre elas. O coeficiente de correlação é uma medida que quantifica a similaridade entre duas grandezas não determinísticas e pode ser calculado pela equação
abaixo:
(4.10)
onde
é o coeficiente de correlação,
é o tamanho da amostra e,
e
são as
grandezas entre as quais se deseja calcular o coeficiente de correlação.
4.2
Seleção de Ações
A técnica de mineração de dados proposta para a seleção de ações se baseia em
duas medidas conhecidas como: suporte e confiança. Estas medidas são normalmente utilizadas para minerar padrões freqüentes de um banco de dados, com o
objetivo de criar regras de associação ou de classificação (Han & Kamber, 2006).
Neste trabalho estas duas medidas são utilizadas para medir o grau de utilização e
importância de cada ação para o sucesso do agente em realizar o drible: se uma
ação é freqüentemente utilizada e a ocorrência desta ação nos episódios de sucesso
é baixa então esta ação é removida. O cálculo do suporte mede a freqüência de uso
de uma ação . A Equação 4.11 mostra como calculá-lo.
(4.11)
onde
é frequência em que a ação
é realizada pelo agente e
é a contagem de todas as ações realizadas pelo agente.
A segunda medida, confiança, informa o quanto uma ação é importante para
o sucesso do drible e é definida por:
(4.12)
onde
é a freqüência em que a ação
zado com sucesso ( ) pelo agente e
acontece quando o drible é reali-
é a frequência em que a ação
é rea-
4.3 Aprendizagem por Reforço e a Mineração de Dados
lizada pelo agente. Então, se
ação
e
48
então a
é removida.
O uso do suporte evita eliminar ações nos casos em que a medida de confi-
ança não é conclusiva. Por exemplo, sem o uso do suporte, uma ação que foi utilizada uma única vez e que participou de um episódio de insucesso teria confiança de
0%. No entanto, tirar conclusões da relevância de uma ação com apenas um exemplo do seu uso não é confiável. O suporte evita que casos como estes ocorram.
4.3
Aprendizagem por Reforço e a Mineração de Dados
É comum distinguir três categorias de métodos de aprendizagem, são eles: aprendizagem supervisionada, aprendizagem não-supervisionada e aprendizagem por reforço. Normalmente os métodos da aprendizagem supervisionada são os mais utilizados na mineração de dados (Cohen & Maimon, 2005), portanto, a relação entre a
aprendizagem supervisionada e a aprendizagem por reforço é exemplificada a seguir. Por exemplo, considere um algoritmo de aprendizagem que precise extrair um
modelo de resposta para diversas situações diferentes. No aprendizado supervisionado o algoritmo contará com um conjunto de observações rotuladas por um professor (ou oráculo). O rótulo de cada observação é considerado pelo agente como a
resposta desejada da situação, que é dada pelas variáveis desta observação.
Na aprendizagem por reforço, o privilégio de se ter um professor não é possível. Em vez disto, o algoritmo vê as situações (estados), escolhe as respostas (ações) de forma autônoma e obtém recompensas de um crítico que indica o quão boa
foram as ações escolhidas (Cohen & Maimon, 2005). As variáveis que compõem a
observação do ambiente são as mesmas em ambas as abordagens (Cohen &
Maimon, 2005).
De acordo com Cohen e Maimon (2005), as ações tomadas pelo agente podem ser consideradas as respostas desejadas utilizadas na aprendizagem supervisionada. No entanto, estas respostas somente são conhecidas após a interação do
agente com o ambiente. Contudo, se o treinamento do agente for armazenado em
um banco de dados, na forma estado-ação, é possível utilizar estes dados para o
treinamento de um modelo da aprendizagem supervisionada.
4.3 Aprendizagem por Reforço e a Mineração de Dados
49
O problema desta abordagem é que nem sempre todas as ações tomadas pelo agente são desejáveis - alguma ação pode ter ocasionado ao agente não atingir
seus objetivos. Ainda é desconhecido um meio para identificar as ações, realizadas
em um episódio, que não contribuíram para o agente alcançar seus objetivos. Neste
trabalho, o foco é propor um meio para selecionar as ações mais relevantes (Seção
4.2).
Para a seleção das variáveis mais relevantes pretende-se rotular cada estado
com a respectiva ação realizada pelo agente. Desta forma é obtido o mapeamento
de toda a política do agente. A seleção realizada desta forma permite a identificação
das variáveis que influenciam na decisão do agente (ações realizadas). Esta seleção, porém, é problemática em ambientes da aprendizagem por reforço, pois no início do aprendizado as ações têm a mesma probabilidade de serem selecionadas.
Outra característica que torna difícil a aplicação desta seleção é a possibilidade de o
agente executar ações aleatórias durante todo o treinamento. Para solucionar estes
problemas as ações aleatórias não devem ser armazenadas no banco de dados e os
dados de treinamento utilizados devem originar-se dos episódios em que o treinamento do agente começa a convergir.
O objetivo desta seleção é saber quais variáveis variam sistematicamente de
acordo com o atributo classe. De acordo com Gennari et al. (1989), em ambientes
da aprendizagem supervisionada uma variável é considerada relevante se varia sistematicamente de acordo com o atributo classe. Esta afirmação leva às seguintes
hipóteses nos ambientes da aprendizagem por reforço:
Se uma variável tem alto grau de correlação com o atributo classe, então esta variável é uma boa candidata para determinar a ação do agente.
e
Se uma variável tem baixo grau de correlação com o atributo classe, então
esta variável é uma boa candidata para ser removida.
Espera-se que se uma variável não é relevante para um política , também
seja irrelevante para uma outra política
, onde
é melhor que . Caso isto não
seja verdade, o desempenho do agente não irá aumentar.
4.3 Aprendizagem por Reforço e a Mineração de Dados
50
O esquema da Figura 4.2 sugere como o armazenamento dos dados do treinamento do agente deve ser feito. As tabelas Resultado e ResultadoTemAções
são as que armazenam os dados de treinamento e que possibilitam o agrupamento
destas ações em episódios. A Subseção 4.3.1 dá uma breve descrição das tabelas e
campos do esquema de armazenamento. A Subseção 4.3.1 mostra como a etapa de
armazenamento e seleção dos dados no esquema deve ser realizada.
4.3.1 Armazenamento e Seleção dos dados
Esta seção apresenta uma sugestão para o armazenamento do treinamento do agente. As tabelas e os principais campos do esquema de armazenamento representados pela Figura 4.2 são descritos a seguir:
1. Tabela Resultado: tabela que armazena os dados gerais de um episódio. Esta
tabela tem relacionamento de muitos para um com a tabela Experimento e
de um para muitos com a tabela ResultadoTemAções. Neste caso, um resultado faz parte de somente um único experimento e para cada resultado há
uma seqüência de ações armazenada na tabela ResultadoTemAções.

campo episódio: número do episódio.

campo execução: número da repetição do experimento.

campo sucesso: indica se o agente conseguiu realizar o drible. Este campo deve possuir os valores “S” ou “N” correspondendo a sucesso e falha
na realização do drible, respectivamente.

campo janela: indica os episódios que fazem parte da mesma janela de
tempo.
2. Tabela ResultadoTemAções: tabela que armazena todas as variáveis do ambiente e as ações realizadas pelo agente a cada instante de tempo. Esta tabela tem relacionamento de muitos para um com a tabela Resultado e de
muitos para um com a tabela Ação.

campo número: instante do tempo.
4.3 Aprendizagem por Reforço e a Mineração de Dados
51
3. Tabela ação: tabela que armazena todas as possíveis ações do agente. Esta
tabela mantém uma descrição do código de todas ações.
4. Tabela experimento: tabela que armazena os dados gerais de um experimento.

campo tamModelo: quantidade de memória utilizada pelo modelo.
Figura 4.2 Esquema Snowflake de armazenamento do treinamento do agente. Os Dados de treinamento estão armazenados em duas tabelas principais:
Resultado e ResultadoTemAção.
Capítulo 5
Experimentos e Análise Estatística dos Dados
Os experimentos apresentados neste capítulo foram divididos em cinco etapas. A
primeira etapa (Seção 5.1) realiza uma busca experimental pelos parâmetros do
modelo de aprendizado.
Determinado os melhores parâmetros de acordo com a distribuição da freqüência relativa de sucesso no drible, a segunda etapa (Seção 5.2) identifica e seleciona os atributos mais relevantes utilizando os algoritmos apresentados nas Seções
4.1.1, 4.1.2 e 4.1.3 do Capítulo 4. O armazenamento e seleção destes dados foram
realizadas conforme descrito na Seção 4.3.
Os experimentos realizados na terceira etapa (Seção 5.3) identificam e selecionam as melhores ações utilizando a métrica apresentada na Seção 4.2 do Capítulo 4. Após determinar os melhores atributos e ações do problema, a quarta etapa
(Seção 5.4) combina as melhores ações e variáveis identificadas e um novo treinamento é realizado. A última etapa (Seção 5.5) avalia a qualidade do drible e valida o
modelo com o teste do agente.
5.1
Treinamento do Agente
O treinamento do agente foi realizado utilizando o algoritmo
com a técnica de tile-coding. O algoritmo de aprendizado
combinado
direciona o agen-
te para que obtenha uma maior recompensa ao longo do tempo enquanto que a técnica de tile-coding permite manter as estimativas de recompensas como uma função
parametrizada. A técnica de tile-coding também permitirá ao agente generalização
que é importante em ambientes como o do futebol de robôs onde não é possível visitar todos os possíveis estados do ambiente.
Para o problema abordado, cada variável possuiu
tilings de uma dimensão.
O tamanho definido para cada tile foi determinado de acordo com o tipo da variável.
52
5.1 Treinamento do Agente
53
Para as variáveis que representam velocidade, ângulo ou a distância os tiles tiveram
tamanhos 0.2, 5 e 2, respectivamente. Estes valores foram retirados do trabalho de
Stone e Sutton (2001).
Uma das tarefas do projetista de um modelo computacional é definir quais serão os valores dos parâmetros. Estes valores devem ser escolhidos cuidadosamente, pois influenciam no desempenho do modelo na fase de aprendizagem. O modelo
utilizado possui cinco parâmetros que afetam no desempenho do aprendizado do
agente, são eles:
1. Taxa de aprendizado (alpha) – Este parâmetro deve ter valores pequenos para que o modelo possa captar variações temporais. Segundo Sutton e Barto
(1998), é garantido convergência para uma política ótima se este parâmetro
decair com o tempo.
2. Desconto (gamma) – O desconto determina o interesse do agente pelas recompensas futuras. Quanto mais gamma se aproxima de zero o agente tornase mais oportunista interessando-se mais pelas recompensas imediatas.
3. E – Parâmetro que define a probabilidade de o agente explorar ao invés de
seguir uma política determinística.
4. Elegibility Trace (lambda) – Permite recompensar ou punir todo o percurso
que o agente seguiu até o fim do episódio. Uma parcela da recompensa recebida no fim do episódio é retropropagada para seus estados antecessores. A
retropropagação do sinal de recompensa diminui à medida que o estado antecessor se afasta do estado final. Este parâmetro determina o quanto o sinal
de recompensa deve diminuir em função do tempo.
5. Quantidade de Tilings – Este parâmetro determina como a experiência de um
estado deve ser compartilhada com seus vizinhos. A resolução deste compartilhamento é determinada por este parâmetro.
Como não há formas teóricas de determinar qual o melhor ajuste para estes
parâmetros, o projetista do modelo deve ajustar estes valores experimentalmente,
por meio de um projeto experimental (Jain, 1991). Para acelerar este processo, optou-se pelo projeto experimental linear, iniciando a busca com os valores de parâmetros que são freqüentemente encontrados na literatura. Os parâmetros iniciais utilizados como ponto de partida são apresentados na Tabela 5.1.
5.1 Treinamento do Agente
54
Tabela 5.1 Valores iniciais para os parâmetro do modelo.
Alpha
Gamma
E
Lambda
Tilings
0.007812
0.95
0.01
0.75
8
Tabela 5.2 Espaço de busca.
Parâmetro
Valores
Alpha
(frações de potência de 2)
Gamma
0.95 (constante)
E
0, 0.01, 0.1
Lambda
0.5, 0.75, 0.90, 0.95
Tilings
2, 4, 8, 16, 32 (potências de 2)
Tabela 5.3 Variação inicial dos parâmetros do modelo.
Parâmetro
Primeira Variação
Segunda Variação
Alpha
0.015625
0.00390625
Gamma
-
-
E
0
0.1
Lambda
0.5
0.9
Tilings
4
16
A condução dos experimentos desta etapa se deu da seguinte forma. Com o
objetivo de determinar os melhores valores para os parâmetros do modelo, os parâmetros alpha, E, lambda e tilings foram fixados em seus valores iniciais e cada parâmetro foi variado individualmente. Inicialmente foram determinadas duas variações
para cada um dos parâmetros do modelo (Tabela 5.3). Se em uma das variações for
possível notar um ganho no desempenho do aprendizado, então o parâmetro que
proporcionou este ganho deverá continuar variando em direção ao melhor resultado.
A busca conduzida desta forma pode falhar se os parâmetros tiverem uma forte relação entre eles. Se isto for verdade, o ideal será fazer um projeto
-fatorial ou
-
fatorial no espaço de busca dos parâmetros, a custos bem mais elevados.
Para limitar o espaço de busca o parâmetro Alpha foi variado à potência negativa de dois e o parâmetro Tiling foi variado seguindo a recomendação de Albus
5.2 Seleção de Atributos
55
(1975) sendo atribuídos valores múltiplos de dois. Para o restante dos parâmetros os
valores atribuídos basearam-se nos mais comuns encontrados na literatura. A Tabela 5.2 mostra o espaço de busca. O desempenho de uma execução será calculado a
cada 300 episódios utilizando a freqüência relativa de sucesso do agente no drible.
Para determinar o melhor parâmetro será levado em consideração o tempo de convergência e o desempenho obtido pela área abaixo da curva.
5.2
Seleção de Atributos
Esta seção trata da construção do modelo no que se diz respeito à representação do
ambiente e escolha dos parâmetros do modelo de aprendizado. Todas as subseções
desta seção, exceto a Subseção 5.2.1, utilizam abordagens estatísticas para selecionar quais variáveis devem ser escolhidas para representar o ambiente. Assumese que estas variáveis são as mais relevantes para o problema abordado. As variáveis que não fazem parte desta seleção são consideradas irrelevantes e devem ser
descartadas. Espera-se que, ao treinar o modelo sem estas variáveis, seja possível
observar um aumento ou uma variação irrelevante no desempenho do drible.
As subseções desta seção estão organizadas como segue. Na Subseção
5.2.1 o agente foi treinado com todas as variáveis descritas na Tabela 3.4. Os experimentos desta etapa devem ser armazenados em um banco de dados para que os
algoritmos de seleção utilizados nas subseções 5.2.1, 5.2.2 e 5.2.3 possam utilizálos para identificar as variáveis mais relevantes.
Algumas considerações sobre o modelo utilizado nas próximas seções são
feitas a seguir. Primeiro, o método de exploração
é o mais utilizado na
literatura e foi utilizado para a construção dos modelos. Foi decido não utilizar o método softmax, pois não havia motivos suficientes que justificassem a sua utilização
(ver Seção A.3 na página 103). A técnica de elegibility traces foi utilizada com replacing traces. Segundo Sutton e Barto (1998), a utilização da técnica com accumulating traces tem desempenho pior do que com replacing traces.
A segunda consideração a ser feita é com relação ao decaimento do valor do
parâmetro alpha. Para garantir a convergência do modelo é preciso que o parâmetro
alpha decaia com o tempo, sendo assim, optou-se por utilizar um decaimento exponencial dado como segue:
5.2 Seleção de Atributos
56
(5.1)
onde
é o valor inicial de alpha,
é número atual do episódio,
é a quantidade total de episódios e
é uma constante que possibilita
determinar a velocidade de decaimento do parâmetro alpha. A Figura 5.1 mostra as
curvas de decaimento de alpha de acordo com a variação da constante
e
zou-se
para
. Nos experimentos realizados utili-
.
Figura 5.1 Decaimento exponencial da taxa de aprendizado.
Para tornar os resultados mais confiáveis cada treinamento foi repetido dez
vezes. Em todos os casos um único treinamento com 4200 episódios durou cerca de
1 hora para concluir. O treinamento do agente ocorre em tempo real, portanto, a capacidade de processamento da CPU utilizada não tem influência no tempo de execução dos experimentos.
5.2.1 Treinamento com Todos os Atributos
As curvas de aprendizagem para as variações apresentadas na Tabela 5.3 são apresentadas nas Figuras 5.2, 5.3, 5.4, 5.5 e 5.6. Cada curva representa a média do
5.2 Seleção de Atributos
57
desempenho em 10 execuções. O objetivo da construção destes modelos foi unicamente para determinar os melhores valores dos parâmetros alpha, E, lambda e tillings.
A Figura 5.2 mostra os desempenhos do agente com a variação do parâmetro
alpha (taxa de aprendizado). Note que a figura mostra uma curva a mais além das
três já esperadas. Isto foi devido ao fato de o máximo desempenho do sistema ter
sido observado para o valor superior ao limite originalmente planejado para este parâmetro nos experimentos sobre o aprendizado. A variação deste parâmetro terminou com o valor 0.03125 em que foi observada uma redução no desempenho do
modelo se comparado com o aprendizado no qual alpha teve valor 0.015625. Apesar
de os resultados apresentados na Figura 5.2 não possibilitarem determinar a melhor
variação com confiança, porém, escolheu-se alpha = 0.015625, pois este valor apresentou o melhor desempenho na maior parte do treinamento. Nota-se que quando
Alpha teve valor muito alto (0.03125) o desempenho do agente foi melhor no inicio,
mas devido às grandes alterações nos tiles, o desempenho do agente não teve a
mesma tendência que obteve no inicio do treinamento.
Figura 5.2 Curvas de desempenho (média de dez execuções) do agente com todas
as variáveis, mudando apenas o parâmetro alpha (taxa de aprendizado).
As curvas de aprendizado para a variação do parâmetro E são apresentadas
na Figura 5.3. As curvas mostram que o agente obteve um melhor desempenho
quando E foi igual a zero, no entanto, a curva de aprendizado para E igual a 0.1 ob-
5.2 Seleção de Atributos
58
teve um resultado satisfatório com relação à curva anterior. Nota-se que no inicio do
aprendizado a exploração proporcionou uma aceleração no inicio do aprendizado,
mas após o episódio 2000 o treinamento aparenta convergir com apenas 30% de
sucesso. Contudo, tornar o agente guloso em relação à política (E = 0) pode fazer
com que apresente um desempenho pior em treinamentos com mais de 4200 episódios, nestes casos o agente pode estar preso em alguma política sub-ótima o que
poderá resultar em uma convergência prematura. Neste caso optou-se em realizar
dois treinamentos, um para E igual a 0 e o outro para E igual a 0.01.
Figura 5.3 Curvas de desempenho (média de dez execuções) do agente com todas
as variáveis, mudando apenas o parâmetro E.
A Figura 5.4 mostra as curvas de aprendizado de acordo com a variação do
parâmetro lambda. O aprendizado foi iniciado com lambda = 0.75 e, seguindo a estratégia dos experimentos (ver Seção 5.1), o agente também foi treinado para 0.5 e
0.9. Foi notado um aumento no desempenho do agente quando o valor de lambda
aumentou para 0.9 sugerindo a variação deste parâmetro mais uma vez nesta direção. Sendo assim, o agente foi treinado com lambda = 0.95 e mais uma vez foi notado um aumento no desempenho do drible. O agente foi treinado uma última vez
sendo lambda = 1 onde foi observada uma redução do desempenho. Esta redução
no desempenho deve-se ao retorno total da recompensa recebida, no fim do episódio, para as ações passadas (ver Subseção 2.1.1). Neste caso, ainda que o algorit-
5.2 Seleção de Atributos
mo tenha características temporais, a aproximação de
59
é idêntica ao algoritmo
Monte Carlo (Sutton & Barto, 1998).
Figura 5.4 Curvas de desempenho (média de dez execuções) do agente com todas
as variáveis, mudando apenas o parâmetro lambda (elegibility traces).
Figura 5.5 Curvas de desempenho (média de dez execuções) do agente com todas
as variáveis, mudando apenas a quantidade de tilings.
A Figura 5.5 mostra as curvas de aprendizado para a variação do parâmetro
tiling. As duas variações iniciais (ver Tabela 5.3) para o parâmetro tilings não permitiram identificar com certeza a curva que apresentou o melhor desempenho. Sendo
assim, decidiu-se variar este parâmetro mais uma vez em ambas as direções do espaço de busca, com tilings igual a 2 e 16. Analisando as duas curvas adicionais, po-
5.2 Seleção de Atributos
60
de-se notar que o desempenho com tilings igual a 2 foi superior aos demais. Isto aconteceu devido a baixa resolução obtida com apenas 2 tiles (ver Seção 2.3). Desta
forma, o desempenho do agente não foi afetado pelas variações estocásticas do
ambiente.
Treinamento do Agente
(Melhores Variações)
50
Desempenho
40
30
20
10
0
0
2000
4000
6000
8000
10000
12000
E=0
E=0.01
Episódio
Figura 5.6 Curvas de desempenho (média de dez execuções) do agente com todas
as variáveis e com a combinação dos melhores valores para os parâmetros gamma,
alpha, E, lambda e quantidade de tilings.
De acordo com as Figuras 5.2, 5.3, 5.4 e 5.5 os melhores valores para os parâmetros alpha, E, lambda e tilings foram respectivamente, 0.015625, 0, 0.95 e 2. A
Figura 5.6 mostra o treinamento do agente com a combinação dos melhores valores
para os parâmetros retirados dos treinamentos anteriores.
O modelo treinado com
Com
utilizou em média 17.7MB de espaço em memória.
o desempenho do agente é pior até o episódio 8000, o desempenho
do agente nos episódios seguintes tem desempenho similar ao do treinamento com
. O modelo treinado com
utilizou em média 18.1MB de espaço em
memória. Este último modelo consumiu 409KB a mais que o modelo construído com
. Em termos de tempo de convergência, o modelo com
modelo construído com
.
foi superior ao
5.2 Seleção de Atributos
61
5.2.1.1 Análise da Correlação dos Atributos
Para facilitar a análise da correlação entre as variáveis do problema, o treinamento
da Figura 5.6 foi armazenado em um banco de dados na forma do esquema apresentado na Figura 4.2 (pagina 51). A quantidade de registros existentes no banco de
dados foi de 670826 para o treinamento com todas as variáveis e
.
A Figura 5.7 mostra a correlação das variáveis que obtiveram o coeficiente de
correlação maior que sete décimos. No inicio do treinamento o agente ainda não tem
consciência de suas ações podendo perder o controle da bola chutando-a para longe. Este comportamento explica a linha vertical formada nas Figura 5.7c-f.
De acordo com a Figura 5.7 as variáveis oBDist, bDist, oSD, aSD, aPosX,
bPosX, oPosX, aPosY, bPosY e oPosY tiveram grau de correlação maior que oito
décimos. As demais variáveis não apresentadas na Figura 5.7 tiveram correlação
menor que 0.65. A correlação entre oBDist e bDist (Figura 5.7a) sugere que uma das
variáveis seja removida, também é sugerido o mesmo entre oSD e aSD (Figura
5.7b). Entre as variáveis aPosX, bPosX, oPosX, aPosY, bPosY e oPosY (Figura
5.7c-h) foi possível observar o maior coeficiente de correlação com aproximadamente 0.99.
Medir a correlação das variáveis é uma técnica útil para verificar se existe redundância entre as mesmas, quando elas são de natureza numérica. Variáveis redundantes podem aumentar a complexidade do modelo e até reduzir o seu desempenho. No entanto, deve-se ter cuidado com a remoção de uma variável correlacionada. Apesar de oBDist e bDist terem um alto grau de correlação entre si, o contexto
destas duas variáveis são diferentes. A variável oBDist é a distância na qual o oponente se encontra da bola e, bDist é a distância na qual o agente se encontra da
bola.
Note que no inicio da reta de regressão linear da Figura 5.7a a distribuição
dos dados não é linear. No inicio de todo episódio o oponente inicia distante da bola
e o agente com a bola junto ao seu corpo (ver Seção 3.3 na página 30). Neste ponto
estas duas variáveis têm valores e funções totalmente diferentes. Naturalmente, após alguns instantes de tempo os valores destas duas variáveis estarão bem próximos, pois o agente se aproxima com a bola do oponente para realizar o drible e o
oponente se aproxima da bola para tomá-la, ambos têm o mesmo objetivo que é ter
a posse de bola.
5.2 Seleção de Atributos
(a)
62
(b)
Variável bDist x oBDist
Variável aSD x oSD
corr = 0,874527
corr = 0,985993
26
45
24
40
22
20
35
18
30
25
14
aSD
bDist
16
12
10
20
15
8
6
10
4
5
2
0
0
-2
-5
-2
0
2
4
6
8
10
12
14
16
18
20
22
24
26
-5
0
5
10
15
oBDist
(c)
(d)
Variável aPosX x bPosX
40
40
30
30
20
20
10
10
oPosX
aPosX
50
0
-10
-20
-20
-30
-30
-40
-40
0
20
40
-50
-60
60
-40
-20
0
bPosX
(e)
(f)
30
30
20
20
10
10
oPosY
aPosY
40
0
-10
-20
-20
-30
-30
0
10
20
30
-40
-40
40
-30
-20
-10
bPosY
(g)
40
60
0
-10
-10
20
corr = 0,977967
40
-20
45
Variável oPosY x bPosY
corr = 0,993429
-30
40
bPosX
Variável aPosY x bPosY
-40
-40
35
0
-10
-20
30
corr = 0,974656
50
-40
25
Variável oPosX x bPosX
corr = 0,981928
-50
-60
20
oSD
0
10
20
30
40
30
40
bPosY
(h)
Variável aPosX x oPosX
Variável aPosY x oPosY
corr = 0,994257
corr = 0,993429
40
50
40
30
30
20
20
10
aPosY
aPosX
10
0
-10
0
-10
-20
-20
-30
-30
-40
-50
-50
-40
-30
-20
-10
0
oPosX
10
20
30
40
50
-40
-40
-30
-20
-10
0
10
20
oPosY
Figura 5.7 Correlação entre as variáveis com coeficiente maior que sete décimos.
Dados retirados do treinamento com todas as variáveis.
5.2 Seleção de Atributos
63
A importância da variável bDist é clara: o agente a todo o momento utiliza esta variável para saber se está a uma distância mínima para realizar um chute, caso
não esteja, o agente deve se aproximar da bola. Mas nada se sabe da importância
do restante das variáveis correlacionadas. A utilização das abordagens estatísticas
para a seleção de atributos descritas na próxima seção pode ajudar a decidir quais
variáveis redundantes devem ser removidas e se realmente devem ser removidas.
5.2.2 Taxa de Ganho
O primeiro algoritmo utilizado para identificar as variáveis mais relevantes é a taxa
de ganho (ver Seção 4.1.2).
A Tabela 5.4 mostra as variáveis ordenadas pelo seu respectivo ganho. As
variáveis do topo da tabela são consideradas as mais relevantes, pois possuíram a
maior taxa de ganho. Conseqüentemente as que estão nas últimas linhas da tabela
são consideradas as menos relevantes.
As variáveis bPosX, bPosY, oPosY, aPosX, aPosY e oPosX obtiveram as
menores taxa de ganho e portanto foram removidas do aprendizado do agente. Visto
que a Figura 5.7 já sugeria sua remoção pela alta correlação existente entre elas.
Utilizando a taxa de ganho apenas confirmou-se a sua remoção.
É importante lembrar que a taxa de ganho não tem nenhuma relação com a
correlação entre as variáveis. Não é possível verificar a redundância existente entre
as variáveis utilizando a taxa de ganho. Isto pode ser notado comparando o ganho
das variáveis bDist, oBDist, aSA e oSA e o coeficiente de correlação da Figura 5.7.
É recomendável que apenas uma das duas variáveis correlacionadas permaneça
para a construção do modelo. Como não se sabe a importância das variáveis oBDist, aSD e oSD decidiu-se remover as variáveis que tivessem a menor taxa de ganho, neste caso as variáveis aSA e oBDist. Se o desempenho do agente no treinamento for menor do que o com todas as variáveis, então estas variáveis podem ter
alguma relevância e devem voltar a fazer parte do modelo.
Após a remoção das variáveis bPosX, bPosY, oPosY, aPosX, aPosY, oPosX,
aSD e oBDist restaram apenas 15 variáveis de um total de 23. Isto é, uma redução
de aproximadamente 35%.
O mesmo procedimento realizado na Seção 5.2.1 para encontrar os melhores
parâmetros será realizado novamente após a seleção de atributos. As Figuras 5.8,
5.2 Seleção de Atributos
64
5.9, 5.10 e 5.11 mostram o desempenho do agente de acordo com a variação dos
parâmetros alpha, E, lambda e tilings, respectivamente.
Tabela 5.4 Taxa de ganho para as variáveis do ambiente.
Variável
Ganho
bDist
0,48
oBAngle
0,13
bVel
0,13
oDist
0,12
oVelY
0,11
bDir
0,11
oVelX
0,11
aVelY
0,11
oBDist
0,09
aVelX
0,09
oAngle
0,07
oSD
0,06
aSD
0,05
bAngle
0,05
aBodyA
0,05
oSA
0,05
aSA
0,04
bPosX
0,01
bPosY
0,01
oPosY
0,01
aPosX
0,01
aPosY
0,01
oPosX
0,00
O desempenho do agente variando o parâmetro alpha (ver Figura 5.8) apresentou comportamento semelhante ao modelo com todas as variáveis. Com alpha
igual a 0.015625 foi possível observar o melhor desempenho entre as variações. O
5.2 Seleção de Atributos
65
valor deste parâmetro coincidentemente é o mesmo que o modelo com todas as variáveis.
Figura 5.8 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro Alpha após a remoção das variáveis segundo a taxa de ganho.
Figura 5.9 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro E após a remoção das variáveis segundo a taxa de ganho.
A Figura 5.9 mostra que o incentivo da exploração no modelo construído com
as variáveis relevantes selecionadas segundo a taxa de ganho e o grau de correlação passou a proporcionar um aumento no desempenho do agente. Isto aconteceu
devido às variáveis irrelevantes já proporcionarem uma exploração natural, mas de
5.2 Seleção de Atributos
66
forma inadequada. Quando as variáveis irrelevantes foram removidas, o incentivo da
exploração permitiu ao agente explorar com mais consciência. Com
foi
possível observar o melhor desempenho. No treinamento com todas as variáveis a
exploração não apresentou nenhum aumento no desempenho ou no tempo de convergência do modelo.
A Figura 5.10 mostra as curvas de desempenho quando variado o parâmetro
lambda. Para este parâmetro o melhor desempenho do agente foi obtido quando
lambda foi igual a 0.75.
Figura 5.10 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro Lambda após a remoção das variáveis segundo a taxa de ganho.
Figura 5.11 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro Tilings após a remoção das variáveis segundo a taxa de ganho.
5.2 Seleção de Atributos
67
Com a variação do parâmetro tiling não foi possível observar nenhuma diferença significativa no desempenho dos modelos apresentado na Figura 5.11. No entanto, a curva de desempenho com tiling igual a 4 tem área maior que as outras curvas no decorrer do aprendizado, sendo assim, optou-se em utilizar este valor para o
parâmetro tiling.
A Figura 5.12 mostra a curva de desempenho do agente na realização do drible. Os parâmetros alpha, E, lambda e tilings escolhidos para treinar o agente foram
0.015625, 0.01, 0.75 e 4, respectivamente. A remoção das variáveis irrelevantes
proporcionou uma estabilidade no treinamento do modelo fazendo com que o desempenho do agente não oscilasse tanto quanto o modelo com todas as variáveis.
Treinamento do Agente
(Melhores Variações)
60
50
Desempenho
40
30
20
10
0
0
2000
4000
6000
8000
10000
12000
E=0
E=0.01
Episódio
Figura 5.12 Curvas de desempenho (média de dez execuções) do agente com a
combinação dos melhores valores para os parâmetros gamma, alpha, E, lambda e
tilings após a remoção das variáveis irrelevantes de acordo com a taxa de ganho e a
redundância (correlação).
Comparando a curva de aprendizado com as apresentadas na Subseção
5.2.1 percebe-se que o modelo construído com as variáveis selecionadas segundo a
taxa de ganho e a redundância converge com desempenho superior ao construído
com todas as variáveis (Figura 5.6). O modelo também apresentou uma aceleração
no aprendizado do agente. Se o treinamento fosse interrompido na metade do tem-
5.2 Seleção de Atributos
68
po, i.e., quando completado 6000 episódios, seu desempenho ainda seria superior
ao desempenho do modelo com todas variáveis construído em 12000 episódios.
O modelo com
utilizou em média 2.15MB de espaço em memória. Com
o desempenho do agente até o episódio 1700 é muito próximo ao modelo
com
, mas após o episódio 1700 o desempenho é pior. No final o modelo con-
verge com aproximadamente 50% de sucesso contra 57% do modelo com
modelo treinado com
. O
utilizou em média 1.7MB de espaço em memória. Es-
te último modelo consumiu 460KB a menos que o modelo construído com
.
5.2.3 Las Vegas Filter
Uma vantagem clara do algoritmo LVF em relação à taxa de ganho é a remoção automática das variáveis irrelevantes. A taxa de ganho apenas avalia a capacidade de
uma única variável em particionar os dados. No entanto, tem-se uma quantidade
muito maior de subconjuntos de atributos para avaliar. Ao invés de analisar individualmente todas as variáveis de um problema o algoritmo LVF analisa os possíveis
subconjuntos que as variáveis podem formar. É claro que este tipo de análise tem
um custo, mas o algoritmo tem-se mostrado eficiente em termos de tempo de processamento e resultados (Liu & Setiono, 1996).
As variáveis bPosX, bPosY, oPosY, aPosX, aPosY e oPosX foram eliminadas
antes da execução do algoritmo, pois possuem um alto grau de correlacionamento e
uma baixa taxa de ganho. Teoricamente estas variáveis não devem trazer nenhuma
informação útil para o agente. Deixá-las no processo de aprendizado do agente só
limitaria a realizar o drible em uma pequena região do campo. As variáveis oBAngle,
oSD e aSD não foram eliminadas antes da execução do algoritmo, foi deixado a cargo do algoritmo determinar a relevância destas variáveis.
O algoritmo foi iniciado com um subconjunto de variáveis selecionadas aleatoriamente e com MAX igual a 1310 (1% do espaço de busca). Foram observadas as
taxas de inconsistência e escolhido o subconjunto de atributos no qual foi possível
observar a menor taxa de inconsistência. Após a execução do algoritmo, o conjunto
de variáveis selecionado foi: oVelY, bDist, oDist, oBDist, aSD, oSD, bAngle, oAngle,
oSA e aBodyA. As seguintes variáveis foram removidas: aVelX, aVelY, bVel, oVelX,
oBAngle, aSA, bDir. A inconsistência das variáveis selecionadas foi de 0.00929. O
5.2 Seleção de Atributos
69
algoritmo LVF não removeu nenhuma das 4 variáveis (bDist, oBDist, aSD, oSD) correlacionadas no momento de sua execução. Apesar de estas variáveis apresentarem um grau de correlação alto, em certas regiões do espaço de estados elas apresentam funções totalmente diferentes.
As figuras abaixo mostram as curvas de aprendizado do agente de acordo
com a variação dos valores dos parâmetros alpha, E, lambda e tilings. As curvas de
desempenho para a variação do parâmetro alpha é apresentado na Figura 5.13. Para determinar o valor deste parâmetro foram necessárias mais duas variações além
das três planejadas inicialmente. Isto foi devido ao desempenho do modelo ter aumentado quando o valor do parâmetro alpha também aumentou. A variação terminou quando observado uma redução no desempenho do aprendizado quando alpha
teve valor igual a 0.0625.
Figura 5.13 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro alpha após a remoção das variáveis irrelevantes pelo algoritmo
LVF.
A Figura 5.14 mostra o desempenho do modelo quando variado o parâmetro
E. Percebe-se que com
o desempenho do modelo é superior aos demais
modelos até o episódio 3300. O modelo construído com
é superior a partir do
episódio 3200. A exploração permitiu ao agente encontrar uma sub-política ótima
mais rápido que o modelo com E=0, mas o agente continua a explorar o que impede
que desempenho continue a aumentar. Valores muito altos para o parâmetro E im-
5.2 Seleção de Atributos
70
possibilitaram ao agente permanecer em uma política provocando uma convergência
prematura.
Figura 5.14 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro E após a remoção das variáveis irrelevantes pelo algoritmo
LVF.
Com a variação do parâmetro lambda percebe-se uma influência maior no
desempenho do modelo. A Figura 5.15 mostra as variações do parâmetro lambda.
Nenhuma das três variações iniciais (0.5, 0.75 e 0.9) apresentou diferença no desempenho. Portanto, foi preciso variar este parâmetro mais duas vezes com lambda
igual a 0.95 e 1. O modelo com lambda igual a 0.95 apresentou desempenho melhor
que as demais variações. Com lambda igual a 0.95 permitiu acelerar o aprendizado
culpado ações passadas pelo insucesso do agente no fim dos episódios. Isto possibilitou que o agente não insistisse em executar estas ações com freqüência, passando a tentar o restante das ações.
A Figura 5.16 mostra as variações do parâmetro tiling. Nenhuma das três variações iniciais (4, 8 e 16) apresentou diferença no desempenho. Sendo assim, o
parâmetro tiling foi variado em ambas às direções do espaço de busca (tiling=2 e
tiling=32).
5.2 Seleção de Atributos
71
Figura 5.15 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro Lambda após a remoção das variáveis irrelevantes pelo algoritmo LVF.
Figura 5.16 Curvas de desempenho (média de dez execuções) do agente mudando
apenas o parâmetro Tilings após a remoção das variáveis irrelevantes pelo algoritmo
LVF.
A Figura 5.17 mostra o desempenho do agente na realização do drible. Seguindo a mesma estratégia dos experimentos anteriores, os parâmetros utilizados
para o modelo foram
,
,
e
. De acor-
do com a figura o desempenho do agente atinge convergência com 52% de sucesso. Este modelo utilizou em média 882KB de espaço em memória. O desempenho
5.3 Seleção de Ações
do modelo com
modelo com
72
está bem próximo ao com
. O uso de memória do
foi de apenas 12KB a menos que o modelo com
. A ace-
leração do aprendizado e o aumento do desempenho foram alcançados no modelo
construído com as variáveis selecionadas segundo o algoritmo LVF. Note que após
o episódio 6500 o desempenho do agente é superior ao do modelo construído com
todas as variáveis.
Treinamento do Agente
(Melhores Variações)
60
50
Desempenho
40
30
20
10
0
0
2000
4000
6000
8000
10000
12000
E=0
E=0.01
Episódio
Figura 5.17 Curvas de desempenho (média de dez execuções) do agente com a
combinação dos melhores valores para os parâmetros gamma, alpha, E, lambda e
tilings após a remoção das variáveis irrelevantes pelo algoritmo LVF.
5.3
Seleção de Ações
Nesta seção será apresentada a segunda etapa dos experimentos. Nas seções anteriores foram apresentadas algumas técnicas para a identificação das variáveis irrelevantes e redundantes em ambientes da aprendizagem por reforço, agora pretendese estudar outro ponto importante da aprendizagem por reforço: o espaço de ações
do agente. Há varias razões que incentivam a seleção de ações. Assim como as variáveis irrelevantes, as ações irrelevantes podem atrasar e até mesmo atrapalhar a
convergência do agente. Nesta seção será apresentado como as ações irrelevantes
para o agente podem ser identificadas e removidas para reduzir a complexidade do
5.3 Seleção de Ações
73
modelo, acelerar o tempo de convergência e possivelmente obter um ganho no desempenho do modelo.
Os experimentos desta seção iniciam analisando o suporte e confiança (Han
& Kamber, 2006) das regras induzidas sobre a presença das ações executadas pelo
agente nos treinamentos dos modelos anteriores. Serão usados, separadamente, os
dados coletados de todos os episódios das Figuras 5.6, 5.12 e 5.17. Neste estudo
não se pretende levar em consideração as probabilidades conjuntas de uma seqüência de ações realizadas em um episódio. Apesar de ser uma aproximação da
condição real, esta escolha evita a explosão das combinações possíveis e viabiliza
uma análise que, por mais simples que seja, agrega valor à solução do problema,
como será mostrado a seguir. As ações com maior participação em episódios de
sucesso serão consideradas relevantes e as com menor participação serão consideradas irrelevantes e deverão ser removidas dos próximos treinamentos. Espera-se
que sem estas ações o tempo de convergência dos modelos diminua, e que o desempenho aumente.
5.3.1 Análise das Ações com Todos os Atributos
A primeira figura (Figura 5.18a-b) analisada mostra o nível de confiança das ações
para o treinamento com todas as variáveis. Nesta primeira figura percebe-se que
grande parte das ações não passa dos 20% de confiança caso a exploração não
seja incentivada, i.e, se
. Isto significa que em 80% das ocorrências destas a-
ções estiveram em episódios de insucesso do agente em todo o treinamento. Algumas ações não alcançam nem os 10%, talvez boa parte destas ações tenham resultado no sucesso do agente por alguma falha do oponente ou até mesmo pelo acaso.
Ações com baixo nível de confiança são boas candidatas para serem removidas,
mas isto depende também do suporte que será analisado mais a frente. A exploração proporcionou um aumento na confiança das ações como pode ser visto na Figura 5.18b.
5.3 Seleção de Ações
74
Figura 5.18 Confiança das ações extraídas do treinamento do agente com todas as
variáveis para dois níveis de exploração.
A segunda figura (Figura 5.19a-b) mostra o suporte das ações. O suporte indica a proporção da execução de uma ação em relação ao total de ações, independente de estarem associadas a episódios de sucesso ou não e dos tipos de ação.
Analisando a figura do suporte percebe-se que a exploração deveria ser mais incentivada ou que o treinamento devesse ter continuado além dos doze mil episódios. O
aumento do suporte quando incentivada a exploração não pode ser observado
quando o parâmetro E foi de 0 para 0.01. No entanto, a Figura 5.19b mostra uma
distribuição mais uniforme do suporte entre as ações com suporte abaixo de 0.2%.
Figura 5.19 Suporte das ações extraídas do treinamento do agente com todas as
variáveis para dois níveis de exploração.
Um dos grandes problemas da baixa exploração do espaço de ações do agente deve-se à grande quantidade de ações. Executar todas estas ações em cada
subespaço do espaço de busca do agente é muito custoso. Se isto fosse realmente
necessário, o tempo de convergência do modelo iria aumentar consideravelmente,
provavelmente produzindo algum aumento no desempenho do agente. Contudo,
grande parte destas ações podem ser consideradas irrelevantes ou desnecessárias.
5.3 Seleção de Ações
75
Eliminando as ações irrelevantes espera-se que o suporte se distribua nas demais
ações que não foram eliminadas.
5.3.2 Análise das Ações com Atributos Eliminados por Taxa de Ganho
Após a eliminação das variáveis irrelevantes pela Taxa de Ganho houve um crescimento individual significativo no suporte de algumas ações (Figura 5.21a), mas também proporcionou a redução do suporte em outras ações. Isto deve-se a aceleração
do aprendizado que a eliminação das variáveis pela taxa de ganho proporcionou. O
aumento do suporte de algumas ações indica que o agente pode ter encontrado a
política mais rápido que o modelo anterior, passando a executar estas ações com
mais freqüência. Isto explica a redução do suporte no restante das ações.
Figura 5.20 Confiança das ações extraídas do treinamento do agente após remoção
das variáveis segundo a taxa de ganho para dois níveis de exploração.
Figura 5.21 Suporte das ações extraídas do treinamento do agente após remoção
das variáveis segundo a taxa de ganho.
Houve uma redução na confiança destas ações (Figura 5.20a) e com a exploração a redução foi maior, ao mesmo tempo em que o crescimento da confiança de
5.3 Seleção de Ações
76
algumas ações aumentou drasticamente. Isto mostra que o agente passou a executar as ações relevantes com mais freqüência que os modelos anteriores que tinham
todas as variáveis. As variáveis irrelevantes limitaram o agente a um pequeno grupo
de ações.
5.3.3 Análise das Ações com Atributos Eliminados por LVF
A duas últimas figuras (Figuras 5.22 e 5.23) mostram a confiança e o suporte
do treinamento do agente após a remoção das variáveis irrelevantes pelo algoritmo
LVF. O uso do suporte está bem mais distribuído e as confianças das ações aumentaram. Isto mostra que o agente está mais consciente em suas ações.
Figura 5.22 Confiança das ações extraídas do treinamento do agente após a remoção das variáveis irrelevantes pelo algoritmo LVF para dois níveis de exploração.
Figura 5.23 Suporte das ações extraídas do treinamento do agente após a remoção
das variáveis irrelevantes pelo algoritmo LVF para dois níveis de exploração.
5.3 Seleção de Ações
77
5.3.4 Remoção das Ações nos Modelos Discutidos
A Tabela 5.5 mostra a quantidade de variáveis removidas em cada modelo para
e
. Devido ao baixo suporte da maior parte das ações o parâmetro
não foi utilizado. A grande quantidade de exemplos armazenados na base de dados
(10 repetições do treinamento com doze mil episódios) permitiu utilizar a medida de
confiança com segurança, pois mesmo com o suporte muito baixo, as ações foram
executadas pelo menos 1000 vezes.
Tabela 5.5 Quantidade de variáveis removidas.
Modelo
Modelo 1
(Todas as Variáveis)
Modelo 2
(LVF)
Modelo 3
(Taxa de Ganho)
0
0.01
0
0.01
Qtde de Ações
Removidas
37
12
55
26
0
0.01
0
0.01
71
65
89
85
0
0.01
17
17
27
32
E
0
0.01
0
0.01
0
0.01
Qtde de Ações
Restantes
76
101
58
87
42
48
24
28
96
96
86
81
63
43
42
27
82
80
64
55
31
26
20
17
50
70
71
86
0
0.01
31
33
0
0.01
0
0.01
0
0.01
49
58
82
87
93
96
15%
20%
30%
40%
15%
20%
30%
40%
15%
20%
30%
40%
A Figura 5.24a-d mostra as curvas de desempenho dos modelos construídos
apenas com as ações relevantes. A quantidade de ações utilizada em cada treinamento é apresentada na Tabela 5.5. No Modelo 3 foram removidas a maior quantidade de ações, totalizando 93 e 96 ações para
Em seguida o Modelo 1 com 89 ações removidas para
e
, respectivamente.
.
5.3 Seleção de Ações
Na Figura 5.24a com
78
igual a 15% não foi possível notar nenhum aumento
no desempenho em nenhuma das curvas de aprendizado do treinamento com todas
as variáveis. Para o modelo com E=0 construído com as variáveis selecionadas segundo a taxa de ganho e a redundância nota-se uma aceleração no inicio do treinamento, mas o desempenho do modelo diminuiu aproximadamente 8% terminando o
treinamento com 50% de sucesso. Com E=0.01 o desempenho do modelo também
diminui aproximadamente 5%. O último modelo testado com
foi o construí-
do com as variáveis selecionadas segundo o algoritmo LVF. Para ambos os modelos
construídos com E=0 e E=0.01 pode-se observar uma desaceleração no aprendizado, mas a convergência ficou bem próxima ao modelo construído com todas as variáveis.
(a)
(b)
Comparação do Treinamento
Comparação do Treinamento
(Theta=20%)
55
55
50
50
45
45
40
40
35
35
Desempenho
Desempenho
(Theta=15%)
30
25
20
30
25
20
15
15
10
10
5
5
0
0
0
2000
4000
6000
8000
10000
12000
0
2000
4000
6000
Episódio
N/A E=0
LVF E=0.01
(c)
N/A E=0.01
Tx. Ganho E=0
8000
10000
12000
Episódio
Tx. Ganho E=0.01
LVF E=0
N/A E=0
LVF E=0.01
(d)
Comparação do Treinamento
N/A E=0.01
Tx. Ganho E=0
Tx. Ganho E=0.01
LVF E=0
Comparação do Treinamento
(Theta=30%)
(Theta=40%)
55
60
50
50
45
35
Desempenho
Desempenho
40
30
25
20
40
30
20
15
10
10
5
0
0
0
2000
4000
6000
8000
10000
12000
0
2000
4000
6000
Episódio
N/A E=0
LVF E=0.01
N/A E=0.01
Tx. Ganho E=0
8000
10000
12000
Episodes
Tx. Ganho E=0.01
LVF E=0
N/A E=0
LVF E=0.01
N/A E=0.01
Tx. Ganho E=0
Tx. Ganho E=0.01
LVF E=0
Figura 5.24 Curvas de desempenho (média de dez execuções) de todas as abordagens relativas as seleções de ações variando o parâmetro
Na Figura 5.24b com
.
igual a 20% foi possível notar um aumento de 5% no
desempenho do modelo construído com todas as variáveis para ambos valores do
5.3 Seleção de Ações
79
parâmetro de exploração (E=0 e E=0.01). As curvas de desempenho para E=0 e
E=0.01 do modelo construído segundo a taxa de ganho e a redundância tiveram desempenho bem próximo durante todo o treinamento. Houve uma aceleração no inicio do aprendizado se comparado com o modelo construído com todas as ações,
mas o desempenho diminui aproximadamente 8% quando E foi igual a zero e continuou o mesmo para E=0.01. Para o modelo construído com as variáveis selecionadas pelo algoritmo LVF o desempenho diminuiu 5% em ambas as curvas (E=0 e
E=0.01).
Na Figura 5.24c com
igual a 30% o modelo construído com todas as variá-
veis e E=0 aumentou o desempenho em aproximadamente 5% se comparado com o
modelo com todas as ações. Com as ações selecionadas com
igual a 20% o de-
sempenho foi próximo para este modelo. Para o modelo construído com as variáveis
selecionadas segundo a taxa de ganho e a redundância houve uma redução no desempenho para ambas as curvas. O modelo construído com E=0 teve desempenho
de 45% enquanto que para E=0.01 o desempenho foi de aproximadamente 40%.
Com a seleção das ações para o modelo construído com as variáveis selecionadas
pelo algoritmo LVF, o desempenho com E=0 foi o mesmo desempenho do modelo
construído com todas as ações. Com E=0.01 o desempenho foi 10% menor que o
modelo construído com todas as ações.
A Figura 5.24d mostra as curvas de desempenho dos modelos construídos
com
igual a 40%. O desempenho do modelo construído com todas as variáveis
obteve os melhores resultados quando
foi igual a 30%. Com E=0 houve uma ace-
leração no desempenho do agente. O desempenho do modelo após 6000 episódios
atingiu aproximadamente 50% de sucesso. No fim do treinamento o modelo terminou com aproximadamente 55% de sucesso. Com E=0.01 o modelo também apresenta uma aceleração no aprendizado e converge com 50% de sucesso. O desempenho do restante dos modelos ficou abaixo do desempenho com todas as ações
exceto para o modelo com E=0.01 construído utilizando as variáveis selecionadas
pelo algoritmo LVF que teve desempenho próximo ao modelo construído com todas
as ações.
5.4 Comparação dos Modelos
5.4
80
Comparação dos Modelos
Para avaliar a eficiência das abordagens utilizadas decidiu-se avaliar o uso da memória e o desempenho do agente no drible. Para isto construíram-se intervalos de
confiança de 95% segundo a distribuição t-student apresentados em gráficos Boxwhisker.
5.4.1 Teste do Desempenho
Para avaliar o desempenho do agente no drible foi retirado de cada curva de aprendizado o modelo que teve desempenho próximo a média. Todos estes modelos serão testados 10 vezes no mesmo ambiente em que foram treinados. Cada teste equivale à freqüência relativa de sucesso do agente no drible em 300 episódios. Durante o teste dos modelos a aprendizagem e a exploração não serão realizadas.
Teste do Modelo
(Todos Atributos)
54
52
50
Desempenho
48
46
44
42
40
38
36
34
32
Conf. 40%, E=0.01
Conf. 40%, E=0
Conf. 30%, E=0.01
Conf. 30%, E=0
Conf. 20%, E=0.01
Conf. 20%, E=0
Conf. 15%, E=0.01
Conf. 15%, E=0
Todas Ações, E=0.01
Todas Ações, E=0
30
Média
Média±EP
Média±2,262*EP
Figura 5.25 Comparação do desempenho no teste dos modelos (média de dez execuções) com todas as variáveis.
A Figura 5.25 compara o desempenho dos modelos construídos com todos os
atributos. Note que a exploração proporcionou um aumento no desempenho em to-
5.4 Comparação dos Modelos
dos os casos exceto para
81
. No desempenho dos modelos das Figuras 5.26
e 5.27 este comportamento também é observado, exceto para
nos mode-
los construídos com os atributos selecionados segundo a taxa de ganho e a redundância.
Teste do Modelo
Conf. 40%, E=0.01
Conf. 40%, E=0
Conf. 30%, E=0.01
Conf. 30%, E=0
Conf. 20%, E=0.01
Conf. 20%, E=0
Conf. 15%, E=0.01
Conf. 15%, E=0
Todas Ações, E=0.01
60
58
56
54
52
50
48
46
44
42
40
38
36
34
Todas Ações, E=0
Desempenho
(Taxa de Ganho e Redundância)
Média
Média±EP
Média±2,262*EP
Figura 5.26 Comparação do desempenho dos modelos (média de dez execuções)
no teste com as variáveis selecionadas segundo a Taxa de Ganho e a Redundância.
Observando as Figuras 5.25, 5.26 e 5.27, nota-se que a seleção de ações
proporcionou um aumento significativo no desempenho dos modelos. Na Figura 5.25
o melhor desempenho foi quando
foi igual a 40%. Neste caso, a redução da quan-
tidade de ações foi de aproximadamente 75% de um total de 113 ações.
No modelo construído com os atributos selecionados segundo a taxa de ganho e redundância, o melhor desempenho também foi obtido através da seleção de
ações (Figura 5.26). Apenas no modelo LVF o melhor desempenho foi obtido apenas com a seleção de atributos. No entanto, o desempenho com
igual a 40% e
E=0.01 obteve desempenho muito próximo do melhor conforme pode ser visto na
Figura 5.27.
5.4 Comparação dos Modelos
82
Teste do Modelo
(LVF)
50
48
Desempenho
46
44
42
40
38
36
34
Conf. 40%, E=0.01
Conf. 40%, E=0
Conf. 30%, E=0.01
Conf. 30%, E=0
Conf. 20%, E=0.01
Conf. 20%, E=0
Conf. 15%, E=0.01
Conf. 15%, E=0
Todas Ações, E=0.01
Todas Ações, E=0
32
Média
Média±EP
Média±2,262*EP
Figura 5.27 Comparação do desempenho dos modelos (média de dez execuções)
no teste com as variáveis selecionadas pelo algoritmo LVF.
De uma maneira geral, a seleção de atributos proporcionou um aumento significativo no desempenho dos modelos. Apenas quando E foi igual a 0 é que o desempenho dos modelos das Figuras 5.26 e 5.27 foi próximo ao dos modelos da Figura 5.25. O melhor desempenho foi obtido com a seleção de atributos segundo a
taxa de ganho e redundância.
5.4.2 Uso da Memória
A Figura 5.28 compara o uso da memória com a variação dos parâmetros
e
nos
modelos construídos com todas as variáveis. A seleção de ações proporcionou uma
redução no uso da memória. No pior caso, com
e
, o uso da memória
foi reduzido em média 30% a menos do que o modelo com todas as ações. No melhor caso tem-se uma redução de aproximadamente 95%.
5.4 Comparação dos Modelos
83
Uso da Memória
(Todas as Variáveis)
20
18
16
14
12
10
8
6
4
2
Conf. 40%, E=0.01
Conf. 40%, E=0
Conf. 30%, E=0.01
Conf. 30%, E=0
Conf. 20%, E=0.01
Conf. 20%, E=0
Conf. 15%, E=0.01
Conf. 15%, E=0
Todas Ações, E=0.01
Todas Ações, E=0
0
Média
Média±EP
Média±2,262*EP
Figura 5.28 Comparação do uso da memória dos modelos (média de dez execuções) com todas as variáveis.
Uso da Memória
(Taxa de Ganho)
2,4
Memória em Megabytes
2,2
2,0
1,8
1,6
1,4
1,2
1,0
0,8
0,6
Conf. 40%, E=0.01
Conf. 40%, E=0
Conf. 30%, E=0.01
Conf. 30%, E=0
Conf. 20%, E=0.01
Conf. 20%, E=0
Conf. 15%, E=0.01
Conf. 15%, E=0
Todas Ações, E=0.01
Todas Ações, E=0
0,4
Média
Média±EP
Média±2,262*EP
Figura 5.29 Comparação do uso da memória dos modelos (média de dez execuções) com as variáveis selecionadas pelo algoritmo Taxa de Ganho.
5.5 Qualidade do Drible
84
De acordo com a Figura 5.30, os atributos selecionados pelo algoritmo LVF
proporcionou a maior redução no uso de memória, cerca de 900KB contra 2,2MB da
taxa de ganho e 17,7MB do modelo com todos os atributos e ações, i.e., uma redução de 60% se comparado com a taxa de ganho e mais que 95% se comparado com
a utilização de nenhuma abordagem para a seleção de atributos e ações. Os resultados são significativos e mostram que a seleção de atributos pode diminuir consideravelmente o uso de memória dos modelos baseados em tabelas.
Uso da Memória
(LVF)
1,0
Memória em Kilobytes
0,9
0,8
0,7
0,6
0,5
Conf. 40%, E=0,01
Conf. 40%, E=0
Conf. 30%, E=0,01
Conf. 30%, E=0
Conf. 20%, E=0,01
Conf. 20%, E=0
Conf. 15%, E=0,01
Conf. 15%, E=0
Todas Ações, E=0,01
Todas Ações, E=0
0,4
Média
Média±EP
Média±2,262*EP
Figura 5.30 Comparação do uso da memória dos modelos com as variáveis selecionadas pelo algoritmo LVF (média de dez execuções).
A combinação dos dois métodos, seleção de ações e atributos, proporcionou
uma redução ainda maior em todas as abordagens, se comparado somente com a
seleção de atributos. Em alguns experimentos foi possível notar um aumento no uso
da memória quando a exploração foi incentivada. No entanto, é um custo necessário
para o desempenho do modelo aumentar.
5.5
Qualidade do Drible
Existem duas medidas que se pode utilizar para medir a qualidade do drible, o tempo de execução do drible e a distância final do oponente. Dribles que são realizados
5.5 Qualidade do Drible
85
rápidos possibilitam jogadas mais rápidas e velocidade é um critério chave para
qualquer estratégia de um time de futebol. A distância do oponente que o agente
conseguiu também é importante para a qualidade do drible. Quanto maior a distância que o agente conseguir de seu oponente, menores serão as chances de perder a
bola após o drible. Em todos os experimentos o tempo médio do drible ficou em torno de 13 passos e a distância final do oponente em torno de 1.2 metros.
Capítulo 6
Conclusão
O principal objetivo deste trabalho foi mostrar como as técnicas de mineração de
dados podem ser utilizadas nos ambientes da aprendizagem por reforço. Os experimentos utilizaram algumas técnicas de mineração de dados para selecionar as variáveis e ações mais relevantes do problema abordado, o drible. A aplicação destas
técnicas serviu para reduzir a dimensionalidade do problema com a eliminação das
variáveis e ações menos relevantes. Foi mostrado que a redução da dimensionalidade pode aumentar o desempenho do agente e reduzir o tempo de convergência
dos modelos da aprendizagem por reforço.
Para tornar possível a utilização das técnicas de mineração de dados, inicialmente foi preciso que o treinamento do agente estivesse presente em um banco de
dados. O Capítulo 4 mostrou uma possível forma de armazenamento para o treinamento do agente através do esquema apresentado na Figura 4.2 (página 51).
Mesmo com o treinamento armazenado em um banco de dados, ainda não é
possível utilizar os algoritmos para a seleção de atributos sem antes transformar o
problema que, naturalmente é por reforço, em um problema supervisionado. A Seção 4.3 (página 48) propôs utilizar a ação do agente como atributo classe. De acordo
com Cohen e Maimon (2005), as ações tomadas pelo agente podem ser consideradas as respostas desejadas utilizadas na aprendizagem supervisionada. Desta forma foi possível obter todo mapeamento da política do agente. A utilização destes
dados para a seleção de atributos permite identificar quais atributos influenciam na
decisão do agente.
86
6.1 Resultados e Discussões
6.1
87
Resultados e Discussões
O Drible
Uma das contribuições deste trabalho foi demostrar que o algoritmo
com-
binado com o aproximador linear CMAC pode ser utilizado com sucesso em problemas como o do drible. O drible é um problema da aprendizagem por reforço de
grande complexidade e pouco abordado na literatura.
Neste trabalho, o ambiente do drible foi composto de 23 variáveis de estado
contínuas e 113 ações realizáveis (ver Tabela 3.4 e Tabela 3.3 nas páginas 33 e
32). Mesmo com esta complexidade, o agente aprendeu a driblar e conseguiu alcançar um desempenho de 45% (Figura 5.6, página 60), no teste o desempenho foi bem
próximo (Figura 5.25, página 80). Após a eliminação de algumas variáveis irrelevantes segundo a taxa de ganho e a redundância (Tabela 5.4, página 64), o modelo
conseguiu atingir um desempenho médio de 55% (Figura 5.12, página 67). No teste,
o desempenho do modelo foi maior quando removidas as variáveis e ações irrelevantes (Figura 5.26, página 80).
Convergências mais rápidas foram alcançadas quando as ações irrelevantes
foram removidas. A remoção das variáveis irrelevantes também proporcionou uma
redução no tempo de convergência e, mais importante, um aumento do desempenho
do agente.
O agente utilizou em média 13 passos para conseguir realizar o drible, algo
em torno de 2.5 segundos para concluir. A distância final entre o oponente e o agente ficou em média 1.2 metros. Esta distância permitiu ao agente continuar com a bola após o drible sem a possibilidade de perdê-la para o oponente.
Modelo Utilizado
Através da utilização do algoritmo
combinado com o aproximador Linear
CMAC foi possível construir um modelo capaz de aprender através da interação com
o ambiente. Com o uso deste aproximador foi possível construir um modelo capaz
de generalizar. A quantidade de estados visitados pelo agente foi muito menor do
que a quantidade total existente no problema do drible. O modelo construído possibi-
6.1 Resultados e Discussões
88
litou utilizar em regiões do espaço de estados nunca visitados, o conhecimento adquirido em regiões vizinhas.
Mesmo com a quantidade de variáveis irrelevantes presentes no treinamento,
o modelo foi capaz de atingir níveis de desempenho muitos bons, o que mostrou sua
tolerância a ruídos. Riedmiller (Riedmiller, 1999) mostrou que o tempo de convergência das redes neurais de múltiplas camadas pode aumentar drasticamente com o
aumento da quantidade de ações. Este comportamento não é observado quando
utilizado o aproximador linear CMAC.
Os experimentos mostraram que o CMAC é uma técnica confiável e adequadamente aplicável em ambientes complexos com grande quantidade de ações e variáveis. A grande quantidade de ações e variáveis não foi um obstáculo para o modelo, tendo a convergência garantida em todos os experimentos.
Mineração de Dados na Aprendizagem por Reforço
Nos modelos da aprendizagem por reforço, a qualidade dos atributos e ações é de
grande importância para a convergência e generalização. A escolha cuidadosa dos
atributos do ambiente e ações do agente é de fundamental importância para seu aprendizado, pois atributos desnecessários aumentam o espaço de busca, tornando
difícil encontrar uma solução ótima (Coons et al., 2008).
Os experimentos realizados mostraram que a simples aplicação de algumas
técnicas da mineração de dados em problemas da aprendizagem por reforço possibilita aumentar o desempenho destes modelos. Através do uso da mineração de dados foi possível identificar e eliminar as variáveis e ações irrelevantes. Com isto a
complexidade do modelo pode ser reduzida, a generalização aumentada e o tempo
de convergência diminuído.
Seleção de Atributos
De uma maneira geral, as técnicas utilizadas para selecionar atributos proporcionaram um aumento no desempenho do treinamento do agente (ver Figuras 5.26 e 5.27
nas páginas 81 e 82). O mesmo pode ser observado no teste dos modelos (Seção
5.4, página 80). A eficiência das técnicas de seleção de atributos utilizada no pro-
6.1 Resultados e Discussões
89
blema abordado mostrou desempenhos bem próximos. No entanto, em termos absolutos, a utilização da taxa de ganho permitiu obter o melhor desempenho segundo a
freqüência relativa de sucesso do agente no drible em ambos os casos: treinamento
e teste. Contudo, para utilizar esta técnica é preciso de no mínimo um pouco de conhecimento do problema, pois os atributos mais relevantes não são selecionados
automaticamente, ao invés disto esta técnica apenas faz um ranking entre as variáveis.
A remoção das variáveis redundantes e com menor taxa de ganho permitiu
aumentar o desempenho e reduzir o tempo de convergência no treinamento do modelo construído (ver Figura 5.12 na página 67). A quantidade de memória utilizada
por este modelo foi de aproximadamente 2,2 MBytes com E=0 e 1,6 MBytes com
E=0.01; neste caso, houve uma redução de 90% se comparado com o uso de memória do modelo com todas as variáveis. Com isto pode-se dizer que o uso da taxa
de ganho como medida para identificar e selecionar os atributos mais relevantes é
muito adequada a ambientes da aprendizagem por reforço.
Apesar do modelo construído com as variáveis selecionadas pelo algoritmo
LVF ter apresentado desempenho pior que a taxa de ganho, este algoritmo é capaz
de identificar automaticamente
subconjuntos de atributos relevantes de todos os
subconjuntos de atributos existentes, onde
. Esta abordagem di-
minui consideravelmente o espaço de busca. A modificação do algoritmo proposta
por este trabalho mostrou que o critério de inconsistência é uma medida eficiente
para a avaliação de um subconjunto de atributos.
O algoritmo LVF possibilitou uma redução maior da quantidade de atributos,
se comparado com a taxa de ganho. Conseqüentemente a quantidade de memória
utilizada foi menor, consumindo em média 600 Kbytes, i.e, uma redução de aproximadamente 95% se comparado com o uso de memória do modelo com todas as
variáveis.
Seleção de Ações
De uma maneira geral, as técnicas utilizadas para selecionar ações proporcionaram
um aumento no desempenho do treinamento do agente apenas quando não utilizado
nenhuma abordagem para a seleção de atributos. No teste a combinação das técnicas proporcionou um aumento no desempenho dos modelos. Com a combinação da
6.2 Contribuições e Relevância
90
seleção de ações com a seleção de atributos utilizando a taxa de ganho o desempenho do agente no treinamento caiu no mínimo 4%, mas a redução de memória foi
maior. No teste do modelo, a seleção de ações proporcionou um aumento de aproximadamente 4%, no desempenho do modelo.
No treinamento, as variáveis selecionadas pelo algoritmo LVF não reduziu o
desempenho quando
foi igual a 40%, mas para
houve uma redução de
no mínimo 3%. O mesmo comportamento foi observado no teste do modelo.
As medidas de suporte e confiança mostraram ser eficientes na identificação
das ações mais relevantes. Os experimentos mostraram que a técnica de seleção de
ações pode proporcionar um aumento no desempenho dos modelos da aprendizagem por reforço. Além disto, com a seleção de ações foi possível reduzir o tempo de
convergência em alguns modelos.
Assim como na seleção de atributos, a técnica utilizada para selecionar as
ações proporcionou uma redução no uso da memória em todos os casos (ver Figuras 5.28, 5.29 e 5.30 nas páginas 83 e 84). O pequeno intervalo de confiança em
todos os modelos mostra que a variação do uso da memória entre os treinamentos
foi baixa. O modelo construído com as variáveis selecionadas pelo algoritmo LVF
continuou a apresentar o menor uso da memória, consumindo em média 450KB. Em
seguida a taxa de ganho com 600KB e por último o modelo com todas as variáveis
que consumiu em média 1MB.
6.2
Contribuições e Relevância
Neste trabalho, foram apresentados um modelo de aprendizagem baseado na técnica de aproximação paramétrica CMAC, a modelagem do ambiente do drible como
um problema da aprendizagem por reforço, um esquema para armazenamento dos
dados de treinamento do agente, a seleção dos dados armazenados e a análise dos
resultados do drible e da utilização das técnicas de mineração de dados para aumentar o desempenho e reduzir o consumo de memória do modelo.
A utilização das abordagens descritas neste trabalho possibilitou aumentar o
desempenho do modelo CMAC. Outra característica importante foi a redução de
memória que a seleção de atributos e ações proporcionaram. Com o uso das técnicas de mineração foi possível notar uma redução de 95% no consumo de memória
dos modelos se comparado com o construído com todas as variáveis. A utilização de
6.3 Trabalhos Futuros
91
17MB de memória nos computadores atuais não apresenta um obstáculo, mas se o
modelo é construído para operar em sistemas embarcados, tais como uma geladeira, câmera fotográfica ou celular a quantidade de memória utilizada pode determinar
o valor final do aparelho. Outra vantagem considerada é a possibilidade da redução
do consumo de energia e processamento. Uma outra vantagem da seleção de atributos e ações foi com relação ao tempo de convergência que diminuiu. Apesar do
tempo de convergência não ter alcançado valor significativos no modelo CMAC, a
utilização da técnica em outros modelos, tais como as redes neurais de múltiplas
camadas podem proporcionar uma redução significativa no tempo de convergência
(Riedmiller, 1999).
Além de possibilitar o uso das técnicas descritas no Capítulo 4, o armazenamento do treinamento do agente em um banco de dados através do esquema apresentado na Figura 4.2 (página 51), resultou em uma série de outras vantagens, tais
como a análise do comportamento do agente, possibilidade de transformação das
variáveis, treinamento off-line e outras.
Em suma, as contribuições apresentadas por este trabalho foram:

A utilização das técnicas de mineração de dados para a identificação de
atributos e ações relevantes.

A redução do consumo de memória dos modelos.

Redução da complexidade e aumento do desempenho do agente.

A solução do problema do drible utilizando o algoritmo
combina-
do com a técnica de tile-coding.
O produto final da dissertação, o modelo, mostrou ser capaz de realizar o drible com eficiência, demonstrando que a utilização da mineração de dados em ambientes da aprendizagem por reforço é valida e merece especial atenção como alvo de
novos estudos.
6.3
Trabalhos Futuros
Como trabalhos futuros planeja-se aplicar outras técnicas da mineração de dados
além das descritas neste trabalho. Também pretende-se aplicar as técnicas descri-
6.3 Trabalhos Futuros
92
tas no Capítulo 4 em outros problemas da aprendizagem por reforço que são encontrados freqüentemente na literatura, tais como o keepaway (Stone & Sutton, 2001).
Outro trabalho que pretende-se realizar é a utilização das técnicas de mineração
de dados para reduzir a complexidade de outros modelos, tais como uma rede neural. Segundo Riedmiller (Riedmiller, 1999), a complexidade do problema tem forte
influência no desempenho deste modelo. Deseja-se também verificar o quanto o drible pode melhorar a eficiência de um time.
Apêndice A
Aprendizagem por Reforço
A.1 Introdução
A aprendizagem por reforço não é definida por caracterizar métodos de aprendizagem, mas por caracterizar um problema de aprendizagem e, qualquer método que
seja capaz em solucioná-lo é considerado como um método da aprendizagem por
reforço (Sutton & Barto, 1998). Estes Métodos devem ser capazes de associar ações aos estados do ambiente, para que, de tal forma, possibilite selecionar as melhores ações que maximizem seu sinal de recompensa. Basicamente este tipo de
aprendizagem caracteriza-se em um problema de otimização, onde o agente deve
buscar otimizar a escolha de sua ações, através de sua interação com o ambiente,
em função da recompensa recebida em cada estado visitado.
Em um sistema de aprendizagem por reforço, existem quatro elementos principais, são eles: uma política que define o comportamento do agente em um dado
momento, uma função de recompensa que define o objetivo do agente, uma função valor que indica os estados que o levam a maior recompensa ao longo do tempo, e opcionalmente, um modelo do ambiente que define os estados e outros aspectos do ambiente (Sutton & Barto, 1998).
93
A.1 Introdução
94
Figura A.1 Interação agente-ambiente. Traduzido da fonte: (Sutton & Barto, 1998)
Na Figura A.1, o agente interage com o ambiente em uma seqüência de tempo discreto,
. A função de recompensa permite o mapeamento de
cada estado do ambiente em um sinal numérico chamado recompensa,
do agente é realizar uma ação
possa levar a um estado
em um estado
. A tarefa
, seguindo uma política que o
que resulte em um maior retorno de recompensas
ao longo do tempo, pois estados que aparentemente dão a maior recompensa podem levar a outros que não dão (Sutton & Barto, 1998). A busca por estados que
aumentem a sua recompensa ao longo do tempo, permite que o agente sempre visite os estados que o levem para a maior quantidade de recompensa acumulada e
não para a maior num dado momento. Em suma o agente deve ser orientado para
maximizar o retorno
definido por:
(A.1)
onde
é o instante de tempo final.
Existem casos em que o ambiente não termina naturalmente em um episódio.
Nestes casos
pode facilmente tender ao infinito e conseqüentemente
também
tenderá. Para solucionar este problema é utilizada uma taxa de desconto (Sutton &
Barto, 1998). A taxa de desconto permite determinar a importância das recompensas
futuras sobre as passadas. A equação a seguir aplica a taxa de desconto na expressão do retorno
definida anteriormente:
(A.2)
onde
é um parâmetro compreendido no intervalo
. Os métodos de aprendiza-
gem por reforço devem especificar como o agente deve mudar a sua política em
A.1 Introdução
95
função de sua experiência para maximizar a soma das recompensas descontadas
que recebe ao longo do tempo (Sutton & Barto, 1998).
Uma política, segundo Sutton e Barto (1998), é o mapeamento dos estados
em probabilidades de se realizar uma ação, denotado por . Este mapeamento é
tido como a probabilidade de selecionar uma ação
o estado é , ou seja,
no instante de tempo
quando
. A estimativa de quanto será prazeroso para o agente
seguir uma determinada política pode ser obtida através de uma função valor.
A função valor pode ser representada por uma função valor-estado ou uma
função valor-ação. A função valor-estado, denotada por
um estado
, representa o valor de
em uma política . Em outras palavras, a função valor-estado define o
retorno esperado quando o agente inicia em
e segue uma política
logo após.
Se mantida a estimativa de recompensa das ações separadas para cada estado é possível obter uma função valor-ação. A função valor-ação, denotada por
, define o retorno esperado quando o agente inicia em , realiza uma ação
e segue uma política
logo após.
Uma propriedade fundamental das funções valor é que estas satisfazem uma
relação recursiva entre o valor de um estado e os valores de seus estados sucessores (Sutton & Barto, 1998). A equação de Bellman para
que mantém esta recursi-
vidade é dada a seguir:
(A.3)
,
de forma similar a equação de Bellman pode ser obtida para uma função valor-ação
,
A.1 Introdução
96
(A.4)
onde em ambas as equações,
gue uma política
aleatória,
se realizada a ação ,
denota o valor esperado dado que o agente seé probabilidade de transição entre os estados
é a recompensa esperada desta transição,
babilidade de uma ação
ocorrer no estado
e
e
é a pro-
é a taxa de desconto. O processo
que retorna para cada estado o valor de todos os estados sucessores é chamado de
fullbackup ou retorno total (Sutton & Barto, 1998).
A.1.1 Política Ótima
De acordo com Bellman (1952), uma política ótima consiste em uma seqüência de
ações que sejam mais vantajosas de acordo com algum critério estabelecido previamente. A solução de um problema da aprendizagem por reforço é alcançada quando o agente encontra uma política que seja melhor do que todas as outras políticas,
possibilitando receber uma maior quantidade de recompensa ao longo do tempo.
Segundo Sutton e Barto (1998), uma política
é melhor que outra política
retorno esperado no total dos estados é maior que o da política
vras,
é melhor que
Se uma política
por
se e somente se
se o
. Em outras pala-
para todos os estados.
é melhor que todas as outras então esta política, denotada
, é chamada de ótima. Existe ao menos uma política que é igual ou melhor
que todas as outras políticas e compartilham a mesma função valor-estado, que neste caso é chamada de função valor-estado ótima e é denotada por
ou por
caso
A.2 Programação Dinâmica
97
se utilize uma função valor-ação (Sutton & Barto, 1998). A função valor-estado ótima
é definida pela equação a seguir:
(A.5)
onde
é a função valor-estado ótima,
sição entre os estados
e
se realizada a ação , e
desta transição. Para cada estado
para um estado
em que
é o estado atual,
é probabilidade de trané recompensa esperada
existe uma ou mais ações que levam o agente
é máximo. Uma política que associa probabilidade
maior que zero apenas para estas ações é considerada política ótima. Outra forma
de encontrar uma política ótima é através uma função valor-ação:
(A.6)
onde
tados
é a função valor-ação ótima,
e
se realizada a ação , e
é a probabilidade de transição entre os esé recompensa esperada desta transição.
As Equações A.5 e A.6 são derivadas do princípio da otimalidade, definido por
Bellman como: “Uma política ótima tem a propriedade de que qualquer que seja o
estado inicial e decisões iniciais, as próximas decisões devem ser constituídas de
uma política ótima” (Bellman, 1952). Este conceito constitui a base da programação
dinâmica e da aprendizagem por reforço (Sutton & Barto, 1998).
A.2 Programação Dinâmica
O termo programação dinâmica refere-se a uma coleção de algoritmos que, dado o
perfeito modelo do ambiente como um processo de decisão de Markov (Markov Decision Process ou MDP), é suficiente para se encontrarem políticas ótimas (Sutton &
Barto, 1998).
Um ambiente é dito como Markoviano, ou de possuir a propriedade de Markov, se todas as informações relevantes do ambiente que descrevem o seu estado
A.2 Programação Dinâmica
98
atual sejam suficientes para determinar o seu futuro estado e recompensa (Sutton &
Barto, 1998). Desta forma, a dinâmica do ambiente pode ser formalmente definida
em termos probabilísticos:
ou seja, dados apenas os estados atuais, ambientes que possuem a propriedade de
Markov possibilitam a predição dos próximos estados
e recompensa . O estado
atual contém a informação dos estados anteriores. Assim, a decisão de que ação
tomar não depende da seqüência de estados anteriores.
Para utilizar os algoritmos da programação dinâmica é preciso que seja conhecida a probabilidade de transição entre os estados e a recompensa esperada
desta transição. Esta característica limita o uso da programação dinâmica na maioria
dos problemas de aprendizagem por reforço porque, na maioria dos casos, as probabilidades de transição não são conhecidas. Outra restrição deve-se ao alto processamento computacional necessário para se encontrar uma política ótima.
A.2.1 Processo de Aprendizagem
O processo de aprendizagem dos métodos da programação dinâmica resume-se em
duas etapas conhecidas como policy evaluation (avaliação da política) e policy improvement (otimização da política) (Sutton & Barto, 1998). A etapa de policy evaluation consiste em gerar um episódio, seguindo uma política inicialmente arbitrária , e
calcular as novas estimativas
para cada estado
visitado durante o episódio.
A próxima etapa, policy improvement, consiste em encontrar uma nova política
tal forma que,
, de
.
A.2.1.1 Policy Evaluation
O objetivo da etapa de policy evaluation é computar a função valor-estado ou valoração para uma política probabilística ou determinística . De uma maneira simples
as funções valor podem ser encontradas resolvendo-se um sistema de equações
lineares dado pelas Equações A.3 ou A.4. Outro meio para encontrar as funções valor é através de um processo iterativo. Este processo pode ser obtido utilizando as
A.2 Programação Dinâmica
equações de Bellman para aproximar
99
gradativamente em um procedimento itera-
tivo:
(A.7)
e
(A.8)
Desta forma,
ções valor
biente. Se
é obtida através de uma seqüência de estimativas de funobtidas através de
então é garantido que
passagens por todos os estados do am(Sutton & Barto, 1998).
A.2.1.2 Policy Improvement
A etapa de policy improvement trata de encontrar políticas melhores tornando-as
gulosas em relação à função estado-valor de uma outra política. As equações de
Bellman descritas na subseção anterior referiram-se a uma política probabilística
. Nesta seção as equações A.7 e A.8 são alteradas, para referenciar uma política determinística
, conforme descrito a seguir.
(A.9)
e
(A.10)
Dada uma política determinística , uma forma para encontrar melhores políticas é considerar outras ações, onde
que aparenta ser melhor de acordo com
. Selecionar em cada estado a ação
permite encontrar uma nova política
A.2 Programação Dinâmica
100
que seja melhor que ou igual que à anterior. Formalmente esta nova política é dada
por:
(A.11)
Estas ações fazem parte de uma nova política
, então seguir
. Se para todo
,
permite obter um retorno que é maior que ou
igual a .
A.2.1.3 Policy Iteration
O processo conhecido como policy iteration (Iteração da Política) refere-se à idéia de
que, por meio de sucessivas iterações entre policy evaluation e policy improvement,
é possível se obter uma seqüência monotonicamente crescente de melhores políticas e estimativas que podem convergir para uma política ótima
(Sutton & Barto,
1998), ou seja:
Desta forma, se for garantido que o processo de iteração entre as etapas de
policy evaluation e policy improvement ocorra infinitas vezes, é possível encontrarem-se as estimativas
de cada estado e uma política ótima
.
O Algoritmo A.1 mostra o pseudocódigo da policy iteration. Este algoritmo é
dividido nas duas etapas, policy evaluation e policy improvement, descritas anteriormente. O algoritmo é resumido a seguir. Dada uma política determinística e inicialmente arbitrária a primeira etapa do algoritmo encontra os valores da função valorestado para cada estado desta política. A próxima etapa, policy improvement, encontra uma nova política fazendo-a gulosa com respeito aos valores de
processo se repete a partir da etapa anterior se
.
. O
A.2 Programação Dinâmica
101
início:
, para todo ;
Policy Evaluation:
repita
;
para cada
faça
;
;
;
fim
até
;
Policy Improvement:
;
para cada
faça
;
;
se
então
;
fim
se
então
;
senão vá para Policy Evaluation;
fim
Algoritmo A.1 Algoritmo policy iteration.
Formalmente, o processo de avaliação da política converge apenas quando o
número de iteração tende a infinito, mas na prática, segundo Sutton & Barto (Sutton
& Barto, 1998), o processo pode ser finalizado em poucas iterações. Neste algoritmo, a medida de convergência consiste no teste de
realiza-
do ao fim da atualização das estimativas de cada estado e, o critério de parada é
atingido quando este valor for suficientemente pequeno (Sutton & Barto, 1998). O
processo iterativo do Algoritmo A.1 é finalizado quando a política não se altera, o
que é considerado como convergência para uma política ótima
.
A.2 Programação Dinâmica
102
A.2.1.4 Value Iteration
A desvantagem do método iterativo esta relacionada ao tempo necessário para a
convergência de
que ocorre somente quando o número de iteração tende a infini-
to (Sutton & Barto, 1998), tornando a convergência de
para
lenta, já que as pró-
ximas políticas são calculadas somente após o termino da etapa anterior. Felizmente
a etapa policy evaluation pode ser interrompida sem perder a garantia de convergência (Sutton & Barto, 1998). Para isto, o algoritmo value iteration combina as etapas de policy evaluation e policy improvement em uma única passagem pelos estados do ambiente. A equação resultante é semelhante à equação ótima de Bellman
(Equação A.5):
( A.12)
Para
arbitrário, a seqüência
ções que garantem a existência de
converge para
sob as mesmas condi-
(Sutton & Barto, 1998). A combinação entre
as etapas de policy evaluation e policy improvement também pode ser obtida utilizando a equação ótima de Bellman para uma função valor-ação. O Algoritmo A.2
apresenta o método value iteration.
início:
, para todo ;
repita
;
para cada
faça
;
;
;
fim
até
;
;
Algoritmo A.2 Algoritmo value iteration.
A.3 Algoritmos da Aprendizagem por Reforço
103
A grande desvantagem dos algoritmos policy iteration e value iteration devese às múltiplas passagens pelos estados do ambiente. Se o ambiente tem um número muito grande de estados uma única passagem pelos estados teria um custo computacional muito alto (Kaelbling et al., 1996).
A.3 Algoritmos da Aprendizagem por Reforço
Nas seções anteriores foram apresentados os principais conceitos e algumas dificuldades encontradas nos métodos da programação dinâmica. A principal dificuldade
encontrada, o que limita o seu uso, é a necessidade do modelo completo do ambiente. Como visto anteriormente, o modelo completo do ambiente contém as probabilidades de transições entre os estados, sendo esta informação, não encontrada em
grande parte dos problemas da aprendizagem por reforço. Outra dificuldade encontrada é o seu alto processamento. A cada iteração, os algoritmos da programação
dinâmica realizam múltiplas passagens por todos os estados do ambiente o que leva
a um custo computacional muito alto. Contudo, os algoritmos da programação dinâmica são exponencialmente mais rápidos do que qualquer busca direta no espaço
de políticas (Sutton & Barto, 1998).
Esta seção aborda os principais métodos da aprendizagem por reforço, cada
qual com suas vantagens e desvantagens. Uma das principais características destes
métodos é a possibilidade de sua utilização em problemas que não disponibilizam o
modelo completo do ambiente. As próximas seções apresentam algoritmos que
permitem que o aprendizado ocorra on-line através da interação do agente com o
ambiente. Este tipo de aprendizado não requer múltiplas passagens por todos os
estados do ambiente a cada iteração, ao invés disto, são utilizados apenas exemplos da seqüência de estados, ações e recompensas retiradas da interação do agente com o ambiente. No entanto, é preciso garantir que todas as ações tenham alguma probabilidade de serem escolhidas. De um modo geral, a solução para este problema é incentivar a exploração assegurando que todas as ações tenham chances
de serem executadas. De acordo com Sutton e Barto (1998), existem dois tipos de
métodos que podem assegurar isto, chamados de métodos on-policy e off-policy.
Basicamente os métodos on-policy avaliam e aperfeiçoam a política que é utilizada para tomar suas decisões, ou seja, estes métodos estimam o valor da política
A.3 Algoritmos da Aprendizagem por Reforço
104
enquanto a utilizam no controle do agente. Já nos métodos off-policy, estas duas
funções são separadas. A política utilizada para o controle do agente, chamada de
política de comportamento, deve ser independente da política que é avaliada e otimizada, chamada de política de estimação (Sutton & Barto, 1998).
Em ambos os métodos a política é geralmente flexível. Sendo assim, a estimativa de todo par estado-ação tem probabilidade
de ser escolhida. Uma
possível variação para estes métodos consiste em fazer com que o agente siga uma
política
(Watkins, 1989) descrita a seguir.
Agentes que seguem uma política
devem, na maior parte do tem-
po, selecionar uma ação que possui o maior valor de estimativa e, no restante do
tempo, selecionar aleatoriamente uma ação qualquer com probabilidade
com o
intuito de explorar o espaço de ações. Contudo, selecionar uma ação através de
uma política
permite que, no momento da exploração, todas as ações
possuam mesma probabilidade de serem escolhidas. Isso significa que a probabilidade de escolher a segunda melhor ação é igual à probabilidade de escolher a pior
de todas. Em algumas tarefas em que as piores ações são muito ruins, isto pode ser
insatisfatório (Sutton & Barto, 1998).
A solução para este problema é variar a probabilidade de seleção de uma ação de acordo com o valor de sua estimativa de recompensa, ou seja, ações que
tenham uma maior estimativa de recompensa terão probabilidade maior de serem
escolhidas em relação às demais (Sutton & Barto, 1998). Esta regra é conhecida
como softmax (Bridle, 1990). Geralmente, na softmax, a probabilidade de se escolher uma ação
em um instante de tempo
é calculada pela distribuição de Gibbs a
seguir:
(A.13)
onde
é um parâmetro positivo chamado temperatura. Altas temperaturas fazem
com que todas as ações sejam quase equiprováveis.
A.3.1 Monte Carlo
Diferente dos algoritmos da programação dinâmica, o método Monte Carlo (Michie &
Chamber, 1968) possibilita o aprendizado através da experiência do agente com o
A.3 Algoritmos da Aprendizagem por Reforço
105
ambiente. Embora um modelo seja necessário, este necessita apenas gerar apenas
exemplos de transições entre os estados. O método Monte Carlo estima
com-
putando a média dos retornos recebidos após o agente visitar o estado . Neste caso, para garantir que os retornos sejam bem definidos, utiliza-se o método Monte
Carlo apenas em tarefas episódicas.
A convergência do método Monte Carlo é assegurada conforme a lei dos
grandes números (Shen, 2002). Por exemplo, dado um número aleatório
de uma distribuição uniforme com média
que a média
dos valores de
, onde
e variância
retirado
desconhecidas, é provado
possa convergir para
se
, ou seja,
. Esta propriedade é conhecida como a
lei dos grandes números. Portanto, se o método Monte Carlo estima o valor de
computando a média dos retornos recebidos em
em
episódios, conforme
a fórmula abaixo:
(A.14)
então, pela lei dos grandes números, à medida que
proxima de
tende a infinito
se a-
. Estas são teorias que dizem um pouco a respeito da efetividade
do modelo.
As próximas subseções mostram a variação do algoritmo de Monte Carlo para
as duas classes de algoritmos, on-policy e off-policy. Os algoritmos apresentados
nas próximas seções estimam a função valor-ação ao invés da função valor-estado.
A vantagem de se possuir estimativas de estado-ação é a facilidade de sua aplicação em tarefas de controle e onde não se tem um modelo do ambiente (Sutton &
Barto, 1998). Sem o conhecimento do modelo do ambiente a função valor-estado
sozinha não é suficiente para determinar uma política, pois não seria possível obter
a estimativa do próximo estado sem antes executar uma ação.
A.3.1.1 Monte Carlo On-Policy
Esta parte do documento mostra como encontrar melhores políticas utilizando o método Monte Carlo, pela abordagem on-policy. O objetivo desta busca é aumentar o
retorno do agente. A Subsubseção A.2.1.3 mostrou como o algoritmo policy iteration
A.3 Algoritmos da Aprendizagem por Reforço
106
pode gradativamente encontrar políticas melhores através das etapas de policy evaluation e policy improvement. O método Monte Carlo pode estimar o valor de
através da média dos retornos recebidos. Esta é a etapa de policy evaluation para o método Monte Carlo. A etapa de policy improvement é realizada tornando
a política gulosa com respeito à função valor, i.e.,
início:
para cada
.
faça
;
;
fim
repita
Gere um episódio seguindo ;
para cada
faça
retorno após a primeira ocorrência de s,a;
;
;
;
fim
para cada
para todo
faça
;
faça
fim
fim
até ;
fim
Algoritmo A.3 Monte Carlo on-policy
Uma possível complicação do método Monte Carlo é a possibilidade da convergência para uma política que não será ótima. Isto pode acontecer em casos em
que o agente encontra uma política subótima e permanece nela sem visitar o restante dos pares estado-ação. O método Monte Carlo on-policy assegura que todos os
pares estado-ação serão sempre visitados. Para que isto seja possível deve-se fazer
A.3 Algoritmos da Aprendizagem por Reforço
107
com que a política seja sempre flexível, por meio dos métodos apresentados na Seção A.3.
O Algoritmo A.3 mostra o método Monte Carlo on-policy, onde a probabilidade
é atualizada seguindo uma política
, ou seja, em um estado
probabilidade de escolher uma ação seguindo uma política ótima é
probabilidade
a
e, com
de escolher uma ação aleatória.
A.3.1.2 Monte Carlo Off-Policy
O método Monte Carlo on-policy apresentado na Subsubseção A.3.1.1 estima a função valor de uma política dada uma seqüência infinita de episódios gerados por esta
mesma política. Já os métodos off-policy podem estimar a função valor de uma política
dados os episódios gerados por uma outra política
para estimar os valores de
toda ação tomada em
utilizando os episódios de
, onde
. Porém,
é necessário garantir que
seja, também, ocasionalmente tomada em
(Sutton &
Barto, 1998).
Dado as políticas
e
, o estado inicial e uma seqüência de estados, ações e
recompensas gerada utilizando
em
e
, a probabilidade de toda esta seqüência acontecer
será denotado por
e
, respectivamente. Seja
o retorno
observado de um estado . Para realizar a média e obter a estimativa de
necessário ponderar cada retorno
ocorrer em
e
, ou seja,
após observar
é
observado, pela probabilidade relativa de
. A estimativa do método Monte Carlo para
retornos é:
( A.15)
Apesar de, a Equação A.15 envolver as probabilidades
e
que
normalmente são consideradas desconhecidas em problemas onde o método Monte
Carlo é aplicado, nesta equação elas aparecem como uma razão
que
pode ser calculada admitindo nenhum conhecimento da dinâmica do ambiente. Seja
o instante de tempo final do -ésimo episódio envolvendo o estado , sendo
assim:
A.3 Algoritmos da Aprendizagem por Reforço
108
Se
( A.16)
então,
.
início:
para cada
( A.17)
faça
;
;
;
;
fim
repita
Gere um episódio seguindo
;
;
para cada
faça
;
;
;
;
;
fim
para cada
faça
;
fim
até ;
fim
Algoritmo A.4 Monte Carlo off-policy
O Algoritmo A.4 apresenta o algoritmo de Monte Carlo off-policy. Neste algoritmo são utilizadas duas políticas
e
. A política
é a política de estimação e
é
a política de comportamento. A política de comportamento pode ser qualquer uma,
mas que possa garantir que
para todo par estado-ação (e.g.,
)
e a política de estimação deve ser sempre gulosa (greedy) com respeito aos valores
A.3 Algoritmos da Aprendizagem por Reforço
de
109
. Uma vantagem deste método é a possibilidade de o agente explorar o
espaço de estados enquanto se mantém em uma política gulosa.
Um problema em potencial apontado por Sutton & Barto (1998) é que a aprendizagem deste método é realizada somente quando
. Se
é verdade na maior parte do tempo que o aprendizado será lento, principalmente para os estados iniciais (Sutton & Barto, 1998).
Apêndice B
Modelos Baseados no Gradiente Descendente
B.1 Introdução
Esta seção descreve como a experiência de um limitado sub-conjunto de estados
pode ser utilizada para generalizar, produzindo uma boa aproximação em um conjunto de estados muito maior. Este subconjunto de estados - conhecidos também
como exemplos de treinamento – é utilizado pelos métodos baseados no gradiente
descendente para aproximar uma função que mapeie este conjunto de estados em
suas respectivas estimativas de recompensa.
De acordo com Sutton e Barto (1998) é possível utilizar qualquer método da
aprendizagem supervisionada que aprenda através de exemplos; o que inclui as redes neurais artificiais (Haykin, 1994), árvores de decisão (Quinlan, 1986), e outros
tipos de regressão multivariada (Duda et al., 2000). No entanto, o uso de alguns modelos pode ser problemático em ambientes da aprendizagem por reforço. Por exemplo, os modelos construídos com as redes neurais artificiais assumem um conjunto
de exemplos de treinamento estático, conjunto este que é processado várias vezes
pela rede neural até que o erro seja suficientemente pequeno. Porém, é importante
que o aprendizado em ambientes da aprendizagem por reforço ocorra on-line enquanto o agente interage com o ambiente ou com o modelo do ambiente. Para isto,
segundo Sutton e Barto (1998), é necessário que os métodos sejam capazes de aprender a partir de dados adquiridos incrementalmente.
Os modelos baseados no gradiente descendente são aproximadores parametrizados de acordo com um vetor de parâmetros . Na aprendizagem, o vetor de parâmetros
é ajustado a cada instante de tempo a fim de reduzir a soma dos erros
quadráticos definida por:
110
B.1 Introdução
111
(B.1)
onde
é o valor esperado,
para todo
e
é o valor obtido de uma função diferenciável de
é um vetor coluna com um número fixo de componentes,
, onde
é muito menor que o número total de estados. A
função de custo da Equação B.1 é uma medida de como escolher o vetor de parâmetros
de tal forma que seja encontrado uma solução ótima
que satisfaça a
condição:
(B.2)
onde
é o erro total gerado pelo modelo em um conjunto de exemplos.
De acordo com Haykin (1994), este é um problema irrestrito de otimização,
onde deve ser minimizada a função de custo
tros
em relação ao vetor de parâme-
.
O valor esperado da Equação B.1 é definido de acordo com o método de a-
prendizado escolhido. Por exemplo, o valor esperado para o método Monte Carlo é
(Subseção A.3.1) e dos métodos por diferença temporal é
(Seção
2.1).
Os métodos baseados no gradiente descendente minimizam o erro dado pela
Equação B.1 ajustando o vetor de parâmetros, para cada exemplo dado, uma fração
na direção em que o erro seja menor. A atualização de um elemento do vetor de parâmetros dá-se através de:
(B.3)
onde
(B.4)
Este tipo de método é chamado de gradiente descendente pelo fato de os ajustes em
serem proporcionais ao gradiente negativo do erro quadrático dos e-
xemplos (Sutton & Barto, 1998).
B.1 Introdução
112
B.1.1 Algoritmo do Mínimo Quadrado Médio
O algoritmo apresentado a seguir é baseado na utilização dos valores instantâneos
da função de custo, ou seja,
(B.5)
(B.6)
onde
é o sinal de erro no tempo . O fator
cação da derivada. O operador gradiente
é apenas para efeito de simplifi-
é definido como:
(B.7)
Sendo
o vetor gradiente da função de custo definido pela Equação B.5,
então:
(B.8)
De acordo com a regra da cadeia do cálculo, é possível expressar o gradiente
como:
(B.9)
e diferenciando as equações B.5 e B.6 em ambos os lados, obtêm-se, respectivamente:
(B.10)
e
(B.11)
A última derivada parcial da Equação B.9 varia de acordo com o modelo. Se o
modelo é linear, então:
B.1 Introdução
113
(B.12)
onde
é uma função que codifica o sinal de entrada em um vetor binário. A codifi-
cação deste vetor varia de acordo com o modelo utilizado. Finalmente, diferenciando
a Equação B.12 em relação a
resulta em:
(B.13)
Substituindo as equações B.10, B.11 e B.13 em B.9 e depois em B.4, é possível formular o algoritmo do mínimo quadrado médio (LMS – Least Mean Square)
(Widrow & Hoff, 1960) como segue:
(B.14)
A Figura B.1 ilustra o funcionamento da versão linear do algoritmo LMS em
um problema da aprendizagem por reforço. Apresentado o novo estado ao crítico a
recompensa é calculada e o algoritmo LMS é ativado, nesta etapa, o erro é computado e o processo de aprendizagem se inicia, conforme as equações B.6 e B.3 respectivamente.
Figura B.1 Modelo linear.
As variações da função que codifica o sinal de entrada são apresentadas nas
próximas subseções. A Seção B.2 apresenta a variação não-linear de . O modelo
linear utilizado nos experimentos é descrito na Seção 2.3.
B.2 Redes Neurais Multilayer Perceptron
114
B.2 Redes Neurais Multilayer Perceptron
As Redes Neurais Artificiais (McCulloch & Pitts, 1943) consistem em um método para solucionar problemas de inteligência artificial. Originadas da idéia de modelar matematicamente as habilidades intelectuais humanas, as Redes Neurais Artificiais podem resolver problemas que necessitem do raciocínio lógico, sendo utilizadas em
diversos problemas dos mais variados domínios como reconhecimento de voz e imagem, automatização de processos industriais, hospitalares e mecânicos (Haykin,
1994).
Figura B.2 Rede Neural Multilayer Perceptron.
Conectando os neurônios de uma camada com todos os outros da camada
seguinte é possível criar uma estrutura particular de rede conhecida como Multilayer
Perceptron (Múltiplas Camadas de Neurônio). Nessa estrutura, apresentada na Figura B.2, a saída da camada de entrada é transmitida para todos os neurônios da primeira camada oculta, que por sua vez submete para camadas posteriores até que,
com esse processo, a camada de saída seja alcançada.
Estabelecida a estrutura de uma rede o aprendizado ocorre alterando o estímulo de cada neurônio via o algoritmo back-propagation (Rumelhart et al., 1986), ou
seja, são apresentados para a rede neural os estímulos iniciais e o resultado que ela
deve apresentar até o seu aprendizado.
B.2 Redes Neurais Multilayer Perceptron
115
A aprendizagem de uma Rede Neural Artificial Multilayer Perceptron consiste
em duas fases: Propagação do estímulo e Retropropagação do erro. Na propagação
os estímulos de entrada são propagados por todos os neurônios de todas as camadas da rede até a camada de saída. A ativação de um neurônio
ativado pela saída
dos neurônios da camada imediatamente à esquerda, pode ser obtido calculando a equação definida a seguir:
(B.15)
onde
representa o número de neurônios da camada
chamado de bias. A saída do neurônio
e
é um neurônio especial
é obtida computando a função de ativação
sigmoid definida a seguir:
(B.16)
Esta função pode ser de outra natureza, desde que seja, não linear, contínua
e diferenciável. A continuidade da função é um requisito devido ao gradiente descendente trabalhar com derivadas para retropropagar os erros.
Depois de propagado os estímulos de entrada, deve-se retropropagar o erro
- gerado na saída
do neurônio
da camada de saída - calculado por:
(B.17)
onde o termo
, conforme visto na Seção Apêndice B, varia de acordo com o méto-
do de aprendizado utilizado, ou seja,
(B.18)
para o algoritmo Q-Learning,
(B.19)
para o algoritmo Sarsa, e
(B.20)
para o algoritmo Monte Carlo.
O cálculo dos ajustes nos pesos sinápticos
vés da equação:
de um neurônio
dá-se atra-
B.2 Redes Neurais Multilayer Perceptron
116
(B.21)
onde
é a taxa de aprendizado que determina a intensidade de ajuste dos pesos
sinápticos e
é um termo que varia de acordo com a camada na qual se encontra o
neurônio .
Para os neurônios da última camada, o termo
é definido como segue:
(B.22)
onde
é a derivada da função de ativação. Normalmente é utilizada a fun-
ção sigmóide logística ou a tangente hiperbólica, da família das squashing functions.
Caso os neurônios não estejam na camada de saída o erro não pode ser aplicado diretamente a eles. Neste caso, utiliza-se a equação:
(B.23)
onde
são todos os termos dos neurônios que estão na camada imediatamen-
te à direita do neurônio oculto
e
são todos os pesos sinápticos associados
ao neurônio .
Os novos pesos sinápticos passam a ser atualizados pela equação:
(B.24)
A Rede Neural Artificial do tipo Multilayer Perceptron possui a propriedade de
aproximador universal de funções com grande capacidade de generalização e de
alto desempenho devido a seu processamento paralelo e distribuído (Haykin, 1994).
Foi provado que uma rede Multilayer Perceptron com uma camada oculta pode aproximar qualquer função conhecida com uma precisão especificada (Hornik et al.,
1989).
O Algoritmo B.1 mostra a combinação das redes neurais com o algoritmo QLearning. Conforme apresentado, a rede neural é iniciada com seu vetor de pesos
aleatórios implicando em um conjunto de ações e estados arbitrários no inicio do
aprendizado.
Note que para obter a resposta desejada é preciso conhecer a estimativa de
recompensa do estado sucessor. Isto é um pouco problemático para o aprendizado
da rede neural, pois esta estimativa possui uma margem de erro. É possível eliminar
B.2 Redes Neurais Multilayer Perceptron
117
esta margem de erro combinando as redes neurais com o algoritmo de Monte Carlo
ao invés do algoritmo Q-Learning.
Outro problema associado à utilização deste aproximador em ambientes da
aprendizagem por reforço diz respeito à sua característica de aproximador global, ou
seja, ao aproximar
de
as estimativas de recompensa
de outros estados
também serão afetadas, o que aumenta muito o tempo de convergência do algoritmo.
início:
inicie uma rede neural com o vetor de parâmetros randômico;
para cada
faça
estado inicial do episódio;
para cada
faça
estimativa de
produzida pela rede neural.
fim
escolha uma ação
seguindo uma política
derivada de ;
repita
realize a ação , observe a recompensa, , e o próximo estado, ;
para cada
faça
;
fim
escolha uma ação
seguindo uma política
derivada de ;
;
;
; /* taxa de aprendizado, resposta desejada e
* estimativa dada pela rede neural. */
;
;
até
;
fim
fim
Algoritmo B.1 Combinação do algoritmo Q-Learning com as redes neurais artificiais
multilayer perceptron.
Referências Bibliográficas
Agakov, F. et al., 2006. Using Machine Learning to Focus Iterative Optimization. In CGO '06:
Proceedings of the International Symposium on Code Generation and Optimization.
Washington, 2006. IEEE Computer Society.
Aha, D.W., Kibler, D. & Albert, M.K., 1991. Instance based learning algorithms. Machine
Learning, pp.37-66.
Albus, J.S., 1971. A Theory of Cerebellar Function. Mathematical Biosciences, pp.25-61.
Albus, J.S., 1975. A new approach to manipulator control: The cerebellar model articulation
controller (CMAC). Journal of Dynamic Systems, Measurement, and Control, pp.220-27.
Alhajj, R. & Kaya, M., 2003. Employing olap mining for multiagent reinforcement learning.
Design and application of hybrid intelligent systems, pp.759-68.
Bagnell, J.A. & Schneider, J., 2001. Autonomous helicopter control using reinforcement
learning policy search methods. In Proceedings of the International Conference on Robotics
and Automation., 2001. IEEE.
Barto, A.G., Sutton, R.S. & Anderson, C.W., 1990. Neuronlike adaptive elements that can
solve difficult learning control problems. Artificial neural networks: concept learning, pp.8193.
Bellman, R., 1952. On the Theory of Dynamic Programming. In Proceedings of the National
Academy of Sciences., 1952.
Boer, R. & Kok, J., 2002. The Incremental Development of a Synthetic Multi-Agent System:
The UvA Trilearn 2001 Robotic Soccer Simulation Team. Master Thesis, Faculty of Science:
University of Amsterdam.
118
Referências Bibliográficas
119
Boyan, J. & Moore, A., 1995. Generalization in Reinforcement Learning: Safely
Approximating the Value Function. In Neural Information Processing Systems 7. The MIT
Press. pp.369-76.
Braga, A.P.S. & Araújo, A.F.R., 2002. Applying topological maps to accelerate reinforcement
learning in mobile robot navigation. In IEEE International Conference on Systems, Man and
Cybernetics. Hammamet, 2002. IEEE.
Brassard, G. & Bratley, P., 1996. Fundamentals of Algorithms. New Jersey: Prentice Hall.
Bridle, J.S., 1990. Training stochastic model recognition algorithms as networks can lead to
maximum mutual information estimates of parameters. In Advances in Neural Information
Processing System: Proceedings of the 1989 Conference. Morgan Kaufmann. pp.211-17.
Brindley, G.S., 1964. The use made by the cerebellum of the information that it receives from
sense organs. IBRO Bull.
Cavazos, J. & Moss, J.E.B., 2004. Inducing heuristics to decide whether to schedule. In
Proceedings of the ACM SIGPLAN'04 conference on programming language design and
implementation., 2004. ACM Press.
Cavazos, J. & Moss, J.E.B., 2006. Hybrid optimization: Which optimization to use? In
International Conference on Compiler Construction., 2006. ACM Press.
Cheny, M. et al., 2003. RoboCup Soccer Server.
Cohen, S. & Maimon, O., 2005. Reinforcement-Learning: An Overview from a Data Mining
Perspective. In Data Mining and Knowledge Discovery Handbook. Springer. pp.469-86.
Coons, K.E. et al., 2008. Feature selection and policy optimization for distributed instruction
placement using reinforcement learning. In PACT’08: Proceedings of the 17th international
conference on Parallel architectures and compilation techniques. New York, 2008. ACM.
Crites, R.H. & Barto, A.G., 1996. Improving elevator performance using reinforcement
learning. In Advances in Neural Information Processing Systems 8., 1996. MIT Press.
Dayan, P., 1992. The convergence of TD(λ) for general λ. Machine Learning, pp.341-62.
Duda, R.O., Hart, P.E. & Stork, D.G., 2000. Pattern Classification. 2nd ed. Wiley-Interscience.
Referências Bibliográficas
120
Fayyad, U.M. & Irani, K.B., 1993. Multi-interval discretization of continuousvalued attributes
for classification learning. In Thirteenth International Joint Conference on Articial
Intelligence., 1993.
Gennari, J.H., Langley, P. & Fisher, D., 1989. Models of incremental concept formation.
Artificial Intelligence, pp.11-61.
Grossman, S.P., 1967. The Motor System and Mechanics of Basic Sensory-Motor Integration.
In Textbook of Physiological Psychology. New York: Wiley. Ch. 4.
Hall, M.A., 1999. Correlation-based Feature Selection for Machine Learning. PhD Thesis,
Departament of Computer Science: The University of Waikato.
Han, J. & Kamber, M., 2006. DataMining: Concepts and Techniques (The Morgan Kaufmann
Series in Data Management Systems). 2nd ed. Morgan Kaufmann.
Haykin, S., 1994. Neural Networks: A Comprehensive Foundation. New York: Macmillan.
Hornik, K., Stinchcombe, M. & White, H., 1989. Multilayer feedforward networks are
universal approximators. Neural Networks, pp.359-66.
Hunt, E., Martin, J. & Stone, P., 1966. Experiments in Induction. New York: Academic Press.
Jain, R., 1991. The Art of Computer Systems Performance Analysis: Techniques for
Experimental Design, Measurement, Simulation, and Modeling. New York: WileyInterscience.
Kaelbling, L.P., Littman, M.L. & Moore, A.W., 1996. Reinforcement Learning: A Survey.
Journal of Artificial Intelligence Research, pp.237-85.
Kheradmandian, G. & Rahmati, M., 2009. Automatic abstraction in reinforcement learning
using data mining techniques. Robotics and Autonomous Systems, Julho.
Kitano, H. & Asada, M., 1998. Robocup humanoid challenge: Tha’s one small step for a robot,
one giant leap for mankind. In Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and System (IROS-98)., 1998.
Kitano, H. et al., 1995. Robocup: The robot world cup initiative. In Proceedings of the IJCAI-95
Workshop on Entertainment and AI/Alife., 1995.
Referências Bibliográficas
121
Kitano, H. et al., 1997. Robocup: The robot world cup initiative. In Proceedings of the First
International Conference on Autonomous Agents (Agent-97)., 1997.
Kohavi, R., 1995. Wrappers for Performance Enhancement and Oblivious Decision Graphs.
PhDthesis, Stanford University.
Kohavi, R. & John, G., 1996. Wrappers for feature subset selection. Artificial Intelligence,
special issue on relevance, p.273–324.
Kohavi, R. & Sommerfield, D., 1995. Feature subset selection using the wrapper method:
Overfitting and dynamic search space topology. In In Proceedings of the First International
Conference on Knowledge Discovery and Data Mining., 1995. AAAI Press.
Kononenko, I., 1995. On Biases in Estimating Multi-Valued Attributes. In 14th International
Joint Conference on Articial Intelligence., 1995.
Langley, P., 1994c. Selection of relevant features in machine learning. In In Proceedings of
the AAAI Fall Symposium on Relevance., 1994c. AAAI Press.
Langley, P. & Sage, S., 1994a. Induction of selective Bayesian classifiers. In Proceedings of the
Tenth Conference on Uncertainty in Artificial Intelligence. Seattle, 1994a. Morgan Kaufmann.
Langley, P. & Sage, S., 1994b. Oblivious decision trees and abstract cases. In In Working
Notes of the AAAI-94 Workshop on Case-Based Reasoning. Seattle, 1994b. AAAI Press.
Lin, C.-S. & Kim, H., 1991. CMAC-based adaptive critic self-learning control. In IEEE
Transactions on Neural Networks., 1991. IEEE.
Liu, H. & Motoda, H., 1998. Feature Selection for Knowledge Discovery and DataMining.
Norwell: Kluwer Academic Publishers.
Liu, H. & Setiono, R., 1996. A probabilistic approach to feature selection - A filter solution. In
13th International Conference on Machine Learning., 1996. Morgan Kaufmann.
Lu, H., Yuan, S. & Lu, S.Y., 1996. On preprocessing data for effective classification. In ACM
SIGMOD’96 Workshop on Research Issues on Data Mining and Knowledge Discovery., 1996.
ACM.
Referências Bibliográficas
122
Matoušek, K. & Aubrecht, P., 2006. Data modelling and pre-processing for efficient data
mining in cardiology. In New Methods and Tools for Knowledge Discovery in Databases.,
2006. Information Society.
McCulloch, W. & Pitts, W., 1943. A Logical Calculus of Ideas Immanent in Nervous Activity.
Bulletin of Mathematical Biophysics, pp.115-33.
Michie, D. & Chamber, R.A., 1968. BOXES: An experiment in adaptive control. In Machine
Intelligence 2., 1968. Oliver and Boyd.
Mitchell, T.M., 1997. Machine Learning. New York: McGraw-Hill.
Oliveira, R. et al., 2009. A Data Mining Approach to Solve the Goal Scoring Problem. Neural
Networks, IEEE - INNS - ENNS International Joint Conference on Neural Networks, pp.234752.
Quinlan, J.R., 1986. Induction of decision trees. Machine Learning, pp.81-106.
Quinlan, J.R., 1993. C4.5: Programs for machine learning. California: Morgan Kaufmann.
Riedmiller, M., 1999. Concepts and facilities of a neural reinforcement learning. Journal of
Dynamic Systems, Measurement, and Control, pp.323-38.
Riedmiller, M., 2005. Neural fitted Q iteration – first experiences with a data efficient neural
reinforcement learning method. In In 16th European Conference on Machine Learning.,
2005. Springer.
Riedmiller, M.A. et al., 2001. Karlsruhe brainstormers - a reinforcement learning approach to
robotic soccer. In RoboCup 2000: Robot Soccer World Cup IV. London, 2001. Springer-Verlag.
Rumelhart, D.E., Hinton, G.E. & Williams, R.J., 1986. Learning Internal Representations by
Error Propagation. Parallel Distributed Processing: Explorations in the Microstructure of
Cognition, pp.318-62.
Rummery, G.A., 1995. Problem Solving with Reinforcement Learning. PhDthesis, Cambridge
University.
Russell, S.J. & Norvig, P., 2003. Artificial Intelligence: A Modern Approach. 2nd ed. Prentice
Hall.
Referências Bibliográficas
123
Shannon, C.E., 1948. A mathematical theory of communication. Bell System Technical
Journal, pp.379-423.
Shen, L., 2002. A law of large numbers and a central limit theorem for biased random
motions in random environment.
Silberchatz, A., Korth, H.F. & Sudarshan, S., 1999. Sistema de Banco de Dados. São Paulo:
Makron Books.
Stephenson, M., Amarasinghe, S., Martin, M. & O’Reilly, U.-M., 2002. Meta optimization:
Improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN’03
Conference on Programming Language., 2002. ACM Press.
Stone, P., 1998. Layered Learningin Multi-Agent Systems. PhD thesis, School of Computer
Science: Carnegie Mellon University.
Stone, P. & Sutton, R.S., 2001. Scaling reinforcement learning toward RoboCup soccer. In
Proc. 18th International Conf. on Machine Learning. San Francisco, 2001. Morgan Kaufmann.
Stone, P., Sutton, R.S. & Kuhlman, G., 2005. Reinforcement learning for robocup soccer.
Internationa lSociety for Adaptive Behavior, pp.165-88.
Sutton, R.S., 1988. Learning to predict by the methods of temporal differences. In Machine
Learning., 1988. Kluwer Academic Publishers.
Sutton, R.S. & Barto, A.G., 1998. Reinforcement Learning: An Introduction. Cambridge: The
MIT Press.
Tesauro, G., 1994. Td-gammon, a self-teaching backgammon program, achieves master-level
plays. Neural Computation, pp.215-19.
Vieira, D.C.L., Adeodato, P.J.L. & Gonçalves Jr., P.M., 2010. Improving Reinforcement
Learning Algorithms by the Use of Data Mining Techniques for Feature and Action Selection.
In Proceeding of the 2010 IEEE Conference on Systems, Man and Cybernetics (SMC2010).
Istanbul, 2010.
Watkins, C.J.C.H., 1989. Learning from Delayed Rewards. PhDthesis, Cambridge University.
Widrow, B., Gupta, N.K. & Maitra, S., 1973. Punish/Reward: Learning with a Critic in Adaptive
Threshold Systems. IEEE Transactions on Systems, Man, and Cybernetics, pp.455-65.
Referências Bibliográficas
124
Widrow, B. & Hoff, M.E., 1960. Adaptive switching circuits. In 1960 WESCON Convention
Record Part IV. New York, 1960. Mit Press.