Aprendizado por Reforço - Avaliando o Reforço

Resumo do Cap.2 do Livro: Reinforcement Learning: An Introduction de Richard S. Sutton e Andrew G. Barto - Evaluative Feedback

O grande diferencial do aprendizado por reforço é que a informação que ele recebe avalia suas ações, ao invés de simplesmente instruí-lo, como no supervisionado.

1. Métodos de valor pra ação (action-value)

Assume-se que existe uma função Q(a) de valor para cada ação, e o objetivo do agente é fazer uma esstimativa dessa função. A função pode ser por exemplo a média de todos os reforços recebidos por cada ação, de modo que a ação ótima seria a que possui maior estimativa de valor.

2. Aproveitar x Experimentar (Exploit x Explore)

Um dos desafios do aprendizado por reforço é equilibrar o compromisso entre aproveitar a ação ótima do momento ou experimentar novas ações que podem ter reforço ainda maior. Uma das técnicas é o método ε-greedy: o agente escolhe a ação ótima com probabilidade 1-ε ou uma ação aleatória com probabilidade ε. No entanto, se ε for constante, o agente nunca terá performance 100% ótima.

3. Softmax

Softmax é outro método para guiar a escolha das ações. Ao contrário do ε-greedy que escolhe totalmente aleatoriamente uma ação, o Softmax atribui probabilidades a todas as ações, sendo que as melhores são mais prováveis (baseado nas estimativas de valor pra ação). Assim, todas as ações podem ser escolhidas e quanto maior diferença houver nas estimativas, mais provável será a esoclha da melhor. As distribuições mais comumente usadas são a de Gibbs ou Boltzmann.

4. Atualização incremental

A fórmula geral para se atualizar um valor incrementalmente é:

NovaEstimativa = ValorVelho + Passo[ValorNovo - ValorVelho]

Se o passo for 1/num. passos, o valor será sempre a média.

5. Problemas dinâmicos

O problema pode não ser estacionário e com o passar do tempo os reforços podem mudar pra cada ação. Nessa caso, fazer a média de todos os reforços pode ser ruim, sendo melhor dar maior importância aos reforços mais recentes. Para isso pode-se usar a atualização incremental da estimativa de Q(a) com um passo constante 0 < alfa < 1. Q' = Q + alfa(reforço - Q)

6. Inicialização otimista

Experimentar todas as ações no início é importante, para se conhecer logo melhor as opções disponíveis. Para incentivar essa exploração, podemos inicializar as estimativas de valor de maneira otimista. Por exemplo, se sabemos que os reforços raramente passam de 10, podemos inicializar as estimativas de todas ações com o valor de 50 de modo que sempre que for experimentada, esse valor vai baixar. Aí todas as que não foram experimentadas ainda terão estimativa maior e portanto serão as melhores do momento, e ai serão experimentadas também.

7. Comparação de reforços

8. Perseguição

Aprendizado por Reforço - Introdução

Resumo do Cap.1 do Livro: Reinforcement Learning: An Introduction de Richard S. Sutton e Andrew G. Barto

Aprendizado por Reforço é aprender o que fazer em cada situação, de modo a maximizar sua recompensa. O agente deve descobrir o que fazer com tentativas e deve considerar não apenas as recompensas imediatas, mas as futuras também. É diferente do Aprendizado Supervisionado no qual o agente recebe exemplos do que fazer por um supervisor. Um agente de aprendizado por reforço possui um objetivo explícito, pode sentir alguns aspectos do ambiente e realizar ações que modificam-no e assim deve explorá-lo para encontrar a melhor política de ação.

