Qu’est-ce que le problème du cadre en IA, et pourquoi McCarthy et Hayes l’ont-ils appelé un problème?

Si vous prenez votre téléphone pour chercher le numéro d’un ami, vous ne vous arrêtez pas pour vérifier que vous possédez toujours le téléphone, que votre ami habite toujours à la même adresse ou que la cuisine est toujours de la même couleur. Vous savez simplement que chercher quelque chose ne change pas ces choses-là. Un ordinateur qui raisonne avec une logique stricte ne le sait pas. À moins qu’on le lui dise, il n’a aucune raison de supposer que quoi que ce soit survit à une action. Ce vide, c’est le problème du cadre.

D’où vient le nom

Le terme apparaît pour la première fois dans un long article de John McCarthy et Patrick J. Hayes, « Some Philosophical Problems from the Standpoint of Artificial Intelligence » (Quelques problèmes philosophiques du point de vue de l’intelligence artificielle). Il a été publié en 1969 dans Machine Intelligence 4, un volume dirigé par Bernard Meltzer et Donald Michie et imprimé par Edinburgh University Press. McCarthy, l’un des fondateurs du domaine, travaillait à l’Université Stanford.

Le point de départ de l’article est qu’un programme censé agir intelligemment dans le monde doit porter une certaine image générale de ce monde, et que construire une telle image oblige les chercheurs en IA à affronter de vieilles questions philosophiques sur la connaissance, la cause et la capacité. Les auteurs voulaient un programme qui décide quoi faire en démontrant, dans un langage formel, qu’un plan donné atteindra son but.

Les outils : situations et fluents

Pour y arriver, McCarthy et Hayes ont proposé un cadre de travail qu’on appelle aujourd’hui le calcul des situations. Trois idées le portent :

• Une situation est un instantané du monde à un moment donné.
• Un fluent est tout fait dont la valeur dépend de la situation, comme « Pat a un téléphone » ou « il pleut ».
• Une action fait passer d’une situation à la suivante, et des règles disent quels fluents sont vrais ensuite.

L’article développe un exemple très terre à terre : une personne qui entre en conversation avec une autre en cherchant son numéro dans l’annuaire téléphonique, puis en le composant. Les auteurs ont écrit des règles pour chercher un numéro et pour faire un appel, puis ont tenté de prouver que le plan fonctionne.

Cela n’a pas fonctionné. Les règles ne disaient rien sur la question de savoir si la personne qui appelle a toujours le téléphone, ou si l’ami est toujours chez lui, une fois l’action de recherche terminée. En logique, ce qui n’est pas énoncé ne peut pas être supposé. Pour sauver la preuve, les auteurs ont dû ajouter une règle disant, en somme, que chercher un numéro ne touche pas à ces faits. Ils ont admis que ces hypothèses supplémentaires étaient « tout à fait ad hoc », c’est-à-dire ajoutées pour ce seul cas.

Pourquoi il devient ingérable

Dans la section intitulée « The Frame Problem » (le problème du cadre), ils ont détaillé le coût. S’il y a un certain nombre d’actions et un certain nombre de fluents, il peut falloir un énoncé distinct « cette action ne change pas ce fait » pour presque chaque paire. Voici le calcul pour un modeste robot domestique :

Les règles utiles, celles qui portent sur ce que fait réellement chaque action, augmentent lentement. Les règles « rien d’autre n’a changé », que les logiciens appellent axiomes de cadre, augmentent comme le produit. Murray Shanahan, dans la Stanford Encyclopedia of Philosophy, en donne une illustration simple : des règles pour peindre un objet et pour le déplacer ne permettent pas, à elles seules, à un système logique de conclure que déplacer l’objet ne change pas sa couleur.

Comment on a tenté de le résoudre

McCarthy et Hayes ont eux-mêmes esquissé une issue : regrouper les fluents dans un « cadre », comme les variables d’un programme informatique, et décrire chaque action seulement par ceux qu’elle change, tous les autres étant présumés rester tels quels. Les constructeurs de robots ont pris une voie semblable. Le planificateur du robot Shakey du SRI, appelé STRIPS, décrivait chaque action par ses préconditions, les faits qu’elle supprime et les faits qu’elle ajoute, et supposait que tout le reste demeurait en place. L’IEEE décrit cette conception comme une solution pratique au problème du cadre.

Les logiciens voulaient quelque chose de plus rigoureux. La règle empirique sous-jacente, selon laquelle une action laisse un fait intact à moins d’avoir une raison de penser le contraire, porte le nom de « loi d’inertie du sens commun ». La logique classique a du mal à l’exprimer, parce qu’y ajouter de l’information nouvelle ne peut jamais annuler une conclusion antérieure, une propriété appelée monotonie. Cela a mené à de nouvelles logiques « non monotones » dans lesquelles des conclusions peuvent être retirées, dont la circonscription de McCarthy lui-même, dans les années 1980. Les progrès ont été lents, et des casse-têtes comme le problème du tir de Yale (Yale shooting problem) ont montré à quel point les nouvelles logiques donnaient facilement des réponses étranges. En 2016, Shanahan jugeait le problème technique étroit plus ou moins résolu.

Les philosophes, pendant ce temps, ont repris le nom et l’ont élargi. Daniel Dennett et Jerry Fodor se sont demandé comment n’importe quel être pensant, humain ou machine, décide lesquelles de ses nombreuses croyances revérifier après avoir agi. Cette question plus large de la pertinence est loin d’être réglée.

Les systèmes d’IA d’aujourd’hui font-ils encore face au problème du cadre?

Sous sa forme d’origine, il concerne les systèmes qui stockent les connaissances sous forme d’énoncés logiques explicites, et ces systèmes disposent maintenant de solutions qui fonctionnent. Les réseaux de neurones qui dominent les manchettes sur l’IA en 2019 n’écrivent aucun axiome de cadre; ils apprennent des régularités à partir de données, si bien que le problème ne se présente pas sous la même forme.

La version plus large, elle, n’a pas disparu. Une voiture autonome, un robot d’entrepôt ou un programme de planification doit encore décider quelles parties du monde une action pourrait toucher et lesquelles il peut ignorer sans danger. Se tromper dans un sens comme dans l’autre coûte cher : vérifiez trop peu et le système rate un changement qui compte; vérifiez trop et il n’agit jamais. McCarthy et Hayes ont donné un nom à ce dilemme en 1969, et il demeure l’une des façons les plus claires d’expliquer pourquoi le sens commun est si difficile à construire.