Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts

La base de connaissances, la conséquence logique et la vérification de modèles, les clauses de Horn, le chaînage avant et arrière, la résolution, Prolog et les systèmes experts, de MYCIN aux graphes de connaissances — sur un petit système qui reconnaît un animal.

15 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 24 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Avant que les machines ne se mettent à apprendre à partir de données, on a essayé d’enseigner à la main l’intelligence artificielle : écrire ce que sait un expert sous forme de règles « si–alors » et laisser l’ordinateur en tirer des conclusions. C’est ainsi que sont nés les systèmes experts des années soixante-dix et quatre-vingt, qui diagnostiquaient des infections ou configuraient des ordinateurs sur commande. Puis ils se sont heurtés à leurs limites, et un hiver de l’intelligence artificielle est venu. Leurs idées n’ont pourtant pas disparu : elles vivent dans Prolog, dans les bases de connaissances derrière les moteurs de recherche et dans la vérification de ce qu’affirment les modèles de langage.

Cette partie fait suite à Logique et démonstrations, où vous trouverez les connecteurs, l’implication et le modus ponens.

1. La base de connaissances et le moteur d’inférence

Définition — base de connaissances

Une base de connaissances KB est un ensemble de phrases d’un langage formel (ici la logique propositionnelle) que le système tient pour vraies. Le système sait faire deux opérations avec elle : dire — ajouter à KB une nouvelle phrase — et demander — savoir si une phrase α découle de KB.

Cette approche est dite déclarative. Vous ne programmez pas la démarche pour arriver à la réponse : vous écrivez seulement ce qui est vrai, et la démarche est toujours le même moteur d’inférence. Vous voulez apprendre quelque chose de nouveau au système ? Vous ajoutez une phrase, vous ne réécrivez rien.

Tout au long de cette partie, nous serons accompagnés d’un petit système expert inspiré du ZOOKEEPER de manuel de Patrick Winston : douze règles qui permettent de reconnaître un animal d’après ses propriétés observées. Nous avons observé un animal qui a des poils, des crocs et des griffes, est fauve et rayé de noir. Qu’est-ce que c’est ?

2. Conséquence logique et modèles

Définition — modèle et conséquence logique

Un modèle d’une phrase est une affectation des symboles propositionnels dans laquelle la phrase est vraie. L’ensemble des modèles d’une phrase α est noté M(α).

α découle de KB (en est une conséquence logique), ce qu’on écrit KB ⊨ α, si et seulement si M(KB) ⊆ M(α) : dans tout modèle de la base de connaissances, α est vraie aussi.

KB ⊨ α ⇔ M(KB) ⊆ M(α)

KB ⊨ α

ce que l’on demande : α découle-t-elle de la base ? Le symbole ⊨ parle de vérité dans des mondes, pas de notre capacité à déduire quelque chose

M(KB)

les mondes que la base admet : les affectations dans lesquelles toutes ses phrases sont vraies à la fois (la base est leur conjonction) ; les autres mondes ne nous intéressent pas, la base affirme qu’ils ne se sont pas produits

⊆

inclusion : dans aucun monde admis α ne peut manquer ; un seul contre-exemple suffirait pour que α ne découle pas

M(α)

les mondes où α est vraie ; il peut y en avoir beaucoup plus : α peut aussi être vraie là où la base ne l’est pas

La façon la plus directe de vérifier une conséquence logique est la vérification de modèles (model checking) : parcourir toutes les affectations, garder celles où toute la base est vraie et regarder si la question y est vraie aussi. Notre base a 24 symboles propositionnels (« a des poils », « mammifère », « tigre »…), il y a donc 2²⁴ = 16 777 216 affectations. Parmi elles, 13 440 sont des modèles de la base, et « tigre » est vrai dans tous. La réponse est oui, mais au prix de seize millions de lignes d’une table de vérité. Chaque symbole supplémentaire double le nombre ; pour une base de plusieurs centaines de symboles, le calcul ne finirait jamais.

