Intelligence artificielle - weave
IA Lab

De quoi AlphaGo Zero est-il le progrès ?

29 janvier 2018

Résumé

Dans une percée historique récente (octobre 2017) l’algorithme AlphaGo Zero mis au point par DeepMind est parvenu à maîtriser le jeu de Go à un niveau suprahumain sans l’aide d’aucune supervision humaine. Pour parvenir à cette prouesse, AlphaGo Zero combine de manière astucieuse trois techniques classiques de l’IA : l’apprentissage par renforcement, la recherche arborescente et l’apprentissage profond. Nous expliquerons comment ces différents éléments s’articulent au sein de l’algorithme AlphaGo Zero et nous examinerons ses atouts et ses limitations. Enfin, nous évoquerons une application à moyen terme de ce type d’algorithme au problème du repliement des protéines, l’un des Graal de la recherche biomédicale actuelle.

  1. Résoudre le jeu de Go – un problème « No-Data »
  2. Le Deep Learning à la rescousse de la recherche arborescente
  3. Du jeu de Go au repliement des protéines

1. Résoudre le jeu de Go – un problème « No-Data »

Une méditation artificielle

A moins d’avoir passé ces derniers mois en hibernation ou exilé sur la planète Mars sans connexion internet, la nouvelle a dû vous parvenir : en seulement 40 jours d’exploration numérique autonome le système AlphaGo Zero (AGZ) mis au point par DeepMind a redécouvert 3000 ans de connaissances humaines sur le jeu de Go compilées jusque-là dans des ouvrages spécialisés, dans des collections d’aphorismes ainsi que dans d’innombrables parties de grands maîtres. Nous ne reviendrons pas ici sur la saga AlphaGo qui a défrayé la chronique depuis plus d’un an, rappelons simplement que AlphaGo Zero l’a emporté 100 contre 0 contre le système qui avait préalablement battu le champion Lee Sedol en 2016.

Figure 1 : Comparatif des performances – source [AG0].

Dans une forme de méditation artificielle que nous allons décrire en détail, AGZ a joué des millions de parties contre son meilleur adversaire, lui-même, et est devenu… imbattable !

Du Tic-Tac-Toe au jeu de Go

Le développement de nouveaux algorithmes pour les jeux est moins futile qu’il n’y paraît de prime abord. Pour les chercheurs de DeepMind, dont l’objectif n’est rien moins que de « résoudre l’intelligence » [SIN], il ne s’agit pas de créer des algorithmes à vocation ludique ou capable d’entraîner de futurs champions mais plutôt de faire avancer la recherche fondamentale sur les problèmes difficiles de l’IA comme l’apprentissage non-supervisé ou, à long terme, le développement d’une IA généraliste. Mais, avant d’en venir à AGZ, replaçons rapidement le problème dans son contexte.

Pour les jeux à somme nulle et à information complète[1] dont font partie le Tic-Tac-Toe, les échecs et le Go, un résultat théorique [VNE] garantit l’existence d’une stratégie optimale, que l’on appelle l’algorithme du minimax. Il consiste pour un joueur à chercher à minimiser sa perte dans le pire des cas, celui où son adversaire joue de manière optimale. Dit autrement, pour chaque position s du jeu il existe une fonction de valeur voptimal(s) qui détermine l’issue de la partie à condition que les deux joueurs jouent parfaitement. On s’en doute, une telle stratégie optimale est en règle générale inaccessible en pratique pour cause d’explosion combinatoire[2]. Font exception les jeux élémentaires comme le Tic-Tac-Toe dont l’arbre complet peut être construit explicitement (figure 2).

Figure 2 : Le jeu de Tic-Tac-Toe est assez simple pour que l’on puisse calculer la stratégie optimale dictée par l’algorithme du minimax – source [TTO].

Pour aborder des jeux plus complexes, il existe deux solutions que l’on peut combiner :

  1. La première consiste à limiter la profondeur de l’arbre de recherche en remplaçant, à partir d’une certaine profondeur, l’évaluation récursive exacte de voptimal(s) (qui est impossible en pratique) par une approximation v(s) judicieuse. Une manière d’obtenir une telle approximation consiste par exemple à dérouler le jeu (rollout) à partir s jusqu’à son terme en appliquant une stratégie facile à calculer (voire même aléatoire). Ce type d’approche a par exemple permis de construire des programmes d’échecs aux performances suprahumaines.
  2. Le seconde option consiste à limiter la largeur de l’arbre en échantillonnant les mouvements a possibles à partir de s à l’aide d’une distribution de probabilité p(s,a) qui suggère les coups les plus prometteurs.

