La logique et la représentation des connaissances

L’essentiel de ce site porte sur l’apprentissage à partir de données - estimer des quantités incertaines, et rester rigoureux sur le degré de cette incertitude. Il existe en intelligence artificielle une tradition plus ancienne qui pose une autre question : étant donné ce que je sais déjà, qu’est-ce qui doit être vrai ?

Ce n’est pas une question statistique. Elle admet une réponse définie, et la machinerie qui la calcule est la logique.

A. Bases de connaissances, modèles, conséquence logique

Une base de connaissances (BC) est un ensemble de phrases affirmées vraies au sujet du monde. Un modèle est une assignation complète de valeurs de vérité à chaque proposition - un monde possible entièrement spécifié. Une phrase est vraie dans certains modèles et fausse dans d’autres, et l’on note $M(\alpha)$ l’ensemble des modèles où $\alpha$ est vraie.

La relation centrale est la conséquence logique :

$\text{KB} \models \alpha$ - lu « la BC implique $\alpha$ » - signifie que $\alpha$ est vraie dans tout modèle où la BC est vraie. De façon équivalente, $M(\text{KB}) \subseteq M(\alpha)$.

L’idée est familière en arithmétique, où $x = 0$ implique $xy = 0$ : dans tout monde où $x$ est nul, $xy$ l’est aussi, quel que soit $y$.

La conséquence logique est un fait de signification, non d’algorithme. Russell et Norvig formulent la distinction de façon mémorable : voyez les conséquences de la BC comme une meule de foin et $\alpha$ comme une aiguille. La conséquence logique, c’est que l’aiguille est dans la meule ; l’inférence, c’est de l’y trouver.

B. Dérouler une conséquence à la main

Prenons le cadre standard. Un agent explore une grille de cavernes dont certaines contiennent des puits. Une case est venteuse exactement quand une case adjacente contient un puits. L’agent démarre en $[1,1]$, ne sent aucun vent, se déplace en $[2,1]$, et sent du vent.

Trois cases sont en jeu : $[1,2]$, $[2,2]$ et $[3,1]$. Chacune contient ou non un puits : il y a donc $2^3 = 8$ mondes possibles.

La BC dit deux choses :

• Pas de vent en $[1,1]$. Ses voisines sont $[1,2]$ et $[2,1]$, donc aucune ne contient de puits. En particulier $[1,2]$ est sans puits.
• Du vent en $[2,1]$. Ses voisines sont $[1,1]$, $[2,2]$ et $[3,1]$. L’agent se tenait sans risque en $[1,1]$, donc au moins l’une de $[2,2]$, $[3,1]$ contient un puits.

Énumérons les huit et marquons là où la BC tient :

Exactement trois modèles survivent. Testons maintenant deux conclusions candidates.

$\alpha_1$ : « il n’y a pas de puits en $[1,2]$ ». Vraie dans les trois modèles survivants. Donc $\text{KB} \models \alpha_1$ - l’agent peut s’y rendre sans risque.

$\alpha_2$ : « il n’y a pas de puits en $[2,2]$ ». Fausse dans deux des trois. Donc $\text{KB} \not\models \alpha_2$. Notez soigneusement ce que cela ne dit pas : cela n’établit pas non plus qu’il y a un puits en $[2,2]$, puisqu’un modèle survivant n’en contient pas. La conclusion honnête est que les indices ne tranchent pas.

Cette procédure - énumérer tous les modèles, vérifier que $\alpha$ tient partout où la BC tient - est la vérification de modèles, et c’est une transcription directe de la définition de la conséquence logique.

Les huit mondes sont dans la figure ci-dessous, les trois qui survivent à la base de connaissances étant marqués. Choisissez une conclusion et le tableau marque quelque chose de plus utile encore : chaque monde survivant où cette conclusion est fausse. Pour « pas de fosse en [2,2] » il y en a deux, et chacun est un monde parfaitement compatible avec tout ce qui est su - c’est cela que signifie « non impliquée », et c’est pourquoi affirmer le contraire serait tout aussi peu fondé. Désactivez une phrase de la base et regardez l’ensemble survivant grandir.

C. Correction, complétude et coût

Dès lors que l’inférence est une procédure et non une définition, deux propriétés comptent. Un algorithme est correct (ou préservant la vérité) si tout ce qu’il dérive est réellement une conséquence : il n’invente jamais de conclusions. Il est complet s’il peut dériver tout ce qui est conséquence : il n’en manque jamais une.

La vérification de modèles est les deux. Elle est correcte parce qu’elle implémente directement la définition, et complète parce qu’il n’y a qu’un nombre fini de modèles et qu’elle les examine tous.

Le coût est le problème. Avec $n$ symboles propositionnels il y a $2^n$ modèles, si bien que la complexité en temps est $O(2^n)$ - la complexité en espace n’est que $O(n)$, l’énumération pouvant se faire en profondeur d’abord. Nos trois inconnues ont donné huit lignes ; trente en donneraient plus d’un milliard.

Ce n’est pas non plus une simple faiblesse d’un algorithme naïf. Décider la conséquence propositionnelle est co-NP-complet : aucune méthode connue n’évite donc un comportement exponentiel dans le pire cas. Les systèmes pratiques emploient en conséquence des règles d’inférence qui dérivent des conclusions syntaxiquement au lieu d’énumérer des mondes - le modus ponens et ses proches - nettement plus rapides sur les problèmes typiques tout en restant corrects.