Exemple — vérification de modèles sur trois symboles

Base KB = {pleut ⇒ mouillé, mouillé ⇒ glissant, pleut}, question α = glissant. Trois symboles donnent 2³ = 8 affectations (1 = vrai, 0 = faux) ; l’implication p ⇒ q n’est fausse que pour p = 1, q = 0.

pleut	mouillé	glissant	pleut ⇒ mouillé	mouillé ⇒ glissant	KB
0	0	0	1	1	0
0	0	1	1	1	0
0	1	0	1	0	0
0	1	1	1	1	0
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Toute la base n’est vraie que dans la dernière ligne, donc |M(KB)| = 1. Dans cette ligne, « glissant » est vrai aussi : M(KB) ⊆ M(glissant), et donc KB ⊨ glissant. L’algorithme a parcouru 8 lignes et évalué dans chacune les 3 phrases de la base ; en général, la vérification de modèles coûte O(2ⁿ · |KB|).

Exemple — d’où viennent les 13 440 modèles

Dans tout modèle de la base, les cinq faits observés sont vrais, et les règles R1, R6 et R9 imposent alors « mammifère », « carnivore » et « tigre ». Ces 8 symboles sont vrais de façon fixe. Les 16 autres se répartissent en groupes qu’aucune règle ne relie entre eux, et les nombres de leurs affectations se multiplient :

• « donne du lait » (R2 est satisfaite, mammifère est vrai) et « mange de la viande » (R5 est satisfaite, carnivore est vrai) : libres, 2 · 2 = 4 ;
• « a des taches sombres », « guépard » avec la règle R8 : trois affectations ; les taches sans guépard sont interdites ;
• « a des sabots », « ongulé », « a un long cou », « girafe », « zèbre » avec R7, R10, R11 : si ongulé est faux, les sabots doivent l’être aussi et les trois autres symboles sont libres (8 possibilités) ; s’il est vrai, zèbre doit être vrai, les sabots sont libres et le cou avec la girafe ont 3 possibilités (2 · 3 = 6) ; au total 14 ;
• le groupe des oiseaux « a des plumes », « vole », « pond des œufs », « oiseau », « ne vole pas », « nage », « manchot » avec R3, R4, R12 : sans oiseau, ni les plumes, ni à la fois vole et œufs ne peuvent être vrais (3 possibilités), et les trois derniers symboles sont libres (8) : 24 ; avec oiseau, les plumes sont libres (2), vole et œufs libres (4), et des huit affectations de « ne vole pas, nage, manchot » seule 1, 1, 0 est interdite (7) : 56 ; au total 80.

En tout 4 · 3 · 14 · 80 = 13 440, exactement le nombre compté par la vérification de modèles. Et dans chacun d’eux tigre est vrai, puisqu’il fait partie des symboles vrais de façon fixe.

3. Inférence : correcte et complète

Au lieu de parcourir des mondes, on peut manipuler des phrases : à partir de celles qu’on a, en fabriquer de nouvelles selon des règles d’inférence comme le modus ponens. C’est aussi ce que fait l’être humain.

Définition — inférence, correction, complétude

On écrit KB ⊢ α quand α peut être obtenue à partir de KB par un nombre fini d’applications de règles d’inférence.

Une procédure d’inférence est correcte si KB ⊢ α entraîne KB ⊨ α : elle ne déduit que ce qui découle vraiment.

Elle est complète si KB ⊨ α entraîne KB ⊢ α : elle déduit tout ce qui découle.

Définition — clause de Horn

Une clause de Horn est une disjonction de littéraux dont au plus un est positif. Une clause avec exactement un littéral positif est définie et peut s’écrire comme une règle

p₁ ∧ p₂ ∧ … ∧ p_k ⇒ q,

où p₁, …, p_k sont les prémisses et q la conclusion. Pour k = 0, c’est un fait q.

