Version classiqueVersion mobile

Informatique et sciences cognitives

 | 
Catherine Garbay
, 
Daniel Kayser

Raisonnement de l’homme et raisonnement de la machine

Jacques Pitrat

Texte intégral

Introduction

1Les êtres humains raisonnent pour prendre des décisions, pour résoudre des problèmes et ils donnent des explications qui sont la description des raisonnements conduisant au résultat. Les systèmes d’I.A. peuvent aussi utiliser des raisonnements pour accomplir les tâches qui leur sont données et expliquer leur démarche. Nous allons donner des exemples de tels raisonnements et montrer que des systèmes artificiels peuvent les utiliser, mais nous verrons aussi que la connaissance de notre façon de raisonner est une aide essentielle pour la réalisation de tels systèmes.

2Le raisonnement permet d’obtenir des connaissances nouvelles par une succession d’opérations explicites à partir de connaissances données. Ce peut être la preuve d’un nouveau théorème ou la résolution d’un problème par une succession d’étapes ; chaque étape amène des éléments nouveaux qui serviront de base aux étapes suivantes.

3Comme point de départ, nous allons présenter un problème et indiquer les raisonnements qui conduisent à sa solution ; cela nous servira par la suite à montrer certains avantages et certaines difficultés liées à leur utilisation. Le but de ce problème est de montrer qu’il y a une infinité de nombres premiers ; une succession de raisonnements va nous en convaincre.

4Nous commençons par un raisonnement par l’absurde, c’est-à-dire nous supposons que la propriété que nous voulons prouver est fausse et nous allons montrer que cela conduit à une contradiction. Nous supposons donc qu’il n’y a qu’un nombre fini de nombres premiers. Dans ce cas, il y en a un qui est plus grand que tous les autres, nous l’appelons N.

5N étant le plus grand nombre premier, considérons le nombre (1 x 2 x 3 x 4 x... x (N - 1) x N) + 1. Les mathématiciens appellent factorielle la fonction qui est le produit des N premiers nombres et l’écrivent sous la forme N !. Nous considérons donc le nombre N ! + 1. Faisons maintenant un raisonnement par cas :

6Ou bien ce nombre est premier ou bien il n’est pas premier.

7Si N ! + 1 est premier, il est plus grand que N puisqu’il est le successeur d’un produit contenant N. Nous avons donc une contradiction puisque nous avions supposé que N était le plus grand nombre premier.

8Si N ! + 1 n’est pas premier, il a au moins un diviseur premier P. Mais aucun des nombres inférieurs ou égaux à N ne peut diviser N ! + 1 puisque tous divisent N ! et qu’un nombre ne peut diviser le successeur d’un de ses multiples : P est donc plus grand que N. Comme il est aussi premier, cela contredit encore notre hypothèse.

9L’hypothèse de départ est fausse puisqu’elle conduit à une contradiction dans les deux seuls cas possibles. Il y a donc bien une infinité de nombres premiers.

10L’établissement d’un tel raisonnement est délicat car il faut éviter de faire trop d’essais qui ne servent à rien et il faut savoir choisir ceux qui mèneront au but. Naturellement, dans le cas présent je n’ai donné que les étapes nécessaires pour justifier le résultat, mais le premier qui l’a démontré a fait sans aucun doute de nombreux raisonnements inutiles qui n’apparaissent pas ici. En effet, une fois le but atteint, il suffit d’écarter tous les essais inutiles : on crée ainsi une explication simple. Si un lecteur accepte les règles de raisonnement qui permettent de passer d’une étape à la suivante ainsi que les éléments posés initialement comme vrais, l’explication le convainc de la justesse du résultat obtenu.

11Nous n’utilisons pas que le raisonnement pour prendre des décisions, par exemple l’intuition fait intervenir des mécanismes inconscients qui ne correspondent pas toujours à des raisonnements que nous accepterions, mais ils conduisent souvent à des résultats utiles. Mais, à la différence de l’intuition, le raisonnement est particulièrement intéressant parce qu’il est conscient, il est donc possible de le faire partager par d’autres personnes et aussi de le vérifier une fois qu’il est achevé. Si l’on a répertorié les règles que l’on a le droit d’appliquer dans un raisonnement, il est relativement facile de donner à une machine la possibilité de faire des raisonnements analogues aux nôtres, et nous pouvons aussi les vérifier. Des systèmes comme ALICE (Laurière 1976) et CHERCHEUR (Pitrat 2006) utilisent des raisonnements pour obtenir le résultat cherché, et leurs résultats nous sont parfaitement compréhensibles. Nous rencontrons toutefois deux difficultés dans cette tâche. La première est de recenser les règles de raisonnement que nous avons le droit d’appliquer pour les formaliser et donner ainsi à une machine la possibilité de les appliquer. La deuxième difficulté est de lui donner l’aptitude de savoir choisir parmi les raisonnements possibles celui qui fera avancer vers la solution. Sans cela, on risque de voir la machine faire un grand nombre d’essais inutiles ; la combinatoire peut être tellement élevée que cela pourrait demander des milliards d’années aux ordinateurs les plus puissants.

12Quand nous utilisons le raisonnement pour résoudre un problème, d’autres types de raisonnements viennent se superposer lors de cette résolution. En effet, en même temps que nous résolvons ce problème, nous rencontrons souvent d’autres problèmes qui portent sur la façon de résoudre le problème initial : nous les appellerons donc « méta-problèmes », le préfixe « méta » servant à indiquer que nous ne travaillons plus au niveau du problème, mais à celui où l’on examine comment résoudre le problème.

13Par exemple :

14Nous choisissons la méthode de raisonnement que nous utiliserons pour la prochaine étape.

15Nous cherchons une meilleure formulation de ce problème.

16Nous prédisons ce que doivent donner les prochaines étapes que nous avons prévu de faire.

17Nous vérifions si ces prédictions sont satisfaites et, sinon, quelles en sont les raisons.

18Nous trouvons et corrigeons les erreurs que nous avons pu faire au cours de la résolution.

19On utilise souvent des raisonnements pour résoudre ces méta-problèmes, je les appelle donc méta-raisonnements pour les distinguer des raisonnements qui nous font avancer directement vers la solution. Nous allons les rencontrer plusieurs fois par la suite. Ces méta-raisonnements n’apparaissent pas dans l’explication des solutions : dans l’exemple vu plus haut, je ne dis pas pourquoi j’ai décidé de commencer par faire un raisonnement par l’absurde. Quand ces méta-raisonnements sont explicités, cela conduit à une méta-explication qui ne justifie pas la solution, mais qui indique comment on est arrivé à la trouver.

20L’intelligence artificielle est très utile pour étudier le raisonnement parce que tout doit être précisé dans un tel système et peut donc être examiné ; elle est d’ailleurs parfois utilisée uniquement pour modéliser le comportement humain. Si le modèle fonctionne, nous sommes sûrs de n’avoir rien omis dans la description d’un comportement conduisant à la résolution de problèmes. Inversement, un chercheur en I.A. a toujours intérêt à commencer par s’inspirer de ce qu’il sait du comportement d’experts humains, quitte à s’en écarter s’il trouve des méthodes plus efficaces. Enfin, quand un système performant a été réalisé, il est judicieux de voir si des humains n’utiliseraient pas des méthodes analogues.

21Pour qu’un système puisse raisonner comme nous le faisons, il doit comporter un large ensemble de méthodes de raisonnement. Nous commencerons par présenter un mode très simple de raisonnement, la combinatoire, puis deux exemples montreront par la suite l’intérêt d’autres types de raisonnements. Pour que ces méthodes soient utilisées efficacement, elles doivent être accompagnées d’un mode d’emploi et nous allons voir comment constituer celui-ci. Nous décrirons les caractéristiques du développement méta-combinatoire entraîné par l’utilisation systématique des méthodes connues. Un des avantages du raisonnement est que ses solutions permettent de donner des explications ; de plus, si l’utilisation des raisonnements est bien explicitée, il est également possible de donner des méta-explications qui ne se contentent pas de convaincre l’utilisateur, mais qui lui indiquent aussi comment on a pu trouver une solution. Nous examinerons ensuite comment un homme ou une machine peuvent résoudre des problèmes sans utiliser de raisonnement. Enfin, nous donnerons deux exemples de méta-raisonnements qui peuvent intervenir au cours de la résolution d’un problème : formaliser un problème et monitorer la recherche de la solution.

La recherche combinatoire

22Une machine aussi bien qu’un être humain peut utiliser une forme très simple de raisonnement : faire une recherche combinatoire. Souvent, le but du raisonnement est de trouver la valeur d’un certain ensemble d’inconnues. Lors d’une recherche combinatoire, on considère toutes les valeurs possibles d’une de ces inconnues, puis après chacune de ces valeurs toutes les valeurs d’une autre inconnue, etc. À chaque étape, on vérifie l’absence de contradiction - parce qu’une des contraintes du problème n’est plus satisfaite - et s’il existe un moyen de déterminer rigoureusement la valeur de certaines des inconnues restantes. On développe ainsi une arborescence dont le nombre de feuilles caractérise la difficulté de cette recherche ; dans certains cas, ce nombre s’évalue en milliards.

