A pesquisa em árvore Monte Carlo se qualifica como aprendizado de máquina?

9

Para o meu melhor entendimento, o algoritmo MCTS (Monte Carlo Tree Search) é uma alternativa ao minimax para pesquisar uma árvore de nós. Ele funciona escolhendo um movimento (geralmente aquele com maior chance de ser o melhor) e, em seguida, executando um playout aleatório em movimento para ver qual é o resultado. Esse processo continua pelo tempo alocado.

Isso não soa como aprendizado de máquina, mas uma maneira de atravessar uma árvore. No entanto, ouvi dizer que o AlphaZero usa o MCTS, por isso estou confuso. Se o AlphaZero usa o MCTS, por que o AlphaZero aprende? Ou o AlphaZero fez algum tipo de aprendizado de máquina antes de disputar alguma partida e depois usou a intuição que ganhou com o aprendizado de máquina para saber quais movimentos se gasta mais tempo jogando com o MCTS?

Ignorância inercial
fonte

Respostas:

6

A Pesquisa de árvores de Monte Carlo geralmente não é vista como uma técnica de aprendizado de máquina, mas como uma técnica de pesquisa. Existem paralelos (o MCTS tenta aprender padrões gerais a partir dos dados, em certo sentido, mas os padrões não são muito gerais), mas realmente o MCTS não é um algoritmo adequado para a maioria dos problemas de aprendizado.

AlphaZero foi uma combinação de vários algoritmos. Um era o MCTS, mas o MCTS precisa de uma função para dizer quão bons estados diferentes do jogo podem ser (ou então, ele precisa simular jogos inteiros). Uma maneira de lidar com essa função em um jogo como o xadrez ou o Go é aproximar-se treinando uma rede neural, que foi o que os pesquisadores da Deep Mind fizeram. Este é o componente de aprendizado do AlphaZero.

John Doucette
fonte
6

A resposta de John está correta, pois tradicionalmente o MCTS não é visto como uma abordagem de Machine Learning, mas como um algoritmo de pesquisa em árvore, e que o AlphaZero combina isso com técnicas de Machine Learning (redes neurais profundas e aprendizado por reforço).

No entanto, existem algumas semelhanças interessantes entre o próprio MCTS e o Machine Learning. Em certo sentido, o MCTS tenta "aprender" o valor dos nós a partir da experiência gerada por esses nós. Isso é muito parecido com o funcionamento do RL (Reinforcement Learning) (que normalmente é descrito como um subconjunto do Machine Learning).

Alguns pesquisadores também experimentaram substituições da fase de retropropagação tradicional do MCTS (que, do ponto de vista da RL, pode ser descrita como implementação de backups de Monte-Carlo) com base em outros métodos de RL (por exemplo, backups com diferença temporal) . Um artigo abrangente que descreve esses tipos de semelhanças entre o MCTS e o RL é: Sobre a pesquisa de árvores em Monte Carlo e o aprendizado por reforço .

Observe também que a fase de seleção do MCTS é normalmente tratada como uma sequência de pequenos problemas de bandidos multimarcas e esses problemas também têm fortes conexões com a RL.


TL; DR : o MCTS não é normalmente visto como uma técnica de aprendizado de máquina, mas se você o examinar de perto, poderá encontrar muitas semelhanças com o ML (em particular, o aprendizado por reforço).

Dennis Soemers
fonte
1

Bem-vindo ao campo minado de definições semânticas na AI! Segundo a Encyclopedia Britannica ML, é uma "disciplina preocupada com a implementação de software que pode aprender de forma autônoma". Existem muitas outras definições para ML, mas geralmente elas são tão vagas, dizendo algo sobre "aprendizado", "experiência", "autônomo" etc. em ordem variável. Não existe uma definição de benchmark conhecida que a maioria das pessoas use, portanto, a menos que alguém queira propor uma, o que quer que alguém poste nelas precisa ser apoiado por referências.

De acordo com a definição da Encyclopedia Britannica, o argumento para chamar o MCTS de parte do ML é bastante forte (Chaslot, Coulom et al., Trabalho de 2006-8, é usado para a referência do MCTS). Existem duas políticas usadas no MCTS, uma política de árvore e uma política de simulação. No momento da decisão, a política de árvore atualiza os valores de ação expandindo a estrutura da árvore e fazendo backup dos valores do que encontrar na pesquisa. Não há codificação embutida em quais nós devem ser selecionados / expandidos; tudo isso vem da maximização de recompensas das estatísticas. Os nós mais próximos da raiz parecem cada vez mais inteligentes à medida que “aprendem” a imitar distribuições / estado e / ou valores de ação dos correspondentes da realidade. Se isso pode ser chamado de "autônomo" é uma questão igualmente difícil, porque no final foram os humanos que escreveram as fórmulas / teoria que o MCTS usa.

Johan
fonte