L’algorithme MCTS (Monte-Carlo Tree Search) [MCT] combine les deux idées précédentes. Il construit par itération un arbre dont chaque nœud porte l’estimation v(s) d’une configuration s et chaque lien (s,a), correspondant à une action a légitime à partir de s, porte une probabilité p(s,a) de gagner le jeu si l’on choisit l’action a. On peut montrer que les estimations v(s) et p(s,a) de MCTS convergent vers les valeurs optimales à mesure que l’arbre croit. Les programmes de Go les plus performants avant l’avènement d’AlphaGo utilisaient un tel MCTS. Nous n’aborderons pas ici le détail de son fonctionnement car nous décrirons dans la section 2 la variante conçue spécifiquement pour AGZ et qui est plus simple que le MCTS original.

Un thème récurrent de ces approches arborescente consiste à trouver un moyen efficace d’explorer l’arbre du jeu en optant pour un bon compromis entre l’exploitation de l’information acquise, qui consiste à choisir des mouvements qui ont de bonnes chances d’être favorables, et l’exploration, qui consiste à choisir des mouvements rarement utilisés et dont on ignore encore la valeur.

Pendant longtemps les experts pensaient qu’une évaluation précise de v(s) et de p(s,a) demeurerait inaccessible pour le jeu de Go tant le nombre de transitions (≈ 250) est élevé. Mais… c’était sans compter comme nous le verrons sur l’apprentissage par renforcement et sur les réseaux de convolutions !

Voici les principales motivations pour l’étude du jeu de Go par les techniques de l’IA :

  • Démontrer la possibilité de résoudre un problème très complexe sans aucune intuition ou expérience humaine et sans données étiquetées, celles-ci étant souvent très couteuses à produire voire indisponibles.
  • Etudier dans quelle mesure il est possible de compenser l’explosion combinatoire d’un arbre de décision très profond et très large par une évaluation très précise des positions et des coups.
  • Appliquer l’algorithme créé pour résoudre le jeu Go à d’autres problèmes de recherche de stratégies.

Nous n’aborderons pas dans cet article les questions liées à l’architecture matérielle de AGZ qui exploite en particulier des processeurs spécialisés TPU [TPU] développés par Google pour le Deep Learning.

2. Le Deep Learning à la rescousse de la recherche arborescente[3]

La « Big Picture »

Avant d’entrer dans les arcanes des trois principaux mécanismes qui constituent AGZ, à savoir : a) l’apprentissage par renforcement, b) une variante de la recherche arborescente MCTS et c) les réseaux de convolution, nous présentons dans ce paragraphe une vue d’ensemble de l’algorithme.

Au cœur d’AGZ il y a l’instauration d’un cercle vertueux au moyen d’un grand nombres de parties que l’algorithme joue contre lui-même, figure 3.

  1. [Self-play] : AGZ joue un grand nombre de parties contre lui-même (self-play). A chaque instant t il choisit le coup at qu’il va jouer en examinant la position st des pierres sur le tablier et en utilisant une stratégie π. Cette stratégie π est de type probabiliste, ce qui signifie qu’elle définit une distribution de probabilité πt sur tous les coups légitimes à partir de st parmi lesquels at est choisi au hasard, ce qu’on note a πt. Pour chaque partie jouée, AGZ enregistre la succession des configurations st, des distributions πt (et pas seulement des coups joués !) ainsi que l’issue de la partie zt du point de vue de celui qui joue à l’instant t (1 = « gagné », 0 = « perdu »).
Figure 3 : A chaque instant t l’algorithme sélectionne le coup at qu’il va jouer selon une stratégie π existante. Il mène le jeu à son terme à l’instant t=T et note lequel des deux « adversaires » a gagné – source [AG0].
  1. [Calcul des coups] : Un coup at joué à l’instant t selon la stratégie π se base sur une exploration arborescente du jeu à partir de l’état st (figure 4). Pour limiter la profondeur et la largeur de cette exploration, AGZ la guide au moyen d’une fonction de prédiction f(st) qu’il a appris (au sens machine learning du terme) en s’observant jouer avec une stratégie antérieure (voir le point 3 ci-dessous). Cette fonction f(st) estime d’une part la valeur vt d’une position st en évaluant les chances de gagner la partie à partir de là. D’autre part, f(st) fournit aussi une distribution de probabilité pt = [p(st, a1), p(st,a2),… ] qui estime les chances de choisir les différents coups possibles a1, a2,… à partir de la configuration st.

