Article publié sur le site Contrepoints :

https://www.contrepoints.org/2016/02/25/240449-intelligence-artificielle-lenigme-des-cent-chapeaux

Il ne se passe pas une semaine sans que la presse internationale ne relaie les exploits et les réussites des algorithmes, de l'intelligence artificielle et des réseaux de neurones. La société Google DeepMind, basée à Londres, vient ainsi d'obtenir une très belle victoire au jeu de Go contre le champion européen Fan Hui (en cinq matchs à zéro), à l'aide du programme AlphaGo, s'appuyant sur des processus d'apprentissage (machine learning). Le jeu de Go constituait jusqu'à présent un défi de taille pour les équipe de R&D en intelligence artificielle (IA) avec un espace des déplacements possibles beaucoup plus important que pour le jeu d'échec (10 puissance 359 pour le Go contre seulement 10 puissance 123 pour les échecs). AlphaGo doit maintenant se mesurer à des champions de niveau supérieur et rien ne dit que la prochaine victoire sera aussi facile à obtenir...

Google DeepMind choisit très justement de s'attaquer à des problèmes classiques, connus du grand public, et de les traiter par ses algorithmes d'apprentissage et ses réseaux de neurones. Il s'agit là d'une stratégie efficace et rentable en terme de communication. Les succès de son IA sur des jeux ou des énigmes célèbres (qui échappaient jusqu'à présent au traitement algorithmique) sont immédiatement relayés au niveau mondial et chacun peut dès lors mesurer simplement la performance établie. Cette fois, c'est sur l'énigme des cent chapeaux que la filiale de Google vient d'enregistrer une avancée importante. Son programme, combinant l'apprentissage automatisé et une approche multi-agent, vient de résoudre (partiellement) cette célèbre énigme.

Avant de revenir sur la performance de l'équipe de chercheurs de DeepMind, il convient de rappeler l'énoncé de l'énigme. Le lecteur peut facilement transformer son énoncé sans dénaturer le problème s'il juge l'histoire sous-jacente un peu trop violente dans le contexte actuel. Pour l'anecdote, on notera que l'énigme des cents chapeaux est régulièrement posée aux candidats lors des entretiens d'embauche de la banque d'affaire Goldman Sachs mais également durant les entretiens de recrutement de... Google !

1 - L'énigme des 100 chapeaux.

Un bourreau aligne 100 prisonniers dans une file unique et place un chapeau rouge ou bleu sur la tête de chacun des prisonniers. Chaque prisonnier peut voir les chapeaux des personnes situées devant lui dans la file, mais il ne peut pas voir son propre chapeau, ni celui des personnes situées derrière lui. Le nombre de chapeaux rouges ou bleus présents dans la file est inconnu. Le bourreau commence sa macabre besogne par la fin de la file. Il demande au dernier prisonnier la couleur de son chapeau. Le prisonnier interrogé doit répondre "rouge" ou "bleu". S'il répond correctement, il vit. Si au contraire il donne la mauvaise réponse, il est abattu immédiatement et en silence sans que les autres prisonniers ne le sachent. Chacun entend la réponse du prisonnier interrogé, mais personne ne sait si elle était juste ou fausse. Le bourreau continue ainsi pour chaque prisonnier en remontant du dernier de la file jusqu'au premier. La nuit précédant l'exécution, les prisonniers ont eu le droit de se concerter afin de décider d'une stratégie commune optimale.

Question : En adoptant cette meilleure stratégie, combien de prisonniers, au maximum, peuvent être sauvés à coup sûr ?

Afin de ne pas "spoiler" l'énigme, le lecteur est invité à stopper la lecture de l'article à ce niveau ou à passer la partie 2 pour réfléchir à la meilleure stratégie. Une fois qu'il a déterminé le nombre de prisonniers sauvés par sa stratégie, il peut alors revenir à la partie 2 qui lui fournit la solution optimale.

2 - La solution de l'énigme des 100 chapeaux

Une fois le contexte bien compris, on commence assez naturellement par imaginer que le dernier prisonnier (le centième et premier interrogé) a une chance sur deux de rester en vie et qu'il s'agit pour lui d'une simple épreuve de pile ou face. Il doit donc choisir entre Rouge ou Bleu et peut décider de sauver le prisonnier suivant en révélant la couleur du chapeau qu'il voit devant lui. En procédant ainsi, il sauve le 99 ème prisonnier qui une fois interrogé va donner la bonne couleur de son chapeau mais ne va pas sauver le 98 ème. En itérant le processus, le 98 ème prisonnier donne la couleur du chapeau du 97 ème et le sauve. Cette stratégie élémentaire ne sauve finalement qu'un prisonnier sur deux et laisse l'autre moitié entre les mains d'un choix au hasard de type pile ou face. Comme on peut s'y attendre, cette première stratégie n'est pas la meilleure. On peut faire beaucoup mieux. Il est possible de sauver 99 prisonniers de manière certaine sur les 100 ; le centième prisonnier étant quoi qu'il arrive soumis au premier choix aléatoire avec une probabilité égale à un demi d'être sauvé.

La stratégie optimale consiste alors à utiliser la parité du nombre de chapeaux rouges (par exemple) devant soit. Le centième prisonnier commence ainsi par compter le nombre de chapeaux rouges devant lui puis annonce "rouge" si ce nombre est pair et "bleu" s'il est impair. Le 99 ème prisonnier compte à son tour le nombre de chapeaux rouges devant lui. Si ce nombre a la même parité que précédemment, alors ceci signifie que son chapeau est bleu car il n'a pas modifié le total des chapeaux rouges. Si la parité est différente, ceci signifie que son chapeau est rouge. Les prisonniers suivants procèdent de la même façon. Cette stratégie permet de sauver tous les prisonniers du 99 ème au premier. Le centième a quant à lui une chance sur deux de s'en sortir vivant. C'est la meilleure stratégie possible sur ce problème.

3 - L'approche des algorithmes de Google DeepMind

Les chercheurs de Google DeepMind et d'Oxford ont publié un article décrivant la démarche algorithmique et les résultats obtenus sur l'énigme des chapeaux.

http://arxiv.org/pdf/1602.02672.pdf

Le groupe de chercheurs a développé un réseau DDRQN (Deep Distributed Recurrent Q-Networks) composés d'agents (les prisonniers) capables d'apprendre à communiquer entre eux sans pré-requis particulier, dans le but de résoudre collectivement un problème donné. Les réseaux DDRQN exploitent la dynamique des systèmes multi-agents dans lesquels les agents établissent un protocole de communication puis collaborent dans la résolution du problème tout en apprenant de leurs expériences. Un réseau de neurones participe à la composante d'apprentissage non supervisé du réseau DDRQN. Les tests de ce réseau ont été réalisés sur plusieurs énigmes dont celle des cent prisonniers et les résultats obtenus ont vite dépassé les attentes initiales de l'équipe de recherche. Les agents du réseau ont construit leur propre protocole de communication puis ont élaboré des stratégies émergentes afin de résoudre l'énigme (c'est-à-dire maximiser le nombre de prisonniers épargnés par le bourreau). Les solutions émergeant du réseau DDRQN se sont avérées parfois très différentes de celles issues d'une réflexion humaine "biologique". Les chercheurs de DeepMind éprouvent d'ailleurs encore quelques difficultés à expliquer complètement certaines des stratégies construites par le système alors que celles-ci sont presque optimales... Le réseau DDRQN fait ainsi émerger des solutions "exotiques" issues de la communication et de la coopération entre agents. On se situe dans le "cœur du réacteur" d'une future intelligence artificielle forte capable d'innover et d'engendrer des solutions inédites pour un problème donné !

