AlphaGO, dissection d’une révolution

Cet article a pour but de présenter un des moments clés de la révolution du Deep Learning ces dernières années, à savoir, la mise au point d’un système algorithmique capable de dépasser les meilleurs joueurs humains au jeu de Go. Cette révolution avait eu quelques échos médiatiques, sous le nom d’AlphaGo, une réussite du groupe Deepmind qui aujourd’hui encore est un des leaders de la recherche en Deep Learning. Nous vous proposons ici de détailler les enjeux et l’approche qui a été implémentée, ceci en deux parties : une première partie visant le grand public, et une seconde partie plus détaillée à destination de Data Scientists ou ingénieurs motivés.

L’ensemble des illustrations et données proviennent de la publication dans le journal Nature [https ://deepmind.com/research/alphago/]

Présentation globale.

Le contexte

Si cette réussite a eu un retentissement important, c’est parce que le problème abordé est d’une complexité considérable, au point d’avoir auparavant été considéré comme impossible à adresser. Dans l’absolu, pour tout environnement de ce type (comme les dames ou les échecs), il est théoriquement possible de résoudre le problème par un algorithme qui ira, à partir d’un plateau de jeu, tester l’ensemble de toutes les possibilités et les dérouler jusqu’à avoir prévu un grand nombre de coups dans le futur, voire leur totalité. Néanmoins, cette approche se heurte en pratique à la dimensionalité de l’espace dans lequel on travaille : le nombre de possibilités au jeu de dame est très limité. Aux échecs, où des algorithmes comme Big Blue existent depuis longtemps, on estime à 35^80 la « taille » de l’espace de l’ensemble des états possibles. Au jeu de Go, l’espace est encore plus grand (environ 250^150), au point qu’une approche de ce type n’a aucune chance de réussir (à moins de vouloir attendre quelques années entre deux coups). Cette explosion de la complexité était un mur infranchissable avant l’arrivée d’AlphaGo.

Face à cette barrière, les approches existantes auparavant effectuaient un grand nombre de simulations de jeu sans jamais être exhaustives, et créaient donc une représentation statistique de l’état d’un jeu et donc du meilleur coup à jouer. L’algorithme utilisé était la Monte Carlo Tree Search. Bien que très efficace, il ne suffisait pas à dépasser un niveau d’amateur. Gardons de côté cet algorithme car il sera en partie réutilisé par AlphaGo.

Apprentissage par renforcement et Deep Learning

Pour résoudre ce problème du jeu de Go, les auteurs se sont placés dans un canevas théorique dit d’apprentissage par renforcement [https://en.wikipedia.org/wiki/Reinforcement_learning]. Cette approche existait bien avant l’explosion du Deep Learning, et est assez passionnante en ceci qu’elle est très « libre » dans la définition d’un problème et la modélisation qui en résulte. Une approche Deep Learing « classique », nous devons définir une fonction de coût et celle-ci sera une limite forte. En renforcement, on définit un agent évoluant dans un environnement. À chaque instant, l’agent constate l’état de l’environnement et choisit parmi une collection d’actions à sa disposition. Son objectif est de maximiser une récompense qui est définie en amont d’une manière libre. Attention : cette liberté de définition donne l’impression que tout problème peut être adressé de cette manière d’une manière très générique. En pratique, une modélisation « efficace » peut être assez complexe à mettre en œuvre, voire impossible, et la convergence d’un algorithme sur ce type d’approche est souvent beaucoup plus laborieux qu’en apprentissage supervisé « classique ».

Si l’apprentissage par renforcement existait depuis longtemps, le Deep Learning est arrivé avec de nouveaux outils, les réseaux de neurones, qui sont excellents pour approximer des fonctions particulières. Identiquement au traitement d’images ou à la prédiction de séries où l’on peut aujourd’hui approximer une fonction de transformation par un réseau de neurone et l’entraîner sur de la donnée pour arriver à un résultat satisfaisant, une approche similaire est possible pour l’apprentissage par renforcement. Ainsi, des fonctions supposées donner le meilleur coup à jouer à partir de l’état d’un plateau, ou destinées à prédire la chance de réussite d’un joueur à partir d’un état donné, seront dans AlphaGo approximées par des réseaux de neurones soumis à apprentissage. Cet apprentissage permet d’éviter la définition d’un algorithme « exact » et d’exploiter la donnée à disposition avec un algorithme de convergence particulier pour générer l’approximation voulue.

Il convient de noter qu’AlphaGo n’a pas inventé le « Deep Reinforcement Learning ». De nombreux acteurs avaient déjà travaillé sur ce sujet, depuis les travaux de Mnih [https://scholar.google.com/citations?user=rLdfJ1gAAAAJ&hl=en] destinés à entrainer des réseaux à jouer à des jeux vidéos issus de l’Atari 2600. Néanmoins, l’approche AlphaGo s’est fortement distinguée de ces prédécesseurs en ceci qu’elle était fortement spécialisée sur le problème du Go. À ce titre, on peut voir ces travaux comme une première forme d’ingénierie spécialisée sur un problème de ce type.

Aujourd’hui, le « Deep Reinforcement Learning » est utilisé pour le contrôle robotique ou d’agents numériques, comme pour la régulation d’énergie dans un Data Center ou la résolution de problèmes d’optimisation complexes. Ce sujet est en constante effervescence avec sans cesse de nouvelles avancées, dont très récemment la création d’agents capables de jouer efficacement au jeu Starcraft 2 de Deepmind toujours [https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/]

L’approche

Attention : cette présentation reste sommaire et globale, reportez-vous à la deuxième partie pour data scientists pour une vision plus détaillée

On peut distinguer l’approche d’AlphaGo en deux parties : la création de quatre réseaux de neurones différents, et leur utilisation dans un parcours efficace de l’environnement pendant le jeu. Les quatre réseaux générés par apprentissage sont les suivants :

• Un premier réseau est entraîné à prédire, à partir d’une large collection de parties jouées par des experts humains, le coup qui a ensuite été joué. On entraine donc ce réseau à retrouver ce qui a été joué par l’expert humain dans une situation très particulière, à partir du plateau « brut » du jeu de Go. L’apprentissage est supervisé, comme une classification « usuelle ».

• Le second réseau vise à prédire la même chose, mais avec une architecture beaucoup plus simple. De plus, là où le premier exploite comme donnée d’entrée le plateau de Go avec la position de chaque pièce, celui-ci prend en entrée des pré-calculs particuliers de features propres au jeu de Go. On retrouve ici l’idée que s’il est possible de donner en entrée à un réseau de neurones un pré-calcul pertinent, il est souvent intéressant de le faire et ainsi de décharger en partie l’apprentissage. Ce deuxième réseau est bien moins performant que le premier, mais beaucoup plus rapide. L’apprentissage reste supervisé.

• Le troisième réseau lui ne vise plus à prédire ce qu’a fait un expert dans une base de données statique, mais à prédire une meilleure action de jeu selon un apprentissage par renforcement. Pour entraîner ce réseau, on part du premier réseau supervisé, et on le fait ensuite progresser par self play, i.e. en le faisant jouer contre d’anciennes versions de lui-même. Ce réseau dit de policy prend en entrée l’état du plateau et donne en sortie le coup à jouer.

• Enfin, le quatrième réseau va apprendre à prédire la victoire ou l’échec du troisième réseau à partir d’un état du plateau de jeu. Prenant en entrée ce plateau, il donnera en sortie l’estimation de victoire ou de défaite uniquement.

À ce stade, on peut être surpris par le nombre de réseaux générés. L’idée est que chacun de ces réseaux sera utilisé à un moment différent dans la Monte Carlo Tree Search (MCTS), soit, l’algorithme qui va statistiquement tester un ensemble de coûts et peu à peu construire une représentation d’arbre logique des différentes actions possibles pour pouvoir estimer le meilleur coup. On retrouve donc ici avec la MCTS la méthode qu’utilisait déjà les anciens algorithmes de jeu, mais en exploitant en interne ces différents réseaux qui vont permettre à AlphaGo de dépasser un professionnel humain lors d’une partie de jeu.

Résultats et points d’attention

AlphaGo a créé une révolution, mais au prix d’une approche très spécifique. De fait, très peu de travaux ultérieurs ont réutilisé cette approche, à l’exception notable d’AlphaGo Zero. En effet, là où de nombreuses approches de Deep Reinforcement Learning existent avec la vocation d’être assez génériques et donc de pouvoir être utilisées sur des problèmes différents (Deep Q Learning, Rainbow, A3C, et une multitude d’autres travaux), cette approche est trop spécifique.

Néanmoins, l’utilisation de la Monte Carlo Tree Search reste une piste intéressante de travail pour un agent devant faire face à un système à forte dimensionalité. Et il est possible que cette approche d’architecture spécifique soit une base des travaux de demain, où pour aborder un problème complexe, on doive créer différents réseaux adaptés au problème dans une architecture dédiée.

L’initialisation d’un réseau à partir d’une grande base de parties d’expert est une approche très intéressante (quand bien même elle sera abandonnée pour AlphaGo Zero). Il y a là un moyen d’initialiser un réseau qui ne pourrait pas apprendre depuis un état initial « vide ». De même, l’amélioration d’un réseau en le faisant jouer contre d’anciennes versions de ce même réseau est une solution très élégante d’amélioration.

En revanche, un bémol évident est sur la plan technique. Pour son apprentissage, AlphaGo utilisait 48 CPUs et 8 GPUs dans sa version « simple », jusqu’à 1200 CPUs et 176 GPUs dans une version distribuée.

Présentation technique

Des connaissances fondamentales en Deep Reinforcement Learning (fonction V et Q par exemple), comme en architecture DNNs (CNN, ReLu) peuvent être nécessaires à la compréhension intégrale de cette partie.

Détail de l’apprentissage

Comme dit plus haut, quatre réseaux différents ont été conçus lors de l’apprentissage d’AlphaGo :

Le premier réseau, SL policy network, vise donc par apprentissage supervisé à retrouver le coup joué suivant dans une base de parties d’expert. Le réseau comprend 13 couches convolutives avec alternance de Rectified Linear Units, pour une précision finale de 57%. Le réseau modélise donc la distribution des actions selon l’état en entrée, avec une architecture convolutive classique destinée à générer des représentations haut niveau du plateau de jeu de Go. Le gradient est exploité par Stochastic Gradient Ascent.

Le second réseau, le fast rollout policy network, exploite en entrée un ensemble de features pré-calculées :

Il est d’architecture plus simple que le SL policy network, et est aussi entraîné selon un apprentissage supervisé classique, pour une précision finale de 24.2%. Là où son inférence prend 2 micro-secondes, l’inférence du SL policy prenait elle environ 3ms. On a donc un réseau environ 1000 fois plus rapide donc l’efficacité sera une clé de la réussite de la Monte Carlo Tree Search

Le troisième réseau, le policy network, est lui un réseau classique de Deep Reinforcement Learning (pour les approches de policy gradient contrairement aux approches de Q Learning où l’objectif est alors de modéliser une fonction d’évaluation de chaque action pour un état). Il a exactement la même structure que le SL policy network, et ses poids sont donc initialisé sur les poids appris de ce dernier modèle. Il est ensuite amélioré par self play, à chaque fois contre une version antérieure aléatoire de ce réseau. Selon les auteurs, le fait de choisir aléatoirement l’adversaire du réseau parmi un pool d’anciennes versions permet de fortement stabiliser l’entrainement. Encore une fois, ce réseau est optimisé par stochastic gradient ascent..

Le dernier réseau est un value network classique. La fonction V en renforcement vise à donner l’espérance de la récompense attendue à partir d’un état donné, et est un outil central de modélisation d’un problème classique. Ce réseau vise à apprendre le résultat attendu par utilisation du policy network, i.e., la réussite ou non de ce réseau à partir d’un état du plateau de jeu.

Deux points d’attention intéressants :

• Du fait de la symétrie interne d’un plateau de jeu de Go, une data augmentation a été réalisée de la même manière que l’on augmentera un dataset d’images par des symétries de l’image classifiée.

• Le dernier réseau avait une forte tendance à partir en overfit (la malédiction usuelle de notre domaine…) Le dataset de coups d’experts a donc été enrichi d’un vaste échantillon de parties en self play jouées par le policy network.

Monte Carlo Tree Search

L’algorithme central d’AlphaGo reste cette Monte Carlo Tree Search qui était déjà au cœur des anciennes approches dédiées au jeu de go. Une description extensive est disponible sur Wikipedia [https://en.wikipedia.org/wiki/Monte_Carlo_tree_search]. Fondamentalement, l’idée de la MCTS est d’effectuer un grand nombre de simulations afin de construire au fur et à mesure un arbre dont les nœuds sont des états de l’environnement, les arrêtes sont les actions reliant un état à un autre, et où chaque nœud est porteur d’une estimation de la valeur de son état. Par exemple, dans le schéma ci-dessous, un joueur « blanc » et un joueur « noir » jouent l’un face à l’autre.

Le joueur blanc joue en premier (état en haut de l’arbre), puis chaque joueur jouent à tour de rôle. Ici, on observe dans chaque nœud le nombre de parties gagné par le joueur qui va jouer (blanc puis noir) sur le nombre de partie totale rencontrée. Cet arbre est généré en répétant une procédure en quatre étapes :

1. La sélection : on part de la racine de l’arbre et on choisit, en voulant maximiser le score déjà obtenu tout en gardant une dose d’exploration aléatoire, un parcours de l’arbre jusqu’à aller à une feuille en bas de l’arbre.

2. L’expansion : à partir de la feuille retenue, on décide d’une action et donc on créé un nouveau nœud.

3. La simulation : on utilise une procédure de simulation pour donner une première estimation de la valeur de ce nœud (mène-t-il à une victoire ou non)

4. La backpropagation : à partir de cette valeur, on remonte l’arbre en mettant à jour chaque nœud rencontré, tant sur le nombre de parties jouées que sur le nombre de parties gagnées.

En répétant cette procédure de nombreuse fois, on arrive à une modélisation « ad-hoc » de l’état initial et de la valeur de chaque action disponible. On peut donc ensuite utiliser cet arbre pour retenir l’action la plus intéressante.

Monte Carlo Tree Search et AlphaGo

Dans le cadre d’AlphaGo, chaque étape de la procédure est spécifique et utilise les réseaux de neurones précédemment entraînés.

Pour la sélection : chaque nœud est choisi par un tirage aléatoire, où la probabilité de chaque action est définie par une fonction mêlant d’une part une estimation de la valeur de l’action (la fonction Q sur le schéma), et d’autre part un paramètre u(s,a) qui a lui pour objectif de favoriser les actions les moins utilisées. On a donc une pondération entre la valeur de chaque état et le besoin d’une exploration.

Pour l’expansion : une fois arrivé sur une feuille de l’arbre, on déroule l’ensemble des actions possibles avec le SL policy network afin de générer les probabilités initiales qui seront ensuite utilisées pour la prochaine sélection. On choisit ensuite l’action la plus « intéressante » en termes de probabilités

Pour la simulation : deux formes d’évaluation sont faîtes pour la simulation : l'une utilise le value network pour estimer la valeur du nœud, l’autre va exploiter la fast rollout policy afin de dérouler une partie jusqu’à une fin du jeu. L’interet de ce deuxième modèle apparaît alors dans la mesure où malgré une précision faible, il est très rapide et donc handicape peu la performance nécessaire à cette action. Les deux résultats sont combinés à parts égales pour donner la valeur attribuée à ce nœud.

Pour la backpropagation : Chaque nœud et chaque action rencontrée lors de la sélection voient leur fonction Q mise à jour à partir de la valeur attribuée au dernier nœud.

Dans leur publication, les auteurs précisent qu’ils ont testé la plupart des combinaisons possibles de modèles pour les différentes phases de la MCTS, pour ne garder que les résultats optimaux. De plus, une approche bayésienne a été mise en place afin d’optimiser les hyper-paramètres utilisés dans AlphaGo.

Visualisation et performances

Pour illustrer, le schéma ci-dessous montre les différentes valeurs disponibles selon les réseaux entraînés pour un état du tableau :

a) Evaluation effectuée en utilisation le value network pour estimer la valeur des différents états disponibles par action unique à partir de l’état du plateau de jeu.

b) Evaluation de la valeur de chaque état par un parcours de l’arbre de la MCTS, en utilisant uniquement le value network pour les transitions (et donc la fonction Q)

c) Evaluation similaire, mais cette fois ci en utilisant uniquement des déroulements complets avec le fast rollout policy

d) Résultats issus du SL Policy Network avec les principales actions retenues

