Le développement de l'heuristique

Piètre élève qui ne dépasse pas le maître...

Léonard de Vinci

Eurisko : le cancre génial

L'heuristique, science de la découverte, pousse depuis bien des années les meilleurs informaticiens à s'arracher les cheveux. Comment amener un programme à s'améliorer lui même, et à acquérir ainsi cette autonomie qui est une des caractéristiques de l'être vivant. Dans  [Le hasard et la nécessité], Jacques Monod propose trois critères pour définir l'être vivant : l'invariance reproductive (un oeuf de canard ne donnera jamais un bébé crocodile), la morphogenèse autonome (le développement de l'embryon est pré-codé, il ne dépend plus de circonstances extérieures), et la téléonomie, ou aptitude à se diriger vers un but. A travers l'heuristique, les chercheurs espèrent réaliser des programmes capables de s'auto-améliorer, et de conquérir ainsi un peu de cette aptitude à se diriger vers un but ne dépendant pas totalement des décisions de son concepteur.

Vers la guerre des étoiles

L'enjeu est important : comme arme dissuasive ultime, la guerre des étoiles n'intègre-t-elle pas des systèmes experts capables de poursuivre la guerre, même si les Etats-Unis venaient à être entièrement détruits ? L'heuristique devient ainsi un domaine de raison et de déraison ultime : d'ailleurs, quand on le laisse libre, Eurisko a tendance à devenir incohérent : il exprime son auto-satisfaction en augmentant sans cesse les coefficients qui notent la valeur de ses propres progrès. Et cela ne fait rire personne !

Si les rejetons d'Eurisko devaient développer des "attitudes" analogues de structure avec la paranoïa ou la mégalomanie humaine, il faudrait de toute urgence y introduire des garde-fous, non modifiables, alors qu'Eurisko sait déjà se modifier lui-même. Car Eurisko est par ailleurs tout à fait génial : il est capable de démontrer des théorèmes, de concevoir des circuits électroniques d'un type tout à fait nouveau,  de proposer des suggestions, et d'expliciter ses modes de raisonnement. Historiquement, Eurisko est le premier programme a avoir fait preuve de ce qui ressemble vraiment à de la créativité, et ce, dans des domaines fort différents les uns des autres. Car outre la conception de circuits électroniques,  Eurisko est champion du monde invaincu  de cette super-bataille navale baptisée Traveller,  et qui fait fureur aux Etats-Unis.

Apprentissage et adaptation

Le 4 Juillet 1981 a  marqué une date importante dans l'histoire de l'intelligence artificielle. Alors que la plupart des américains célébrait la fête nationale, les fanatiques du jeu Traveller, se rassemblaient à San Mateo, en Californie. Traveller est à la bataille navale ce qu'une Ferrari est à un tricycle de gamin. Extrêmement complexe, le jeu se développe selon plusieurs centaines de pages de règles. Chaque joueur dispose de  trois mille milliards de crédits pour réaliser une flotte spatiale.

La spécification de chaque vaisseau est libre : les notions paramétrables sont la taille, la vitesse, le blindage, l'armement, etc. Au total, pour construire un seul vaisseau, les joueurs doivent prendre en compte jusqu'à cinquante critères. Si un vaisseau est conçu pour la rapidité, tout blindage le ralentira. S'il est gros, il lui faudra emporter davantage de carburant, et par conséquent, il sera encore plus lent. Le choix du type de moteur, et des systèmes-radar, peut également se révéler décisif. Bref, même si l'on peut construire jusqu'à cent vaisseaux, la plupart des concurrents préfère construire sa flotte en panachant , avec en général plusieurs trés gros vaisseaux, hyper-puissants, dotés d'une considérable puissance de feu, et offrant à leurs propriétaires le sentiment réconfortant du commandant en chef trônant dans son vaisseau amiral.

Du fait du nombre immense de possibilités, les candidats doivent réaliser des compromis. Ces derniers exigent un apprentissage et une adaptation, en fonction des victoires ou défaites. Traveller semblait donc un terrain idéal pour tester les possibilités d'Eurisko, qui se veut au départ un programme non spécifique capable de s'adapter à des situations aussi différentes que possible les unes des autres. Le but de B. Lenat et de son équipe, consistait à réaliser un logiciel d'heuristique générale, programme ambitieux capable de réaliser des apprentissages indépendants du domaine d'application..

L'heuristique pour l'heuristique

Lenat n'a jamais joué à Traveller. Les concurrents de San Mateo s'en doutaient un peu, en voyant de quelle façon Eurisko avait composé sa flotte : une vraie plaisanterie. Trés peu de puissance de feu, 96 petits vaisseaux ressemblant à des nains, hyper-maniables, peu armés et très vulnérables.,

l'équivalent d'une armée de puces au milieu d'un combat d'éléphants. D'ailleurs, au cours des deux minutes du premier affrontement, l'adversaire détruisit cinquante des quatre-vingt-seize vaisseaux d'Eurisko, tandis que ce dernier ne réussissait qu'à détruire dix-neuf vaisseaux ennemis.

Restait un détail important : la flotte adverse ne se composait que de vingt vaisseaux. Ce fut un Waterloo naval. Mais comment Eurisko avait gagné son premier combat ? La réponse semble simple à postériori : Lenat avait découvert des règles d'heuristique efficaces. Mais si nous avons répondu au "quoi ?", reste maintenant à définir le "comment ?". Pour arriver à ce résultat, les flottes de test d'Eurisko avaient en effet subi des mutations en série, au cours des dix mille simulations hyper-rapides réalisées sur les ordinateurs de Stanford.

Non seulement Lenat avait réalisé d'excellentes règles d'heuristique, mais surtout, il avait bûché la méta-heuristique, c'est à dire l'art de réaliser de l'heuristique sur de l'heuristique : un peu comme si un homme utilisait son propre laboratoire pour modifier ses propres gènes, et se rendre ainsi plus intelligent.

La force des combinaisons aléatoires

Lenat compare son programme aux processus d'évolution en génétique. Parti de quelques concepts de base introduits à sa naissance, Eurisko combine ensuite et modifie les règles pour tester ce qui se passe. Il conserve les combinaisons qui se révèlent bénéfiques, et rejette celles qui conduisent à des catastrophes. Bien sur, les critères de mesure sont au départ emmagasinés dans le logiciel de base. Les premières règles sont fixées. C'est à partir d'elles que la situation va évoluer.Les structures qui s'élaborent sont donc à priori le fruit du hasard, et de l'interaction des forces en présence. Certaines structures seront viables, et continueront à survivre pendant quelques générations ou plus. D'autres disparaîtront rapidement. Les structures que Lenat souhaitait voir évoluer étaient bien sûr celles relatives aux flottes de Traveller, et pour ce faire, Eurisko avait été nourri de 146 concepts permettant de définir ce qu'était Traveller.

La spécificité de la méthode, cependant, reposait sur le fait que Traveller n'intervenait qu'en tant qu'exemple permettant de tester des algorithmes, et non pas en tant que règles spécialisées définitivement dans un jeu symbolisant la société des loisirs. Cette aptitude à généraliser, Lenat la devait à son passé de mathématicien et de physicien, habitué à formaliser des concepts abstraits, dans la complexité de leur interaction.

La lumière de la découverte

Parmi les concepts introduits dans Eurisko à l'occasion de l'épisode Traveller, on trouvait des notions d'ordre général, telles que "accélération, agilité, dommages, armes", et d'autres plus précises, telles que "rayon laser, navette de sauvetage, canon à mésons, etc." . Les concepts d'Eurisko sont structurés sous forme de "boîtes" ou "frames", contenant des slots, eux- mêmes chargés de signification selon une structure pouvant atteindre plusieurs niveaux d'emboîtement. Dans son ouvrage "[Machinery of the mind]" (Times Book 1986), qui retrace l'histoire de l'intelligence artificielle, George Johnson choisit d'accorder une grande place à Lenat et à Eurisko. Il lui offre même le dernier chapitre de la partie consacrée aux aspects techniques de l'IA, chapitre qu'il intitule "la lumière de la découverte".

Pourtant, prises une à une, les structures d'Eurisko semblent relativement banales. Par exemple,  la "boîte" représentant le canon à énergie (voir[ Machinery of the mind], page 186/187) possède un slot "est", qui indique qu'il s'agit d'une arme, à la fois défensive, et offensive, en même temps qu'un objet physique appartenant au jeu. Les notions d' arme, et d' objet physique possèdent à leur tour leurs propres slots, permettant de les définir, ce qui crée un réseau relationnel complexe.

De même, chaque concept possède un slot spécial destiné à rappeler le nom de son créateur. Dans le cas où Eurisko en est l'inventeur, le concept possède en outre un historique permettant de savoir comment il a été inventé. La méthodologie de l'heuristique s'en trouve renforcée, puisqu'à partir des découvertes significatives, les concepts ayant  permis de les mettre à jour voient leur valeur augmenter. Ainsi, les mauvaises règles d'heuristique disparaissent progressivement, tandis que les bonnes se multiplient, du moins en attendant d'être à leur tour dépassées. Par exemple, une des méta-règles permettant de spécialiser les règles d'heuristique précise que si une règle est excellente, alors, il faut tenter de la spécialiser, créant ainsi une nouvelle règle d'heuristique.

Mais Eurisko ne se contente pas de créer des nouveautés, il les teste aussitôt, afin d'éviter les monstruosités qui sont l'apanage des programmes d'heuristique trop sophistiqués : ils perdent le sens du significatif, deviennent fou, et ne se raccordent plus au monde réel. En politique, c'est souvent le cas des grands leaders, des visionnaires, et des dictateurs. Pour illustrer cette notion, la science fiction a popularisé le terme de "bersekkers", au sens de machines tueuses devenues folles.

Rester terre à terre

A l'origine, Lenat travaillait avec Cordell Green, en 1972, sur un générateur de programme qui, à partir de la description d'une tâche à accomplir, était censé écrire le programme correspondant. Le travail de Green pouvait se résumer à une recherche méthodologique pour établir un plan et ses différentes étapes. Pour ce faire, le générateur devait commencer par apprendre la logique, fidéle en cela à l'école de pensée qui donna naissance au robot ["Shakey"], et à toute une série de programmes capables de démontrer des théorèmes, c'est à dire de construire des preuves permettant de prendre des décisions.

Quand Lenat entra dans ce champ d'investigation, il avait derrière lui une carrière de physicien et de mathématicien , avec un intérêt poussé pour les abstractions pures, les formes de haute énergie, la relativité générale, l'astrophysique, bref, pour tout un monde qui ne favorise pas la notion terre à terre des choses. C'est la raison pour laquelle Lenat décida, en 1971, de se reconvertir à quelque chose de plus concret : l'intelligence artificielle. A ses yeux, elle permettait de vérifier plus rapidement ses hypothèses, tout en offrant un domaine d'abstraction cependant  fascinant.

La philosophie de la navette de sauvetage

Les différentes versions d'Eurisko furent revues et corrigées à la main, par Lenat, qui s'efforçait de comprendre quels mécanismes conduisaient aux bonnes découvertes. Ainsi, nuit après nuit, Eurisko multipliait les simulations, testant l'ancienne meilleure version contre la nouvelle, modifiant ici et là des morceaux de code LISP, sans comprendre toujours ce qui se passait, mais élaborant sans cesse de nouveaux critères conduisant à une meilleure compréhension globale. Et du point de vue des joueurs normaux, la flotte d'Eurisko était vraiment très bizarre. Une petite navette de sauvetage, par exemple, se promenait toujours au milieu des batailles les plus rageuses, surnageant à tous les coups meurtriers, évitant les puissants jets laser, mésons, et autres. Non armée, elle semblait ne servir à rien. Mais elle était toujours là. En fait, cette navette très bon marché, très maniable, et totalement inoffensive, faisait dépenser à l'adversaire une puissance de feu énorme, sans autre résultat que de diminuer son énergie en pure perte.

La lance et le bouclier

Une notion bien connue des joueurs d'échecs est celle qui oppose les deux attitudes stratégiques, d'attaque et de défense : c'est la dialectique de la lance et du bouclier, dans laquelle le bouclier se révèle souvent extrêmement puissant. Karpov est resté champion du monde pendant onze ans, en utilisant la tactique du bouclier. Il a fallu le génie créatif et le dynamisme de Kasparov pour faire prévaloir la lance, tout comme l'avait fait auparavant le "génie total" que ses biographes accordent à Bobby Fischer. Mais si attaquer efficacement exige du génie, cette denrée, par définition, ne s'avère pas la mieux partagée du monde. Séduits par le principe de la lance, la plupart des compétiteurs de Traveller choisissait de réaliser une flotte extrèmement maniable d'une vingtaine de vaisseaux, lourdement armés, et peu défendus. Puissants et rapides, ils étaient censés pouvoir s'imposer par leur pouvoir destructif, en jouant sur leur agilité pour éviter le feu ennemi. L'essentiel du budget passait donc à intégrer des armes surpuissantes, tandis que le blindage était négligé.

Eurisko, de son côté, fort de sa logique expérimentale, estimait que de nombreux vaisseaux blindés, presque invulnérables et très bon marché puisque fabriqués au prix de la ferraille, finiraient par avoir raison des mastodontes surpuissants mais peu nombreux. Bien que lents, maladroits et peu armés, les vaisseaux d'Eurisko réussissaient néanmoins à s'approcher suffisamment pour détruire les monstres apocalyptiques hypersophistiqués des flottes concurrentes.

 

Apprendre plus vite

Le succès d'Eurisko, qui écrasa tout ses concurrents en 1981, mécontenta fort les organisateurs. Aussi, en 1982, toutes les règles furent-elles changées, et gardées secrètes jusqu'à la semaine précédant les nouveaux championnats. Eurisko étant conçu comme un programme d'apprentissage général, indépendant du domaine d'application, l'occasion se présentait donc de vérifier son aptitude à relever un défi en temps limité. Et surtout, en un an, Eurisko s'était considérablement amélioré. Il avait appris à généraliser davantage ses méthodes. Bien qu'ayant gagné à nouveau en 1982, Eurisko ne se présenta pas en 1983. Les organisateurs avaient en effet prévenu que dans l'hypothèse où Eurisko gagnerait à nouveau, les championnats n'auraient plus lieu. 

Eurisko se retira invaincu, et retourna à sa vocation première : aider au développement d'heuristiques d'intérêt général. Les principales applications d'Eurisko ont été liées à la conception de circuits VLSI , et à l'utilisation de la troisième dimension utilisant, des techniques de recristalisation par rayon laser. Les idées générées par Eurisko sont considérées comme tout à fait originales, et d'autant plus intéressantes qu'elles sont atteintes par des moyens simples, traçables, vérifiables, et reproductibles. Eurisko aura contribué à poser les bases d'une science qui se cherche encore, l'heuristique, et dont les principes, s'ils peuvent être développés, permettront de faire avancer un peu plus les systèmes de cinquième génération.

 

Bibliographie :

* A Guide to Experts Systems  , Donald A. Waterman, Addison Wesley  1986

* Machinery of the mind  , George Johnson, Times Books 1986

* The Human use of Human beings (Cybernétics and Society), Norbert Wiener, Discus Books, Avon 1967

 

Encadré :

Cybernétique et Société

Dans un livre paru en 1950 * ([Cybernetics & Society,] réédité par Discus Books, Avon, 1967), Robert Wiener, père de la cybernétique, expose déjà le problème d'identité que l'évolution " de l'intelligence artificielle ne manquera pas de faire surgir.- "Je voudrais mettre en évidence ici le point de vue sémantique, selon lequel des mots tels que vie, but, et âme, sont grossièrement inappropriés à une pensée scientifique précise. Ces termes ont gagné leur signification à travers notre reconnaissance de l'unité d'un certain groupe de phénomènes, et ils ne nous fournissent pas de fondement adéquat pour  caractériser cette unité.

Chaque fois que nous découvrons un phénomène nouveau qui appartient dans une certaine mesure à la nature de ceux que nous avons déjà appelés "le phénomène du vivant", mais qui ne se conforment pas à tous les aspects que définit le terme "vie", nous nous trouvons confrontés avec le problème de savoir si nous devons élargir la définition du "vivant", de façon à l'inclure, ou à redéfinir le "vivant" de façon plus restrictive de façon à l'exclure..."

Un auteur plus récent pose la question d'une façon tout à fait fascinante. Dans [Gödel, Escher, Bach (Interéditions 1985)] Douglas Hofstadter présente l'exemple de la mosaïque du tabac, dont les éléments, considérés comme inertes, et éloignés les uns des autres, vont soudain se rapprocher, s'auto-assembler, pour donner alors naissance à un être vivant. La notion de vie n'apparaît,  selon les définitions classiques, qu'au moment précis où l'assemblage est réalisé. De tels exemples ne peuvent que mettre en évidence la nécessité devant laquelle nos sociétés se trouveront bientot de redéfinir un ensemble de concepts touchant à l'identité, et à la spécificité de la vie et de la pensée. Ces querelles de vocabulaire entrainant dans leur sillage des turbulences philosophiques et religieuses, et mettant en question la conception de l'homme lui même, on peut présupposer que ces bouillonnements iront dans le sens d'un échauffement, en d'autres termes, vers ce refus de l'entropie que l'on appelle la vie.

 

Encadré Nø2

Les structures résiduelles contre l'entropie

La notion d'entropie continue de fasciner aussi bien les chercheurs que les écrivains de science fiction. Les programmes d'intelligence artificielle, et principalement dans le domaine de l'heuristique, tendent à créer un ordre, une hiérarchie, qui s'oppose au chaos, au hasard pur, bien que prenant appui sur ce dernier. Il nous a semblé intéressant de juxtaposer dans cet encadré la pensée de Norbert Wiener ( considéré comme un des plus grands esprits de son temps , il obtint son doctorat à l'âge de 18 ans,  travailla avec Bertrand Russel, puis toucha à tous les domaines pendant ses 45 ans de carrière au MIT )   avec les concepts de l'heuristique, qui utilisent la notion de feed-back, telle que la définissait Wiener dans ses ouvrages sur la cybernétique (cybernétique = guidage par feed-back).- "Le concept de structure résiduelle a été mis en valeur à nouveau dans l'oeuvre du Dr W. Ross Ashby. Il l'utilise pour expliquer le concept de machine qui apprend. Il souligne qu'une machine de structure aléatoire atteindra des positions proches (&de l'équilibre, et que ces structures de presque équilibre dureront, par leur nature même, beaucoup plus longtemps que les autres, qui n'apparaîtront que de façon temporaire. Le résultat en est que dans une "machine d'Ashby",  de même que dans la nature Darwinienne, nous avons l'apparence d'une téléologie (action dirigée vers un but) dans un système qui n'est pas construit comme tel, simplement parce que la téléologie réside dans sa nature transitoire... Bien que l'entropie doive gagner à long terme, dans les états intermédiaires, un organisme ou une société  tendront à s'assembler plus longuement dans ces modes d'activité dans lesquels les différentes parties travaillent de concert, en fonction d'une structure plus ou moins significative... En physique, l'idée de progrès s'oppose (ainsi) à la notion d'entropie, bien qu'elles ne soient pas en absolue contradiction. de même, beaucoup plus longtemps que les autres, qui n'apparaîtront que de façon temporaire.