<figure><img src="image_1.png" /></figure>

JOËL QUINQUETON

Métaconnaissance ou Apprentissage en profondeur ?

Volume 3, n° 1-2 (2022), p. 51-58.

<http://roia.centre-mersenne.org/item?id=ROIA_2022__3_1-2_51_0>

© Association pour la diffusion de la recherche francophone en intelligence artificielle et les auteurs, 2022, certains droits réservés.

<figure><img src="image_2.png" /></figure>

Cet article est diffusé sous la licence

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/
# Métaconnaissance ou
Apprentissage en profondeur ?

Joël Quinqueton<sup>a</sup>

<sup>a</sup> LIRMM 161 rue Ada 34090 Montpellier, France

E-mail: jq@lirmm.fr

URL: http://www.lirmm.fr/~jq.

RÉSUMÉ. — Une des idées maitresses de Jacques Pitrat est qu’un programme pourrait, plus qu’un humain, avoir la capacité d’être un bon chercheur en Intelligence Artificielle. À travers quelques souvenirs, nous essayons d’illustrer les étapes et travaux de Jacques Pitrat qui ont jalonné son cheminement vers cette idée : MACISTE, MALICE et CAIA.

MOTS-CLÉS. — Métaconnaissance, Raisonnement, Intelligence, Conscience.

## 1. QUELQUES SOUVENIRS...

