Auteur: Serge Boisse
Date: Le 31/03/2023 à 17:03
Type: web/MOC
Tags: programme,ia,maths
pub: oui
commentaires: ouiCopier

AM, l'ordinateur qui est un mathématicien amateur

AM est un système, écrit par Douglas Lenat en 1977, qui « fait des découvertes » en mathématiques, comme le ferait un mathématicien amateur qui ne connaîtrait au départ que des rudiments de la théorie des ensembles. Par exemple AM va découvrir le concept de nombre entier en associant à chaque nombre la classe des listes qui ont cette longueur ; puis plus tard il découvrira le concept d’addition en considérant l’opération « union » sur des ensembles qui n’ont pas d’éléments communs (la taille de l’ensemble résultat est alors la somme de la taille des deux ensembles de départ).

AM possède des heuristiques, qui sont des règles (fixes et préprogrammées) qui lui disent ce qu’on peut faire avec un nouveau concept, comme « trouver d’autres exemples », « considérer les cas extrêmes »,  « chercher l’opération inverse », « répéter plusieurs fois la même opération », etc. C’est ainsi qu’il va découvrir la multiplication en considérant l’idée (suggérée par la dernière heuristique citée) d’ajouter plusieurs fois une même quantité. En s’apercevant alors que a x b est pareil que b x a, AM va en déduire que la multiplication est un concept intéressant, et il va en chercher d’autres propriétés.

AM fonctionne seul, mais il est guidé par l’utilisateur, qui lui suggère ce qui est intéressant,  et qui lui donne des noms pour les concept qu’il vient de découvrir (« multiplier X par Y » est plus parlant que « faire R=0, puis répéter Y fois : {R=R+X} » !)

AM est réellement impressionnant : il est parvenu à « retrouver » seul le concept de nombre premiers, le fait que tout nombre s’écrit de manière unique comme un produit de nombre premiers, et même la conjecture de Goldbach (tout nombre pair est la somme de deux nombres premiers), sans toutefois arriver à la prouver. Puis, après ces découvertes incroyables, faites pendant les premières semaines de son fonctionnement, il s’est mis à « plafonner », à tourner en rond et avoir de plus en plus de mal à inventer des concepts nouveaux et intéressants. Les raisons de ce « plafonnement » sont en elle-même très intéressantes. Mais décrivons AM plus en détail :

En arrivant à l’université de Stanford, en 1972, Douglas 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, le père d’Eliza dont nous avons déjà parlé, présente AM de la façon suivante : « sa structure primaire de connaissance est une hiérarchie de concepts et de propriétés  liées à ces concepts, qui est en fait un exemple presque parfait de ce que Minsky appelle des cadres (voir plus haut chapitre 4). 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. Chaque concept possède une valeur numérique qui exprime son « intérêt » pour la tâche en cours, et cette valeur peut être modifiée par le programme lui-même.

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'auto-modifier : de quoi réjouir profondément Douglas Hofstadter qui aborde le sujet dans son justement fameux livre « Gödel, Escher, Bach : les brins d’une guirlande éternelle ». 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 cœur 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 redé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 d’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 les nombres premiers, ou des théorèmes possibles (conjecture de Goldbach).

 
Le concept de nombre premier dans AM

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.  Par exemple l ‘heuristique « regarder ce qui se passe quand on donne la même valeur à tous les arguments d’une fonction » le conduisit à découvrir les fonctions doublement (x + x) et carré (x . x).

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. Ou bien, il passe très longtemps à chercher des exemples de « nombre impair divisible par 2 ».

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.

Après ces découvertes incroyables, AM est entré dans une phase de « malaise ». Ne parvenant plus à trouver de nouvelles choses intéressantes dans la théorie des nombres, il est revenu à la théorie élémentaire des ensembles, dont il n’est pas parvenu à sortir quelque choses. Il passait en général son temps à chercher pourquoi l’ensemble vide possédait la propriété fascinante que toutes ses instances étaient identiques ! AM note lui même, dans ses « derniers moments » : « attention, aucune tâche dans l’agenda n’a une priorité supérieure à 200 ! ». Il manquait visiblement à AM certaines heuristiques, mais lesquelles ?

Sur un plan épistémologique, on peut s’interroger sur la « nouveauté » des concepts trouvés par AM. Pour qu'une idée d'AM soit considérée comme réellement 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. Le programme biomorph de Dawkins, dont nous avons déjà parlé, montre comment l’homme peut, consciemment ou inconsciemment, guider l’évolution d’un programme qui contient des algorithmes génétiques en interagissant avec lui. Il se pourrait que AM ait fait toutes ces découvertes parce que Lenat voulait qu’il les fasse. Cependant c’est peut probable car le successeur d’AM, Eurisko, que nous allons décrire dans quelques instants, est arrivé aux mêmes découvertes en inventant lui même les heuristiques dont il avait besoin.

Mais l'intérêt d'AM réside moins dans ses découvertes que dans sa méthodologie. Un 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. Par exemple AM n’a pas découvert les fractions, ni les nombres décimaux, ni le concept de mathématique de groupe : pourquoi, peut-on se demander ? Vraisemblablement par ce que la représentation interne de ses données est devenu, à partir d‘un certain point, inadaptée. Comment arriver alors à ce qu’un programme puisse inventer ses propres représentations internes ? Il manque visiblement à AM une imagerie sensorielle !

Un autre aspect concerne l’optimisation du temps de calcul : par exemple AM n’a pas trouvé que tous les diviseurs d’un nombre n étaient inférieurs à ce nombre, et ne s’est donc pas servi de cette propriété pour restreindre l’espace dans lequel il cherchait les diviseurs : pour lui, un « diviseur » était un élément de l’ensemble « image inverse de la multiplication », et un diviseur de 100, par exemple, pouvait a priori être n’importe quel nombre, aussi grand soit-il !

Cependant, après avoir joué quelques années avec AM, Lenat en est arrivé à la conclusion que pour pouvoir faire de vraies découvertes, il fallait qu’un programme « inventif » soit capable d’inventer non seulement de nouveaux concepts, mais aussi de nouvelles heuristiques. c’est pourquoi il s’est mis à écrire un programme, inspiré d’AM mais bien plus général, et encore plus fascinant : EURISKO

NB: cette page est extraite de mon livre "L'esprit, l'IA et la SIngularité".

La suite>: Eurisko