e) Pourcentage de visite de chaque action lors d’un déroulement de la MCTS

f) Coup retenu après déroulement de la MCTS.

Une autre analyse précieuse est celle des ablations possibles, procédure typique aux approches DRL sérieuses. Pour rappel, il s’agit de tester la solution en enlevant tout ou partie des éléments qui font son architecture. Vous retrouverez dans le schéma ci-dessous au milieu les résultats comparés du modèle selon les réseaux utilisés parmi les quatre décrits ci-dessus. Le schéma de gauche donne le résultat global en ELO d’AlphaGo, et celui de droite les performances comparées d’AlphaGo selon les parallélisations mises en œuvre et le hardware disponible.

Pour aller plus loin

Si le sujet vous a intéressé, il serait dommage de ne pas aller voir la « suite » de l’aventure AlphaGo avec AlphaGo Zero [https://deepmind.com/blog/alphago-zero-learning-scratch/]. Nous aurons l’occasion d’en reparler, mais cette nouvelle version a eu pour principal intérêt de ne plus avoir besoin d’une large partie d’experts pour initialiser le réseau, ainsi qu’une utilisation de la MCTS différente, cette fois ci au sein de l’apprentissage. Un travail concurrent mais non moins intéressant est Thinking Fast And Slow With Deep Learning & Tree Search de Anthony et al, qui malgré sa malédiction de sortir en même temps qu’AGZ, propose une approche globale d’amélioration d’une policy efficace et pertinente.

Si vous avez détecté des erreurs ou des approximations au sein de cet article (ce qui est fort possible), n’hésitez pas à nous les signaler et nous les adresserons dès que possible.