4 - Derrière les énigmes, des enjeux stratégiques

Au delà de la simple résolution d'énigme, les applications industrielles des réseaux DDRQN sont nombreuses notamment en robotique civile et militaire. Un groupe d'agents robots capables d'apprendre à communiquer pour élaborer une stratégie de coopération et résoudre collectivement un problème, constitue une réelle avancée algorithmique et technologique. En 2015, les équipes de R&D de Google DeepMind avaient déjà développé un système s'appuyant sur des réseaux de neurones capables d'apprendre à jouer à une cinquantaine de jeux vidéo d'arcade Atari 2600 en "observant" simplement les différentes parties jouées par des humains. Après la phase d'apprentissage, le système était en mesure d'affronter seul les meilleurs joueurs et de les battre systématiquement...

Derrière cette succession de petites victoires algorithmiques, c'est bien le niveau global d'intelligence artificielle qui progresse à grande vitesse. Les enjeux du Deep Learning sont réellement stratégiques. Les géants Google, Facebook et Amazon investissent aujourd'hui massivement dans des programmes de recherche sur l'apprentissage profond non supervisé et sur la reconnaissance automatisée d'objets dans une image. L'Europe, pour une fois, se situe aux avants postes de l'innovation mondiale en intelligence artificielle puisque c'est à Londres que sont installés les laboratoires de Google DeepMind. Paris accueille quant à elle depuis un an le FAIR (Facebook AI Research) qui constitue un autre fleuron mondial de la R&D en IA.

http://deepmind.com/

https://research.facebook.com/ai

« How old do I look ? » est la question à laquelle un système de machine learning biométrique développé par Microsoft se propose de répondre. Il suffit de charger la photo de votre choix et l'application calcule presque instantanément votre âge apparent et détermine votre genre. On se prend vite au jeu avec les photos de ses proches, de ses amis et celles de personnalités. En testant l'application avec deux photos prises à deux mois d'intervalle, l'écart d'évaluation peut dépasser les dix ans ! Ainsi, pour la photo standard figurant sur mon blog, l'application m'a gratifié d'un généreux 37 ans en se trompant de 11 ans alors qu'avec une autre photo prise à la même date, j'ai soudainement pris dix ans de plus, me ramenant à une cruelle réalité. Globalement, le système fonctionne assez bien. Je conseille de réaliser une quinzaine de tests pour constater que les algorithmes de machine learning ont le coup d’œil.

Alors, êtes-vous prêt(e) à confronter votre image à la machine ??

http://how-old.net/#

Il faut lire également l'article décrivant l'effet viral imprévu déclenché à la mise en ligne de l'application :

http://blogs.technet.com/b/machinelearning/archive/2015/04/29/fun-with-ml-stream-analytics-and-powerbi-observing-virality-in-real-time.aspx

Deux calculs réalisés sur des personnalités américaines particulièrement préoccupées par le vieillissement :

Ray Kurzweil, né en 1948 : sous-estimation de 17 ans !!

Natascha Vita-More, née en 1950 : sous-estimation de 34 ans... BRAVO Natascha, vous avez mystifié le bot  !