Podemos identificar 4 elementos principais num sistema de aprendizado por reforço: a política, a função de recompensa, uma função de valor e um modelo do ambiente. A política representa qual a melhor ação a se fazer em cada estado. Ou seja, é o comportamento do agente, que deve ser otimizado com o aprendizado. A função recompensa atribui um número para cada estado. Quando o agente atinge determinado estado do ambiente, ele recebe essa recompensa. Isso define qual é o objetivo dele, que será o estado com a maior recompensa. A função valor representa a recompensa acumulada (e não imediata). Ela dá valor a todos os estados numa determinada seuência de ações que leva ao objetivo. O componente central dos algoritmos de aprendizado por reforço é como estimar e atualizar essa função. O modelo, opcional, pode ajudar a predizer o próximo estado e recompensa.

No Cap. 11 teremos o exemplo do sistema de Gerry Tesauro que possui a capacidade de generalizar a sua experiência

Classificadores Bayesianos

Na disciplina de Raciocício Probabilístico, apresentei um trabalho sobre classificadores Bayesianos (principalmente Naive Bayes) e apliquei-os a uma tarefa de análise sintática da língua portuguesa. A apresentação pode ser encontrada aqui e o relatório aqui

A tarefa era a seguinte: dada uma frase, classificar o tipo de sujeito que ela possui: Sujeito Explícito, Oculto, Indeterminado ou Inexistente (oração sem sujeito). Isso foi feito extraíndo-se alguns atributos das frases e usando probabilidades calculadas de um conjunto de treinamento (aprendizagem supervisionada).

Escolhi os seguintes atributos, de fácil extração: número de palavras da frase, número e pessoa do verbo, classe gramatical do termo anterior ao verbo, presença de "-se", infinitivo do verbo é "haver";

Por exemplo, na frase: "Ele leu o blog.", temos os seguintes atributos:

Núm. palavras: 4

Núm e pessoa do verbo: 3a pessoa, singular

Classe do termo anterior: pronome

Presença de "-se": não

É verbo "haver": não

E se for parte do treinamento, fornecemos a classe: Sujeito Explícito.

Com o Naive Bayes Classifier, assumimos que todos os atributos são independentes. Então bastam as probabilidades a priori de cada classe e as condicionais de cada atributo dada a classe.

Então a aprendizagem calcula probabilidades a priori com suas frequencias, como:

p(Suj. Explicito) = quantidade de frases SE / quantidade total de frases no conjunto de treinamento

E também as probabilidades condicionais, por exemplo:

p(termo anterior=pronome|classe=suj. oculto)

Nos testes que realizei, treinando com frases de textos jornalísticos e do conto "A cartomante" de Machado de Assis, obtive taxa de acerto de 84%.

Capacidade de uma Rede Neural de Hopfield

Resumo do artigo: McEliece, R.; Posner, E.; Rodemich, E.; Venkatesh, S.; “The capacity of the Hopfield associative memory”; In Information Theory, IEEE Transactions on, Vol 33 Issue 4, p. 461 – 482; Julho, 1987. Disponível em: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=22761&arnumber=1057328&count=15&index=7

Uma rede neural com arquitetura de Hopfield é uma rede com n nós todos conectados entre si. A entrada é dada mudando-se os valores de cada nó e a saída são os valores em cada nó, após atualizados. Cada neurônio tem como função de transferência a função sinal, representando assim um bit com valor -1 ou +1.

A arquitetura de Hopfield é chamada também me memória associativa, pois essa rede neural apresenta a característica de "recuperar" os exemplos treinados, cada um sendo um "atrator". É freqüentemente associada à ideia de reconhecimento de imagens.

O artigo ilustra um exemplo de uma rede com m = 3 exemplos e apenas n = 5 nós. É mostrado que, dada uma entrada com apenas distância de Hamming = 1 de um dos pontos fixos, é possível que o ponto resultante da rede não seja a memória mais próxima ou nem nenhuma delas.

O artigo apresenta 2 definições para capacidade da rede com m atratores, cada um atraindo com um raio ρn, 0 < ρ < ½, ou seja, uma entrada com no máximo metade dos valores errados com relação a um dos m atratores (distância de Hamming até ρn) será atraída corretamente. A primeira fórmula designa a capacidade para que exatamente todas as m memórias sejam atratores: m < n / (4ln(n))