23Pour donner un exemple de recherche combinatoire, prenons le problème du carré magique de taille 3. Il s’agit de mettre les nombres de 1 à 9 dans les cases d’un carré de 3 x 3 cases de telle sorte que les sommes des lignes, colonnes et diagonales soient les mêmes (voir figure 1).

24Une formalisation naturelle de ce problème pose les huit contraintes suivantes où les valeurs des cases sont représentées par les lettres de A à I et où la valeur commune des sommes est représentée par la lettre S :

(1) A + B + C = S

(2) D + E + F = S

(3) G + H + I = S

(4) A + D + G = S

(5) B + E + H = S

(6) C + F + I = S

(7) A + E + I = S

(8) C + E + G = S

Fig. 1 - Emplacement et contenu des cases d’un carré magique de taille 3.

25Le problème peut être résolu simplement en utilisant une méthode combinatoire : on considère successivement les neuf valeurs possibles pour A puis, pour chaque valeur de A, les huit valeurs restantes pour B (puisque B ne peut pas prendre la valeur déjà donnée à A), puis les sept valeurs restant pour C, on détermine la valeur de S grâce à (1), on considère les six valeurs restant pour D, on détermine la valeur de G par (4) (puisque les valeurs des trois autres inconnues qui y figurent sont fixées), puis celle de E par (8), celle de F par (2), celle de H par (5), celle de I par (3) et on vérifie enfin que (6) et (7) sont vrais avec les valeurs précédemment trouvées. Naturellement, on vérifie aussi que la valeur de chaque inconnue ainsi calculée est bien comprise entre 1 et 9 et que cette valeur n’a pas déjà été affectée à une autre inconnue.

26Toutes les solutions possibles du problème sont donc ainsi engendrées en faisant neuf choix pour A, huit pour B, sept pour C et six pour D : un tel programme trouve les huit solutions de ce problème et l’arborescence ainsi développée possède 9 x 8 x 7 x 6 soit 3 024 feuilles. C’est beaucoup pour un humain mais, pour un ordinateur, le temps de développer une si petite arborescence est négligeable. Cette forme de raisonnement, quoique extrêmement fruste, exige souvent beaucoup d’intelligence pour être menée judicieusement. En particulier, il est important de bien choisir l’ordre dans lequel on fixe la valeur des inconnues, de déterminer celles d’entre elles à qui l’on affecte temporairement une valeur en priorité. En effet, un autre choix peut conduire à une taille d’arborescence bien plus grande. Nous aurions pu, par exemple, choisir de considérer pour le troisième choix les sept valeurs possibles de H au lieu de considérer celles de C. Cela aurait été moins intéressant car cela ne nous aurait pas donné la valeur de S et si, de plus, nous avions ensuite choisi les six valeurs restantes pour I, nous aurions dû encore fixer la valeur d’autres inconnues : l’arborescence en aurait été considérablement augmentée.

27Nous pouvons donc utiliser un méta-raisonnement pour choisir dans quel ordre considérer les inconnues. Un bon méta-raisonnement privilégie les inconnues qui permettent de définir d’autres inconnues le plus rapidement possible. Par exemple, on choisit une inconnue telle que si sa valeur est fixée pour une des égalités, toutes les inconnues sauf une auront leur valeur fixée : on obtiendra immédiatement la valeur de cette dernière inconnue, il ne sera pas besoin d’ajouter un niveau dans l’arborescence. C’est ce méta-raisonnement qui a été utilisé pour définir l’ordre donné plus haut pour le carré magique.

28Notre vitesse de traitement de l’information et notre mémoire limitée nous rendent rarement aptes à résoudre les problèmes par cette approche. Gauss lui-même n’avait vu que 76 des 92 solutions du problème consistant à placer huit Dames sur un échiquier sans quelles se prennent, problème trivial pour un programme combinatoire. Un humain ne peut utiliser qu’exceptionnellement une recherche combinatoire complète avec succès. Par contre, les ordinateurs réussissent souvent à résoudre des problèmes de cette façon, d’autant plus facilement que l’auteur du programme a pu, en étudiant préalablement le problème, définir une méthode combinatoire performante. Nous ne considérons pas qu’une machine fait preuve de beaucoup d’intelligence quand elle résout un problème en se contentant de développer une très grande arborescence avec la méthode combinatoire qui lui a été donnée, au contraire de l’humain qui a trouvé cette méthode. Cependant, un système d’I.A. peut à son tour se montrer intelligent en définissant lui-même une telle méthode et en écrivant le programme qui la met en œuvre. Un système d’I.A. comme CHERCHEUR peut parfaitement écrire lui-même des programmes combinatoires performants ; dans ce cas, le système fait réellement preuve d’intelligence.

29Développer une arborescence de dix millions de feuilles demande à une machine un délai de l’ordre de la seconde : l’homme et la machine ne jouent pas ici dans la même catégorie. La quasi-totalité des problèmes de cryptarithmétique illustre cette inégalité ; dans de tels problèmes il s’agit de remplacer des lettres par des chiffres de façon que l’opération soit correcte et qu’à des lettres différentes correspondent des chiffres différents. Un grand classique est la cryptaddition suivante : DONALD + GERALD = ROBERT

30Il y a cinquante ans, Frederic Bartlett (1958) a observé plusieurs sujets en train de résoudre le problème dans une version très simplifiée où la valeur de D est donnée. Malgré cette aide, la performance de beaucoup de sujets n’était pas éblouissante. Un programme combinatoire résout, lui, immédiatement ce problème, il suffit qu’il considère les valeurs possibles des huit lettres qui se trouvent dans les deux opérandes, sachant qu’elles sont différentes : en effet, les valeurs des deux lettres, B et T, qui sont uniquement dans le résultat, pourront en être déduites en faisant simplement l’addition. Si l’on ne fait pas l’effort de réduire davantage cette combinatoire, cela ne fait que 1 814 400 feuilles, une quantité totalement négligeable pour un ordinateur mais à plusieurs ordres de grandeur de ce que nous pouvons réaliser. Si l’on fait l’effort d’écrire un programme combinatoire plus astucieux, on peut réduire l’arborescence à seulement 176 feuilles, comme dans le cas du programme combinatoire écrit par CHERCHEUR.

31Toutefois la recherche combinatoire mécanique n’est pas toujours satisfaisante, même quand elle donne rapidement la solution. En effet, la machine ne fournit pas d’autre explication que celle de dire : j’ai tout essayé et je n’ai pas trouvé d’autres solutions que celles que je vous ai données. Justifier le résultat reviendrait à imprimer des millions d’essais qu’aucun humain ne peut de toute façon ni comprendre ni vérifier. C’est pourquoi il est utile que les machines utilisent d’autres méthodes qu’un développement combinatoire systématique et, en particulier, emploient des méthodes de raisonnement analogues à celles dont nous nous servons. Elles produisent ainsi des solutions proches des nôtres que nous pouvons et comprendre et vérifier. Par ailleurs, des combinatoires si vastes, dont la résolution demanderait des milliards d’années aux ordinateurs les plus puissants, existent. Là encore, un système d’I.A. utilisant d’autres méthodes de raisonnement, analogues aux nôtres, peut arriver à la solution dans un temps raisonnable.

32Il est enfin des cas où il est impossible d’utiliser la recherche combinatoire. Ainsi, dans le cadre du problème de la démonstration de l’infinité de nombres premiers, une recherche combinatoire se résumerait à examiner tous les nombres en vérifiant si chacun d’entre eux est ou non premier : mais comme il en existe une infinité, cette méthode est absolument irréalisable.

33La combinatoire reste une méthode souvent utilisée par l’être humain tant qu’elle reste limitée au développement d’une arborescence de moins d’une centaine de feuilles, en l’absence d’autre méthode. Les mathématiciens utilisent ainsi les preuves par cas, mais le nombre de cas envisagé étant toujours faible, ils regardent par exemple ce qui se passe si X est positif, puis si X est nul et enfin si X est négatif. Nous en avons vu un exemple plus haut en considérant successivement le cas où un nombre est premier puis le cas où ce même nombre n’est pas premier.

34À l’inverse, la combinatoire est largement utilisée par les ordinateurs parce que cette méthode est facile à mettre en œuvre et qu’elle obtient souvent des réussites spectaculaires dues à la vitesse des ordinateurs actuels. À part la difficulté que nous avons à en vérifier les résultats, cette méthode est excellente pour autant qu’elle résolve les problèmes dans un temps acceptable, ce qui est souvent le cas : nous devons utiliser des trésors d’intelligence pour résoudre la majorité des problèmes uniquement parce que notre lenteur nous interdit d’utiliser une méthode combinatoire, ce pourquoi les ordinateurs sont souvent considérés comme stupides parce qu’ils utilisent cette méthode tandis que nous avons recours à des méthodes plus élégantes. Mais les systèmes d’I.A. peuvent également utiliser d’autres méthodes de raisonnement et donner des solutions aussi - voire plus - belles que celles obtenues pas d’excellents experts humains. Mais quand le but est uniquement d’arriver au résultat le plus rapidement possible, ce n’est généralement pas la meilleure marche à suivre car la combinatoire est une méthode de raisonnement où les machines excellent.