« Cette exploration arborescente guidée du jeu peut être envisagée comme la phase où AGZ « réfléchit » au meilleur coup at à jouer en exploitant l’expérience capitalisée dans la fonction de prédiction fθ. »

Figure 4 : A chaque instant t AGZ procède à une exploration arborescente guidée par la fonction de prédiction fq. Au terme de cette exploration AGZ calcule une distribution de probabilité πt sur les coups possibles à partir de st qu’il échantillonne pour choisir le coup at – source [AG0].

L’exploration guidée se termine par l’obtention d’une distribution πt (point 1) utilisée pour choisir le coup at à jouer. C’est là que s’amorce le cercle vertueux :

« La distribution πt, calculée par une exploration arborescente guidée par la distribution prédite pt, est une version améliorée de cette prédiction. L’exploration arborescente fonctionne comme un amplificateur de qualité. »

  1. [Apprentissage de la fonction de prédiction] : La fonction de prédiction f est apprise à partir d’échantillons[4]  de jeux tirés parmi les parties les plus récentes qu’AGZ a joué contre lui-même. La fonction f = fθ dépend de paramètres[5] θ ajustés par itérations[6]  pour maximiser la similarité entre les prédictions f(st) = (pt, vt) et ce qui ce qui est effectivement observé (πt, zt) dans les échantillons de parties déjà jouées. On peut envisager la fonction de prédiction fθ comme l’expérience acquise par AGZ lorsqu’il se regarde jouer. Dit autrement, fθ essaie de reproduire par observation la manière de jouer de π mais sans jouer effectivement ! C’est la deuxième partie du cercle vertueux :

« La fonction de prédiction fθ (st) essaie en permanence d’imiter (avec pt) les résultats de l’exploration arborescente qui fournit (avec πt) de meilleurs résultats qu’elle ! »

  1. [Mise à jour de la stratégie] : Lors de points de contrôle réguliers[7] au cours de l’optimisation des paramètres θ de la fonction de prédiction fθ , on évalue ses performances. Pour cela on fait jouer un grand nombre[8] de fois la stratégie courante π, guidée par la version fθ* la plus performante de f observée jusque-là, contre une nouvelle stratégie π’ guidée cette fois par la fonction fθ en cours d’optimisation. Si π’ l’emporte sur π dans plus de 55% des parties on remplace la stratégie π par π’ pour la génération des jeux sur lesquels on va entraîner fθ.

« L’amélioration progressive de la fonction de prédiction fθ, qui « court après la stratégie π », est convertie en une amélioration de progressive de la stratégie π. »

Et… la boucle est bouclée !

Quelques itérations (<5) de relecture de ce paragraphe « La Big Picture » devraient permettre aux idées d’infuser. Passons maintenant aux détails.

Zoom sur l’apprentissage par renforcement

La forme la plus commune d’apprentissage automatique est le machine learning supervisé (voir section 2 de l’article II) [LEM]. Dans ce schéma l’algorithme est entraîné au moyen d’une liste d’observations pour lesquelles on connaît les réponses de référence que l’algorithme devrait idéalement reproduire.

Dans le cadre d’un jeu de stratégie comme le Go l’algorithme doit prédire le coup at qui a le plus de chances de mener à la victoire à partir de la configuration st. Il n’existe hélas aucune vérité de référence qui permettrait de savoir à cet instant t si le coup at est un judicieux ou non[9] . L’issue de la partie zt ne détermine que la qualité de la stratégie π qui dicte les coups at  et non pas la qualité des coups individuels. Un tel problème, pour lequel on cherche à optimiser une stratégie π qui associe une action at à une situation st dans le but de maximiser une certaine récompense fournie par un environnement, s’appelle un problème d’apprentissage par renforcement (AR). La récompense peut être une somme de récompenses dispensées à chaque instant t ou alors, comme pour le jeu de Go, cette récompense n’est acquise qu’au terme du jeu. Un algorithme AR apprend par interaction avec l’environnement et non par supervision à l’aide de données de références.

Figure 5 : L’apprentissage par renforcement dans AGZ procède indirectement en optimisant la fonction de fθ qui doit prédire au mieux les distributions πt observées et l’issue zt observée. Concrètement la fonction fθ. est réalisée grâce à un réseau de convolution – source [AG0].