Pourquoi « une disjonction avec au plus un littéral positif » est-elle la même chose qu’une règle ? L’implication A ⇒ q est équivalente à ¬A ∨ q, et d’après la loi de De Morgan, ¬(p₁ ∧ … ∧ p_k) est la même chose que ¬p₁ ∨ … ∨ ¬p_k :

¬p₁ ∨ … ∨ ¬p_k ∨ q ≡ (p₁ ∧ … ∧ p_k) ⇒ q

¬p₁ ∨ … ∨ ¬p_k

les littéraux négatifs de la clause ; ensemble, ils disent « une des prémisses n’est pas vraie », et c’est exactement la négation de la conjonction des prémisses

(p₁ ∧ … ∧ p_k)

les prémisses de la règle : la disjonction de littéraux négatifs est devenue une condition grâce à De Morgan ; aucune ne peut être négative, sinon la règle dirait « si … n’est pas vrai »

q

le seul littéral positif, la conclusion ; s’il y en avait deux positifs, on obtiendrait « alors q ou r », et le moteur d’inférence ne saurait pas lequel ajouter

⇒

la clause est vraie quand une des prémisses n’est pas vraie ou quand la conclusion l’est : c’est la définition de l’implication ; la forme de règle ne fait que lire autrement la même disjonction

4. Chaînage avant

Algorithme — chaînage avant

1. Chaque règle retient combien de ses prémisses ne sont pas encore connues. Mettez tous les faits dans l’agenda.
2. Prenez un symbole dans l’agenda. S’il a déjà été traité, passez au suivant.
3. Pour chaque règle qui l’a parmi ses prémisses, diminuez le compteur de 1. S’il tombe à 0, la règle se déclenche : ajoutez sa conclusion à l’agenda.
4. Recommencez jusqu’à ce que l’agenda soit vide.

Théorème. Pour une base de clauses de Horn définies, le chaînage avant est correct et complet pour les symboles propositionnels : il déduit exactement ceux qui découlent de KB. Il s’exécute en un temps linéaire par rapport à la taille de la base.

Dès la première observation, « a des poils », la règle R1 se débloque et ajoute « mammifère » à la fin de l’agenda. Les quatre autres observations ne déclenchent rien pour l’instant, mais elles font baisser les compteurs. Quand vient le tour de mammifère, il débloque R6 (les crocs et les griffes sont déjà connus) : « carnivore » apparaît. Carnivore débloque R9, et nous avons un tigre. En huit étapes, sans millions de lignes. La règle R5 (« un mammifère qui mange de la viande est un carnivore ») ne s’est jamais déclenchée : nous ne savons pas si l’animal mange de la viande, et nous n’avons pas besoin de le savoir.

def dopredne(fakta, pravidla):
    chybi = {r.id: len(r.kdyz) for r in pravidla}
    zname, agenda = set(), list(fakta)
    while agenda:
        p = agenda.pop(0)
        if p in zname:
            continue
        zname.add(p)
        for r in pravidla:
            if p in r.kdyz:
                chybi[r.id] -= 1
                if chybi[r.id] == 0:          # toutes les prémisses sont connues
                    agenda.append(r.pak)
    return zname

Le cœur de l’algorithme est le compteur de chaque règle r de prémisses P(r) :

manque(r) = |P(r)| − |P(r) ∩ Connus|

manque(r)

combien de prémisses nous ne connaissons pas encore ; à manque(r) = 0, la règle se déclenche ; grâce au nombre, le moteur le remarque sans parcourir la liste des prémisses

|P(r)|

la valeur initiale : au départ nous ne savons rien, toutes les prémisses manquent

|P(r) ∩ Connus|

les prémisses déjà traitées ; chaque symbole traité diminue de 1 le compteur de chaque règle où il apparaît, et il n’est traité qu’une fois, donc rien n’est compté deux fois

Comment les compteurs baissent pendant notre exécution (après le traitement du symbole de la ligne ; en gras le zéro, c’est-à-dire le déclenchement) :