Deux exemples de raisonnement

35Il est souvent possible de résoudre un problème en limitant beaucoup la combinatoire, au point que, dans certains cas, on arrive directement à la solution. Pour cela, parfois nous devons envisager une grande variété de raisonnements. Reprenons sous cet angle le problème du carré magique (voir figure 1). Nous pouvons nous rendre compte que l’énoncé présente de nombreuses symétries, par exemple par rapport à la colonne centrale. Nous rompons ces symétries en ajoutant de nouvelles contraintes comme A < C, A < G, A <I : en effet, à cause des symétries les quatre coins sont équivalents, et nous supposons que A possède la plus petite valeur de ces quatre coins. Nous ajoutons encore C < G car, une fois A connu, les deux coins C et G jouent encore le même rôle et nous pouvons donc supposer que C contient un nombre plus petit que G. Nous avons ainsi changé la formulation du problème en ajoutant de nouvelles inégalités. Un autre raisonnement nous permet également d’ajouter une nouvelle contrainte : comme les valeurs des inconnues de A à I sont toutes différentes, elles prennent toutes les valeurs de 1 à 9. Donc leur somme est égale à la somme des neuf premiers nombres :

36(10) A+B + C + D + E + F + G + H + I= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

37Cette méthode de sommation de toutes les inconnues d’une bijection est souvent utile car elle donne une vue globale du problème.

38Nous allons maintenant utiliser des raisonnements basés sur le calcul algébrique. En additionnant (1), (2) et (3), nous obtenons :

39A + B + C + D + E + F + G + H + I = S + S + S

40Nous voyons que les neuf inconnues A-I sont à gauche et 3 x S à droite. Nous en déduisons donc grâce à (10) que 45 = 3 X S, donc S= 15.

41En additionnant de même (2), (5), (7) et (8), nous avons :

42D + E + F + B + E + H + A + E + I + C + E + G = S + S + S + S

43Les neuf inconnues sont à gauche, toutes une fois sauf l’inconnue E qui y est quatre fois, alors qu’à droite S figure quatre fois, ce qui donne 60. En remplaçant les neuf inconnues par 45 grâce à (10), nous trouvons ainsi : 45 + 3 x E = 60, donc E vaut 5.

44En éliminant C entre (6) et (8) nous tirons : (11) E + G = F + I. De même, l’élimination de H entre (3) et (5) donne : (12) I + G = B + E. Mais en éliminant E entre (11) et (12), nous arrivons à :

45(13) 2 x G = B + F

46Nous allons nous tourner vers des raisonnements ayant recours aux notions de parité. Nous déduisons de (13) que B et F ont la même parité puisque leur somme est paire. Par symétrie, nous établissons finalement que B, D, F et H sont de la même parité. Par conséquent, comme il y a au moins quatre inconnues de l’autre parité, nous en déduisons que A, C, G et I ont elles aussi la même parité, mais différente de la précédente.

47Considérons (1) A + B + C= 15. Comme A et C sont de la même parité, A + C est pair ; comme 15 est impair, cela signifie que B est impair. Donc D, F et H sont aussi impairs, il ne reste plus que les valeurs paires pour les inconnues A, C, G et I ; elles valent donc 2, 4, 6 ou 8 tout en étant différentes. Mais les contraintes éliminant les symétries indiquent A < C, A < G et A < I, donc A vaut 2. Nous voyons par (7) que I vaut 8. il reste les valeurs paires 4 et 6 pour C et G ; mais la dernière contrainte de symétrie, C < G, entraîne C = 4 et G = 6. Il est maintenant facile de trouver les valeurs des inconnues restantes puisqu’il existe pour chacune une contrainte où elle est la seule dont la valeur n’ait pas encore été déterminée. Les sept autres solutions s’obtiennent par symétrie à partir de celle que nous venons de trouver.

48Les raisonnements employés dans cette résolution sont d’une grande diversité. Une des nombreuses règles utilisées dit par exemple que si la somme d’une expression X paire et d’une expression Y est égale à une expression Z impaire, alors l’expression Y est impaire. C’est ainsi que travaille un expert humain en résolution de problèmes et c’est également ainsi que fonctionnent certains systèmes d’I.A. qui utilisent des raisonnements, par exemple les systèmes ALICE et CHERCHEUR : pour ce carré magique, ils trouvent, comme nous, directement la solution, sans devoir développer une arborescence.

49Nous allons maintenant considérer un problème tout à fait différent parce que dépourvu de solution. En effet, comme l’ont montré L. Siklóssy et J. Roach (1973), il est possible de prouver qu’un problème impossible est impossible. Nous avons un échiquier tronqué, auquel il manque deux cases opposées sur la même diagonale. Nous pouvons le donner sous plusieurs formes (voir figure 2), ce qu’ont fait C. Kaplan et H. Simon (1990) qui ont étudié des sujets humains en train de résoudre ce problème. Le but est de recouvrir les 62 cases de l’échiquier tronqué avec 31 dominos, chaque domino recouvrant deux cases.

50Certains sujets reçoivent un échiquier dont toutes les cases sont blanches, comme celui à gauche de la figure 2 ; ils ont de grosses difficultés à résoudre ce problème. Par contre, ceux qui reçoivent l’échiquier où chaque case est alternativement marquée « pain » et « beurre » trouvent assez facilement qu’il n’y a pas de solution. En effet, en essayant de recouvrir cet échiquier, ils arrivent facilement à poser 30 dominos, chacun d’entre eux correspondant à une tartine avec un morceau de pain et un morceau de beurre. À la fin, ils voient qu’il reste deux morceaux de pain sec et ils n’ont aucune difficulté à faire le raisonnement suivant : chaque domino est posé sur un morceau de pain et un morceau de beurre. Pour que le problème ait une solution, il faut qu’il y ait autant de morceaux de pain que de morceaux de beurre. Or il y a 32 morceaux de pain et seulement 30 morceaux de beurre. Le problème est donc impossible.

Fig. 2 – Deux présentations du problème de l’échiquier tronqué : à gauche sans aide : à droite avec aide.

51Ce raisonnement est un cas particulier d’une méthode de raisonnement bien plus générale : supposons qu’il existe un invariant, c’est-à-dire un élément conservant la même valeur quelle que soit l’action entreprise. Si la valeur de cet invariant est différente dans la situation de départ et dans la situation que l’on cherche à atteindre, alors le problème est impossible puisqu’aucune action ne peut modifier la valeur initiale de l’invariant pour la valeur finale désirée. Ici l’invariant est la différence entre le nombre de cases marquées pain et le nombre de cases marquées beurre : la pose d’un domino à un emplacement quelconque enlève toujours un morceau de pain et un morceau de beurre, donc ne change pas la valeur de la différence. Cet invariant vaut 2 dans l’état initial (32 pains et 30 beurres), il ne peut donc pas atteindre la valeur 0 qu’il doit avoir dans la situation finale où toutes les cases sont supposées recouvertes, sans cases marquées pain ou beurre : la différence entre ces deux nombres doit devenir nulle.

52Cette méthode n’est pas toujours applicable : pour certains problèmes impossibles un tel invariant n’existe pas. Par ailleurs, il faut trouver cet invariant ; la présentation du problème y aide beaucoup, ce pourquoi les sujets qui reçoivent l’échiquier avec des cases vides éprouvent bien plus de difficultés à résoudre ce problème que ceux qui le reçoivent avec les cases marquées pain ou beurre.

Les méthodes de raisonnement

53Plusieurs méthodes de raisonnement ont été utilisées pour les problèmes dont nous avons donné la solution, par exemple le raisonnement par l’absurde, le calcul formel sur les contraintes, la prise en compte des parités des expressions, la création de nouvelles contraintes comme (10), la démonstration de l’impossibilité d’un problème à l’aide d’un invariant, etc. Plutôt que de faire le recensement de toutes les méthodes de raisonnement connues, je vais présenter les difficultés que leur utilisation entraîne et donner à titre d’exemple une méthode particulière.

54Une première difficulté de cette approche est de connaître les méthodes de raisonnement qui peuvent être utiles. Formaliser les méthodes de raisonnement est une tâche doublement importante : du point de vue de l’enseignement, cela permet de donner à un novice la connaissance de méthodes qu’il ignorait. Pour un système d’I.A. cela apporte des outils puissants qui permettront à celui-ci de trouver des solutions auparavant hors de portée. Nous avons besoin des experts humains pour définir ces méthodes de raisonnement.

55Mais nous avons aussi besoin que ces experts nous disent quand il est pertinent d’utiliser une méthode plutôt qu’une autre. En effet, s’il est relativement facile de trouver de nouvelles méthodes de raisonnement en observant des experts et de les insérer dans le pool des méthodes connues par un système d’I.A., il est en revanche très difficile pour ce système de les utiliser à bon escient. En ce qui concerne le carré magique, nous avons vu que le système éliminait des inconnues entre les différentes contraintes. Mais CHERCHEUR a aussi établi de nombreuses autres contraintes que celles que j’ai exposées, par exemple l’égalité D +15 = I + 2 x C + G qui n’a en définitive pas servi du tout. Et ceci n’est rien à côté du nombre incroyable de contraintes correctes, mais sans intérêt parce que trop complexes, qui peuvent être engendrées si le système contrôle mal ses raisonnements. Un système mal dirigé peut engendrer des millions de contraintes inutiles, quoique correctes, comme : 2B + 4G + 5H = 30 + 2A + D + 2F.