Il existe différentes approches à ce problème d’AR [RLI, HOM]. Celle qu’utilise AGZ (dont nous avons décrit les grandes lignes au paragraphe « La Big Picture » ) est une variante d’une approche classique qu’on appelle Policy Iteration. Elle consiste à alterner l’amélioration puis l’évaluation d’une stratégie. Dans AGZ l’amélioration intervient cependant de manière très indirecte puisqu’elle est la conséquence de l’amélioration continue de la fonction de prédiction fθet de l’amplification de qualité par la recherche arborescente à chaque point de contrôle. L’évaluation procède, on l’a vu, en confrontant la stratégie courante π, basée sur la meilleure fonction de prédiction existante fθ*, avec une nouvelle stratégie π’ guidée par la fonction fθ récupérée au point de contrôle.

Subtilité : même si la recherche d’une stratégie optimale par AGZ est un problème d’AR, l’entraînement de la fonction de prédiction fθ procède de manière supervisée. En effet, une fois les jeux déroulés selon π, on connaît à chaque instant t aussi bien la distribution πt que l’issue zt que fθ = (pt, vt) doit essayer de prédire.

Zoom sur la recherche arborescente

La recherche arborescente, guidée par une fonction de prédiction f, a pour objectif de calculer une distribution de πt sur les coups at (permis à partir d’une configuration initiale st) qui attribue une grande probabilité aux coups at qui ont une meilleure chance de faire gagner celui qui les joue.

A priori on pourrait se demander : « pourquoi ne pas jouer systématiquement le meilleur coup suggéré par πt plutôt que d’échantillonner cette distribution ? ». En fait l’approche probabiliste apporte un compromis entre l’exploitation, qui consiste à jouer souvent les meilleurs coups connus, et l’exploration, qui consiste à accorder une petite chance malgré tout aux coups risqués.

Dans ce paragraphe nous expliqueront comme fonctionne le guidage de l’exploration arborescente par la fonction de prédiction f, voir la figure 6.

Figure 6: L’exploration arborescente procède par itérations (=simulations) de 3 phases, voir le texte. Après un nombre d’itérations qu’on peut choisir pour régler le niveau de jeu, la distribution πt est calculée – source [AG0].

La racine de l’arbre correspond à la configuration st pour laquelle on souhaite construire la distribution πt au terme de l’exploration. Les autres nœuds, à l’exception des feuilles, correspondent à des configurations s accessibles à partir de st et pour lesquelles on a déjà évalué la fonction de prédiction f(s) = (p(s), v(s)). Les feuilles correspondent à des configurations s qui n’ont n’a pas encore reçu d’évaluation avec f. Les liens (s,a) entre nœuds correspondent à des mouvements a légaux déjà explorés à partir de s.

Chaque itération (ou simulation) part de la racine de l’arbre et le traverse jusqu’à parvenir à une feuille.

A chaque lien (s,a) sont associés plusieurs statistiques :

  • Le nombre N(s,a) d’itérations qui l’ont déjà parcouru
  • Les probabilités p(s) = [p(s,a1), p(s,a2),… ] calculées par f(s) associées aux différents mouvements a1, a2,… possibles à partir de s
  • Un gain moyen par itération Q(s,a) ainsi qu’un gain cumulé sur toutes les itérations W(s,a) dont le calcul sera explicité au point c)

Chaque simulation comporte 3 phases (figure 6) :

  1. Sélection d’un chemin de la racine jusqu’à une feuille : pour chaque configuration s sur son chemin AGZ sélectionne le mouvement a qui maximise, non pas directement le gain moyen Q(s,a), mais plutôt la somme Q(s,a) + « un terme qui favorise les mouvements a probables selon p(s,a) mais qui n’ont encore reçu qu’un petit nombre N(s,a) de visites ». De cette manière AGZ favorise l’exploration de l’arbre lors les premières simulations et sélectionne par la suite des mouvements a qui offrent un gain potentiel élevé Q(s,a). La phase se termine lorsqu’on parvient à une feuille sL non encore évaluée.
  2. Evaluation de la feuille : on évalue sL avec f(sL) qui fournit à la fois la valeur v(sL) de la position sL et les probabilités de transition p(sL) = [p(sL,a1), p(sL,a2),… ] vers les nœuds accessibles. On initialise les statistiques des liens ajoutés à partir de sL : N(sL,a)=0, Q(sL,a)=0 et W(sL,a)=0.
  3. Mise à jour des statistiques : les statistiques de tous les liens (s,a) visités par le dernier chemin qui relie st à sL sont mises à jour : les nombres de visites sont incrémentés N(s,a) → N(s,a) + 1, on ajoute l’évaluation v(sL) de la position sL au gain total W(s,a) → W(s,a) + v(sL) et on recalcule le gain moyen Q(s,a) → W(s,a)/N(s,a).

