Douglas Lenat : le maître de l'heuristique

A la frontière de l'I.A. l'heuristique représente une branche prometteuse pour l'avenir des systèmes experts. Inspirée du comportement humain, elle a trés tôt fasciné les premiers chercheurs en I.A. Son but ultime ? Rendre les systèmes experts intelligents et indépendants de leurs créateurs, en leur permettant de "naviguer" en univers incertain. Nous voilà proche d'une création de démiurge.

Inspirée des recherches en psychologie expérimentale, l'heuristique concerne l'art d'apprendre à apprendre. On pourrait la résumer en précisant son but : elle tend à la découverte. Chercheur en mathématiques pures, puis en physique fondamentale, Douglas B. Lenat s'est orienté vers l'intelligence artificielle en 1971, pour échapper au désespoir de n'être ni Galilée, ni Newton, ni Einstein : "il devint clair que je ne serais jamais le meilleur mathématicien du monde, et je trouvais cela très déprimant. En ce qui concerne la physique, j'étais particulièrement intéressé par les hautes énergies, l'astrophysique, et la relativité générale. Je suis allé assez loin dans chacun de ces domaines pour comprendre, à chaque fois, à quel point chacune de ces activités devenait mathématique et stylisée. C'était un jeu sans fin dont la carte routière se dépliait à l'infini".

Si la recherche pure atteignait des sommets d'abstractions "devenant si pures et si raréfiées qu'elles semblaient perdre le contact avec le réel (perdre toute pertinence)", pourquoi dés lors Lenat ne se serait-il pas interrogé sur les modalités de la découverte elle-même ? En se consacrant à l'heuristique, son haut pouvoir d'abstraction lui a valu une approche nouvelle de l' I.A. Le programme A.M. (Automated Mathematician), qui constitue sa thèse de doctorat, a rapidement été considérée comme une des pierres angulaires de l'intelligence artificielle.

En raison de ses aspects philosophiques et métaphysiques (si une machine peut apprendre par elle-même, alors qu'est-ce que la vie, qu'est-ce que l'intelligence et qu'est-ce que l'homme ?) l'heuristique a très tôt fasciné les chercheurs en intelligence artificielle, notamment Newell et Simon dans leur fameux [Human Solving Problem], publié en 1972. Ils ont patiemment observé des sujets humains en train de résoudre des problèmes tout en exprimant à haute voix tout ce qui leur passait par la tête (y compris les onomatopées). Après plusieurs centaines d'heures d'études et d'analyses, Herbert Simon (devenu en 1978 prix Nobel d'économie) en est venu à la conclusion que le comportement humain est un processus tout à fait simple "qu'il implique la résolution de problèmes comme les cannibales et les missionaires, ou la réalisation d'une importante découverte scientifique" (Machinery of the Mind, George Johnson, Times Book 1986).

Au début des années 60, Adrian de Groot mit en évidence que la différence entre des joueurs d'échecs normaux et des grands maîtres ne résidait pas dans la valeur intrinsèque de leur mémoire, mais plutôt dans leur aptitude à reconnaître des formes et des structures déjà connues. A partir de là, l'intelligence artificielle pouvait prendre deux directions. La première, illustrée par le programme Bacon (P. Langley, G. Bradshaw, et H. Simon), consiste à partir de données pour établir des raisonnements fondés sur l'observation et remontant ainsi à des lois générales (Bacon est "data driven").

La seconde approche, choisie par D.B. Lenat  consiste à jouer sur les niveaux de conceptualisation. Il est "theory driven". Pour utiliser le jargon des programmeurs anglo-saxons, Bacon suit une démarche inductive (bottom upø, tandis qu'Eurisko adopte une approche essentiellement déductive ("top down"). Dans les deux cas, bien sûr, les programmes appuient leurs raisonnements sur des données concrètes. Mais alors que Bacon utilise des données qui lui sont fournies au départ, pour bâtir des théories (Bacon redécouvre la loi d'Ohm, la troisième loi de Kepler, la notion de poids atomique et moléculaire, etc.), Eurisko au contraire part d'un ensemble de postulats et de règles qu'il utilise pour en produire d'autres. A cette fin, il génère lui-même les données qu'il utilisera, comme un explorateur qui façonne ses propres outils, qui prépare son propre matériel d'expédition.

