Différence entre le réseau de politique d'AlphaGo et le réseau de valeur

25

Je lisais un résumé de haut niveau sur AlphaGo de Google ( http://googleresearch.blogspot.co.uk/2016/01/alphago-mastering-ancient-game-of-go.html ), et je suis tombé sur les termes "politique réseau "et" réseau de valeur ". À un niveau élevé, je comprends que le réseau de stratégies est utilisé pour suggérer des mouvements et que le réseau de valeurs est utilisé pour "réduire la profondeur de l'arborescence de recherche [et estimer] le gagnant dans chaque position au lieu de rechercher tout le chemin jusqu'à la Fin du jeu."

Ces deux réseaux me semblent redondants. Que fait le réseau de stratégies s'il n'utilise pas le réseau de valeurs pour élaguer ses stratégies? Il semble assez clair que le réseau de valeur est un réseau neuronal d'apprentissage en profondeur; le réseau politique n'est-il qu'une abstraction théorique et non un véritable réseau neuronal? La variable cible pour le réseau de valeur semble être gagnant / perdant. Existe-t-il une variable cible pour le réseau de règles? si oui, c'est quoi? Qu'est-ce que le réseau politique essaie d'optimiser?

Le pdf complet du document de Google, publié dans Nature, peut être trouvé ici: https://vk.com/doc-44016343_437229031?dl=56ce06e325d42fbc72

Ryan Zotti
la source
Comme note rapide: la variable cible pour le réseau de politique est une distribution de probabilité. Extrait de l'article: "Ce réseau neuronal (le réseau de valeurs) a une architecture similaire au réseau politique, mais génère une seule prédiction au lieu d'une distribution de probabilité"
Zimano
3
Si quelqu'un d'autre tombe sur cette vieille question, comme moi, vous serez heureux de savoir que le successeur d'AlphaGo, "AlphaGo Zero", ainsi que son successeur "AlphaZero" se débarrassent en effet de la redondance en formant uniquement UN réseau dont les résultats servir à la fois le réseau de politique (donne une distribution de probabilité sur les mouvements possibles) et le réseau de valeur (donne la probabilité de gagner compte tenu du conseil d'administration). Article de blog ici: deepmind.com/blog/alphago-zero-learning-scratch et le document est lié à l'intérieur.
Kevin Wang

Réponses:

11

En bref, chaque filet a un objectif différent, comme vous l'avez mentionné:

  • Le réseau de valeurs a été utilisé aux nœuds foliaires pour réduire la profondeur de la recherche dans l'arborescence.
  • Le réseau de politiques a été utilisé pour réduire l'étendue de la recherche à partir d'un nœud (orientant vers des actions prometteuses immédiates).

En général, vous pouvez utiliser des méthodes de fonction de valeur pour trouver une stratégie optimale ou rechercher directement dans l'espace de stratégie pour optimiser une fonction de stratégie paramétrée (bien sûr, il y a des avantages et des inconvénients). Vous pouvez utiliser des approximateurs de fonction (par exemple, Deep Nets) dans chaque cas. Je vois que vous êtes principalement confus au sujet du filet de politique, donc je concentre ma réponse là-dessus.

Le filet de politique était d'abord:

formés pour effectuer les mouvements que ferait très probablement un humain étant donné l'état de la carte (donc l'entrée est un état de la carte et la sortie est un histogramme qui montre la probabilité de chaque action étant donné cet état). Le filet peut approximer la fonction de probabilité sous-jacente au mappage des états aux actions. Il est raisonnable de penser à commencer à construire votre politique à partir des données disponibles après tout. Après une formation supervisée utilisant des mouvements d'experts, le filet de politique pourrait jouer le jeu suffisamment (bien que loin d'un niveau de maîtrise). Simplement, vous avez tenté de saisir le schéma général de sélection des actions des joueurs professionnels.

Ensuite,

il a été entraîné dans des jeux avec l'adversaire lui-même, afin d'optimiser la politique apprise précédemment. Cette fois, ses poids ont été mis à jour à l'aide de l'algorithme REINFORCE. Ce faisant, vous mettez à jour les paramètres nets pour maximiser la récompense attendue. Finalement, vous avez un filet qui sélectionne non seulement les actions comme un joueur professionnel, mais aussi pour gagner le jeu (mais il ne peut pas planifier!).