Le nombre d’itérations[10] des étapes a), b) et c) est un paramètre que l’on peut ajuster pour régler la profondeur ou le temps de réflexion alloué à AGZ lors du self-play.

A la fin de ces itérations la probabilité π(st,a) pour chaque coup a légitime à partir de st est définie comme étant proportionnelle au nombre de fois N(st,a) où la coup a été sélectionné[11] .

Une fois le coup a choisi, la nouvelle configuration devient la racine d’un nouvel arbre qui est une branche du précédent. Les statistiques associées à l’ancien arbre sont conservées dans le nouveau.

Zoom sur le réseau de convolution

Le dernier élément à aborder pour décrire le fonctionnement d’AGZ est l’algorithme utilisé pour l’apprentissage de la fonction de fθ qui doit prédire la probabilité v(s) de gagner la partie et les probabilités p(s) = [p(s,a1), p(s,a2),… ] de jouer les coups a1, a2, … à partir d’une configuration s. Les données d’entraînement fθ étant constituées à partir d’un échantillon de parties récemment jouées par AGZ.

AGZ utilise à cette fin un réseau de convolution (CNN) [MAI] spécifique qui constitue à ce jour l’état de l’art pour l’analyse d’images. L’image en l’occurrence est de taille 19 x 19 et est constituée de la position à l’instant t des pierres de celui qui joue, de position de celles de son adversaire[12] et de la couleur de celui qui a la main.

Le réseau CNN utilisé par AGZ est très profond. Il comporte des dizaines de couches organisées par blocs de convolution donc chacun utilise des centaines de filtres. Il ne saurait être question ici d’entrer dans le détail de cette architecture décrite dans [DRI]. Notons simplement quelques points importants.

Figure 7 : Les connexions raccourcis (skip connexions) dans les CNN permettent de construire les réseaux très profonds nécessaires à l’analyse d’images – source [DRI].

A l’heure actuelle la démarche de construction de ces réseaux reste extrêmement empirique, il n’existe ni théorie ni méthode systématique pour les construire. Il a cependant été observé expérimentalement que les réseaux très profonds (avec beaucoup de couches) sont indispensables pour une analyse d’image performante.

L’une des astuces clés découverte par les chercheurs dans [DRI] consiste à utiliser des connexions raccourcis entre couches de neurones comme l’illustre la figure 7.

L’intuition derrière cette astuce est aisée à comprendre. Dans les réseaux très profonds, la transformation que fθ doit apprendre entre l’image d’entrée et la sortie souhaitée est une composition de centaines de « petites » transformations successives réalisées par les couches du CNN. Beaucoup de ces transformations sont vraisemblablement très proches de l’identité, ce qui signifie que leur sortie h(x) n’est qu’une légère modification de leur entrée x. Dans une telle situation la fonction h à apprendre peut s’écrire h(x) = x + ε(x) où ε(x) est proche de zéro. En fait, apprendre la fonction x → x, qui ne fait strictement rien (!), n’est pas naturel pour un RN constitué de couches non-linéaires. On conçoit par conséquent qu’on puisse faciliter l’apprentissage d’une couche en lui demandant d’apprendre la petite perturbation ε(x) proche de zéro. C’est précisément ce que permettent les raccourcis de la figure 7.

3. Du jeu de Go au repliement des protéines


« C’est bien joli toutes ces théories et tous ces algorithmes mais c’est quoi les applications pratiques pour mes clients aujourd’hui ? Faire de l’art pour l’art, moi (nous) c’est pas vraiment mon (notre) truc ! »

Aussi sûrement que reviennent les hirondelles au printemps, la question resurgit, lancinante, lorsqu’un public préoccupé avant tout de pragmatisme et de parts de marché se voit confronté à un sujet de recherche fondamentale aux perspectives un peu floues.

Pour la satisfaction de tous ces lecteurs, qui me tient à cœur, et pour les autres aussi, essayons donc d’y répondre.

De quoi AGZ est-il un progrès ?

Deux versions un peu élaborées de la question « ça sert à quoi ? » pourraient être : « Quelles sont les problèmes pratiques que l’on peut reformuler comme la recherche d’une stratégie optimale d’un jeu à information complète ou à comme un problème d’apprentissage par renforcement ? » Ou encore : « AGZ a-t-il fait progresser un tant soit peu l’IA sur l’un des problèmes difficiles comme l’apprentissage non-supervisé ou l’intelligence artificielle généraliste ? »