Se aceitarmos que apenas a maioria das m memórias sejam atratoras, então a capacidade dobra: m < n / (2ln(n))

Lâmina de Ockham

Como escolher entre as várias hipóteses consistentes?

Lâmina de Ockham: Prefira a hipótese mais simples.

Por Guilherme de Ockham (William of Ockham), filósofo inglês do séc. XIV.

Monty Hall

Problema: Num programa de televisão, existem 6 painéis, numerados 1 a 6. Atrás de 1 deles está o prêmio, enquanto os outros 5 nada contém. O participante escolhe 1 painel no início, mas ainda não revela-se o seu conteúdo. O apresentador então, sabendo onde está o prêmio, começa a abrir os painéis restantes. Ele abre 4 painéis, nenhum com o prêmio. Sobram então 2 painéis, o º 3 que o participante escolheu e o nº 6. O apresentador então pergunta se ele deseja ficar com o que escolheu ou se quer trocar, sendo que depois disso o prêmio será revelado. Qual é a decisão mais recomendada?

Essa é uma variação do famoso problema de Monty Hall, ou da Porta dos Desesperados ou paradoxo dos 3 prisioneiros. Se o objetivo da participante for maximizar a probabilidade de ganhar o prêmio, então a resposta é que ele deve sim trocar de painel. Isso porque a probabilidade de ele ter acertado no início (1/6) não mudou. Cada painel iniciou com essa mesma probabilidade, mas o apresentador fez o favor de reduzir todos os 5/6 de chance restantes a uma única opção. Ou seja, é como se a escolha fosse entre 1 painel ou 5 painéis.

Agora, se enunciarmos o problema um pouco diferente: O participante escolhe 1 painel. O apresentador, sem saber onde está o prêmio, vai abrindo os outros paineis aleatoriamente e chega-se na mesma situação final (4 abertos sem prêmio). E agora, qual a melhor escolha?

Nesse caso, a probabilidade de estar em cada um dos painéis é a mesma, de 50%. O fato do apresentador não saber e ir abrindo aleatoriamente faz com que a chance não mude pois nenhuma nova informação foi adicionada, apenas "deu sorte" de não ter aberto o prêmio ainda.

Estimativa de relevância de domínio semântico em textos

Resumo de: Gliozzo, A., Magnini, B. and Strapparava , C. “Unsupervised domain relevance

estimation for word sense dis ambiguation” In: Conference on Empirical Methods in

Natural Language Processing, 2004. Disponível em: http://wndomains.fbk.eu/publications/EMNLP04.pdf

O artigo apresenta o Domain Relevance Estimation (DRE), uma técnica para identificar a relevância de um texto dentro de certo domínio. Os domínios são conhecidos e pré-fixados, com palavras associadas. Dado um texto, calcula-se quão relevante ele é nesse domínio, e essa informação pode ser importante para resolver o problema de desambiguação do sentido das palavras no texto. Esse trabalho pode ser classificado como resolvedor do problema de Categorização de textos.

Inicia-se com um conjunto de domínios (categorias), tais como Medicina, Matemática ou Esportes, cada um com uma lista de palavras relacionadas. Essas listas foram extraídas do WORDNET DOMAINS, que é uma extensão do WORDNET (uma base de dados de palavras com informações léxicas e semânticas e ligações entre as palavras, como sinônimos, antônimos, derivados, formando uma grande rede), atribuíndo a cada palavra um ou mais labels de domínio. A estrutura de domínios é hierárquica e apresenta 200 domínios diferentes. Cada significado presente em uma palavra no WORDNET ganha label de domínio e a frequência do sgnificado é também computada através do SemCor. Por fim, existe uma label genérica, para palavras que não possuem um domínio de conhecimento específico.