R5 s’arrête à un (il manque « mange de la viande »), et R8, celle du guépard, aussi (il manque « a des taches sombres »). Les autres règles ne figurent pas dans le tableau ; leurs prémisses ne sont pas apparues du tout pendant l’exécution, ou seulement en partie.

Théorème — le chaînage avant est correct et complet (démonstration)

Correction. Chaque symbole déduit provient du déclenchement d’une règle dont toutes les prémisses étaient déjà connues. Dans tout modèle de la base, les faits sont vrais et (par récurrence sur l’ordre de déduction) les symboles déduits auparavant aussi, donc d’après la règle la nouvelle conclusion est vraie elle aussi : c’est le modus ponens.

Complétude. À la fin, prenons l’affectation m : vrai pour les symboles déduits (et les faits), faux pour tous les autres. C’est un modèle de la base : si une règle p₁ ∧ … ∧ p_k ⇒ q n’était pas vraie dans m, tous les p_i seraient déduits et q non ; mais alors le compteur de la règle serait tombé à zéro et q aurait été déduit. Si donc q découle de la base, il est vrai dans le modèle m, et il a donc été déduit. ∎

Le modèle m est le « plus modeste » : il ne croit que ce qu’il doit croire. Pour notre base, c’est l’affectation où sont vrais exactement les 5 observations, mammifère, carnivore et tigre.

5. Chaînage arrière

Algorithme — chaînage arrière

Démontre le but q :

• si q est un fait connu, il est démontré ;
• sinon, pour chaque règle p₁ ∧ … ∧ p_k ⇒ q, essayez de démontrer l’un après l’autre tous les p_i ; si cela réussit pour une règle, q est démontré ;
• si aucune règle ne réussit, la démonstration a échoué.

Pour des clauses de Horn définies, le chaînage arrière est correct et complet, et n’examine que les symboles liés au but.

def zpetne(cil, fakta, pravidla, cesta=()):
    if cil in fakta:
        return True                           # on le sait directement
    if cil in cesta:
        return False                          # cycle : le but se démontre lui-même
    for r in pravidla:
        if r.pak == cil:                      # OU : une règle suffit
            if all(zpetne(p, fakta, pravidla, cesta + (cil,))
                   for p in r.kdyz):          # ET : toutes les prémisses doivent réussir
                return True
    return False                              # on ne sait pas le démontrer

La fonction all s’arrête à la première prémisse qui échoue : c’est pourquoi, pour R5, rien d’autre n’est examiné après l’échec sur « mange de la viande ». La liste cesta (chemin) veille à ce que des règles comme « a ⇒ b, b ⇒ a » ne tournent pas en boucle.

L’algorithme a examiné 11 buts. Il a d’abord essayé de démontrer carnivore avec la règle R5 : il a démontré mammifère, mais a buté sur « mange de la viande ». Nous ne le savons pas ; il a donc abandonné R5 et essayé R6, qui a réussi. C’est là que le chaînage arrière est fort : il sait ce qui lui manque. À un tel moment, un système expert demande à l’utilisateur : « Cet animal mange-t-il de la viande ? » Toute la conversation avec un système expert n’est en fait que du chaînage arrière à voix haute.

Quand utiliser lequel ? Le chaînage avant convient quand des données arrivent et que vous voulez savoir ce qui en découle, par exemple pour surveiller une production. Le chaînage arrière, quand vous avez une question précise : un diagnostic, une requête dans une base de données. Si nous demandions « est-ce un zèbre ? », le chaînage arrière le réfuterait après avoir examiné seulement 5 buts : un zèbre est un ongulé, et notre animal n’a pas de sabots.

6. Résolution : l’inférence pour toute la logique

Les clauses de Horn ne suffisent pas à tout. La phrase « l’animal est un mammifère ou un oiseau » a un « ou » dans sa conclusion, et on ne peut pas l’écrire comme une règle. Pour des propositions quelconques, il existe une règle unique qui suffit à tout.