Les algorithmes d’apprentissage par renforcement (AR) présupposent deux choses des problèmes auxquels on souhaite les appliquer. Tout d’abord il faut disposer d’une notion de récompense fournie par l’environnement d’apprentissage (le fait de gagner ou non au terme d’un jeu p.ex.) et ensuite, il faut aussi pouvoir répéter rapidement et un très grand nombre de fois les interactions entre un agent et son environnement. Deux conditions à l’évidence vérifiées pour le Go dont l’environnement se résume à une table de 19 x 19 cases soumises à quelques règles de jeu. En réalité, peu de problèmes concrets vérifient ces deux conditions. Un système de pilotage de voiture sans conducteur ne saurait par exemple faire 40’000 accidents avant de respecter correctement les règles de la circulation. Il faut s’y résoudre, la réalité le plus souvent ne peut être accélérée ! Aussi peut-on affirmer sans grand risque qu’à AGZ n’est probablement pas un premier pas vers une IA généraliste. Une étape importante consisterait plutôt à faire en sorte qu’une IA construise par elle-même, par l’observation de la réalité dans tout sa complexité, des modèles dynamiques dont elle pourrait ensuite accélérer le déroulement pour prendre des décisions pertinentes [PFQ]. Nous n’en sommes pas là.

Il existe cependant des situations pratiques assez simples pour que l’on puisse simuler l’interaction entre un agent intelligent et son environnement. C’est par exemple ce que font les roboticiens [ELB] qui utilisent différentes formes d’AR avec des environnements simulés, pour que leurs robots apprennent à se mouvoir dans des environnements complexes. Un autre domaine prometteur pour les applications de l’AR est celui de la recherche biomédicale et de la synthèse de médicaments. La taille de l’espace des molécules qu’il s’agit d’explorer est colossale, 1060 au bas mot. A condition de codifier les lois de la chimie et de pouvoir définir un objectif à atteindre l’AR pourrait être un outil d’une efficacité redoutable. La médecine personnalisée pourrait être la première à bénéficier de ces avancées dans la mesure où une molécule pourrait dorénavant être synthétisée pour un seul patient sans avoir à passer par la couteuse et fastidieuse récolte de données statistiques auprès de milliers de patients aux symptômes cliniques similaires.

Il est un problème particulier qui focalise aujourd’hui l’attention des spécialistes de l’IA comme ceux de DeepMind, c’est la quête d’une solution au problème du repliement des protéines [DMS]. Le comportement chimique d’une telle molécule, et donc son efficacité ou sa toxicité, dépendent non seulement de la séquence d’acides aminés (AA) qui la compose mais également de sa structure tridimensionnelle dans l’espace. Parvenir à déterminer cette structure géométrique à partir de la séquence constitue à ce jour l’un des Graal de la recherche biomédicale. Certains chercheurs supposent que des maladies neurodégénératives comme la maladie d’Alzheimer serait due à des molécules mal repliées que l’on appelle les prions.

Des modèles de repliement sont étudiés depuis belle lurette par les physiciens et par les mathématiciens. Ils ont en particulier démontré que ce problème est difficile dans un sens précis[13]. Pour le résoudre au moyen d’un algorithme de type AGZ, il s’agit de le reformuler comme un problème d’AR ce que proposent déjà plusieurs travaux [RLP].

Figure 8 : Repliement en deux dimensions d’un modèle simple de protéine. Les disques noirs représentent des acides aminés (AA) hydrophobes. Chaque couple d’AA qui sont adjacents sans être consécutifs, en vert, le long de la molécule apporte un gain d’énergie (une récompense) égal à -1 – source [RLP].

La figure 8 illustre un tel modèle où chaque disque noir représente un AA hydrophobe (H) et chaque disque blanc un AA hydrophile P. Chaque couple d’AA de type H qui sont adjacents sans pour autant être consécutifs le long de la chaine abaisse le bilan énergétique de la molécule d’une unité, on peut donc le concevoir comme une récompense. Dans la figure, cette énergie vaut -9.

Dès lors le problème du repliement s’énonce simplement : « Étant donnée une suite binaire « HHPPHHPHPPPH… » quelle est la configuration géométrique bi- ou tridimensionnelles qui réalise l’énergie la plus basse ? » On peut concevoir la recherche d’un tel optimum énergétique comme un problème d’AR si l’on image que l’on construit la protéine en ajoutant les AA l’un après l’autre sur un réseau à 2 ou 3 dimensions. Chaque couple d’AA de type H qui sont adjacents mais pas consécutifs se voit gratifié d’une récompense de +1 et on ne connaîtra le bilan énergétique de la protéine, qui est la somme de ces récompenses, qu’une fois le dernier AA posé.