A idéia básica é simples: quanto mais palavras de um certo domínio um certo texto contém, mais relevância para aquele domínio ele possuirá. E a WORDNET é útil nesse cálculo da relevância de uma palavra para o domínio. Ela é definida como sendo uma somatória das relevâncias te todos ossignificados presentes na rede da palavra.

No entanto, a simples contagem de frequências não é adequada pois introduziria ruído ao contar domínios não-relevantes. Normalmente para se contornar isso, usa-se uma aprendizagem supervisionada, mas não é esse o caso. O artigo usa o Gaussian Mixture Model, usando uma técnica de aprendizagem não-supervisionada: estima parâmetros baseado em estatísticas de um grande corpus de palavras. O GMM é um modelo que consiste numa composição de gaussianas e permite representar toda função densidade de probabilidade contínua como uma combinação linear de gaussianas. Nesse caso, será usado um modelo com 2 gaussianas: uma com a densidade de probabilidade relevante para o domínio e outra para o que não é relevante.

Usando Bayes, a relevância R do domínio D para o texto t numa posição j é:

Onde F é a frequência. Não-D é o oposto ao domínio, tudo que não é relacionado ao domínio D em questão. E para aplicar essa fórmula é necessário estimar a função densidade de probabilidade para a frequência dos termos no domínio e para isso um algoritmo de Expectation-Maximization é usado para maximizar o "likelihood" e formar o modelo GM.

No contexto do problema de desambiguação do sentido das palavras, um dos métodos é a desambiguação dirigida por domínio (DDD) onde somente informação de domínio é utilizada.

Concluindo, esse é um método interessante para categorizar textos sem o uso de exemplos prévios, exceto pelo fato do uso do SemCor que possui as frequências dos sentidos das palavras.

Relevance Vector Machine

Resumo do artigo: Michael E. Tipping; Sparse Bayesian Learning and the Relevance Vector Machine; Journal of Machine Learning Research Volume 1(Jun):211-244, 2001.

Disponível em: http://www.jmlr.org/papers/volume1/tipping01a/tipping01a.pdf

Este artigo propõe uma modificação à famosa Support Vector Machine (SVM), aqui denominada Relevance Vector Machine (RVM). Essa modificação tem como base o uso de técnicas de aprendizagem Bayesianas e introduz probabilidades na saída.

O artigo cita como desvantagens da SVM:

• Número de Support Vectors aumenta linearmente com o tamanho do conjunto de treinamento;
• Predições não são probabilísticas;
• Necessidade de estimar parâmetro de erro C (desperdício de computação e dados)
• A função de Kernel K(x,xi) deve satisfazer a condição de Mercer.

A RVM não sofre de nenhuma dessas limitações. O artigo apresenta modelos para os problemas de regressão e classificação.

É dita "esparsa" porque tipicamente o modelo aprendido após o aprendizado é uma soma ponderada de funções básicas, e o resultado mais esparso significa mais coeficientes, ou seja, menos funções consideradas (resposta mais simples).

(A teoria é complexa e não será explicitada aqui.)

O autor aplicou alguns testes comparativos entre RVM e SVM e conseguiu resultados que demonstram menor erro e muito menos vetores resultantes. Por exemplo, na regressão de uma função sinc(x), com 100 amostras, SVM apresentou desvio de 0,029 e 29 vetores enquanto o RVM teve um desvio de 0,0245 e apenas 6 vetores usados.

Apresentação

Nesse blog pretendo postar tudo o que eu ler/aprender relativo ao meu mestrado, i.e., resumos de artigos, livros, exercícios de disciplias e outros, de modo que funcione como um método de controle do meu avanço e de revisão do que já li.

A saber, meu mestrado é na área de Inteligência Artificial - aprendizado de máquina (Machine Learning), lá na Poli/USP sob orientação da profª. Anna Helena Reali Costa e teve início em janeiro de 2011.