Le jour où la machine vainquit l'homme… au Jeopardy

Arnaud de la Grandière |


Les progrès de l'intelligence artificielle se mesurent à ses victoires emblématiques. La dernière en date jusqu'ici, la célèbre partie d'échecs qui vit le champion du monde - et accessoirement plus grand Maître de tous les temps - Gary Kasparov perdre face à Deep Blue, l'ordinateur taillé sur mesure par les soins d'IBM, en 1997 par deux manches contre une sur un total de six.

Big Blue était depuis à la recherche d'un nouveau défi pour surpasser sa dernière prouesse, et a fini par jeter son dévolu sur le fameux jeu télévisé Jeopardy. Ce jeu, toujours aussi populaire sur les écrans américains depuis 1964 (il connut une diffusion en France, présentée par Philippe Risoli, de 1988 à 1992 sur TF1), propose à ses participants des réponses auxquelles ils doivent trouver la question qui y correspond.

Pour cela, les candidats doivent tout d'abord choisir une catégorie sur les six proposées (dont l'intitulé peut tout autant leur donner un contexte que les troubler en fonction de sa formulation), et une mise parmi les cinq disponibles (de $200 à $1000), qui correspond à la difficulté de l'énigme. Le joueur qui a la main choisit donc la catégorie et la mise (chaque mise ne pouvant être tentée qu'une fois, jusqu'à ce que la grille soit vidée), le présentateur donne l'énoncé de la réponse, et chaque participant doit "buzzer" le plus vite pour donner la question qui correspond et emporter la mise, mais si le candidat donne une mauvaise réponse, il verra la mise en jeu déduite de sa cagnotte. Le joueur qui a amassé le plus d'argent une fois la grille vidée gagne la partie.


Si l'adaptation française de Jeopardy était quelque peu primesautière, la version américaine, héritière de son grand âge, est autrement plus sérieuse, difficile et respectée outre-Atlantique


Les énigmes font naturellement appel à la culture et aux vastes connaissances des candidats, mais la difficulté supplémentaire tient dans leur formulation, qui se base souvent sur des jeux de mots et des doubles sens. Autant de chausses trappes pour un ordinateur, sans compter qu'on peut interpréter un seul et même mot de bien des manières. Trouver la réponse dans les temps est un tour de force, comprendre une question en langage clair tient lieu de prodige, mais trouver la réponse dans les temps à une question posée de manière cryptique relève du petit miracle. Le tout, plus vite encore qu'un humain ne saurait le faire. Si Deep Blue a pu battre Kasparov en se reposant simplement sur sa formidable capacité de calcul pour prévoir tous les coups possibles sur l'échiquier, jusqu'à 20 degrés de profondeur, le langage est un champ autrement plus vaste que les 64 cases et 32 pièces du jeu d'échecs, dont les règles restent simples à maîtriser pour une machine.

skitched