56Pour limiter une telle explosion de résultats intermédiaires, on doit associer des connaissances aux méthodes de raisonnement connues afin que le système détermine s’il vaut mieux se servir de celles-ci dès que possible, en dernier recours ou pas du tout. Une priorité peut être associée à chaque méthode ; elle dépendra des caractéristiques des objets auxquels la méthode s’applique. Par exemple, si la méthode est d’éliminer une inconnue entre deux équations, la priorité sera d’autant plus élevée que ces équations contiennent peu d’inconnues, et encore augmentée si ces deux équations sont linéaires ou possèdent beaucoup d’inconnues en commun.

57Donnons un exemple de méthode de raisonnement, ainsi qu’un mode d’emploi possible. Supposons qu’une contrainte soit de la forme A + X = B + Y où A et B sont des inconnues tandis que X et Y sont des expressions quelconques ; si l’on sait que les valeurs de A et B doivent être différentes, alors on peut en déduire X ≠ Y. En effet, si la valeur de l’expression X était la même que celle de l’expression Y, alors on établirait, en éliminant cette valeur commune, A = B, ce qui est contraire à l’hypothèse. Cette règle est totalement générale, mais si on l’applique sans discernement, on dégagera beaucoup de contraintes indiquant que les valeurs de deux expressions sont différentes, mais dont on ne pourra rien tirer. En effet, en général une inégalité n’est utile que si elle contient une seule inconnue, cela permettant d’éliminer des valeurs possibles pour cette inconnue : si nous savons que D ≠ 5, nous éliminons 5 comme valeur possible de D. Par contre, que peut-on déduire du fait que C + 5D + 3F ≠ 5G + 7H + 9I ? Cela ne permet absolument pas de limiter les valeurs possibles d’une des six inconnues qui y figurent. Le méta-raisonnement que nous venons de faire nous conduit à ajouter dans le mode d’emploi de la méthode : les deux expressions X et Y doivent contenir à elles deux une seule inconnue, ce qui élimine le plus grand nombre de cas où cette règle pourrait s’appliquer et donner un résultat inutilisable. Il reste encore à définir si ce raisonnement doit s’appliquer dès que possible ou au contraire en désespoir de cause. Il est manifeste que ce raisonnement a des conséquences moins importantes qu’un autre raisonnement susceptible de montrer qu’une contradiction existe ou qui peut déterminer la valeur d’une inconnue. Par contre, enlever des valeurs possibles pour une inconnue diminuant la taille de l’espace de recherche, ce raisonnement peut donc se révéler parfois intéressant, il est donc raisonnable de lui affecter une priorité moyenne. CHERCHEUR contient une centaine de telles méthodes de raisonnement. Cela est certes insuffisant, un expert humain en résolution de problèmes en connaît encore plus ; toutefois, comme le système peut faire davantage d’essais qu’un humain, cet ensemble de méthodes lui permet d’obtenir parfois des solutions aussi élégantes que surprenantes.

58Donnons un exemple d’application de la méthode que nous venons de décrire. Si l’on sait que les inconnues A et B doivent avoir des valeurs différentes et si l’on a la contrainte A + C = B + 4, la méthode nous indique que l’on a C ≠ 4, ce qui permet d’éliminer une des valeurs possibles de C si nous ne le savions déjà. De même, avec la contrainte A + C3 + 11C = B + 6C2 +6, la méthode donne la nouvelle contrainte : C3 + 11C ≠ 6C2 + 6 d’où l’on déduit C ≠ 1, C ≠ 2 et C ≠ 3. Notons que si la contrainte initiale avait été légèrement différente : A + C3 + 11C = B + C2 + 5, on n’en aurait rien tiré d’utile parce que C3 + 11C est toujours différent de 6C2 + 5 quelle que soit la valeur de C.

59Ce raisonnement ne donne donc parfois aucun résultat intéressant soit parce qu’il est déjà connu, soit parce que la nouvelle contrainte est toujours vraie. D’avoir associé un mode d’emploi à une méthode nous permet d’apporter des explications à son utilisation, lesquelles sont donc des méta-explications : si l’on demande pourquoi la méthode « A + X = B + Y donne X ≠ Y » n’a pas été appliquée à une certaine contrainte, on peut répondre par exemple : parce que dans cette contrainte les expressions correspondant à X et à Y contenaient plus d’une inconnue. De même, si l’on demande pourquoi elle s’est appliquée si tard à une autre contrainte, on répondra : parce que sa priorité est seulement moyenne.

La méta-combinatoire

60Nous avons vu qu’il ne suffit donc pas de disposer d’une gamme étendue de méthodes de raisonnement, il faut savoir les utiliser à bon escient. Si celles-ci sont testées systématiquement, on risque de crouler sous un amas d’essais conduisant en général à des résultats inutiles ou à des échecs. Pire, des raisonnements partant de ces résultats inutiles conduiront à d’autres résultats tout aussi inutiles qui entraîneront à leur tour des essais encore plus inutiles. Par exemple, même pour un problème aussi simple que le carré magique, il est possible d’engendrer un nombre incroyable de nouvelles égalités trop complexes pour faire avancer la résolution. Si ces essais inutiles se produisent rarement, cela ne perturbe pas trop le système, mais si le système a été mal conçu on risque l’explosion méta-combinatoire : au lieu d’une explosion combinatoire due à trop d’inconnues ayant chacune trop de valeurs possibles, l’explosion méta-combinatoire se produit quand on exécute sans discernement des raisonnements qui ne font pas progresser vers la solution. L’ordinateur tourne pendant des heures en produisant des résultats exacts mais qui ne servent à rien. Je mets le préfixe méta devant « combinatoire » pour indiquer la différence entre les deux sortes de combinatoire, la deuxième se produisant au niveau supérieur du choix des méthodes et non au niveau du choix des valeurs des inconnues.

61Il est normal d’obtenir du déchet dans la résolution d’un problème, il est quasiment impossible d’éviter les étapes inutiles. De plus, alors qu’il faut analyser la totalité d’une arborescence pour expliquer un résultat obtenu par une approche combinatoire, il suffit de recourir à ce qui figure dans l’explication pour justifier un résultat obtenu par raisonnement : l’explosion méta-combinatoire ne conduira pas de son côté à des explications plus complexes qu’en son absence, mais entraînera une perte de temps considérable lors de la recherche méta-combinatoire si l’on fait sans succès un grand nombre de raisonnements.

62Remarquons que les ordinateurs ne sont pas les seuls à procéder à de vastes recherches méta-combinatoires. Un mathématicien peut passer dix années à prouver un résultat dont la preuve ne demandera finalement que deux pages. Il aura écrit des milliers de pages au cours de ces années, mais comme cela n’aura servi à rien pour justifier son résultat, tout cela ne figurera pas dans sa publication. Nous pouvons donc obtenir des résultats très élégants par cette approche, mais si les méthodes utilisées ne sont pas sélectionnées judicieusement, le temps pour obtenir la solution peut devenir prohibitif. L’approche méta-combinatoire demande parfois autant, voire plus de temps que l’approche combinatoire, mais son avantage est que les résultats qu’elle produit nous sont bien plus facilement compréhensibles.

63Quand un système fait un développement méta-combinatoire des méthodes de raisonnement connues, il obtient des résultats très intéressants, qu’il ait été efficace ou non : nous sommes capables de suivre les explications qu’il donne : ses solutions sont souvent même bien plus élégantes que les solutions obtenues par des experts humains, tout simplement parce qu’étant plus rapide il peut tester davantage de raisonnements. Pour la cryptaddition DONALD vue plus haut, un très bon expert humain est content s’il arrive à montrer qu’il n’existe qu’une solution avec une arborescence de cinq feuilles : CHERCHEUR y parvient avec une arborescence de seulement deux feuilles, il ne considère que les deux cas E = 0 et E = 9 et montre qu’il y a contradiction dans le premier cas tandis que le second conduit à la solution.

64Alors que l’on identifie trop souvent les ordinateurs à de simples opérateurs faisant une recherche combinatoire immense, une nouvelle génération de systèmes utilisant une grande variété de raisonnements génère des solutions plus satisfaisantes que celles obtenues par les meilleurs spécialistes humains, car ces systèmes accomplissent en fait une recherche combinatoire bien plus restreinte que la nôtre. Leur supériorité tient à ce qu’ils sont rapides et peuvent tester bien plus de méthodes que nous ne pouvons le faire : leur recherche métacombinatoire est bien plus vaste que la nôtre, mais cela n’apparaît pas dans les solutions qu’ils génèrent.

