Diferença entre a rede de políticas da AlphaGo e a rede de valores

25

Eu estava lendo um resumo de alto nível sobre o AlphaGo do Google ( http://googleresearch.blogspot.co.uk/2016/01/alphago-mastering-ancient-game-of-go.html ) e me deparei com os termos "política rede "e" rede de valor ". Em um nível alto, entendo que a rede de políticas é usada para sugerir movimentos e a rede de valores é usada para "Reduzir a profundidade da árvore de pesquisa [e estimar] o vencedor em cada posição no lugar de pesquisar todo o caminho até o Fim do jogo."

Essas duas redes parecem redundantes para mim. O que a rede de políticas está fazendo se não estiver usando a rede de valor para podar suas políticas? Parece bem claro que a rede de valor é uma rede neural de aprendizado profundo; a rede política é apenas uma abstração teórica e não uma rede neural real? A variável alvo para a rede de valor parece ser ganho / perda. Existe uma variável de destino para a rede de políticas; Se assim for, o que é? O que a rede de políticas está tentando otimizar?

O pdf completo do artigo do Google, publicado na Nature, pode ser encontrado aqui: https://vk.com/doc-44016343_437229031?dl=56ce06e325d42fbc72

Ryan Zotti
fonte
Como uma observação rápida: a variável de destino para a rede de políticas é uma distribuição de probabilidade. Do artigo: "Esta rede neural (a rede de valor) tem uma arquitetura semelhante à rede de políticas, mas gera uma única previsão em vez de uma distribuição de probabilidade"
Zimano
3
Se mais alguém se deparar com essa pergunta antiga, como eu, ficará satisfeito em saber que o sucessor do AlphaGo, "AlphaGo Zero", bem como seu sucessor "AlphaZero", de fato, se livram da redundância apenas treinando UMA rede cujos resultados servir as funções da rede de políticas (fornece uma distribuição de probabilidade entre os movimentos possíveis) e da rede de valores (fornece probabilidade de vitória, de acordo com o conselho). Postagem no blog aqui: deepmind.com/blog/alphago-zero-learning-scratch e o documento está vinculado a ele.
Kevin Wang

Respostas:

11

Em resumo, cada rede tem um propósito diferente, como você mencionou:

  • A rede de valor foi usada nos nós das folhas para reduzir a profundidade da pesquisa em árvore.
  • A rede de políticas foi usada para reduzir a amplitude da pesquisa de um nó (orientando para ações imediatas promissoras).

Em geral, você pode usar métodos de função de valor para encontrar uma política ideal ou pesquisar diretamente no espaço de políticas para otimizar uma função de política parametrizada (é claro que existem prós e contras). Você pode usar aproximadores de função (por exemplo, redes profundas) em cada caso. Vejo que principalmente você está confuso sobre a rede de políticas, por isso concentro minha resposta nisso.

A rede de políticas foi a primeira:

treinado para executar os movimentos que provavelmente um ser humano faria em um estado da placa (portanto, a entrada é um estado da placa e a saída é um histograma que mostra a probabilidade de cada ação em relação a esse estado). A rede pode aproximar a função de probabilidade subjacente ao mapeamento de estados para ações. É razoável pensar em começar a criar sua política a partir dos dados disponíveis. Após o treinamento supervisionado com movimentos de especialistas, a rede de políticas pode jogar o jogo suficiente (embora longe do nível de mestrado). Simplesmente, você tentou capturar o padrão geral de seleção de ações de jogadores profissionais.

Então,

foi treinado em jogos com o próprio oponente, a fim de otimizar a política aprendida anteriormente. Desta vez, seus pesos foram atualizados usando o algoritmo REINFORCE. Ao fazer isso, você atualiza os parâmetros da rede para maximizar a recompensa esperada. Eventualmente, você tem uma rede que não apenas seleciona as ações como um jogador profissional, mas também para ganhar o jogo (no entanto, não pode planejar!).

Após essa etapa, eles aproximaram a função de valor de uma versão um pouco mais barulhenta da política aprendida, por regressão (a entrada é o quadro de estado e visa o resultado do jogo). Você pode usar esta rede para afetar a avaliação do nó folha.

Conceitualmente falando, a rede de políticas oferece uma probabilidade de ações, mas isso não indica que você acabará em um estado bom para vencer o jogo. AlphaGo teve alguns "pontos cegos" e durante o torneio fez alguns movimentos muito ruins, mas também um movimento excepcional que um humano nunca poderia ter pensado.

Finalmente, você pode usar seu algoritmo de planejamento (MCTS) em combinação com essas redes. Por que demos todos esses passos? Resumidamente, o MCTS simples, sem qualquer "intuição", teria falhado.

Constantinos
fonte
Acabei de voltar a esta pergunta, tendo aprendido sobre o Critic Actor, e como ele compensa os custos / benefícios entre os métodos puros baseados em valor versus política. Acho que essa resposta se aproxima mais de explicar esse detalhe, mas é bem abordada na palestra de David Silver: www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/pg.pdf (aula 7, também está disponível no YouTube - youtube.com/… ).
Neil Slater
Porém, abordagens puras baseadas em MCTS mostraram-se bem-sucedidas, portanto, em um contexto mais amplo, eu não diria que teria falhado.
Zimano
11
Refiro-me apenas ao caso do jogo Go e também a atingir o nível Master de jogo. Na verdade, David Silver (como outros pesquisadores) estava trabalhando na solução do jogo Go com o MCTS desde seu doutorado. Mas nada poderia competir nos níveis mais altos até a combinação dos métodos acima.
Constantinos
9

Aqui está o meu processo de pensamento conciso na compreensão das duas redes diferentes.

Antes de tudo, o objetivo é encontrar uma solução ótima (ou quase ótima) sem usar uma pesquisa exaustiva, o que é definitivamente um desafio.

Por posição ou estado, haverá N movimentos possíveis e, a cada movimento, haverá sua própria profundidade D em uma árvore de pesquisa completa. É teoricamente ou matematicamente possível percorrer todos os caminhos e encontrar uma (s) solução (s) ideal (is). No entanto, não queremos fazer uma pesquisa completa.

Agora, temos duas perguntas separadas para o desenvolvimento de uma abordagem de aproximação.

Q1 Como podemos ignorar ou desconsiderar alguns movimentos fora de N por posição? (ou seja, redução da respiração)

Q2 Como podemos parar em uma profundidade intermediária em uma árvore de pesquisa, em vez de caminhar até o final do jogo, sem deixar de encontrar uma solução ideal? (ou seja, redução de profundidade)

A rede de políticas foi projetada principalmente para filtrar movimentos inúteis de N, mas sem deixar de encontrar uma solução ideal. Aqui, essa rede conta inicialmente com movimentos de especialistas humanos, ou seja, SL, e aprimorada pela RL posteriormente.

A rede de valor é projetada principalmente para encontrar a probabilidade de ganhar sem uma pesquisa completa.

Essas duas redes têm um objetivo comum de encontrar uma solução ideal. No entanto, em cada opção estratégica de movimento, cada rede desempenha um papel diferente.

Eu só espero que isso ajude. Eu sei que ainda estaria em um nível alto.

Vento P.
fonte
Sua explicação de duas maneiras é muito concisa.
Tim
6

Eu acho que o OP estava confuso sobre AlphaGo com alfa-beta. Em alfa-beta, você realmente usaria a rede de políticas para ajudar na poda, mas não aqui. Novamente, não há poda, pois o algoritmo se baseia na pesquisa de árvores de Monte-Carlo (MCTS).

Quem pensa que minha resposta é muito longa pode pular para a seção de resumo, onde declaro por que as duas redes não são redundantes.

No exemplo a seguir, farei algumas simplificações para facilitar a compreensão de minhas idéias.

Exemplo:

Imagine que você tem uma posição em que existem dois movimentos legais. O primeiro passo é um ponto morto para você, no entanto, o segundo passo oferece uma vantagem vencedora.

  • Primeiro passo: perda forçada para você
  • Segundo passo: vitória forçada para você

Rede de avaliação

Vamos supor que a rede de avaliação que o Google oferece é perfeita. Ele pode avaliar perfeitamente qualquer posição da folha em nosso exemplo. Não mudaremos nossa rede de valor no exemplo.

Para simplificar nosso exemplo, vamos assumir que nossa rede de valor fornece:

  • -1000 para qualquer posição da folha que seja uma perda para você
  • +1000 para qualquer posição da folha que seja uma vitória para você

Rede de políticas

Vamos supor que o Google oferece duas redes de políticas. As probabilidades geradas para nossa posição são:

  • Política 1: 0,9 para a movimentação 1 e 0,1 para a movimentação 2
  • Política 2: 0,2 para a movimentação 1 e 0,8 para a movimentação 2.

Observe que nossa primeira rede de políticas fornece probabilidade anterior incorreta para o nosso exemplo. Dá 0,9 para a jogada 1, que é uma jogada perdida. Isso é bom porque nem mesmo o Google poderia treinar uma rede de políticas perfeita.

Jogando com a primeira rede de políticas

O AlphaGo precisa gerar uma simulação com o Monte-Carlo e precisa escolher o movimento 1 ou 2. Agora, o AlphaGo desenha uma variável aleatória distribuída de maneira uniforme e escolhe:

  • Mova 1 se o número aleatório for <= 0,9
  • Mova 2 se o número aleatório for> 0,9

Portanto, é muito mais provável que o AlphaGo escolha a jogada perdida para simular (em nossa primeira simulação). Em nossa primeira simulação, também usaremos a rede de valor para obter uma pontuação para a simulação. No jornal, é:

insira a descrição da imagem aqui

Esse valor seria -1000, porque essa simulação levaria a uma perda.

Agora, o AlphaGo precisa gerar a segunda simulação. Novamente, o primeiro passo seria muito mais provável. Mas, eventualmente, a segunda jogada seria escolhida porque:

  • Nossa probabilidade anterior para o segundo movimento é 0,1, não zero
  • O AlphaGo é incentivado a tentar movimentos que não foram muito explorados. No artigo, isso é feito por esta equação:

insira a descrição da imagem aqui

Observe que Né o número de movimentos pesquisados ​​para o movimento e está no denominador. Quanto mais provável a pesquisa de nosso primeiro movimento, menor a ufunção. Assim, a probabilidade de selecionar nosso segundo movimento aumenta porque o AlphaGo realmente escolhe um movimento por esta equação:

insira a descrição da imagem aqui

insira a descrição da imagem aqui

Esta é a equação chave . Por favor, olhe com cuidado:

  • Tem um termo Ppara a probabilidade anterior (fornecida pela rede de políticas)
  • Tem um termo Qpara as pontuações da avaliação (fornecidas pela rede de valor)

Agora, sabemos que nosso segundo passo será finalmente escolhido. Quando isso acontece, a rede de valor dá +1000. Isso aumentará Q, o que torna a segunda jogada muito mais provável de ser escolhida nas simulações posteriores.

Dadas simulações suficientes, o número de vezes que o segundo movimento é escolhido para simulação deve ser maior que o número de vezes que o primeiro movimento é escolhido.

Por fim, a decisão que o AlphaGo decide fazer é (citada no artigo):

Quando a pesquisa é concluída, o algoritmo escolhe o movimento mais visitado da posição raiz.

Brincando com a segunda rede de políticas

Nossa segunda rede de políticas precisará de menos iterações para escolher a mudança 2, porque a probabilidade anterior fornecida pela rede de políticas está correta em primeiro lugar.

Observações

Tudo aqui é muito semelhante à Bayesiananálise. Começamos com alguma probabilidade anterior (fornecida pela rede de políticas) e, em seguida, geramos dados para mover a distorção de probabilidade (fornecida pela rede de valores).

Resumos

  • A rede de políticas é usada para gerar probabilidades anteriores para orientar qual movimento a pesquisa de Monte-Carlo deve escolher
  • Rede de valor é usada para gerar dados para validar a rede de políticas. Se a rede de políticas estiver ruim, o AlphaGo precisaria de mais recursos de computação para convergir (se é que alguma vez).
  • Você pode pensar nisso como análise bayesiana
SmallChess
fonte
Eu acho que isso dá uma visão muito mais profunda dos mecanismos internos. Ainda não tenho certeza se explica por que as duas redes. O problema que tenho é "assuma que a rede de avaliação ... é perfeita". Se foi esse o caso, na verdade a rede de políticas é redundante. Basta olhar um passo à frente (para todos os movimentos possíveis) e escolher aquele com a melhor avaliação da rede de valor. É claro que a rede de valor não é perfeita, e eu suspeito que ela se torna mais precisa à medida que avançamos no jogo. . . mas não sei quão verdadeiro / útil isso é, ou se conclui esta resposta.
Neil Slater
@NeilSlater Ok. As redes não são perfeitas, mas as razões que tenho aqui ainda são boas, apenas porque precisamos de mais simulações de MC.
SmallChess
@StudentT Boa explicação de algumas das principais equações. Eu faria uma pequena alteração: não faz muito sentido dizer "Você precisa ver dez movimentos à frente" para entender a posição no Monte Carlo Tree Search. O MCTS é uma pesquisa de número de prova de profundidade, e nunca alcançamos profundidades fixas como atingiríamos com o aprofundamento iterativo do xadrez. Mesmo com a rede de valor permitindo avaliações de nós antes do final do jogo, nós ainda não estão alcançando estes em uma primeira maneira largura, e não há avaliação min-max dos nós, etc.
Imran
@Imran Sinta-se livre para editar minha postagem.
SmallChess
3

Rede de políticas : a rede que aprende a fornecer uma saída definitiva, fornecendo uma entrada específica para o jogo, é conhecida como rede de políticas.

Redes de valor : a rede de valor atribui valor / pontuação ao estado do jogo, calculando uma pontuação cumulativa esperada para o estado atual s. Todo estado passa pela rede de valor. Os estados que recebem mais recompensa obviamente agregam mais valor à rede.

Melhor entendimento com as animações Clique aqui: Redes de políticas versus redes de valor no aprendizado por reforço

insira a descrição da imagem aqui

SAGAR SHARMA
fonte
0

Pelo que entendi a diferença está nas saídas. Onde a rede de políticas gera uma distribuição de probabilidade entre os movimentos possíveis, a rede de valores retorna um valor real que pode ser interpretado como a probabilidade de vitória, dada a configuração desta placa. A partir daí, a pesquisa na árvore Monte-Carlo é realizada com base nas principais movimentações de K e, em seguida, estreitando a árvore de pesquisa novamente, obtendo-se as principais saídas da rede de valor K.

Sinta-se obrigado a me corrigir se estiver errado.

Joonatan Samuel
fonte
2
Você não está errado, AFAIK, mas acho que isso não responde à pergunta. O OP parece estar ciente da diferença entre um modelo baseado em valor ou em política na RL. As duas abordagens realmente têm resultados diferentes. No entanto, é mais comum ver um ou outro, não os dois, e os dois modelos geralmente são redundantes em "Value_maxarg (S ') == Policy_maxarg (S, A)" onde S é o estado atual, A é a ação para take e S 'é o estado resultante. Ou seja, as duas redes em uma configuração RL mais usual produziriam simplesmente o mesmo resultado, mesmo que as saídas sejam diferentes.
Neil Slater