Un symbole ?

Alors que la planète IT vit depuis des années dans le crédo du toujours plus de données (le fameux Big Data) et dans l’obésité du toujours plus de puissance de calcul (des GPU par centaines) AGZ vient démontrer à l’inverse le soft-power du progrès des algorithmes et d’une meilleure compréhension des problèmes d’apprentissage automatique. Non content d’être beaucoup plus puissant que tous ses compétiteurs humains ou artificiels, AGZ parvient à cette prouesse avec une puissance de calcul 44 fois moins importante que la version précédente et, ceci sans aucune donnée !

Avec un peu d’imagination et d’optimisme, peut-être peut-on y voir un symbole encourageant. L’ornière du « toujours plus » quantitatif dans laquelle s’engouffre notre civilisation n’est pas inéluctable après-tout. Des problèmes complexes, trouvent parfois des solutions élégantes, légères et efficaces au prix toutefois d’une certaine audace. L’audace en l’occurrence de remettre en question ce pragmatisme tant vanté qui, au nom d’une efficacité à court terme, renonce à chercher de bonnes solutions et se satisfait de solutions qui se contentent, comme la première version d’AlphaGo, de seulement faire l’affaire.

Notes

  1. Un jeu à somme nulle est un jeu où le gain total d’un joueur correspond exactement à la perte de son adversaire. Un jeu à information complète signifie que chaque joueurs connaît les coups qu’il peut jouer, les gains qu’il peut escompter et les motivations de son adversaire.
  2. Au jeu de Go, il y a environ 250 possibilités à chaque coup. Une partie pouvant comporter 150 coups on peut donc estimer grossièrement le nombre de parties possibles à 250 150 ≈ 10 360 !
  3. Cette section et surtout les 3 derniers paragraphes « Zoom sur… », assez techniques, s’adressent aux lecteurs qui souhaitent se faire une idée précise du fonctionnement de AGZ ou qui aimeraient avoir un pied à l’étrier pour étudier les articles originaux publiés par les chercheurs de DeepMind [AGL, AG0].
  4. Des mini-batch utilisés à chaque mise à jour des paramètres θ de la fonction fθ
  5. Ce sont les poids d’un réseau de convolution, voir le paragraphe suivant
  6. Au moyen d’une descente de gradient stochastique
  7. Une fois toutes les 1000 itérations de la descente de gradient qui optimise fθ
  8. Environ 400 jeux
  9. Sauf à essayer de prédire un jeu humain ce à quoi AGZ se refuse.
  10. Ce nombre de simulations vaut 1’600 dans AGZ.
  11. Plus précisément à N(st,a)ββ est un hyper-paramètre qui permet de régler la dispersion de la distribution  π(st,a) autour de son maximum amax. Lorsque β est grand cette dispersion est faible et les seuls coups a ayant des chances d’être sélectionnés sont ceux très proches de amax et on favorise l’exploitation. A l’inverse pour les petits β cette dispersion est importante et on favorise alors l’exploration.
  12. En réalité les règles du jeu de Go exige de connaître les positions des deux adversaires à l’instant t ainsi qu’aux 7 coups précédents, mais ceci ne change rien au caractère d’information complète du jeu. L’entrée du réseau est donc de taille 19 x 19 x 17, ou 17 = 2 x 8 (pour les positions des deux adversaires) + 1 (pour la couleur).
  13. Il s’agit d’un problème NP-complet ce qui signifie, en gros, que la découverte d’une solution efficace à ce problème, résoudrait du même coup toute une classe de problèmes difficiles, celle des problèmes NP.