65Plus de tels systèmes sont généraux et, paradoxalement, plus ils se révèlent efficaces. En effet, à un certain type de problèmes va correspondre un certain type de raisonnement ; c’est le cas de celui qui conduit à la considération de la contrainte (10) dans le cas du carré magique. Aussi, nous l’ajoutons au pool de raisonnements du système. Comme le système le connaît, il l’utilisera pour la résolution d’autres problèmes alors que nous, humains, n’y aurions pas pensé. Cela conduit souvent à un échec, mais l’ordinateur peut se le permettre si cela n’arrive pas trop souvent ; par contre, dans quelques cas, cela lui donnera la solution d’une façon qui, pour nous, est surprenante. Ainsi, CHERCHEUR a utilisé par exemple avec succès la méthode de sommation des inconnues d’une bijection à des problèmes auxquels je ne pensais pas appliquer ; or cela a conduit à des solutions très élégantes. Je me demande parfois en examinant des résultats de mon système comment il a bien pu parvenir à trouver si rapidement un résultat ; c’est toujours parce qu’il a décidé avec raison d’appliquer un raisonnement que je n’aurais jamais pensé utile dans ce contexte.

L’explication et la méta-explication

66Quand une solution a été obtenue par la seule utilisation de la méthode combinatoire, il n’y a rien à expliquer : la résolution est finie parce tout a été essayé et toutes les solutions obtenues. Nous devons admettre que le résultat est correct en espérant qu’il n’y ait ni erreur de programmation, ni erreur de l’ordinateur. Mais il nous est impossible pratiquement de refaire toutes les étapes suivies par l’ordinateur : les résultats ainsi obtenus ne satisfont pas un utilisateur humain : nous avons besoin d’explications et de vérifications. Par exemple, une base de données de finales de tournois d’échecs créée par un programme combinatoire nous informe qu’il existe un gain dans une certaine position en au plus 517 coups de chaque camp. Pour chaque étape elle indique le meilleur coup, mais dans la plupart des cas la raison pour laquelle ils sont les meilleurs nous est totalement incompréhensible, et cela ne peut aider un novice à améliorer ses performances.

67Par contre, quand la méthode combinatoire intervient de façon restreinte parce que le système se sert aussi des autres méthodes de raisonnement, il lui est souvent possible de donner une explication que nous pouvons suivre. Celle-ci contient toutes les étapes nécessaires pour assurer l’utilisateur de la validité de la solution, et il est facile de créer cette explication automatiquement. Il suffit pour cela de partir des dernières étapes, celles où l’on aboutit à une solution ou à une contradiction, et de considérer le raisonnement qui y a conduit. Il se base sur un certain nombre de faits qui ont été eux aussi établis à partir de raisonnements. Pour chacun d’entre eux, le système opère de la même façon pour le raisonnement qui y a conduit et il poursuit ainsi jusqu’à ce qu’il parvienne à des faits qui soient des données du problème. Tout ce qui n’a pas été ainsi marqué peut être éliminé. L’explication automatiquement engendrée contient tous les raisonnements nécessaires pour établir le résultat. Si nous sommes d’accord sur le droit d’utiliser toutes les méthodes de raisonnement qui y figurent, nous sommes convaincus de la justesse de la solution. Ce procédé demande seulement de garder une trace de tous les essais effectués ; une fois le problème résolu, le système sélectionne automatiquement les raisonnements utiles parmi l’ensemble de ceux qu’il a testés.

68Toutefois, pour certains problèmes très compliqués, un utilisateur humain ne peut utiliser cette explication car elle comporte trop d’étapes : nous ne pouvons contrôler une dizaine de milliers d’étapes de raisonnement, pas plus que nous n’aurions pu les trouver nous-mêmes. Comme dans le cadre de la résolution combinatoire, nous ne parvenons pas à trouver la solution, ni à vérifier son exactitude. Les ordinateurs résolvent maintenant des problèmes en raisonnant mais dont, pour certains, nous ne pouvons vérifier la solution vu la taille énorme de l’explication la plus compacte possible.

69L’explication est fondamentale pour améliorer l’apprentissage : elle indique les raisonnements qui ont été indispensables - puisqu’ils y figurent - et ceux qui ont été inutiles. On peut ainsi modifier les modes d’emploi de ces raisonnements de façon à privilégier les plus utiles et à éliminer - ou à appliquer moins souvent - les inutiles. Un tel système génère des solutions plus élégantes, ou bien trouve plus rapidement une solution identique. Cet apprentissage réduit l’explosion méta-combinatoire en réduisant le nombre des applications de méthodes de raisonnement.

70L’explication d’une solution indique la succession des étapes qui la justifient alors que la méta-explication révèle comment le système est parvenu à la trouver. Dans l’exemple du carré magique, une méta-explication pourrait indiquer l’utilité d’appliquer le raisonnement créant la contrainte (10) - qui donne la valeur de la somme des inconnues d’une bijection - parce que le problème contenait beaucoup de contraintes linéaires avec les inconnues figurant dans (10) ; il y avait donc des chances que celle-ci soit utile si l’on poursuivait par du calcul algébrique. Les humains donnent très rarement des méta-explications, chose regrettable car celles-ci ont une grande importance pédagogique. En effet, elles montrent à l’élève que si certains parviennent à résoudre des problèmes, ce n’est pas parce qu’ils ont une bosse des maths innée, mais parce que sachant choisir les essais utiles, ils ne perdent pas leur temps à des essais dont il est prévisible qu’ils ne serviront à rien. La méta-explication contient justement les méta-raisonnements permettant de choisir parmi les raisonnements possibles. Le raisonnement donné pour le problème de l’existence d’une infinité de nombres premiers m’a toujours laissé insatisfait : l’explication m’a convaincu qu’il en existe bien une infinité, mais je n’ai jamais eu de méta-explication qui m’ait indiqué comment quelqu’un a pu un jour penser à considérer le nombre N ! + 1, qui est la clé de la démonstration.

71Pour un système d’I.A., la méta-explication est également précieuse parce qu’elle permet d’améliorer les modes d’emploi des méthodes connues. Nous disposons pour cela de divers types de méta-explication : comment en vient-on à utiliser à tel moment un certain raisonnement ? Pourquoi n’a-t-on pas résolu le problème avec la solution plus élégante trouvée par un autre système ? Pourquoi n’a-t-on pas vu plus tôt qu’il fallait appliquer le bon raisonnement ? Pourquoi a-t-on perdu tellement de temps à utiliser un type de raisonnement qui n’a finalement servi à rien ? Les réponses à ces questions permettent de déterminer quels modes d’emploi des raisonnements doivent être modifiés, donc d’améliorer les performances du système : il perdra moins de temps dans sa recherche méta-combinatoire à essayer des raisonnements inadaptés et il essaiera en priorité des raisonnements qui supposeront effectivement de grandes chances de succès. CHERCHEUR parvient ainsi à trouver plus souvent et plus rapidement une solution plus élégante aux problèmes posés.

D’autres méthodes que le raisonnement

72Les êtres humains n’utilisent pas uniquement le raisonnement dans la prise de décision. Nous parlons souvent d’intuition quand nous nous servons d’un mécanisme qui n’a rien à voir avec le raisonnement, et qui partage certaines caractéristiques avec la perception, la rapidité par exemple ou le fait qu’il soit inconscient. Ces deux modes sont en concurrence. Ainsi d’un humain qui choisit son conjoint en utilisant le raisonnement, on parlera alors de mariage de raison. Nous pouvons expliquer pourquoi Monsieur Dupont a épousé Madame Dupont bien qu’elle soit stupide, laide et irascible : son but était d’épouser une riche héritière, tout est clair. Par contre, dans d’autres cas, nous sommes incapables de donner les raisons d’un choix similaire, surtout quand il est dû à un coup de foudre. Les raisons données sont en général fausses, le sujet adopte souvent un comportement en contradiction avec toutes les raisons pourtant valables qu’il a données. Nous en savons trop peu sur nos processus inconscients de prise de décision, et en particulier sur l’intuition, pour prétendre la modéliser dans un système d’I.A., mais nous pouvons cependant montrer que de tels systèmes peuvent prendre des décisions en utilisant des méthodes qui ne sont pas basées sur des raisonnements.

73Evoquons à titre d’exemple une méthode due à S. Pinson (1989) qui s’applique dans les cas où un système doit choisir entre plusieurs décisions. Supposons par exemple que nous voulions acheter des actions et que nous hésitons entre plusieurs sociétés. Il est difficile de se servir d’un raisonnement qui tienne compte de tous les facteurs en jeu alors que, pour chaque société envisagée, il existe des aspects favorables et des aspects défavorables. Il faut savoir faire un compromis entre les qualités et les défauts de chacune d’entre elles, et pour cela analyser chacun de ces aspects comme la santé financière, la qualité des produits, du marketing, de l’équipe dirigeante, etc. Des aspects secondaires interviennent pour chaque aspect : afin d’évaluer la qualité de l’équipe dirigeante, il faut naturellement déterminer si le PDG est dynamique et compétent, mais aussi apprécier la valeur de son dauphin pour le cas où il cesserait son activité. La valeur du dauphin peut varier d’excellent à déplorable, mais la façon d’en tenir compte fait intervenir de plus l’importance de ce critère. En effet, la valeur du dauphin du PDG n’est pas très importante si le PDG est jeune et en bonne santé ; par contre, elle est extrêmement importante si celui-ci a 95 ans.