Après cette étape, ils ont approximé la fonction de valeur d'une version un peu plus bruyante de la politique apprise, par régression (l'entrée est le tableau d'état et cible le résultat du jeu). Vous pouvez utiliser ce réseau pour affecter l'évaluation du nœud feuille.

Sur le plan conceptuel, le filet de stratégie vous donne une probabilité sur les actions, mais cela n'indique pas que vous vous retrouverez dans un bon état pour avoir gagné le jeu. AlphaGo a eu quelques "angles morts" et pendant le tournoi a fait de très mauvais coups mais aussi un coup exceptionnel auquel un humain n'aurait jamais pu penser.

Enfin, vous pouvez utiliser votre algorithme de planification (SCTM) en combinaison avec ces réseaux. Pourquoi avons-nous pris toutes ces mesures? En bref, le simple SCTM sans «intuition» aurait échoué.

Constantinos
la source
Je revenais à cette question après avoir appris sur Actor-Critic, et comment cela compense les coûts / avantages entre les méthodes basées uniquement sur la valeur et basées sur les politiques. Je pense que cette réponse est la plus proche d'expliquer ce détail, mais elle est très bien couverte dans la conférence de David Silver: www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/pg.pdf (conférence 7, it est également disponible sur YouTube - youtube.com/… ).
Neil Slater
Les approches purement basées sur les SCTM se sont avérées efficaces, donc dans un contexte plus large, je ne dirais pas que cela aurait échoué.
Zimano
1
Je ne parle que du cas du jeu de Go et aussi de l'atteinte du niveau de jeu Master. En fait, David Silver (comme d'autres chercheurs) travaillait à résoudre le jeu de Go avec les SCTM depuis son doctorat. Mais rien ne pouvait rivaliser aux niveaux les plus élevés avant la combinaison des méthodes ci-dessus.
Constantinos
9

Voici mon processus de réflexion concis pour comprendre les deux réseaux différents.

Tout d'abord, l'objectif est de trouver une solution optimale (ou très quasi optimale) sans recourir à une recherche exhaustive, ce qui est définitivement un défi.

Par position ou état, il y aura N mouvements possibles, et à chaque mouvement il y aura sa propre profondeur D dans un arbre de recherche complet. Il est théoriquement ou mathématiquement possible de parcourir tous les chemins et de trouver une ou des solutions optimales. Cependant, nous ne voulons pas faire une recherche complète.

Nous avons maintenant deux questions distinctes pour développer une approche d'approximation.

Q1. Comment pouvons-nous ignorer ou ignorer certains mouvements de N par position? (c.-à-d. réduction de la respiration)

Q2. Comment s'arrêter à une profondeur intermédiaire dans un arbre de recherche plutôt que de marcher jusqu'à la fin du jeu, sans manquer de trouver une solution optimale? (c.-à-d. réduction de la profondeur)

Le réseau de politique est principalement conçu pour filtrer les déplacements inutiles hors de N, mais sans manquer de trouver une solution optimale. Ici, ce réseau repose initialement sur des mouvements d'experts humains, c'est-à-dire SL, et amélioré par RL plus tard.

Le réseau de valeur est principalement conçu pour trouver la probabilité de gain sans recherche complète.

Ces deux réseaux ont un objectif commun: trouver une solution optimale. Cependant, dans chaque choix stratégique de déménagement, chaque réseau joue un rôle différent.

J'espère juste que cela aide. Je sais que ce serait toujours à un niveau élevé.

Wind P.
la source
Votre explication des deux façons est très concise.
Tim
6

Je pense que l'OP confondait AlphaGo avec l'alpha-bêta. En alpha-bêta, vous utiliseriez en effet le réseau de règles pour aider à l'élagage, mais pas ici. Encore une fois, il n'y a pas d'élagage car l'algorithme repose sur la recherche d'arbre Monte-Carlo (SCTM).

Quiconque pense que ma réponse est trop longue peut passer à la section récapitulative, où j'explique pourquoi les deux réseaux ne sont pas redondants.