Jacques Pitrat fait partie des personnages qui m'ont donné envie de faire de l'I.A., domaine qui me faisait un peu peur au début. J'ai d'ailleurs fait mes travaux de thèses (de 3e cycle et d'État) dans ce que l'on appelait la Reconnaissance des Formes. Je suis revenu à l'I.A. plus tard, par l'Apprentissage Automatique.

Mais pour démarrer dans la Recherche, il fallait, dans les années 70, un DEA, qui, à Paris 6, se composait d'un AEA de R.F. et d'un demi AEA dans l'autre domaine, l'I.A. C'est ce qui m'a valu le plaisir de suivre le cours de Jacques Pitrat, en 1974-75. Il est alors basé sur un programme d'Échecs (Tech, de Gillogly [1, 2, 3]), sur lequel sont illustrés les concepts de base de l'IA naissante, le parcours d'un arbre (de profondeur polynomiale si le problème est NP-complet), le min-max et l'alpha-beta, etc. Il nous parle aussi, bien sûr, de l'algorithme d'unification.

Son assistant de l'époque est Jean-Louis Laurière, qui nous fera profiter d'un des premiers « Chess Challenger » dont il a reçu un exemplaire en démonstration : à peine plus épais qu'un échiquier, sur lequel sont disposées les pièces, qu'il faut déplacer conformément aux indications du programme qui s'affichent sur un écran à diodes (comme les montres avant les cristaux liquides), selon les conventions standard des joueurs d'échecs.

À Montpellier, en 1986, Jacques Pitrat fait une conférence sur la métaconnaissance [10]. Elle est basée à l'époque sur le système MACISTE.
On part d'un système composé d'un moteur d'inférence (mise en oeuvre des règles à partir de faits), et d'une base de règles exprimant la connaissance propre au domaine d'expertise.

Le moteur d'inférence est un programme. L'objectif est d'exprimer les instructions de ce programme sous forme déclarative, c'est à dire sous forme de règles, qui sont donc des règles permettant d'utiliser les règles : cette connaissance sur la connaissance est la *métaconnaissance*.

On exprime ainsi de manière déclarative des (méta)connaissances pour utiliser ces connaissances. Ainsi, il reste de moins en moins d'instructions dans le moteur d'inférence, puisqu'elles sont peu à peu remplacées par des connaissances déclaratives.

On peut même imaginer, et Jacques Pitrat ne s'en prive pas, que l'on peut mesurer le progrès d'une telle activité de (dé)programmation par une « demi-vie », comme celle des isotopes radioactifs, c'est à dire le temps qu'il faut pour diviser par deux le nombre d'instructions d'un programme.

Toujours lors de cette présentation à Montpellier [10], à un chercheur en Génie Logiciel venant du MIT (si je me souviens bien) qui lui demandait comment il gérait le problème de la terminaison et de la preuve d'un programme, il répondit sans sourciller que « Des gens qui boguent, il y en a plein les asiles » !

Ainsi, il mettait en évidence deux aspects différents d'un programme : son élicitation et sa preuve. Les deux relèvent d'une modélisation de l'activité de programmation à base de Logique formelle, mais elles poursuivent deux buts différents.

Ces années là, à l'occasion des colloques annuels d'Intelligence Artificielle du LAFORIA (à Strasbourg en 1986 et à Caen en 1987), Jacques Pitrat parlera de *bootstrap* et même de *double bootstrap* et de *déprocéduralisation*.

Jacques Pitrat a été élu AAAI Fellow en 1994, « For his roles as a pioneer of AI in France, outstanding teacher and student leader; and for his many valuable contributions involving metaknowledge », et ECCAI Fellow en 1999.

Il s'est aussi attaqué au problème de la conscience [12]. La conscience et l'intelligence sont deux concepts différents, ayant parfois des objectifs opposés : n'oublions pas que *Science sans Conscience n'est que ruine de l'âme*.

Ces quelques souvenirs ne prétendent évidemment pas à l'exhaustivité. Ils pointent une idée de Jacques Pitrat qui me séduisait assez, celle du système qui s'auto-programme (le *bootstrap*).

Cette approche a fait l'objet de nombreux échanges qu'il a eus avec Jean-Louis Laurière. Il s'est entre autres fortement inspiré pour MACISTE puis MALICE de la thèse de J.-L. Laurière (le système ALICE) à laquelle il fait souvent référence.

Nous allons donc maintenant présenter ces travaux, tels que Jacques Pitrat les décrit dans son blog [14] : après avoir rappelé quelques aspects importants des travaux de Jean-Louis Laurière, nous présenterons les systèmes MALICE puis CAIA, son *Chercheur Artificiel en Intelligence Artificielle*, qui est l'aboutissement actuel de ses travaux.
## 2. LES SYSTÈMES ALICE ET RABBIT DE J.-L. LAURIÈRE

Le programme ALICE est un résolveur général réalisé par Jean-Louis Laurière [4, 5]. C'est tout d'abord un langage de formulation de problèmes (ALICE = *A Language for Intelligent Combinatorial Exploration*), muni d'un module de résolution associé.

La classe des problèmes acceptés par ALICE est : *Trouver* $x, x \in X, X \text{ fini donné, vérifiant les contraintes } K(x)$.

Le paradigme de cette approche a été énoncé clairement par Jean-Louis Laurière dans ses publications autour du système RABBIT [6], un successeur d'ALICE.

La démarche du résolveur est simple :

* Tant que la propagation est efficace, alors continuer à propager puis à choisir une valeur.

* Dès que ce n'est plus le cas, engendrer automatiquement un programme spécifique d'énumération adapté au problème et au nœud courant de l'arbre de recherche, le compiler et l'exécuter, puis transmettre les résultats au résolveur.

L'efficacité de la propagation est évaluée par la mesure de la restriction des domaines des variables après chaque choix.

Le programme engendré est spécifique à chaque cas, et s'appuie sur les masses des variables, les poids des contraintes et le contexte du problème (coefficients, domaines).

Un poids est attribué à chaque contrainte en fonction de son opérateur : à chaque opérateur ($=, \ne, \le, \ge, \forall, \exists$) est associé un poids, le maximum étant pour $=\ne$ le minimum pour $\ne$. Ce poids est ensuite divisé par le nombre de variables auxquelles s'applique l'opérateur. Il est d'autant plus élevé que la contrainte a peu de chances d'être vérifiée.

Une masse est ensuite affectée à chaque variable en fonction de son nombre d'occurrences dans l'ensemble des contraintes affectées de leur poids. Les variables sont triées par masse décroissante.

C'est la variable de plus forte masse qui sera prise en compte en premier dans la génération du programme à compiler.

## 3. MALICE

Le travail de Jacques Pitrat sur MALICE procède de la même démarche, qui est de pousser au maximum l'utilisation de métaconnaissance. En ce sens, c'est un descendant de MACISTE, travail précédent de Jacques Pitrat [10].

Actuellement, il est possible de télécharger MALICE (version de 2009) sur le site de Jacques Pitrat. C'est, selon son auteur, le résolveur de CAIA. On peut observer son comportement sur les problèmes qu'il a appris à résoudre.
On peut demander à MALICE 3 modes de résolution :

* La méthode intelligente, où MALICE trouve une solution avec un tout petit arbre, un peu comme les solutions trouvées par des humains;

* La méthode combinatoire, où MALICE commence par écrire un programme combinatoire, le compile, le charge et l'exécute;

* La méthode combinatoire améliorée, où MALICE applique la méthode intelligente pour réduire l'espace de recherche, trouve de nouvelles contraintes utiles, jusqu'à ne plus pouvoir rien faire d'autre qu'un retour arrière. Dans cette situation, il écrit un programme combinatoire, le compile, le charge et l'exécute, comme précédemment.

### 4. CAIA

La notion d'intelligence est très relative. Je me souviens que, dans mes cours sur l'histoire de l'I.A., je citais volontiers cet exemple du système GPS (General Problem Solver [7] un des premiers résolveurs de problèmes qui fonctionnait par réduction des différences entre le but et l'état initial), sur la démonstration du théorème qui dit que tout triangle ayant 2 angles égaux est isocèle. Si ma mémoire est bonne, j'avais d'ailleurs tiré cet exemple de mes notes des cours de Jacques Pitrat.