74Pour chaque aspect d’une décision possible (pour choisir une contrainte, ce peut être le nombre de ses variables, le fait qu’elle soit une égalité, etc.), l’utilisateur définit une règle qui détermine à la fois la valeur et l’importance de cet aspect : pour l’aspect « nombre de variables d’une contrainte », une des règles dit que c’est important et que la valeur est d’autant plus élevée que ce nombre est faible. Nous obtenons ainsi, à partir des caractéristiques d’un candidat, un ensemble de couples (valeur-importance) qui sont déterminés par raisonnement. Le système applique ces règles pour chaque décision, ce qui lui associe un ensemble de couples (valeur-importance) ; un algorithme général calcule ensuite la note à donner à cette décision en fonction du nombre de fois où chaque couple est présent. Cette note est un nombre et le système choisit finalement la décision qui présente la note la plus haute. Dans cette phase finale, le résultat n’est plus obtenu par un raisonnement, c’est-à-dire par une succession d’étapes claires, mais par un calcul qui mélange tous les résultats élémentaires.

75Par exemple, si l’on a trois fois le couple (très bon-assez important), deux fois le couple (très mauvais-important) et une fois le couple (excellent-capital), un certain algorithme donnera la même note pour toutes les décisions qui présenteront ces mêmes couples, par exemple 315 419 ; cette valeur sera celle-là quel que soit le domaine où cela s’applique. Si, pour un autre candidat, on a cinq fois le couple (assez mauvais-assez important) et deux fois le couple (moyen-important), le même algorithme donnera la note 264 573. Cette méthode de choix d’une décision peut s’appliquer à de nombreux types de décisions : choisir une méthode de raisonnement, choisir l’inconnue dont on va fixer la valeur, choisir quel problème on va résoudre, etc. Si deux décisions possibles conduisent aux deux ensembles de couples envisagés plus haut, le système préfère le choix qui correspond au premier ensemble. Notons qu’une décision n’est pas facile à prendre sur la base de ces deux ensembles de couples, car le premier présente des extrêmes et des couples très bons et très mauvais sur des critères importants, quand le second cultive la médiocrité ; avec l’algorithme utilisé, le système accepte de prendre des risques.

76Il en résulte que le choix de l’algorithme qui décide en fonction des couples engendrés possède une grande importance pour le comportement du système. Nous pouvons prévoir plusieurs algorithmes en fonction du risque qui est accepté. Par exemple, s’il s’agit de piloter une centrale nucléaire, aucun risque ne peut être accepté et il faudrait donner une très mauvaise note à la première décision : s’il existe un aspect très défavorable pour un seul aspect important, cette possibilité est éliminée. Dans un contexte de recherche, comme de déterminer si un papier doit être accepté ou de décider quel chercheur va être recruté, il faut au contraire éviter la médiocrité et favoriser la décision qui comporte une très bonne note pour au moins un critère important, quoi qu’il en soit par ailleurs. Cela correspond à l’algorithme qui a été utilisé pour prendre les décisions précédentes.

77Cette méthode donne cependant une réponse sans s’appuyer sur des raisonnements clairs avec lesquels tout le monde puisse être d’accord. Nous disposons d’un ensemble de connaissances pour évaluer si un aspect est positif ou négatif, s’il est important ou secondaire ; nous pouvons nous mettre d’accord sur les résultats de cette phase qui, par exemple, détermine qu’un certain aspect est à la fois excellent et de peu d’importance. Mais tout repose ensuite sur l’algorithme qui fait le bilan de tous les aspects ainsi établis. Il devient alors difficile d’expliquer de façon convaincante le comportement de cet algorithme : dans l’exemple précédent, il est probable que le couple (excellent-capital) a été décisif et a réussi à contrer l’effet des deux couples (très mauvais-important) parce qu’il était appuyé par les cinq couples (très bon-assez important), mais cette explication ne peut emporter la conviction de façon aussi forte que le ferait une explication fondée sur un raisonnement, et beaucoup estimeraient qu’il aurait mieux valu privilégier dans l’exemple précédent la deuxième possibilité bien moins risquée. Cet exemple est relativement facile à comprendre parce qu’il ne comporte que très peu de couples. Dans le cas contraire, il n’existe pas d’autre explication que de présenter tous les calculs établissant le résultat final et qui sont loin d’être convaincants.

78Les êtres humains utilisent sans doute des méthodes analogues quand ils choisissent entre plusieurs possibilités où interviennent une multitude d’aspects dont certains amènent à privilégier telle décision tandis que d’autres en favoriseraient une autre. Cela peut se produire aussi bien quand nous choisissons le restaurant où nous allons dîner, le film que nous allons voir ou l’automobile que nous allons acheter. Si nous demandons une explication du choix qui a été fait, il en sera donnée une, mais ce n’est en général pas la bonne, car, dans d’autres circonstances, la décision choisie ne sera pas en accord avec cette explication. Comme l’algorithme qui tient compte simultanément de l’intérêt des diverses caractéristiques d’un problème est inconscient, il nous est difficile de faire partager notre choix même à une personne qui évalue ces caractéristiques exactement comme nous. Je ne prétends pas que nous utilisons la méthode basée sur l’évaluation de couples (valeur-importance), mais les méthodes que nous utilisons entraînent cependant la même difficulté à expliquer nos décisions et conduisent à des comportements analogues.

79La prise de décision dans des situations où de nombreux critères s’opposent est une opération complexe pour les humains et nous ne parvenons pas à justifier totalement de telles décisions parce qu’elles ne sont justement pas entièrement basées sur des raisonnements. Malgré la difficulté qu’il y a à convaincre d’autres personnes de la justesse de notre choix, nous ne connaissons pas d’autre moyen d’arriver à une décision dans des situations aux aspects contradictoires. Nous venons de voir qu’un système d’I.A. peut utiliser lui aussi des méthodes qui ne sont pas des raisonnements pour prendre des décisions dans de telles situations.

Raisonner sur le problème

80Plutôt que d’essayer de résoudre immédiatement un problème, il vaut souvent mieux commencer par examiner son énoncé et, en particulier, déterminer comment formaliser celui-ci avant d’entreprendre sa résolution proprement dite. De même, pendant que l’on résout un problème, il est utile de s’arrêter de temps en temps pour considérer le déroulement de cette résolution et, en particulier, si tout se passe conformément aux prévisions faites au départ : on monitore la résolution. Si l’on voit que l’on tourne en rond, si l’on rencontre une difficulté imprévue, si l’on détecte un résultat intermédiaire manifestement erroné, il est possible de réagir tout de suite en fonction des anomalies ainsi détectées. Dans tous ces cas, le raisonnement est utilisé non pour résoudre directement le problème, mais pour aider à sa résolution en le formalisant sous une forme convenable ou en examinant la façon dont la résolution, basée sur des raisonnements, progresse. Pour distinguer ce type de raisonnements de ceux qui conduisent directement à la solution, je parle de méta-raisonnement. Comme nous l’avons déjà vu, le méta-raisonnement ne résout pas le problème, mais il favorise l’utilisation des raisonnements qui, eux, résolvent le problème.

Formaliser l’énoncé d’un problème

81Les problèmes sont souvent énoncés dans un formalisme très différent de celui qui sera finalement adopté pour le résoudre : ils sont en général exprimés dans une langue naturelle comme le français. Malheureusement, le passage d’un formalisme à un autre est une tâche complexe ; mal conduite, elle peut entraîner un échec du système de résolution alors que ce problème serait résolu sans difficulté posé autrement. Tout le monde sait qu’un problème bien posé est déjà à moitié résolu. Pour les problèmes donnés aux systèmes d’I.A., le chercheur passe souvent un temps considérable à mettre le problème sous une forme telle que son système saura le résoudre facilement. Dans cette situation, l’acte d’intelligence n’est pas dans le programme, il vient du chercheur qui a su transformer l’énoncé.

82Pour montrer l’importance de cette formalisation, considérons l’énoncé suivant inspiré d’un problème paru dans Valeurs Actuelles :

Une mère de quatre filles a eu la conversation suivante avec le préposé qui vient lui apporter son courrier :
- Quel âge ont vos filles ?
- C’est facile à trouver, le produit de leurs âges est 72 et la somme de leurs âges est le numéro de ma maison.
- Je n’ai pas assez d’informations pour résoudre le problème.
- Je vais vous aider, ma fille aînée a une robe rouge.
- C’est intéressant, mais je ne peux toujours pas trouver l’âge de vos filles.
- Je vais encore vous aider, j’ai mis une robe verte à ma fille la plus jeune.
- Maintenant je connais l’âge de vos filles.
On demande quel est l’âge de ces filles.