Dans l'exemple suivant, je ferai quelques simplifications pour rendre mes idées plus faciles à comprendre.

Exemple:

Imaginez que vous ayez une position où il y a deux mouvements légaux. Le premier coup est un mort-perdu pour vous, cependant, le deuxième coup vous donne un avantage gagnant.

  • Premier mouvement: perte forcée pour vous
  • Deuxième coup: victoire forcée pour vous

Réseau d'évaluation

Supposons que le réseau d'évaluation que Google vous propose est parfait. Il peut évaluer parfaitement n'importe quelle position de feuille dans notre exemple. Nous ne changerons pas notre réseau de valeur dans l'exemple.

Pour simplifier notre exemple, supposons que notre réseau de valeur donne:

  • -1000 pour toute position de feuille qui est une perte pour vous
  • +1000 pour toute position de feuille qui est une victoire pour vous

Réseau politique

Supposons que Google vous propose deux réseaux de règles. Les probabilités générées pour notre position sont:

  • Politique 1: 0,9 pour le coup 1 et 0,1 pour le coup 2
  • Politique 2: 0,2 pour le coup 1 et 0,8 pour le coup 2.

Notez que notre premier réseau de règles donne une probabilité antérieure incorrecte pour notre exemple. Il donne 0,9 pour le coup 1, qui est un coup perdant. C'est très bien car même Google ne pouvait pas former un réseau de politique parfait.

Jouer avec le premier réseau politique

AlphaGo doit générer une simulation avec Monte-Carlo, et il doit choisir le mouvement 1 ou 2. Maintenant, AlphaGo dessine une variable aléatoire uniformément distribuée, et il choisira:

  • Déplacez 1 si le nombre aléatoire est <= 0,9
  • Déplacez 2 si le nombre aléatoire est> 0,9

AlphaGo est donc beaucoup plus susceptible de choisir le mouvement perdant à simuler (dans notre toute première simulation). Dans notre première simulation, nous utiliserons également le réseau de valeurs pour obtenir un score pour la simulation. Dans le papier, c'est:

entrez la description de l'image ici

Cette valeur serait -1000, car cette simulation entraînerait une perte.

Maintenant, AlphaGo doit générer la deuxième simulation. Encore une fois, le premier mouvement serait beaucoup plus susceptible de choisir. Mais finalement, le deuxième mouvement serait choisi parce que:

  • Notre probabilité antérieure pour le deuxième mouvement est de 0,1, et non de zéro
  • AlphaGo est encouragé à essayer des mouvements peu explorés. Dans l'article, cela se fait par cette équation:

entrez la description de l'image ici

Notez que Nc'est le nombre de coups recherchés pour le coup et c'est dans le dénominateur. Plus notre premier mouvement est recherché, plus la ufonction est petite . Ainsi, la probabilité de sélectionner notre deuxième coup s'améliore car AlphaGo choisit en fait un coup par cette équation:

entrez la description de l'image ici

entrez la description de l'image ici

C'est l' équation clé . Veuillez le regarder attentivement:

  • Il a un terme Ppour la probabilité a priori (donné par le réseau politique)
  • Il a un terme Qpour les scores d'évaluation (donnés par le réseau de valeur)

Maintenant, nous savons que notre deuxième déménagement sera finalement choisi. Lorsque cela se produit, le réseau de valeur donne +1000. Cela augmentera Q, ce qui rendra le deuxième coup beaucoup plus probable dans les simulations ultérieures.

Avec suffisamment de simulations, le nombre de fois où le deuxième coup est choisi pour la simulation devrait être supérieur au nombre de fois où le premier coup est choisi.

Enfin, le mouvement qu'AlphaGo décide de faire est (cité dans le journal):

Une fois la recherche terminée, l'algorithme choisit le mouvement le plus visité à partir de la position racine.

Jouer avec le deuxième réseau politique

Notre deuxième réseau de stratégie aura besoin de moins d'itérations pour choisir le mouvement 2 car sa probabilité donnée par le réseau de stratégie est correcte en premier lieu.

Remarques