Références

  • [AGL] Mastering the game of Go with deep neural networks and tree search, Silver, A. Huang, C.J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel & D. Hassabis, Nature 529, 484–489 – janvier 2016.
    www.nature.com/articles/nature16961
  • [AG0] Mastering the Game of Go without Human Knowledge, Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel & D. Hassabis, Nature 550, 354–359 – octobre 2017.
    www.nature.com/articles/nature24270
  • [SIN] Solve intelligence. Use it to make the world a better place
    com/about/
  • [TTO] Tic Tac Toe: Understanding the Minimax Algorithm, Never Stop Building – décembre 2013.
    neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13/
  • [VNE] Théorème du minimax de von Neumann, Wikipédia
    wikipedia.org/wiki/Théorème_du_minimax_de_von_Neumann
  • [RLI] Reinforcement Learning: An Introduction, S. Sutton and A.G. Barto, The MIT Press Cambridge, Massachusetts London, England.
    neuro.bstu.by/ai/RL-3.pdf
  • [HOM] Hands On Machine Learning with scikit-learn and TensorFlow, Aurélien Géron, O’Reilly Media – mars 2017.
  • [MAI] Le mécanisme d’attention en IA, Lemberger, IA Lab weave – janvier 2018.
    weave.eu/mecanisme-dattention-simple-astuce-mecanisme-universel/#cnn
  • [PFQ] Plus fort que le Big Data, le Small Data, Lemberger, IA Lab weave – septembre 2017.
    weave.eu/plus-fort-big-data-small-data/
  • [DRI] Deep Residual Learning for Image Recognition, He, X. Zhang, S. Ren, J. Sun, arXiv:1512.03385 [cs.CV] – décembre 2015.
  • [ELB] Emergence of Locomotion Behaviours in Rich Environments, N. HeessD. TBS. SriramJ. LemmonJ. MerelG. WayneY. TassaT. ErezZ. Wang M. Ali EslamiM. RiedmillerD. Silver, arXiv:1707.02286[cs.AI] – juillet 2017.
    www.youtube.com/watch?v=g59nSURxYgk&feature=youtu.be&t=1m27s
  • [WAG] What AlphaGo Zero Means for Artificial Intelligence Drug Discovery, S. Smith, BenchSci – octobre 2017.
    benchsci.com/alphago-zero-artificial-intelligence-drug-discovery
  • [RLP] A Reinforcement Learning Model for Solving the Folding Problem, G. Czibula, M.I. Bocicor and I.G. Czibula, J. Comp. Tech. Appl, 171-182.
    citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.375.8464&rep=rep1&type=pdf
  • [DMS] DeepMind’s Superpowerful AI Sets Its Sights on Drug Discovery, Kahn, Bloomberg Technology – octobre 2017.
    www.bloomberg.com/news/articles/2017-10-18/deepmind-s-superpowerful-ai-sets-its-sights-on-drug-discovery
  • [LEM] Un nouveau chantier pour la sécurité IT : le Machine Learning, section « le machine learning pour les nuls », Lemberger, IA Lab weave – août 2017.
    weave.eu/nouveau-chantier-securite-it-machine-learning/#sect_2
  • [MCT] Monte Carlo Tree Search (MCTS) Tutorial, YouTube Fullstack Academy – mai 2017.
    youtube.com/watch?v=Fbs4lnGLS8M
  • [TPU] Tensor processing unit, Wikipédia
    wikipedia.org/wiki/Tensor_processing_unit

 

L'Intelligence Artificielle,
au-delà des clichés

Livre blanc
Comprendre pour décider
Découvrez l'Intelligence Artificielle pour l'intégrer dès maintenant à vos enjeux stratégiques !
Téléchargez gratuitement

Les informations recueillies sur ce formulaire sont enregistrées dans un fichier informatisé de gestion des Clients et Prospects (CRM).

Le Responsable de traitement est la société weave, 37 rue du rocher 75008 Paris RCS Paris 802 396 085.

Elles sont destinées à l’activité marketing du groupe weave ainsi quà celle de ses filiales, à l’exclusion de tout transfert hors de l’UE. Elles sont conservées pour une durée conforme aux dispositions légales (par exemple 3 ans pour les données prospects).

Ce traitement nécessite votre consentement que vous pourrez retirer à tout moment sans que cela ne remette en cause sa licéité.

Conformément à la loi « Informatique et Libertés » et au règlement européen n°2016/679, vous bénéficiez d’un droit d’accès, de rectification ou d’effacement, ainsi que d’un droit à la portabilité de vos données ou de limitation du traitement. Vous pouvez également pour des raisons tenant à votre situation particulière, vous opposer au traitement de vos données et donner des directives relatives à la conservation, à l’effacement et à la communication de vos données après votre décès. Vous disposez également du droit d’introduire une réclamation auprès de la Commission Nationale de l’Informatique et des Libertés (www.cnil.fr).

Vous pouvez exercer vos droits en nous contactant à l’adresse contact@weave.eu.

En poursuivant votre navigation sur ce site, vous acceptez l’utilisation de cookies pour mesurer notre audience, vous proposer des contenus et des offres personnalisées, ainsi que des fonctionnalités de partage sur les réseaux sociaux. En savoir plus sur notre politique de cookies et notre charte des données personnelles