83Ce problème est difficile à formaliser, mais une fois ceci fait, la résolution est triviale. Pour arriver à le formaliser, nous faisons le méta-raisonnement suivant. Il faut d’abord bien distinguer entre ce que nous savons et ce que le préposé sait. Il connaît le numéro de la maison, donc si cela ne lui suffit pas, cela veut dire que plusieurs décompositions de 72 en quatre facteurs donnent la même somme et la solution est une de ces décompositions. En effet, si le numéro de la maison était 14, le préposé saurait que les âges sont 1, 3, 4 et 6, seule décomposition de 72 en quatre facteurs conduisant à la somme de 14 ; dans ce cas le préposé ne dirait pas qu’il ne peut savoir l’âge des filles. Quand la mère dit que sa fille aînée a une robe rouge, l’information utile pour la résolution est qu’elle n’a pas des jumelles comme aînées puisqu’elle utilise le singulier. Sa dernière phrase indique qu’elle n’a pas non plus de jumelles comme cadettes. Ce raisonnement sur l’énoncé le traduit en contraintes : le système doit chercher au moins deux décompositions qui donnent la même somme et écarter les possibilités restantes qui conduisent à plusieurs valeurs supérieures égales entre elles ou à plusieurs valeurs inférieures égales entre elles. Le problème ainsi formalisé est devenu très facile et un raisonnement simple permet de le résoudre. Pour cela, on engendre d’abord toutes les décompositions possibles de 72 en quatre facteurs. En examinant ces quinze décompositions, nous voyons qu’elles ont toutes des valeurs différentes de leur somme sauf trois dont la somme vaut 15 : (1, 2, 6, 6), (1, 3, 3, 8) et (2, 2, 2, 9). Nous savons donc maintenant que 15 est le numéro de la maison. Comme l’aînée n’est pas une jumelle, cela élimine la première possibilité ; comme la dernière n’est pas une jumelle, cela enlève la troisième possibilité. Il ne reste plus que la solution ; 1 an, 3 ans, 3 ans et 8 ans. Nous sommes donc passés par deux phases où il faut raisonner, mais où les niveaux de raisonnement sont différents : d’abord un méta-raisonnement pose les contraintes et ensuite seulement un raisonnement conduit à la résolution du problème défini par ces contraintes. Pour ce problème, il nous était même impossible de raisonner à partir de la formulation initiale, car nous n’en distinguions pas les contraintes.

84Même si nous concevons une formulation utilisable d’un problème, si celle-ci est mal conçue cela peut conduire à des temps de résolution bien plus élevés que si elle avait été menée judicieusement. Considérons un exemple classique en I.A. (Simon 2004), celui du jeu où chaque joueur place alternativement une de ses pièces, croix pour l’un et ronds pour l’autre, dans une case d’un carré de 3 x 3 cases. Le gagnant est le premier qui obtient trois pièces alignées sur une colonne, rangée ou diagonale. Ce jeu est très facile, nous voyons vite qu’il est intéressant de jouer au centre car quatre lignes s’y croisent ou, à défaut, dans un coin où passent trois lignes alors qu’il y en a seulement deux pour les milieux des côtés. En effet, plus on contrôle de lignes, plus on a de possibilités de gagner et moins l’adversaire en a. La figure 3 donne un exemple de partie où le numéro du coup est marqué dans un coin. Dans cette position où le détenteur des ronds doit jouer, le joueur possédant les croix va nécessairement gagner car il a créé une fourchette : il menace de gagner soit en mettant une croix au milieu de la première colonne, soit en complétant la deuxième diagonale. Les ronds ne peuvent pas contrer simultanément ces deux menaces.

Fig. 3 - Un jeu de « tic-tac-toe » ; les ronds perdent la partie, quoi qu’ils jouent.

85Considérons maintenant le jeu suivant : chaque joueur prend à tour de rôle un jeton dans un tas de neuf jetons numérotés visiblement de 1 à 9. Le gagnant est le premier qui obtiendra trois jetons, parmi tous ceux qu’il aura pris, dont la somme fasse 15. Ce jeu est difficile à jouer, alors qu’il est identique au précédent. En effet, reprenons le carré magique de notre deuxième section. Prendre le jeton marqué 4 revient à poser une pièce dans la case du carré magique qui contient le nombre 4. On gagne quand on a trois jetons dont la somme fasse 15, ce qui correspond bien à la somme des nombres dans chaque ligne du carré magique. La difficulté de cette formalisation vient de ce que la quasi-totalité des joueurs ne possèdent pas d’heuristiques utilisables pour les aider à choisir leur coup. Évidemment, nous voyons qu’il y a quatre lignes passant par le centre, mais peu d’entre nous savent qu’il y a quatre façons possibles d’atteindre 15 avec trois nombres différents dont l’un d’entre eux soit 5 (qui est au centre du carré magique). De même, il est évident que seulement deux lignes passent par chaque milieu des côtés alors que nous ignorons que seulement deux triplets dont la somme fait 15 contiennent un nombre impair différent de 5, par exemple pour 3 : (3, 5, 7) et (3, 4, 8). Il n’est pas non plus évident de voir que nous avons créé une fourchette quand nous avons les jetons 2, 5 et 6 et que les jetons 1, 3, 7 et 8 sont encore disponibles, ce qui correspond à la figure 3. Nous avons effectivement deux moyens de gagner et d’obtenir 15 soit en prenant le jeton 7 (2 + 6 + 7) soit en prenant le jeton 8 (2 + 5 + 8) qui sont tous deux disponibles ; l’adversaire peut au plus contrer une de ces menaces en prenant l’un de ces jetons. Le carré magique nous donne immédiatement toutes ces informations, mais s’il faut d’abord construire un carré magique pour jouer à ce jeu, ce n’est plus du tout un jeu facile.

86Le choix d’une bonne formalisation permet dans ce cas d’utiliser des heuristiques qui nous conduisent à utiliser des raisonnements efficaces. Par contre, avec une autre formalisation, nous sommes démunis et nous ne dégageons pas de raisonnement susceptible de nous aider à avancer sûrement vers le gain.

87Certains mathématiciens, comme Hadamard (1959), ont bien mis en évidence l’importance du choix de l’univers dans lequel ils décident de résoudre un problème. Il semble que pour beaucoup de théories, leurs recherches se soient effectuées dans une formalisation différente de celle utilisée dans le cadre de leurs publications et c’est dans ce formalisme non conventionnel qu’ils prouvent leurs théorèmes avant de convertir leurs preuves dans le formalisme de publication ; cela explique pourquoi les mathématiciens répugnent souvent à publier des résultats qu’ils sont pourtant certains d’avoir prouvés. Cette remarque a d’importantes conséquences pour l’enseignement des mathématiques : les élèves ne voient pas de prime abord comment prouver la majorité des théorèmes qui leur sont présentés parce qu’ils ne connaissent que le formalisme de publication. Le formalisme utilisé par le mathématicien ayant établi ce résultat a souvent l’avantage d’être associé à des heuristiques qui facilitent énormément le choix des raisonnements qui amèneront à la solution. Cela a également d’importantes conséquences pour les recherches sur les systèmes de démonstration de théorèmes : ils travaillent toujours dans le formalisme de publication et ils ne parviennent pas à prouver des résultats que les mathématiciens humains n’arriveraient pas non plus à prouver s’ils devaient travailler dans les mêmes conditions. Nous devons poursuivre des travaux comme ceux de D. Pastre (2002) pour mieux connaître ces formalismes cachés.

Monitorer la recherche de la solution

88Quand un expert est en train de résoudre un problème, il prend de temps en temps du recul. D’une part il vérifie que tout se déroule selon ses prévisions, d’autre part il s’assure qu’il ne trouve pas de résultats intermédiaires laissant à penser qu’il a fait une erreur. Par exemple, si nous trouvons une probabilité plus grande que 1, il est certain qu’il y a une erreur quelque part. Ce monitoring a donc deux aspects : contrôler le bon déroulement de la recherche de la solution et découvrir le plus rapidement possible les erreurs faites. Le monitoring est un raisonnement non sur le problème, mais sur la façon dont se déroule la résolution du problème. Ce contrôle peut s’effectuer aussi à l’aide de méta-raisonnements.

89Considérons d’abord la question du contrôle de la recherche de la solution. Une étude de Schoenfeld (1985) sur des humains résolvant des problèmes de mathématiques a montré qu’il existe trois catégories principales de sujets. Les novices commencent par partir dans une direction sans réfléchir à l’éventualité d’autres directions intéressantes, ils continuent un certain temps dans cette direction, puis l’abandonnent sans vraiment examiner la situation finale pour prendre aussitôt de façon aussi irrationnelle une autre direction. Dans certains cas, ils sont sur le point de trouver la solution au moment où ils abandonnent. Il n’est pas étonnant que les résultats de cette « chasse aux oies sauvages » soient très mauvais.

90La deuxième catégorie est formée par les experts du domaine. Ils examinent l’énoncé, en déduisent un plan de résolution et l’exécutent étape par étape en allant ainsi directement à la solution. Ce comportement est impressionnant par son efficacité, mais il faut beaucoup de temps avant de devenir expert et un expert ne l’est que dans un nombre limité de domaines.

91On pourrait appeler les sujets de la troisième catégorie des méta-experts, car sans être experts du domaine concerné, ils sont experts en résolution de problèmes ; ils pratiquent en particulier un monitoring très étroit de la recherche de la solution. Ils commencent par évaluer les diverses voies possibles, ils raisonnent pour choisir celle qui paraît la meilleure et font des prédictions sur ce qui doit se passer. Ils regardent ensuite régulièrement si tout se passe comme prévu et, sinon, ils examinent pourquoi et peuvent éventuellement décider de changer de direction en tenant compte de ce qu’ils viennent d’observer. Ces sujets ne sont pas aussi performants que les experts, mais ils ont de bonnes performances dans tous les domaines. De toutes les façons, cette phase est indispensable avant de devenir un expert d’un domaine particulier.