En arrivant à Stanford, en 1972, Lenat souhaitait réaliser des programmes qui échapperaient à la logique pure, domaine qu'il connaissait bien, pour s'attaquer à un comportement plus humain, plus exploratoire, plus apte à réaliser l'imprévu. Après quelque temps passé à réaliser des générateurs de programmes, en compagnie de Cordell Green, Lenat eut l'intuition que le vrai problème consistait à "capturer un peu de l'art du programmeur". Edward Feigenbaum présente AM de la façon suivante : "sa structure primaire de connaissance est une hiérarchie de concepts et de propriétés (ou slots) liées à ces concepts, ...qui est un exemple presque parfait de ce que Minsky appelle des cadres ("frames")... des règles de production et des procédures sont attachées à chaque cadre conceptuel". Dans ce schéma, un concept est, ou n'est pas intéressant.

Des règles de production vont donc décider des critères selon lesquels les résultats obtenus méritent d'être poursuivis par d'autres analyses. Cela crée un "méta niveau", et ultérieurement, le système deviendra capable de modifier les règles selon lesquelles il prend des décisions. Ainsi, AM est un des tout premiers programmes à être capable de s'automodifier : de quoi réjouir profondément Douglas Hofstadter qui aborde le sujet dans son justement fameux [G|del, Escher, Bach ](Prix Pullitzer 1979, traduit par Inter-Edition en 1985). AM utilise  des mécanismes de contrôle et de pondération qui lui permettent de gérer son temps-machine, afin de ne pas le gâcher en travaux sans intérêt. Comment juger de l'intérêt d'un travail en cours ? Peut-être est-ce là le coeur du problème.

Lenat utilise des heuristiques sur des heuristiques, en attendant d'aller encore un niveau plus haut. Voici un exemple de méta-niveau : "un concept est intéressant s'il est, accidentellement, la limite précise (ou le cas extréme) d'un autre concept intéressant". Une des difficultés rencontrées réside dans la génération d'exemples. Par exemple, AM a découvert des concepts d'un intérêt apparemment somptueux, mais pour lesquels il ne réussissait pas à trouver d'exemples (sauf un !) ! Il s'est ainsi efforcé longuement de découvrir des exemples pour les notions fascinantes "d'ensemble des nombres premiers pairs" ou "d'ensemble des nombre ne possédant qu'un seul diviseur" !!!

Afin d'améliorer les heuristiques conduisant à des impasses, AM garde trace de ses travaux et possède des capacités d'auto-explication. Ces dernières ne sont pas forcément claires, notamment lorsqu'il tente d'expliquer sa fascination pour les ensembles vides, pour la seule raison qu'ils présentent l'extraordinaire caractéristique d'être égaux entre eux, ou encore qu'il réalise des boucles aveugles en composant des règles sur elles-mêmes, un peu comme un simple d'esprit qui laisse tomber des cailloux parce qu'il peut ensuite les ramasser et recommencer. Ces défauts sont presque aussi intéressants que les réussites d'AM, en ce sens qu'elles permettent d'introduire de nouvelles heuristiques, qui sont autant de garde-fou.