Définition — résolution

Les phrases sont mises en forme normale conjonctive : une conjonction de clauses, chacune étant une disjonction de littéraux. Règle de résolution : des clauses (A ∨ ℓ) et (B ∨ ¬ℓ), déduire (A ∨ B).

Démonstration par l’absurde : KB ⊨ α si et seulement si KB ∧ ¬α est insatisfiable. La résolution déduit de nouvelles clauses à partir de KB ∧ ¬α ; si elle déduit la clause vide, une contradiction est trouvée. Cette procédure est correcte et complète (Robinson, 1965).

( A ∨ ℓ ), ( B ∨ ¬ℓ ) ⊢ ( A ∨ B )

ℓ, ¬ℓ

littéraux complémentaires : dans chaque monde, exactement l’un d’eux est vrai, il ne satisfait donc pas l’une des clauses ; celle-ci doit être satisfaite par son reste. C’est pourquoi ℓ manque dans le résultat

A

le reste de la première clause : il est vrai chaque fois que ℓ est faux (alors seul A rend la première clause vraie)

B

le reste de la seconde clause : il est vrai chaque fois que ℓ est vrai (alors ¬ℓ est faux et B rend la seconde clause vraie)

Algorithme — mise en forme normale conjonctive

1. Éliminez les équivalences : remplacez α ⇔ β par (α ⇒ β) ∧ (β ⇒ α).
2. Éliminez les implications : remplacez α ⇒ β par ¬α ∨ β.
3. Repoussez les négations jusqu’aux symboles : ¬¬α ≡ α, ¬(α ∧ β) ≡ ¬α ∨ ¬β, ¬(α ∨ β) ≡ ¬α ∧ ¬β (De Morgan).
4. Distribuez ∨ sur ∧ : α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ).

Exemple : (pleut ∨ neige) ⇒ mouillé

étape 2 : ¬(pleut ∨ neige) ∨ mouillé

étape 3 : (¬pleut ∧ ¬neige) ∨ mouillé

étape 4 : (¬pleut ∨ mouillé) ∧ (¬neige ∨ mouillé) : deux clauses, toutes deux même de Horn.

La distribution de l’étape 4 peut allonger la formule de façon exponentielle ; en pratique, les solveurs utilisent donc la transformation de Tseitin avec des symboles auxiliaires, qui donne un résultat seulement linéairement plus long (satisfiable si et seulement si la formule d’origine l’est).

La résolution est universelle, mais coûteuse en général : pour la logique propositionnelle, le problème de satisfiabilité (SAT) est NP-complet. Les solveurs SAT modernes traitent pourtant des millions de variables ; nous en avons parlé dans la partie sur la satisfaction de contraintes.

7. Règles avec variables et Prolog

La logique propositionnelle a un défaut : « Rex est un mammifère » et « Micka est un mammifère » sont pour elle deux symboles sans rapport. Une règle sur tous les mammifères devrait être recopiée pour chaque animal séparément. La logique des prédicats de la partie sur la logique et les démonstrations résout cela avec des variables : ∀x : a_des_poils(x) ⇒ mammifère(x).

Définition — unification

Un unificateur de deux expressions est une substitution des variables après laquelle les deux expressions sont identiques. Par exemple, rodič(jan, Y) et rodič(X, petr) (rodič = parent) sont unifiés par la substitution {X / jan, Y / petr}. L’algorithme d’unification trouve l’unificateur le plus général, s’il existe.

def unifikuj(a, b, s):                    # s : substitution trouvée jusqu’ici (dictionnaire)
    if s is None:
        return None                           # a déjà échoué avant
    a, b = dosad(a, s), dosad(b, s)           # applique ce qu’on sait déjà
    if a == b:
        return s
    if je_promenna(a):
        return None if vyskytuje_se(a, b) else {**s, a: b}
    if je_promenna(b):
        return None if vyskytuje_se(b, a) else {**s, b: a}
    if slozeny(a) and slozeny(b) and a.jmeno == b.jmeno and len(a.args) == len(b.args):
        for x, y in zip(a.args, b.args):      # les arguments l’un après l’autre
            s = unifikuj(x, y, s)
        return s
    return None                               # constantes ou prédicats différents