La preuve classique des mathématiciens abaisse la hauteur AH, et applique le premier cas d'égalité des triangles rectangles (1 côté de l'angle droit et 1 angle) pour conclure à l'égalité des triangles AHB et AHC, donc de 2 côtés du triangle ABC.

La preuve fournie par le GPS est plus simple et ne nécessite aucune construction, elle consiste à prouver l'égalité du triangle et de son image dans le miroir ($ABC = ACB$), à l'aide du premier cas d'égalité des triangles (1 côté et les 2 angles adjacents).

La conclusion était que la démonstration de GPS est plus simple, en ce sens qu'elle est composée de moins d'étapes et elle fait appel à un théorème plus basique de Géométrie. Mais sa compréhension nécessite un saut conceptuel consistant à imaginer le triangle symétrique, alors que la démonstration classique est plus conforme à l'intuition, plus constructive au sens de la géométrie, qui s'appuie sur la figure.

Dans son blog sur CAIA, Jacques Pitrat montre le contraire sur l'exemple du problème dit de Saint Exupéry : la solution trouvée par CAIA est plus claire que celle proposée par les Mathématiciens. Cette dernière est plus courte.

Ce problème est le suivant(1) : il s'agit de trouver la valeur de 4 inconnues A, B, C, et P, entiers positifs, P étant premier, satisfaisant les 2 contraintes :

$$A \times B = 311\,850 \times P$$ $$A^2 + B^2 = C^2$$

En fait, la version initiale du problème est plus littéraire : un parallélépipède rectangle dont la hauteur est égale à la diagonale du rectangle de base est exactement constitué

<footnote>(1) Je ne fais que traduire (eh oui !) le blog de Jacques Pitrat [14], qui est en anglais</footnote>
de dés cubiques de 1 cm de côté. La surface du rectangle de base est égale au produit de 311 850 par un nombre premier inconnu. Calculer la hauteur du parallélépipède.

CAIA commence par chercher les symétries, des permutations des inconnues qui laissent invariantes les contraintes. Ce méta-problème de recherche de symétries a déjà été rencontré par CAIA. Il le résout en utilisant la même méthode que pour les autres. Il trouve facilement qu'il n'y a qu'une seule symétrie, qui transforme A, B, C, P en B, A, C, P. Comme il ne veut pas engendrer les solutions symétriques, il ajoute la contrainte :

$$B \le A$$

CAIA met en oeuvre de nombreuses déductions pour résoudre un problème. Quand il a trouvé, il extrait les déductions qui sont nécessaires à la solution : c'est l'explication. Voyons donc l'explication trouvée par CAIA pour le problème de Saint-Exupéry.

Avant chaque nouvelle contrainte, est indiqué son numéro d'ordre tel qu'attribué par CAIA. Ainsi, les contraintes définissant le problème sont numérotées de 1 à 3 et la première contrainte ajoutée porte le numéro 4. Les numéros manquants correspondent aux contraintes ne faisant pas partie de l'explication. La première contrainte utile porte le numéro 22 et distingue 3 cas :

$$ 
\begin{align*}
& (\text{pair}(A), \text{pair}(B), \text{pair}(C)) \\
& (\text{pair}(A), \text{impair}(B), \text{impair}(C)) \\
& (\text{impair}(A), \text{pair}(B), \text{impair}(C))
\end{align*}
$$

Il décide alors de revenir en arrière en examinant successivement ces 3 cas possibles.

Dans le 1er cas, $A \times B$ est un multiple de 4. Comme 311 850 ne l'est pas, P doit être pair. Donc $P = 2$. Cette nouvelle contrainte porte le n° 34. Il vient $A \times B = 623 700$ (n° 39). CAIA essaie alors toutes les possibilités de produits valant 623 700, avec les bonnes parités pour A et B : il y en a 30, dont par exemple 3 850 x 162. Pour chaque combinaison, il vérifie si $A^2 + B^2$ est un carré parfait, ce qui ne se produit jamais. Ce 1er cas est donc contradictoire.