Ces dernières cependant se doivent de ne pas hypothèquer la valeur de l'ensemble, en éradiquant des recherches prometteuses. Par exemple, Lenat s'est montré très irrité avant qu'AM ne découvre la conjecture de Ramanujan, parce qu'il estimait que cette voie ne menait à rien. Une heuristique qui se contente de dire qu'on peut "poursuivre un travail non immédiatement productif, mais par pour trop longtemps" peut en effet se révéler aussi dangereuse qu'utile, si elle n'est pas également pondérée par d'autres éléments (coefficients d'intérêt, autres heuristiques).

Le problème pour Lenat et son équipe consiste également à trouver des articulations souples entre les différentes parties composant AM. AM génère des listes de problèmes "intéressants", et les traite dans l'ordre de leur importance supposée. Ainsi, "un concept n'est pas intéressant si, après plusieurs tentatives, seuls deux exemples ont été trouvés. Pour débuter, le système se voit attribuer un ensemble de concepts de base (une centaine), qui constituent son intelligence du monde. A lui de se débrouiller pour les faire fructifier... Il dispose d'outils : une vaste gamme d'heuristique lui serviront à faire bourgeonner ses connaissances. Le but d'AM consiste donc à "développer de nouveaux concepts, guidé par un large ensemble de 250 règles heuristiques...

A partir de là, il va définir un nouveau concept, ou explorer quelques facettes d'un concept existant, ou examiner un ensemble de données empiriques pour y rechercher des régularités. Ainsi, AM étend sa base de connaissance, redécouvrant pour finir des centaines de concepts tels que nombres premiers, ou théorèmes (conjecture de Goldbach)." (cf Knowledge-Based Systems in Artificial Intelligence, Randall Davis et Douglas B. Lenat,Mac Graw-Hill 1982) . Dans AM, les heuristiques fonctionnent de trois façon : elles suggèrent de nouvelles tâches et les ajoutent à l'agenda (sous-programme de communication gérant la priorité des tâches) après leur avoir attribué un coefficient d'intérêt. Elles créent de nouveaux concepts et vérifient leur intérêt, explorent ces nouveaux concepts pour leur trouver de nouvelles facettes, de nouveaux aspects, de nouvelles corrélations avec d'autres concepts existant.

Ainsi, un concept est intéressant si .... Et le "si" peut très bien surgir beaucoup plus tard. Le programme va donc se promener à travers un monde qui se complexifie à mesure que le temps passe. Chose amusante, le programme devient parfois fou, à force d'auto-satisfaction. Utilisant des coefficients d'intérêt, et pouvant éventuellement dialoguer avec son auteur (et avec les élèves de son auteur), AM attribue en effet les découvertes d'un concept soit à lui-même, soit à la personne qui a introduit un nouveau concept. Il boucle parfois sur lui-même, renvoyant  ses concepts de l'un à l'autre, augmentant leur valeur à chaque passage.

Lenat n'a pas trouvé si facile la tâche de l'amener à renoncer à ses errances. Car comment définir à partir de quel moment une recherche devient inutile ou redondante ? Sans trahir aucun secret, on peut supposer que c'est précisément ce genre de jonglerie qui motive Douglas B. Lenat, et le conduit à passer des nuits blanches devant ses machines. Parmi les idées proposées par AM, deux sont totalement inattendues. AM définit l'ensemble des nombres possédant un nombre "excessivement grand de diviseurs", et remarque des régularités dans les nombres premiers qui les composent. Le point intéressant (nous ne mentionnons pas les formules) réside dans le fait que seul Ramanujan, le prodige indien ami du mathématicien Hardy, avait proposé une conjecture semblable en 1915.

Les deux approches sont cependant, du point de vue de Lenat "radicalement différentes", et ne se recouvrent qu'en partie. La seconde découverte est une application pointue de la conjecture de Goldbach : étant donné un ensemble de tous les angles premiers compris entre 0ø et 180ø, alors tout angle compris également entre 0ø et 180ø peut être approché à 1ø près en additionnant une paire d'angles appartenant à cet ensemble. Sur un plan épistémologique, comme le soulignent en note les éditeurs de [Knowledge Based Systems in artificial Intelligence ]"pour qu'une idée d'AM soit nouvelle, il faut qu'elle ait été précédemment inconnue à la fois de son auteur et de ses utilisateurs. Pourquoi ? Si l'auteur la connaissait, alors les heuristiques fournies à AM pourraient avoir été encodées inconsciemment de façon à fournir un chemin, une direction vers cette découverte".

L'intérêt probable d'AM réside moins actuellement dans ses découvertes que dans sa méthodologie, et dans la direction qu'elles impliquent. Lenat s'efforce de découvrir les caractéristiques de "programmes d'heuristiques" asémantiques, indépendants du domaine à explorer, et permettant de démontrer des théorèmes en utilisant le calcul des prédicats. Un autre aspect intéressant concerne la découverte des propriétés générales des structures, de la découverte d'analogies, de similarités, d'isomorphisme, etc. Il s'agit de déterminer "comment", par quels mécanismes, on découvre et établit des modèles et des structures.

Consécutivement, Lenat développa Eurisko, qui contournait les difficultés rencontrées par AM. En perfectionnant le système de cadres (frames) Lenat permit à Eurisko d'améliorer ses propres heuristiques de façon notable, ce qui fut mis en évidence lors du deuxième championnat de Traveler auqel il participa. Alors qu'en 1981, Eurisko avait eu le temps de se préparer, et avait joué contre lui-même environ 10000 parties, la seconde année, les organisateurs décidèrent de changer les règles dix jours seulement avant le tournois, et ce dans le but d'évincer Eurisko, la majorité des candidats n'appréciant pas de lutter contre une machine. Cependant, comme le dit Lenat "en un an, Eurisko s'était considérablement amélioré", et il remporta à nouveau les championnats de Traveler version 1982.

Puis Eurisko fut définitivement retiré de la compétition, les organisateurs ayant fait savoir que les championnats seraient annulés si Eurisko se présentait à nouveau. Sur le plan conceptuel, Eurisko est une génération au delà d'AM. Contrairement à ce dernier, il découvre des heuristiques puissantes, et des méta-heuristiques. Certaines de ses idées sont si simples que chacun s'étonne de ne pas y avoir pensé plus tôt.  Appliqué au domaine de la circuiterie microscopique, Eurisko découvrit une nouvelle façon d'architecturer les composants.

Quant on lui donna un ensemble de concepts sur LISP, Eurisko devint capable de se modifier lui-même, du moins en partie, ce qui lui donnait également la possibilité de s'auto-détruire. Comme le remarque Lenat : "parfois, une heuristique mutante évoluait et se développait, avec pour seule fonction de se stimuler elle-même. D'autres heuristiques pirataient le système en examinant les concepts découverts par d'autres heuristiques, et en y inscrivant leur propre nom. Devenant ainsi de plus en plus puissantes, elles auraient contaminé tout le système, sans le système de traçage. Une autre heuristique, encore plus étrange, avait décidé que toutes les heuristiques découvertes par la machine, sauf elle-même, étaient dangereuses et devaient être éradiquées (voir p. 194, [Machinery of the Mind ]). A ce stade, Lenat se sentit à son tour devenir étrange, et il se mit à développer lui-même de nouvelles théories darwiniennes sur les analogies entre la biologie et la vie des concepts dans ses programmes. L'intelligence artificielle serait-elle un domaine de démiurges (dieu créateur du monde dans la théogonie d'Hésiode)?

Jacques de Schryver

Encadré :

Programmes et DNA (d'après The Light of Discovery, George Johnson, in Machinery of the Mind, p194-196)

"A force d'expérimenter, Lenat fut frappé par la similarité entre les processus de découverte d'Eurisko et l'évolution darwinienne. Dans les deux cas des programmes (LISP, ADN) génèrent des structures qui sont testées les unes contre les autres et doivent entrer en compétition pour survivre. Un jour Lenat décida de donner à Eurisko la tâche de concevoir un animal. Après plusieurs générations d'évolution simulée, au cours desquelles divers "organismes" mutaient et s'adaptaient dans l'environnement du programme, Eurisko produisit une créature qui était "plus petite, plus faible, avec des os plus légers, et des dents plus longues et plus pointues, des muscle" s de machoires et de pattes plus importants, une taille accrue de cerveau, qui creusait des terriers plus profonds, avait une fourrure plus épaisse, une couche de graisse sous-cutanée supplémentaire, des oreilles plus petites, et un ensemble de méchanismes permettant de métaboliser plus efficacemet l'acide lactique."

Une des règles d'heuristique directement implémentée par Lenat suggérait que "chaque fois qu'un animal amélioré était "produit" avec un changement dans le paramètre X, et que cet animal subissait également un changement dans le paramètre Y ...dans le futur toute mutation de X devrait avoir une chance plus grande de modifier Y." Durant la simulation, cette heuristique aida Eurisko à découvrir qu'une "aptitude diminuée à se défendre au cours d'un combat, et une sensibilité accrue à l'approche ou à la proximité des prédateurs devraient probablement aller de pair. " Sur le même thème, Lenat écit : "Dans le monde naturel il pourrait exister un ensemble d'heuristiques, relié à une entité N (la neige, ou plus précisément peut être une glaciation), et à un concept C (chaleur, ou chaleur corporelle).

Traduites en langage naturel, ces heuristiques pourraient s'exprimer ainsi : "S'il y a davantage de N(eige) dans le monde, alors améliorer les mécanismes pour conserver C(haleur); si C doit être dissipé, alors l'évaporation semble être un bon moyen pour cela. S'il est souhaitable de faciliter l'évaporation, alors augmenter les parties du corps qui ont une grande surface. Si on désire conserver C, alors accroître le sommeil, l'inaction et l'hibernation. En accroissant le sommeil et l'hibernation, on augmente également la vulnérabilité passive. Si on veut diminuer la vulnérabilité passive, alors accroître les protections corporelles ou les perceptions ...Les termes tels que "sommeil", "hibernation", "évaporation" et "vulnérabilité" seraient des symboles décrits en termes d'autres symboles, au sein d'un réseau sémantique.