Tout ici est très similaire à l' Bayesiananalyse. Nous commençons avec une probabilité antérieure (donnée par le réseau de politique), puis nous générons des données pour déplacer la distirubtion de probabilité (donnée par le réseau de valeurs).

Résumés

  • Le réseau de règles est utilisé pour générer des probabilités antérieures afin de guider le mouvement que la recherche Monte-Carlo devrait choisir
  • Le réseau de valeurs est utilisé pour générer des données pour valider le réseau de règles. Si le réseau de politique est mauvais, AlphaGo aurait besoin de plus de ressources informatiques pour converger (si jamais).
  • Vous pouvez y penser comme une analyse bayésienne
SmallChess
la source
Je pense que cela donne un aperçu beaucoup plus profond des mécanismes internes. Je ne sais toujours pas si cela explique pourquoi les deux réseaux. Le problème que j'ai est de "supposer que le réseau d'évaluation ... est parfait". Si tel était le cas, le réseau politique est en effet redondant. Il vous suffit de regarder un pas en avant (pour tous les coups possibles) et de choisir celui avec la meilleure évaluation de réseau de valeur. Bien sûr, le réseau de valeur n'est pas parfait, et je soupçonne qu'il devient plus précis à mesure que le jeu progresse. . . mais je ne sais pas à quel point c'est vrai / utile, ni si cela complète cette réponse.
Neil Slater
@NeilSlater Ok. Les réseaux ne sont pas parfaits, mais les raisons que j'ai ici sont toujours bonnes, juste que nous avons besoin de plus de simulations MC.
SmallChess
@StudentT Belle explication de certaines des équations clés. Je ferais un petit changement: cela n'a pas beaucoup de sens de dire "Vous devez voir dix pas en avant" pour comprendre la position dans Monte Carlo Tree Search. MCTS est une recherche de numéros à l'épreuve de la profondeur, et nous n'atteignons jamais vraiment des profondeurs fixes comme nous le ferions avec l'approfondissement itératif des échecs. Même avec le réseau de valeurs qui nous permet d'évaluer les nœuds avant la fin du jeu, nous n'atteignons toujours pas ceux-ci de manière approfondie, et il n'y a pas d'évaluation min-max des nœuds, etc.
Imran
@Imran N'hésitez pas à modifier mon message.
SmallChess
3

Policy Network : Le réseau qui apprend à donner une sortie définie en donnant une entrée particulière au jeu est connu sous le nom de Policy Network.

Réseaux de valeur : le réseau de valeur attribue une valeur / un score à l'état du jeu en calculant un score cumulé attendu pour l'état actuel s. Chaque état passe par le réseau de valeur. Les États qui obtiennent plus de récompenses obtiennent évidemment plus de valeur dans le réseau.

Mieux comprendre avec les animations Allez ici: Réseaux politiques vs réseaux de valeur dans l'apprentissage par renforcement

entrez la description de l'image ici

SAGAR SHARMA
la source
0

D'après ce que je comprends, la différence est dans les sorties. Lorsque le réseau de règles génère une distribution de probabilité sur les mouvements possibles, le réseau de valeurs renvoie une valeur réelle qui peut être interprétée comme la probabilité de gagner compte tenu de la configuration de cette carte. À partir de là, la recherche d'arbre de Monte-Carlo est effectuée en prenant les mouvements K supérieurs, puis en rétrécissant à nouveau l'arbre de recherche en prenant les sorties réseau de valeur K supérieure.

Sentez-vous obligé de me corriger si je me trompe.

Joonatan Samuel
la source
2
Vous ne vous trompez pas AFAIK, mais je ne pense pas que cela réponde à la question. OP semble être conscient de la différence entre un modèle basé sur des valeurs ou basé sur des politiques dans RL. Les deux approches ont en effet des résultats différents. Cependant, il est plus courant de voir l'un ou l'autre, pas les deux, et les deux modèles sont généralement redondants dans la mesure où "Value_maxarg (S ') == Policy_maxarg (S, A)" où S est l'état actuel, A est une action pour prendre, et S 'est l'état résultant. C'est-à-dire que les deux réseaux dans une configuration RL plus habituelle produiraient simplement le même résultat, même si les sorties sont différentes.
Neil Slater