Les 2 autres cas seront résolus en utilisant la propriété de tout nombre impair x : $x^2 \equiv 1 \pmod 8$. Donc dans le 2e (resp le 3e) cas, la propriété conduira à $A^2 \equiv 0 \pmod 8$ (resp $B^2 \equiv 0 \pmod 8$), ce qui n'est possible que si $A \equiv 0 \pmod 4$ (resp $B \equiv 0 \pmod 4$).

Donc, dans les deux cas, la contrainte $A \times B \equiv 0 \pmod 4$ est vérifiée, donc $P = 2$. La méthode employée sera donc similaire : essayer toutes les possibilités de produits valant 623 700, avec les bonnes parités pour A et B, et vérifier à chaque fois si $A^2 + B^2$ est un carré parfait. Il y en a 36 dans le 2e cas, dont aucune ne produit de carré parfait, et 24 dans le 3e cas, dont 2 produisent des carrés parfaits, donnant les 2 solutions de base du problème :

$$ 
\begin{align*}
A &= 825, B = 756, C = 1119 \\
A &= 1155, B = 540, C = 1275
\end{align*}
$$
La preuve « humaine », telle qu'elle apparaît dans le site Diophante [16] d'où ce problème est tiré, est analysée de façon critique par Jacques Pitrat.

En effet, cette preuve est directe, sans retour arrière, mais utilise 3 nouvelles variables *M*, *N* et *D*.

On pose tout d'abord :

$$ \frac{M}{N} = \frac{C - A}{B} = \frac{B}{C + A} $$

où $\frac{M}{N}$ est une fraction irréductible, donc *M* et *N* sont premiers entre eux, donc de parité différente. On en déduit que :

$$ \frac{B}{M \times N} = \frac{C - A}{M^2} = \frac{C + A}{N^2} $$

d'où on tire :

$$ \frac{A}{N^2 - M^2} = \frac{B}{2 \times M \times N} = \frac{C}{M^2 + N^2} = D $$

où *D* est entier. Il faut donc résoudre :

$$ 2 \times M \times N \times (N - M) \times (N + M) \times D^2 = 311\,850 \times P $$

Comme *M* et *N* sont de parité différente, $M \times N$ est pair, donc $P = 2$. Donc :

$$ M \times N \times (N - M) \times (N + M) \times D^2 = 311\,850 = 2 \times 3^4 \times 5^2 \times 7 \times 11 $$

Donc *D* doit être un diviseur de $3^2 \times 5 = 45$. La suite en découle directement, sans retour arrière, puisque l'on retrouve les 4 solutions pour *D* qui sont les 4 diviseurs de 45 : 3, 5, 9 et 15.

Là encore, nous retrouvons entre la preuve humaine et celle de la machine la même différence, qui est que l'homme n'hésite pas à construire des entités pour le seul usage de la preuve. Néanmoins, cela ne conduit pas dans ce second cas à une preuve très pédagogique.

## 5. EN GUISE DE CONCLUSION...

Ces réflexions un peu décousues autour des travaux de Jacques Pitrat sont ma manière de rendre hommage à son imagination féconde.

Si l'on regarde l'histoire de l'Intelligence Artificielle, il y eut la mode des systèmes experts, dans les années 80, qui a culminé avec l'expert configurateur XCON de la société D.E.C., qui a effectivement été utilisé par cette société et lui a fait gagner de l'argent. On retrouve cette I.A. actuellement dans les règles métiers des Systèmes informatiques de gestion des grandes entreprises et administrations, où elles ont pour principal intérêt de permettre aux décideurs et actionnaires de suivre l'activité de l'entreprise en question, en perturbant le moins possible cette activité.

Dans un domaine que je connais mieux, l'apprentissage automatique, il y avait dès les années 80 deux approches, celle de l'apprentissage symbolique et celle des réseaux de neurones [15]. La seconde posait à l'époque des problèmes quant à l'élicitation de
la connaissance apprise. Elle en pose toujours actuellement, à mon avis, mais c'est in-
contestablement cette approche, rebaptisée *Deep Learning*, qui domine l'I.A. actuelle,
et il faut lui reconnaitre des réalisations intéressantes quant à l'automatisation de tâches
humaines « intelligentes » : conduite de véhicule, reconnaissance de visages,...

Cette évolution de l'Intelligence Artificielle ne s'est apparemment pas faite dans le sens de l'élicitation, cher à Jacques Pitrat, mais on ne peut s'empêcher de penser que ce n'est qu'un effet temporaire d'un objectif social de recherche de résultats immédiats.

