Automatisation du raisonnement Mathématiques
et Démonstration automatique de théorèmes
Dominique Pastre
Université René Descartes - Paris 5
UFR de mathématiques et informatique
Crip5
Cours DEA MIASH - 2002
Chapitre 5 : AM et EURISKO, travaux de D.B.Lenat
Le programme AM1, développé par D.B.Lenat est un travail très original [1 à 7]. Il automatise le raisonnement mathématique d'une manière inhabituelle : il ne démontre rien mais découvre des concepts mathématiques. A partir de concepts ensemblistes généraux (que Piaget pourrait qualifier de pré-numériques et qui sont ceux que possède un enfant de 4 ans), il découvre en particulier les notions de nombres, de nombres premiers et conjecture la décomposition unique d'un nombre en facteurs premiers. Cette approche peut être comparée au travail du mathématicien indien autodidacte génial Ramanujan qui a découvert des résultats nouveaux et importants, mais ne les démontrait pas.
La publication de AM a eu un grand retentissement à l'époque, puis a été fortement critiquée. Certes, si les concepts sont primitifs, les heuristiques, elles, sont très sophistiquées et d'un niveau d'un adulte. D'autre part, les programmes étant écrits en LISP, des concepts évolués y sont implicites, par exemple généraliser l'égalité de listes (et de multi-ensembles) conduit au concept de même-longueur si l'on supprime la condition d'égalité des "CAR", qui est en fait isomorphe au concept de nombre. Enfin, il y a de nombreuses fonctionnalités qui sont programmées et il reste de nombreux points qui ne sont pas très clairs dans la façon dont les programmes fonctionnent.
Néanmoins, je trouve ce travail extrêmement intéressant et je trouve dommage qu'il ne soit plus beaucoup connu et qu'il n'y ait pas plus de travaux poursuivant cette approche. Citons néanmoins les travaux de Simon Colton dont le programme HR a travaillé dans plusieurs domaines mathématiques et a en particulier inventé une nouvelle suite qui a été jugée intéressante [8] .
Lenat ayant constaté que AM, après avoir découvert des concepts intéressants, tournait en rond et ne découvrait plus rien d'intéressant, a analysé ses limites et a conçu le programme EURISKO qui généralise AM. En particulier, dans EURISKO, les concepts ne sont plus seulement mathématiques et les heuristiques sont représentées et traitées comme les concepts, ce qui permet de découvrir de nouvelles heuristiques.
En mathématiques EURISKO a eu les mêmes résultats que AM, en démarrant avec les conceps de AM + 50 heuristiques. EURISKO a été appliqué à d'autres domaines et en particulier a participé à des compétitions de bataille naval ("wargame") où ses résultats ont été très bons et ont conduit les organisateurs à modifier les règles du jeu.
Ensuite Lenat a eu d'autres projet. En 1884 il a lancé le projet Cyc qui consiste à développer une énorme base générale de connaissances de sens commun.
description détaillée de AM
description succinte d'EURISKO, avec quelques exemples d'heuristiques
analyse de systèmes travaillant en mathématiques au niveau méta illustrée entre autres par AM et EURISKO
version pdf de ce texte
On trouvera dans [9,10,11] analyses, critiques, réponses, réflexions autour de ces travaux et de ce type de travaux sur la « découverte scientifique ».
Bibliographie
[1] D.B.Lenat, AM: An Artificial Intelligence Approach to Discovery in Mathematics as Heuristic Search, SAIL AIM-286, Artificial Intelligence Laboratory, Stanford University, 1976
[2] D.B.Lenat, Automated Theory Formation in Mathematics, 5th IJCAI Cambridge 1977, pp.833‑842.
[3] D.B.Lenat, The Ubiquity of Discovery, Artificial Intelligence 9 (1978), pp.257-285.
[4] D.B.Lenat, The nature of heuristics, Artificial intelligence 19(1982), 189-249
[5] R.Davis, D.B.Lenat, Knowledge-Based Systems in Artificial Intelligence, McGraw-Hill, 1982
[6] D.B.Lenat, Theory formation by heuristic search: the nature of heuristics II, background and examples, Artificial intelligence 21(1983), 31-59
[7] D.B.Lenat, EURISKO: a program that learns new heuristics and domain concepts, Artificial Intelligence 21(1983), 61-98
[8] S.Colton, Refactorable Numbers - A Machine Invention, Journal of Integer Sequences, Vol 2, 99.1.2, 1999
[9] G.D.Ritchie, F.K.Hanna, AM: A Case Study in AI Methodology, Artificial intelligence 23(1984), 249-268
[10] D.B.Lenat, J.S.Brown, Why AM and EURISKO Appear to Work, Artificial intelligence 23(1984), 269-294
[11] W-M.Shen, Functional Transformations in AI Discovery Systems, Artificial intelligence 41(1990), 257-272
1La signification de ce sigle a d'abord été “A Mathematician”, puis, plus modestement “I AM that I AM”