Car comme pour son précédent défi, IBM a décidé de confronter son poulain, nommé Watson (d'après le nom du fondateur de la société), aux plus grands champions du jeu télévisé, dans un match retransmis sur CBS. Concrètement, l'énigme est envoyée à Watson sous forme électronique (il n'a donc pas à faire de la reconnaissance vocale ou visuelle, à l'inverse des participants humains), dès que l'énoncé apparaît sur l'écran. D'autre part, l'équipe d'IBM a dû constituer une énorme base de données locale pour fournir le savoir à Watson : interdiction d'utiliser Internet (ce qui n'aurait de toute façon fait que le ralentir). La base de données, incluant des millions de documents (archives du New York Times, la Bible…), dictionnaires, thesaurus, encyclopédies (y compris l'intégralité de Wikipedia et l'Internet Movie Database), occupe quatre téra-octets sur ses disques durs.

Il reste tout de même à Watson à isoler les termes signifiants de l'énigme, et par croisement d'associations trouver la question qui y correspond. Pour ce faire, il lance simultanément plusieurs milliers d'algorithmes éprouvés en matière d'analyse du langage, chacun fournissant une réponse. Celles qui sont le plus fréquemment retournées sont alors confrontées à la base de données pour s'assurer de leur validité, et classées par degré de probabilité. Lorsqu'une solution dépasse un seuil de confiance donné, Watson "buzze", et donne sa réponse à haute et intelligible voix.

Watson a plus d'un avantage sur ses adversaires organiques : ses réflexes sont imparables. Une fois la décision prise de donner la réponse, le buzzer retentit instantanément, alors que les réflexes humains doivent composer avec une latence qui se compte en dizaines de millisecondes. Il reste également de marbre face aux tactiques psychologiques de ses adversaires. Mais à l'inverse, Watson ne tentera sa chance que s'il a trouvé une réponse avec un taux de probabilité suffisant, ce dont les humains peuvent se passer. Ils peuvent également anticiper le moment de buzzer pour rattraper leur handicap en termes de rapidité. D'autre part, Watson, n'entendant pas les réponses des autres participants au jeu, il est tout à fait susceptible de donner une mauvaise réponse qui vient tout juste d'être invalidée par un autre candidat.

Néanmoins pour en arriver là il aura fallu quatre ans de dur labeur. Pour que Watson puisse avoir une chance de gagner face aux meilleurs champions, il lui fallait donner un taux de bonnes réponses supérieur à 85 % en moins de trois secondes et demie, et le logiciel en était bien loin aux tout débuts du projet. Pour donner une mesure des avancées réalisées, Piquant, le prédécesseur de Watson, prenait plusieurs minutes pour ne donner que 35 % de bonnes réponses.

Un élément déterminant du code de Watson fut l'apprentissage par la machine : au lieu de définir des règles une par une, on présente des exemples au programme en lui indiquant leurs valeurs. Pour donner un cas concret, la reconnaissance optique de caractères ne se "programme" pas en définissant les caractéristiques de chaque lettre, qui peuvent varier infiniment d'une police ou d'une écriture à l'autre. A l'inverse, on présente au programme une kyrielle de cas différents en lui indiquant la bonne réponse : le programme cherche, et finit par déterminer les caractéristiques propres à chaque lettre : il devient capable de les reconnaître sous des formes qu'il n'avait pas rencontrées précédemment.

Sans%20titre


C'est le même type de programme qui vous fait des suggestions sur iTunes ou Amazon en fonction de votre historique d'achats, croisé avec ceux de milliers d'autres utilisateurs qui sont susceptibles de partager vos goûts. De la même manière, Watson a ingurgité des milliers d'énigmes du Jeopardy, accompagnées de leurs solutions, et du chaos est né l'ordre : Watson a stocké des associations, un peu à la manière dont notre cerveau crée des connexions synaptiques avec l'expérience. C'est grâce à cet apprentissage par la machine que Watson a pu déterminer les éléments prépondérants dans la formulation si typique du Jeopardy, pour en isoler les termes discriminants.

Mais si les bonnes réponses de Watson font souvent frémir de par leur implacable précision, à l'inverse les erreurs désarmantes qu'il peut parfois commettre prêtent souvent à rire. Watson n'est pas doué du sens commun que nous avons tous : pour lui les réponses n'ont qu'une valeur statistique, et rien ne lui indique que Richard Nixon ne peut résolument pas être une "first lady", à moins qu'on ne lui précise ce genre de subtilités. Ces "bugs" seront parfois retors à élucider, à l'image de l'exaspération qu'un parent peut ressentir face à son enfant si ce dernier ne cesse de répondre "pourquoi ?" à l'explication qui précède.

Un dernier élément qui permettra à Watson de rejoindre les meilleurs joueurs aura été de lui faire savoir la bonne réponse à l'énigme précédente, ce qui lui permet d'interpréter le thème (parfois trompeur tant qu'aucun exemple n'a été donné), et ce qui le rend plus susceptible de mieux répondre à l'énigme suivante, comme c'est également le cas pour les autres joueurs.

Le match en deux manches gagnantes a mis Watson face aux plus redoutables opposants : Ken Jennings, détenteur du record du plus grand nombre de victoires consécutives au Jeopardy (74), et Brad Rutter, gagnant du plus gros pactole au jeu. Le premier match, diffusé le 14 février, fut sans appel : $4.800 pour Jennings, $10.400 pour Rutter, et $35.734 pour Watson, grâce notamment à deux bonnes réponses aux questions bonus qui rapportaient plus d'argent. Bien que Watson fut mené durant la seconde manche, il finit tout de même par la remporter avec $77.147, devant Jennings avec $24.000 et Rutter avec $21.600.
Sur les 94 réponses que Watson a donné, il ne s'est trompé que neuf fois (soit 10 %). Le programme s'est abstenu de répondre à 26 occasions, n'étant pas assez sûr de lui pour tenter sa chance (il avait pourtant la bonne réponse dans 5 de ces cas, soit 19,2 %). En somme, Watson souffre d'un petit déficit de confiance en lui-même, et aurait probablement plus de chances de gagner en prenant un peu plus de risques. Watson remporte un million de dollars, qu'IBM a reversé à des œuvres caritatives.

L'ironie du sort, c'est que c'est précisément Ken Jennings qui aura été l'inspiration pour IBM : lors d'un dîner avec des collègues en 2004, Charles Lickel, manager de la recherche chez IBM alors en quête d'un nouveau défi après la victoire contre Kasparov, remarque que le restaurant devient soudainement silencieux : Ken Jennings était alors au milieu de ses 74 victoires consécutives au jeu télévisé, attirant l'attention de tous les convives en plein repas lors de la retransmission sur les écrans du restaurant. C'est ainsi que Charles Lickel eut l'idée du formidable défi pour les ingénieurs d'IBM, qui fut relevé par Dave Ferrucci et son équipe d'une vingtaine d'ingénieurs. Ceux-ci n'ont d'ailleurs pas manqué de faire savoir à Ken Jennings qu'il y avait "beaucoup de lui en Watson". Bill Atkinson, inspiré par les prouesses de Watson, imagine un avenir où de tels assistants pourraient nous venir en aide au quotidien (lire Bill Atkinson inspiré par un IA très joueuse).

Mais au-delà de la brillante prouesse, Watson aura bel et bien des applications pratiques. Dans les milieux professionnels, un tel logiciel pourra fouiller dans des téra-octets de données pour apporter instantanément la réponse à une requête en langage clair. De même, des domaines où les innombrables connaissances sont constamment mises à jour, comme le support technique, la recherche juridique ou la médecine, pourront bénéficier d'une aide décisionnelle précieuse. IBM est déjà à pied d'œuvre, se donnant 18 à 24 mois pour proposer un produit exploitable commercialement pour l'aide au diagnostic et au traitement des patients. Les coûts d'équipement le réservent pour l'heure aux plus grosses sociétés : il en coûte un million de dollars pour le serveur doté de 2800 processeurs Power 750, et plusieurs millions pour le logiciel (Eric Nyberg, professeur en sciences informatiques à l'université de Carnegie Mellon, estime que Watson a coûté jusqu'à 100 millions de dollars à IBM, d'autres parlent même d'un à deux milliards). Big Blue escompte que le prix deviendra plus accessible d'ici la fin de la décennie, avec l'amélioration de la technologie.



image : IBM Research

Tags
#IBM
avatar Garzak | 
Je suis le seul à y voir le moteur de recherche qui risque de faire pleurer google très bientôt?
avatar Raoul99 | 
Faut vraiment rien comprendre à la beauté des échecs pour hiérarchiser de manière aussi sommaire des artistes comme B Fischer, A Karpov ou G Kasparov. C'est pas des vaches au concours agricole ! Mais bon, c'est tellement chic de dire que Fischer était un génie. Évidement lui aurait gagné aux échecs contre Deepblue et à geopardy contre Watson !
avatar Nao 76230 | 
Je suis le seul à avoir relevé ? "La base de données, incluant des millions de documents (archives du New York Times, la Bible…), dictionnaires, thesaurus, encyclopédies (y compris l'intégralité de Wikipedia et l'Internet Movie Database), occupe [b]quatre téra-octets[/b] sur ses disques durs."
avatar florentmair | 
Tiens je pensais que watson utilisait des BlueGene à la place de P750
avatar Raoul99 | 
Quand à comparer les joueurs sous l'angle de leur apport à la "théorie" des ouvertures, Fischer lui-même avait répondu en inventant les échecs 360. Après reste les classements subjectif, Fischer a donné celui-la en 1964 : Morphy, Staunton, Steinitz, Tarrasch, Chigorin, Alekhine, etc.
avatar Timekeeper | 
Mais putain, un vidéodisque quoi !
avatar Manueel | 
Merci pour ce superbe article qui remet bien les choses à l'heure : Pas un soupçon d'intelligence dans cette machine mais de puissants algorithmes qui permettent de tomber juste de manière statistiquement très satisfaisante Bref un outil puissant qui probablement un jour nous servira de moteur de recherche
avatar Anonyme (non vérifié) | 
@Gibet-b Je force un peu le trait, il est vrai. :D Mais le "de tous les temps" est de trop. Kasparov est un très grand champion. Il fut un compétiteur exceptionnel. L'auteur de parties extraordinaires et l'opposition de style avec Karpov fut un temps merveilleuse. Etudiez les matchs de Moscou (1985) et Leningrad (1986), c'est superbe ! Le meilleur joueur de son époque, sans discussion. Je reste avec un goût très amer du championnat de 1990, une partie à Lyon qu'il ne gagna qu'après deux ajournements. Il était clair qu'il était incapable de trouver seul la faille. Sa préparation et la réintroduction de l'ouverture écossaise a fait sensation sur le coup, mais après ? Qu'il ait encore quelques munitions sans doute, tous en ont, mais combien résisteront à l'analyse ? Une base de donnée ? C'est ce genre de trucs qui ont tué le jeu à force. Les joueurs sont devenus des imitations improbables d'ordinateurs. @Raoul99 : je ne parle pas de théorie des ouvertures mais théorie des échecs. Gibet_b a compris à quoi je faisais allusion en citant ces noms. Ce ne sont pas tant des joueurs que des penseurs des échecs, des stylistes aussi. Booby Fischer était un grand styliste des échecs. Kasparov aurait pu, aurait du aussi marquer le jeu de son empreinte. Les premières années de son règne le laissaient entrevoir. La suite est une lente dégradation avec parfois des éclats de génie (au tournoi de Linarès notamment) . La faute sans doute aux circonstances : les matchs à répétition contre Karpov, le conflit politique contre la FIDE, la fin de l'URSS, la relative faiblesse de l'opposition jusqu'à l'avènement d'une génération plus jeune. A mon sens, Kasparov a marqué le monde des échecs de son empreinte mais il n'a pas marqué le jeu. Le match avec Deep Blue était une supercherie. Je maintiens que c'est du Barnum et qu'il aurait du porter un nez de clown pour jouer. Mais bon, ce genre d'exhibition a toujours existé aux échecs - $ Maintenant, je n'ai pas caché mon scepticisme devant l'idée d'un classement (même le Elo ne signifie pas grand chose sur la durée). A chaque très grand maître correspond un temps, une époque. C'est très difficilement comparable.
avatar bugman | 
En attendant je ne bas toujours pas ce fi** de p*** d'Hiarcs ! :/
avatar Raoul99 | 
@ Arnaud B Fischer n'était pas un styliste, c'était un combatant, comme G Kasparov. Seule la victoire l'intéressait, "la destruction du moi de mon adversaire" disait-il. Son style était ultra-efficace, il se caractérisait notamment par une maitrise parfaite des simplifications et de la fin de partie, en cela il se rapproche de Capablanca. Ce sont évidement des modeles pour la conduite de la partie et pour l'économie des moyens utilisés pour parvenir à la victoire. Fischer n'était pas un théoricien, pas plus que ne l'était Capablanca ou Alekhine. Steinitz ou Nimzovitch ont révolutionné en leurs temps la concéption de la partie d'échec, pas Capablanca ou Fischer.
avatar hawker | 
@ Garzak loooooool trop bien vu. c'est vrai que l'investissment pour ce system doit trouver la reponse dans un moteur de recherche du futur...
avatar Anonyme (non vérifié) | 
Il faudrait savoir, vous dites dans un premier temps qu'il n'était pas un styliste mais ensuite vous décrivez "son style". ;-) La recherche de la victoire est le but même de la partie. Si vous ne vous préoccupez pas de gagner ou de perdre ne vous asseyez pas devant les 64 cases... ou devenez problémiste. Mais on ne saurait réduire le style de Fischer à cela. Son jeu était "ultra-efficace" parce que complet, "universel" écrit Elie Agur. Fischer vivait pour les échecs. Vous dites qu'il se rapproche de Capablanca (en partie seulement) et celui-ci est sans doute le plus grand styliste que les échecs aient connu. Il y a les "penseurs" tels que Steinitz, Réti, Nimzowitsch, et dans une moindre mesure Tarrash et Tartacover. Il y a les "praticiens" tels que Lasker, Capablanca et Alekhine. Si les premiers se sont évertués à construire des systèmes, les seconds ont laissé une science du jeu, en dehors de tout dogme, dont se sont inspirés les générations suivantes. Aux échecs, la somme théorique est constituée des parties et de leurs analyses. Fischer devait beaucoup à l'étude des parties d'Alekhine. Quant à penser les échecs, il s'y est aussi attelé et a laissé une cadence qui porte son nom. Mais encore une fois, j'ai opposé la figure de Fischer à celle de Kasparov à cause du "de tous les temps". On pourrait opposer pareillement celle de Capablanca à Fischer, cette de Morphy à Capablanca, etc. A chaque époque son champion. Anand est bien le champion d'aujourd'hui et ce n'est pas un compliment pour les échecs contemporains.
avatar Arnaud de la Grandière | 
dites, les historiens des échecs, c'est passionnant et tout, mais complètement hors sujet. Je suggère de faire suivre le débat ici : http://listverse.com/2009/09/06/top-10-greatest-chess-players-in-history/ en appuyant votre réflexion sur ceci : http://en.wikipedia.org/wiki/Methods_for_comparing_top_chess_players_throughout_history
avatar apreslapluie | 
En attendant c'est pas très ecolo leur machine ;)
avatar marc_os | 
@ Manueel : Relis par exemple la partie.sur la reconnaissance des caractères. L'IA n'en est plus à "simplement" appliquer des règles prédéfinies. Elle permet aussi a la machine d'apprendre, càd trouver de nouvelles associations et au final reconnaitre des formes de lettres qu'elle n'avait jamais vue ! En tous cas, chapeau bas aux ingénieurs d'IBM !

Pages

CONNEXION UTILISATEUR