Je terminerai cet hommage à Jacques Pitrat par une devinette tirée de son blog,
dans laquelle le rôle de la métaconnaissance est mis en évidence.

Alexandre et Claire sont 2 mathématiciens. Alexandre reçoit le produit de 2 nombres entiers entre 2 et 100, et Claire reçoit leur somme. Chacun ignore la valeur reçue par l'autre. Le but, pour chacun, est de trouver les deux nombres.

– « Je ne peux pas trouver » dit Alexandre.

– « Je le savais » dit Claire.

– « Alors j'ai trouvé » répond-il.

– « Moi aussi » répond-elle.

Sauriez vous trouver ces deux nombres ?

Jacques Pitrat utilise cet exemple pour illustrer la difficulté de formaliser un pro-
blème, et sa conclusion est que c’est une chose trop intelligente pour être laissée aux
humains : laissons les machines s’en occuper !

Il pointe aussi un implicite surprenant de cette devinette : si aucun des deux ne sait
que les nombres sont inférieurs à 100, alors il y a une seconde solution, dans laquelle
pourtant les deux nombres sont inférieurs à 100 ! Bien sûr, chacun sait dans ce cas que
l'autre ne sait pas que les nombres sont <100 !

BIBLIOGRAPHIE

[1] J. J. GILLOGLY, « The Technology Chess Program », https://kilthub.cmu.edu/articles/journal_contribution/The_technology_chess_program/6610793, 1971.

[2] ———, « The Technology Chess Program », *Artificial Intelligence* **3** (1972), p. 145-163.

[3] ———, « Performance Analysis of the Technology Chess Program », Thèse, Carnegie Mellon University, 1977.

[4] J.-L. LAURIÈRE, « A language and a program for stating and solving combinatorial problems », *Artificial Intelligence* **10** (1978), p. 29-127.

[5] ———, *Intelligence Artificielle : résolution de problèmes par l’homme et la machine*, Eyrolles, 1986.

[6] ———, « Programmation de contraintes ou programmation automatique ? », Tech. Report 96.19, Laforia, 1996.

[7] A. NEWELL, J. SHAW & H. SIMON, « GPS a General Problem Solving program », *Information Processing* **256** (1958).

[8] J. PITRAT, « Realization of a Program which chooses the Theorems he Proves », in *Proceedings of the IFIP Congress 65* (W. A. Kalenich, éd.), Spartan Books, Washington, New York, 1965.

[9] ———, « Réalisation de programmes de démonstration de théorèmes utilisant des méthodes heuristiques », Thèse, Université de Paris, 1966.
[10] ——, « MACISTE : a system using metaknowledge to efficiently use knowledge », in *Actes du Congrès International sur les Impacts de L'intelligence Artificielle en Biologie et Santé (IA Biomed)* (Montpellier), Centre de Recherche en Informatique de Montpellier, october 1986, p. 189-195.

[11] ——, « Implementation of a reflective system », *Future Generation Computer Systems - FGCS 12* (1996), p. 235-242.

[12] ——, *Artificial Beings. The Conscience of a Conscious Machine*, Wiley, 2009.

[13] ——, « A Step toward an Artificial Artificial Intelligence Scientist », http://jacques.pitrat.pagesperso-orange.fr/, 2009.

[14] ——, « My view of Artificial Intelligence (Just Another WordPress Site) », http://bootstrappingartificialintelligence.fr/WordPress3/2019/02/caia-as-a-mathematician-part-1/, 2019.

[15] J. QUINQUETON & J. SALLANTIN (éds.), *Apprentissage et machine*, n° 2/3, Intellectica, revue de l'Association pour la Recherche Cognitive, 1987/1, https://www.persee.fr/issue/intel_0769-4113_1987_num_2_1.

[16] A. DE. SAINT-EXUPÉRY, « Problème de théorie des nombres posé à Max Gelée », http://www.diophante.fr/images/stories/diophante/JR_2005/A10168.pdf, 2005.

**ABSTRACT.** — One of Jacques Pitrat’s very ideas is that a program may be better than a human in being a good researcher in Artificial Intelligence. Through some personal recollection and Jacques Pitrat’s description of his work, we try to illustrate the steps along the path he follows towards this idea : MACISTE, MALICE and CAIA.

**KEYWORDS.** — Metaknowledge, Reasoning, Intelligence, Awareness.

Manuscrit reçu le 30 mars 2021, révisé le 25 octobre 2021, accepté le 15 novembre 2021.