Sur l’exemple rodič(jan, Y) et rodič(X, petr) : les prédicats coïncident, on compare donc les arguments. jan et X donnent {X / jan}, Y et petr ajoutent Y / petr. En revanche, rodič(jan, Y) et rodič(petr, eva) ne s’unifient pas : jan et petr sont des constantes différentes. Le test vyskytuje_se (occurs check) empêche une substitution comme X / f(X), qui mènerait à une expression infinie. (Prolog l’omet par défaut pour gagner en vitesse.)

Prolog (Alain Colmerauer, Marseille, 1972) repose sur le chaînage arrière avec unification : c’est un langage dans lequel le programme est une base de connaissances et l’exécution du programme est une requête (rodic = parent, prarodic = grand-parent, kdo = qui) :

rodic(jan, petr).
rodic(petr, eva).

prarodic(X, Z) :- rodic(X, Y), rodic(Y, Z).

?- prarodic(jan, Kdo).
Kdo = eva.

Prolog parvient au but prarodic(jan, Kdo) exactement comme notre arbre pour le tigre : il trouve la règle, unifie X = jan, démontre rodic(jan, Y), trouve Y = petr, puis rodic(petr, Z) avec le résultat eva.

8. Systèmes experts

Un système expert, c’est une base de connaissances rédigée avec un expert et un moteur d’inférence, généralement à chaînage arrière et capable d’expliquer pourquoi il est arrivé à une conclusion : il suffit de lire l’arbre que nous avons dessiné plus haut. Les plus connus étaient trois :

• DENDRAL (Stanford, à partir de 1965) déterminait la structure de molécules à partir des données d’un spectromètre de masse : le premier système à faire le travail des scientifiques selon leurs propres règles.
• MYCIN (Stanford, années 1970) diagnostiquait les infections bactériennes du sang et recommandait des antibiotiques. Il comptait environ six cents règles et, lors d’une évaluation de 1979, ses propositions se sont montrées aussi bonnes que celles des spécialistes de Stanford, voire meilleures. Il n’a pourtant jamais été utilisé à l’hôpital.
• XCON (entreprise DEC, à partir de 1980) assemblait des configurations d’ordinateurs VAX selon la commande. Il comptait des milliers de règles et, selon l’entreprise, faisait économiser des dizaines de millions de dollars par an.

Or la médecine connaît rarement la certitude. MYCIN associait donc à chaque règle un nombre indiquant à quel point l’expert lui faisait confiance :

Définition — facteur de certitude

Le facteur de certitude CF ∈ [−1, 1] exprime le degré de confiance dans une conclusion : 1 vrai à coup sûr, −1 faux à coup sûr, 0 on ne sait pas. Si deux règles avec des facteurs positifs CF₁ et CF₂ soutiennent la même conclusion, le facteur résultant est

CF = CF₁ + CF₂ · (1 − CF₁).

CF = CF₁ + CF₂ · (1 − CF₁)

CF₁

la confiance issue de la première règle ; la seconde règle ne peut pas la diminuer, seulement y ajouter

CF₂

quelle part de l’incertitude restante la seconde règle supprime ; si l’on additionnait simplement, deux indices de 0,6 donneraient un absurde 1,2

1 − CF₁

l’incertitude restée après la première règle ; on ne peut plus retrancher que d’elle, c’est pourquoi le résultat ne dépasse jamais 1

Exemple — trois indices et une règle aux prémisses incertaines

Trois indices 0,6, 0,5 et 0,5 : d’abord 0,6 + 0,5 · (1 − 0,6) = 0,8, puis 0,8 + 0,5 · (1 − 0,8) = 0,9. Vérification par les incertitudes : 1 − 0,4 · 0,5 · 0,5 = 0,9.