Voici l'une de ces règles voisines à l'œuvre : un démonstrateur par résolution, calculs apparents, sur une base de connaissances plus petite que celle ci-dessus. Elle contient la règle selon laquelle $[1,1]$ est venteuse exactement quand $[1,2]$ ou $[2,1]$ contient une fosse, $B_{1,1} \Leftrightarrow (P_{1,2} \lor P_{2,1})$, et la perception $\neg B_{1,1}$, sans aucune perception en $[2,1]$. La liste de clauses est cette base convertie en clauses, plus la requête niée, et chaque ligne en dessous est une résolvante, dans l'ordre où la recherche l'a produite. Demandez « pas de fosse en [1,2] » et la case vide apparaît ; demandez « une fosse en [1,2] » et la recherche sature sans elle, ce qui est une réponse et non un échec. Chaque requête est en outre tranchée une seconde fois en énumérant les huit mondes, sans une ligne de code commune, et la figure indique si les deux s'accordent.

D. Là où la logique propositionnelle s’épuise

Tout ce qui précède employait des propositions : des faits atomiques simplement vrais ou faux. C’est une limitation réelle, et elle apparaît dès que vous cherchez à énoncer quelque chose de général.

Pour exprimer « toutes les cases adjacentes à un puits sont venteuses » en propositionnel, vous devez écrire une phrase par case, et toutes les réécrire si la grille change de taille. La règle elle-même - ce que vous savez réellement - ne peut pas être énoncée. Le verdict de Russell et Norvig est net : la logique propositionnelle est un langage trop chétif pour représenter de façon concise la connaissance d’environnements complexes.

La différence est d’engagement ontologique - ce qu’un langage suppose de la nature de la réalité :

La logique du premier ordre suppose que le monde contient des objets dotés de relations. Cela achète des quantificateurs - $\forall$ (« pour tout ») et $\exists$ (« il existe ») - et avec eux, la généralité. La règle du vent devient une seule phrase quantifiée sur toutes les cases, vraie quelle que soit la taille de la grille.

L’inférence s’élève en conséquence. Le modus ponens généralisé applique la règle familière à des phrases contenant des variables, en trouvant d’abord une substitution $\theta$ qui fait coïncider les prémisses - un procédé appelé unification - puis en appliquant $\theta$ à la conclusion. Un raisonnement qu’il fallait répéter par objet se fait une fois, schématiquement.

C'est un algorithme : la figure ci-dessous l'exécute donc, argument par argument, chaque liaison étant notée au moment où elle est faite, et les deux termes imprimés avec l'unificateur appliqué, de sorte que « identiques » se lise au lieu de s'affirmer. Deux paires qui échouent l'accompagnent. Le test d'occurrence est celui qu'il faut essayer : unifier x avec Mother(x) n'a pas de solution, et une implémentation qui l'omet construit un terme infini au lieu de le dire.

E. Pourquoi cela compte encore

Il serait facile de ranger tout cela dans l’histoire. Ce serait une erreur, pour trois raisons.

Certaines connaissances ne sont pas statistiques. Contraintes, règles, définitions et politiques s’énoncent naturellement comme des phrases qui tiennent ou échouent, et les apprendre à partir d’exemples alors qu’on pourrait simplement les écrire est coûteux et peu fiable.

Les conclusions logiques viennent avec des garanties. Une procédure d’inférence correcte ne renvoie jamais de mauvaise réponse, et elle peut montrer son travail sous forme d’une chaîne de règles appliquées. Un modèle appris offre une probabilité et, d’ordinaire, aucune dérivation. Là où la correction doit être certifiée plutôt qu’estimée, cette différence est décisive.

La question de la représentation n’a pas disparu. Comment encoder ce qu’un système sait pour qu’il puisse le combiner et raisonner dessus est la même question, que le contenu soit des axiomes écrits à la main ou extrait d’un corpus. Ontologies, graphes de connaissances, schémas typés et solveurs de contraintes descendent tous de cette ligne de travaux.

La position réaliste est que les deux traditions répondent à des questions différentes. L’apprentissage traite la perception et l’incertitude ; la logique traite la structure et la conséquence garantie. Les systèmes qui ont besoin des deux finissent en général avec les deux.

À retenir

• Une base de connaissances est un ensemble de phrases affirmées ; un modèle est un monde possible entièrement spécifié.
• $\text{KB} \models \alpha$ signifie que $\alpha$ tient dans tout modèle où la BC tient - $M(\text{KB}) \subseteq M(\alpha)$.
• La conséquence logique est un fait sémantique ; l’inférence en est la recherche - l’aiguille et la meule de foin.
• Dans l’exemple traité, 8 mondes possibles se réduisent à 3 compatibles avec les percepts, impliquant « pas de puits en $[1,2]$ » mais laissant $[2,2]$ réellement indéterminée.
• Ne pas impliquer $\alpha$ n’est pas impliquer $\neg\alpha$.
• Correct veut dire jamais faux ; complet veut dire ne rien manquer. La vérification de modèles est les deux, en temps $O(2^n)$ et espace $O(n)$.
• La conséquence propositionnelle est co-NP-complète : le coût exponentiel dans le pire cas est intrinsèque, non un artefact d’un algorithme naïf.
• La logique propositionnelle ne peut pas énoncer de règles générales ; la logique du premier ordre s’engage sur des objets et des relations, gagnant des quantificateurs et une inférence relevée.

La suite

Pour le pendant probabiliste - raisonner quand les faits ne sont pas simplement vrais ou faux mais tiennent avec un certain degré de croyance - voyez Le théorème de Bayes et la mise à jour des croyances, et pour la couche décisionnelle bâtie par-dessus, Les processus de décision markoviens.