92Actuellement, les systèmes d’I.A. manquent par trop souvent de possibilités de monitoring. Des programmes de démonstration de théorèmes démontrent des théorèmes sans intérêt à partir desquels ils démontrent de nouveaux théorèmes encore moins intéressants, et cela peut durer longtemps. Il faut avoir écrit un jour un programme de démonstration de théorèmes mal conçu pour se rendre compte de l’incroyable nombre de théorèmes qui existent dans toute théorie mathématique ! Seul un contrôle dynamique de l’évolution de la résolution permet de maîtriser ce phénomène.

93Par ailleurs, le monitoring possède un deuxième intérêt ; il vérifie l’absence d’erreur apparente dans les raisonnements ou dans les données. En effet, les études sur les humains en train de résoudre des problèmes (Allwood 1984) ont montré que plus une erreur est trouvée rapidement après qu’elle s’est produite et plus on a de chances d’en trouver la cause ; c’est le cas quand les phases de monitoring sont fréquentes. Savoir retrouver des erreurs est une expertise : les êtres humains qui résolvent bien les problèmes font presque autant d’erreurs que ceux qui les résolvent mal, mais ils savent mieux les trouver et les corriger. Il est inévitable de faire des erreurs, aussi bien pour l’homme que pour les systèmes artificiels, vouloir les éviter totalement est une utopie ; il faut donc pouvoir vivre avec. Pour cela, nous pourrons utiliser des méta-raisonnements afin d’analyser les raisonnements que nous avons effectués et les résultats obtenus en vue d’y déceler des anomalies, signes d’erreurs possibles. Les bons experts humains ont ainsi une grande méta-expertise pour cette activité très complexe ; un livre (Cipra 1985) décrit uniquement des méta-raisonnements qui permettent de trouver ses erreurs en calcul intégral, et il a la taille d’un traité de calcul intégral.

Conclusion

94Il y a une trentaine d’années, les joueurs d’échecs s’amusaient bien en parlant des coups complètement stupides joués par les programmes jouant à ce jeu. Ce n’est plus le cas actuellement : un programme dû à Guid et Bratko (2006) a même servi de juge pour comparer la force de tous les champions du monde d’échecs en appréciant la qualité des coups qu’ils avaient joués au cours de leurs matchs pour le titre. Le développement combinatoire d’arborescences énormes apporte une qualité de jeu qui dépasse celle des meilleurs humains, et cette supériorité va encore progresser dans les prochaines années.

95De la même façon, les programmes qui utilisent des raisonnements restent très sous-estimés actuellement. Nous ignorons trop souvent que la solution trouvée par un système d’I.A. qui raisonne peut se révéler parfois plus élégante et plus claire que celle que nous avons nous-mêmes trouvée. Ces systèmes obtiennent parfois de très belles solutions, bien plus courtes que les meilleures solutions d’origine humaine. Cela se produit quand nous avons su leur donner un bon éventail des raisonnements utiles dans un domaine et une façon efficace de s’en servir. Il faut nous attendre un jour à avoir la même surprise que les joueurs d’échecs : les systèmes d’I.A. obtiendront des résultats d’une qualité au moins égale à celle de nos solutions, et en général bien meilleure. Ils y arriveront parce que grâce à leur vitesse, ils pourront tester bien plus de raisonnements que nous. Comme on ne garde à la fin que les raisonnements utiles, il est normal de parvenir à de meilleures solutions. Mais pour atteindre ce but, ces systèmes ont pour le moment besoin de nous : nous devons analyser les raisonnements dont nous nous servons ainsi que leurs modes d’emploi afin de les leur apporter. Il est d’ores et déjà possible de générer automatiquement des modes d’emploi efficaces, il faudra plus de temps pour que les systèmes trouvent eux-mêmes de nouvelles méthodes de raisonnement.

96Ces systèmes pourront nous être utiles en explicitant des méthodes de raisonnement et leurs conditions d’utilisation, ce qui permettra en retour de mieux enseigner à des sujets humains la manière de résoudre des problèmes dans chaque domaine. Les experts humains sont souvent incapables de transmettre à leurs élèves toutes les informations qu’ils utilisent parce qu’ils ne les connaissent pas eux-mêmes. L’enseignement sera mieux assuré le jour où les raisonnements - et surtout leur mode d’emploi - seront davantage explicités.

97Le progrès à long terme pour de tels systèmes reposera sur le méta-raisonnement. Nous ne faisons pas ainsi que déplacer le problème, l’avantage du méta-raisonnement est que ses règles s’appliquent à des raisonnements dans les domaines les plus variés, il suffit donc de les collecter une seule fois pour être opérationnel dans de nombreux domaines.

98Toutefois, il restera des problèmes où les systèmes d’I.A. utiliseront comme nous des méthodes qui ne reposent pas sur une suite de raisonnements mais sur la prise en compte simultanée d’une multitude de facteurs, ce qui les conduira à des décisions impossibles à expliquer simplement. Il restera aussi des problèmes où le raisonnement autre que la combinatoire n’apporte aucun gain sensible ; ces systèmes devront alors être assez méta-intelligents pour se rendre compte de l’absence de solution intelligente demandant peu d’étapes. La meilleure façon de résoudre le problème est alors d’écrire intelligemment un programme combinatoire qui engendrera le plus rapidement possible une immense arborescence. Mais le système intelligent qui crée un tel programme doit toujours méta-raisonner pour rendre ce programme efficace.

99À très long terme, les systèmes artificiels capables de raisonner trouveront des résultats d’une qualité nettement supérieure à celle obtenue par les meilleurs spécialistes humains parce qu’ils possèdent déjà une énorme supériorité sur nous : leur rapidité. Ils peuvent donc exercer une méta-combinatoire sur les raisonnements utilisés de manière bien plus poussée que nous pouvons le faire nous-mêmes à cause de notre lenteur. Mais cela nous demande de recueillir au préalable ces méthodes de raisonnement, et aussi d’associer à chaque méthode des conditions pour éviter leur utilisation dans des situations où elles n’ont aucune chance de succès. Pour cela, la collaboration avec tous ceux qui étudient le fonctionnement humain est essentielle.

Bibliographie

Références bibliographiques

Allwood C. 1984. « Error detection processes in statistical problem solving ». Cognitive Science, 8 : 413-437.

Bartlett F. 1958. Thinking An Experimental and Social Study. New York, Unwin University Books.

Cipra B. 1985. Erreurs et comment les trouver avant le prof, techniques de calcul différentiel et intégral. Paris, InterÉditions.

Guid M., Bratko I. 2006. « Computer analysis of world chess champions ». ICGA Journal, 29 : 65-73.

Hadamard J. 1959. Essai sur la psychologie de l’invention dans le domaine mathématique. Paris, Librairie Scientifique Albert Blanchard.

Kaplan C., Simon H. 1990. « In search of insight ». Cognitive Psychology, 22 : 374-419.

Laurière J.-L. 1976. Un langage et un programme pour énoncer et résoudre des problèmes. Thèse de l’université Paris 6.

Pastre D. 2002. « L’utilisation de dessins en résolution de problèmes ». Revue d’intelligence artificielle, 16 : 123-164.

Pinson S. 1989. « Une évaluation multi-expert du risque entreprise : le système CREDEX ». Technique et science informatiques, 8 : 127-143.

Pitrat J. 2006. « Meta-explanation in a constraint satisfaction solver ». International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU). Paris : 1118-1125.

Pitrat J. 2009. Artficial Beings. The Conscience of a conscious Machine. ISTE et Wiley.

Schoenfeld A. 1985. Mathematical Problem Solving. Orlando, Academic Press.

Siklóssy L., Roach J. 1973. « Proving the impossible is impossible is possible ». International Joint Conference on Artificial Intelligence, Standford.

Simon H. 2004. Les sciences de l’artificiel. Paris, Folio essais. Gallimard.

Table des illustrations

Légende Fig. 1 - Emplacement et contenu des cases d’un carré magique de taille 3.
URL http://books.openedition.org/editionsmsh/docannexe/image/13896/img-1.jpg
Fichier image/jpeg, 43k
Légende Fig. 2 – Deux présentations du problème de l’échiquier tronqué : à gauche sans aide : à droite avec aide.
URL http://books.openedition.org/editionsmsh/docannexe/image/13896/img-2.jpg
Fichier image/jpeg, 133k
Légende Fig. 3 - Un jeu de « tic-tac-toe » ; les ronds perdent la partie, quoi qu’ils jouent.
URL http://books.openedition.org/editionsmsh/docannexe/image/13896/img-3.jpg
Fichier image/jpeg, 32k

Auteur

Laboratoire d’informatique de Paris 6
Université Pierre-et-Marie Curie, Paris.

© Éditions de la Maison des sciences de l’homme, 2011

Conditions d’utilisation : http://www.openedition.org/6540

Cette publication numérique est issue d’un traitement automatique par reconnaissance optique de caractères.
Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search