Prémisses incertaines. Dans MYCIN (Shortliffe et Buchanan, 1975), une conjonction de prémisses reçoit le facteur de son maillon le plus faible, et la conclusion d’une règle reçoit le facteur de la règle multiplié par ce facteur minimal (la règle n’est appliquée que si le minimum dépasse 0,2) : CF(conclusion) = CF(règle) · min_i CF(p_i). Une règle de facteur 0,7 dont les prémisses ont les facteurs 0,9 et 0,6 apporte ainsi à la conclusion 0,7 · min(0,9 ; 0,6) = 0,42.

À la fin des années quatre-vingt, les limites sont apparues. L’acquisition des connaissances était le goulot d’étranglement : un expert ne sait souvent pas formuler son savoir-faire sous forme de règles, et chaque règle coûtait des heures d’entretiens. Les systèmes étaient fragiles : un pas hors de leur domaine, ils ne savaient rien, et ne savaient même pas qu’ils ne savaient rien. Et des milliers de règles étaient difficiles à maintenir : une nouvelle règle pouvait contredire en silence une ancienne. Le marché des systèmes experts s’est effondré, et le second hiver de l’intelligence artificielle est arrivé. La réponse qui a suivi est l’inverse : ne pas rédiger les connaissances, mais les apprendre à partir des données.

9. Les connaissances dans l’intelligence artificielle d’aujourd’hui

• Graphes de connaissances. Depuis 2012, Google répond à de nombreuses requêtes à partir de son graphe de connaissances, un réseau de faits du type (Prague, capitale, Tchéquie). Wikidata, librement accessible, compte plus de cent millions d’éléments. C’est une base de connaissances, sauf que les faits y l’emportent sur les règles.
• Des règles là où tout doit pouvoir être vérifié. Les calculs d’impôts, les conditions d’assurance, l’octroi de crédits ou les politiques de sécurité s’écrivent encore aujourd’hui sous forme de règles : chaque décision peut être expliquée et défendue.
• Modèles de langage et connaissances. Un modèle de langage contient une quantité énorme de connaissances, mais réparties dans les poids du réseau : on ne peut ni les lire ni les corriger une à une, et le modèle invente parfois des choses avec aplomb. C’est pourquoi on lui adjoint une recherche dans une base de connaissances (RAG), ou des outils et des moteurs d’inférence qui vérifient le résultat.
• L’IA neurosymbolique réunit les deux : le réseau reconnaît ce qu’il voit et la logique en déduit ce qui en découle. Les systèmes qui cherchent des démonstrations mathématiques en sont un exemple : le modèle propose une étape et un outil formel la vérifie mécaniquement.

10. Résumé

• Une base de connaissances est un ensemble de phrases ; KB ⊨ α signifie que α est vraie dans tous les modèles de la base. La vérification de modèles le contrôle, mais au prix de 2ⁿ affectations.
• L’inférence (⊢) travaille sur des phrases plutôt que sur des mondes. Nous voulons qu’elle soit correcte (elle n’invente rien) et complète (elle ne laisse rien passer).
• Pour les clauses de Horn, le chaînage avant (depuis les faits, guidé par les données) ou arrière (depuis le but, guidé par la question) suffit ; le chaînage avant s’exécute en temps linéaire, le chaînage arrière n’examine que ce qui est lié au but.
• Pour toute la logique propositionnelle, il y a la résolution et la démonstration par l’absurde ; pour les règles avec variables, l’unification et Prolog.
• Les systèmes experts ont montré la force et les limites des connaissances écrites à la main, et ont préparé le terrain pour l’apprentissage à partir des données.

Envie d’essayer ? Demandez à un agent d’IA d’écrire un système expert à chaînage arrière qui pose des questions sur les faits manquants, et inventez vos propres règles pour un domaine que vous connaissez.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.