Aller au contenu
skymmeCours de data et d’IA

Retrouvez la logique en data et en IA

Vous ne programmerez sans doute pas en Prolog dans votre prochain poste de data scientist. Mais vous écrirez des requêtes SQL, peut-être des requêtes récursives sur une hiérarchie de produits ; vous interrogerez peut-être un graphe de connaissances ; vous croiserez des outils d’analyse de code qui raisonnent par règles. Tous héritent directement des idées de ce cours : faits, règles, fermeture transitive, monde clos.

Ce dernier chapitre fait le pont. Il n’ajoute pas de Prolog, il montre où ses idées vivent aujourd’hui, et ce qu’elles valent face à l’apprentissage automatique. Nous reprenons le réseau ferré du chapitre 4, avec sa liaison retour liaison(paris, rennes) qui crée un cycle.

Datalog : Prolog sans les pièges

Section intitulée « Datalog : Prolog sans les pièges »

Au chapitre 4, chemin/2 bouclait dès que le réseau contenait un cycle, et une récursion à gauche suffisait à tout bloquer. Ces défauts ne viennent pas de la logique, mais de la stratégie de Prolog : une recherche en profondeur, du but vers les faits (on dit descendante, top-down).

Datalog est un sous-ensemble de Prolog conçu pour les bases de données. Il garde les faits et les règles, mais impose trois restrictions :

  • pas de termes composés : les arguments sont des constantes ou des variables, donc pas de par(Z, T) ni de listes ;
  • pas de coupure, ni de prédicats extra-logiques ;
  • chaque variable de la tête doit apparaître dans le corps (règles « sûres »), et la négation doit être stratifiée : un prédicat ne peut pas dépendre de sa propre négation.

En échange, Datalog change de stratégie. Au lieu de partir de la question, il part des faits et applique toutes les règles, encore et encore, jusqu’à ce que plus rien de nouveau n’apparaisse : c’est l’évaluation ascendante (bottom-up), qui calcule un point fixe. Comme il n’y a pas de termes composés, le nombre de faits déductibles est fini (au plus toutes les combinaisons des constantes existantes), et le calcul termine toujours.

questionchemin(rennes, Y)règlesfaits liaisonProlog : descendantpoint fixe :tous les chemin(X, Y)règles appliquéesà tous les faitsfaits liaisonDatalog : ascendantrecherche enprofondeur :peut bouclertour après tour,jusqu’à ce querien ne change
Prolog part de la question (descendant) et peut boucler ; Datalog part des faits (ascendant) et s'arrête quand un tour n'ajoute plus rien.
rennessaint_malolavalvannesnantesangersle_mansparisarrivée Yrennessaint_malolavalvannesnantesangersle_mansparisdépart X1112323121234123121sans cycle : 19 couples en 4 toursrennessaint_malolavalvannesnantesangersle_mansparisarrivée Yrennessaint_malolavalvannesnantesangersle_mansparis41112323344456125666123445556123344456122333454112223434avec paris → rennes : 56 couples en 6 tourschiffre = tour où le fait chemin(X, Y) apparaît ; violet : les liaisons (tour 1)
Chaque tour ajoute les chemins d'une liaison de plus. Sans cycle, tout est trouvé en 4 tours ; avec le retour Paris-Rennes, il en faut 6, et rien n'est jamais ajouté deux fois.

Conséquence remarquable : en Datalog, l’ordre des règles et des buts ne compte plus. La récursion à gauche chemin(X, Y) :- chemin(X, Z), liaison(Z, Y). est parfaitement valable. On retrouve la promesse initiale de la programmation déclarative : on décrit ce qui est vrai, et le moteur s’occupe du reste.

Datalog est resté longtemps un objet de théorie des bases de données, puis il est revenu dans l’industrie. On retrouve des langages de sa famille dans l’analyse statique de programmes (des outils comme Soufflé, ou le langage de requêtes de CodeQL, qui cherchent des failles en raisonnant sur le code par règles), dans certaines bases de données comme Datomic, ou dans Logica, qui compile des règles vers du SQL.

Le SQL récursif : la fermeture transitive en SQL

Section intitulée « Le SQL récursif : la fermeture transitive en SQL »

Un prédicat est une table, une règle est une vue : vous l’avez vu dès le chapitre 2. Mais une vue SQL classique ne peut pas s’appeler elle-même. Depuis la norme SQL:1999, les expressions de table communes récursives (WITH RECURSIVE) comblent ce manque, et elles sont disponibles dans PostgreSQL, SQLite, MySQL 8 ou SQL Server (ce dernier omet le mot-clé RECURSIVE). Voici chemin/2 en SQL :

-- table liaison(depart, arrivee)
WITH RECURSIVE chemin(depart, arrivee) AS (
    SELECT depart, arrivee FROM liaison               -- cas de base
    UNION
    SELECT l.depart, c.arrivee                        -- cas récursif
    FROM liaison AS l
    JOIN chemin AS c ON l.arrivee = c.depart          -- jointure sur la ville intermédiaire
)
SELECT arrivee FROM chemin WHERE depart = 'rennes' ORDER BY arrivee;

La correspondance avec Prolog est terme à terme : la partie avant UNION est le cas de base, la partie après est le cas récursif, et la condition l.arrivee = c.depart joue le rôle de la variable partagée Z dans liaison(X, Z), chemin(Z, Y). Le moteur évalue la requête exactement comme Datalog, par tours jusqu’au point fixe.

XZYliaison AS lchemin AS cl.departl.arrivee = c.departc.arriveeProlog : liaison(X, Z), chemin(Z, Y) : la variable partagée Z devient la condition du JOIN
Le cas récursif de WITH RECURSIVE joint une liaison et un chemin déjà trouvé sur la ville intermédiaire Z, exactement comme la variable partagée de Prolog.

Exécutée avec SQLite sur le réseau avec cycle, la requête renvoie 8 villes : Angers, Laval, Le Mans, Nantes, Paris, Rennes (grâce au retour depuis Paris), Saint-Malo et Vannes. Elle termine sans difficulté.

PrologDatalogSQL
fait liaison(rennes, laval).faitligne d’une table
prédicat liaison/2relationtable à deux colonnes
règle non récursiverèglevue (CREATE VIEW)
variable partagée entre deux butsvariable partagéeJOIN … ON
deux clausesdeux règlesUNION
règle récursiverègle récursiveWITH RECURSIVE
not(P), monde closnégation stratifiéeNOT EXISTS, monde clos
findall, setofagrégats (selon les moteurs)array_agg, GROUP BY

Les graphes de connaissances

Section intitulée « Les graphes de connaissances »

Un graphe de connaissances (knowledge graph) stocke des faits sous forme de triplets sujet, prédicat, objet : « le far breton est une sorte de gâteau », « Rennes est la préfecture d’Ille-et-Vilaine ». C’est la structure du format RDF et de bases publiques comme Wikidata. Un triplet, c’est un fait binaire comme sorte_de(far_breton, gateau) ; pour manipuler le prédicat lui-même comme une donnée, on l’écrit plutôt sous la forme d’un fait à trois arguments :

triplet(far_breton, sorte_de, gateau).
triplet(gateau, sorte_de, dessert).
triplet(dessert, sorte_de, plat).


% est_un(X, C) : X appartient à la catégorie C, directement ou par héritage
est_un(X, C) :- triplet(X, sorte_de, C).
est_un(X, C) :- triplet(X, sorte_de, D), est_un(D, C).

?- est_un(far_breton, C). donne gâteau, dessert, puis plat. C’est encore une fermeture transitive. Le langage de requêtes SPARQL l’écrit avec un chemin de propriétés : dans Wikidata, ?x wdt:P279+ ?c suit la propriété « sous-classe de » (P279) une ou plusieurs fois, comme est_un, et wdt:P279* accepte aussi zéro pas, comme une fermeture réflexo-transitive.

far_bretongateaudessertplatsorte_desorte_desorte_deest_unest_un (déduit)est_un (déduit)triplets stockés (sujet, prédicat, objet) en gris ; fermeture transitive est_un en dessous
Trois triplets stockés suffisent : la fermeture transitive est_un en déduit que le far breton est aussi un dessert et un plat.

Les graphes de connaissances vont plus loin que la simple fermeture : des langages de règles et d’ontologies (RDFS, OWL) permettent de déduire de nouveaux triplets, par exemple qu’un individu d’une sous-classe appartient aussi à la classe mère. Ces raisonneurs appliquent des règles très proches de Datalog. Ils servent en recherche documentaire, en biologie (ontologies de gènes et de maladies) ou pour intégrer des données hétérogènes. En pratique, on les combine souvent avec l’apprentissage : des modèles appris proposent des triplets manquants, que des règles valident ou complètent.

IA symbolique et apprentissage

Section intitulée « IA symbolique et apprentissage »

Prolog appartient à l’IA symbolique : on représente explicitement les connaissances par des symboles et des règles, et on raisonne par déduction. L’apprentissage automatique, lui, apprend une fonction à partir d’exemples, sans règles explicites (voir le cours Apprentissage automatique). Les deux approches ont des forces opposées.

CritèreIA symbolique (règles, logique)Apprentissage automatique
Point de départdes connaissances d’expertsdes données étiquetées
Raisonnementexact, déductifstatistique, approximatif
Explicationla démonstration est l’explicationà reconstruire (importance des variables…)
Données bruitées, perception (images, sons)mal à l’aisepoint fort
Coût principalécrire et maintenir les règlescollecter et étiqueter les données
Cas nouveaux imprévuséchoue (hors des règles)généralise, parfois à tort

L’IA symbolique n’a pas disparu : elle s’est spécialisée. Les solveurs de contraintes (ECLiPSe lui-même est d’abord un système de programmation logique par contraintes) planifient des emplois du temps, des tournées et des productions industrielles. Les moteurs de règles encodent des réglementations (éligibilité, tarification, conformité), là où chaque décision doit pouvoir être justifiée. La programmation par ensembles réponses (Answer Set Programming), héritière directe de la négation par l’échec, résout des problèmes combinatoires.

Une piste de recherche active, dite neuro-symbolique, cherche à combiner les deux mondes : un modèle de langage traduit une question en requête SQL ou en programme logique, qu’un moteur exact exécute ensuite ; ou des règles vérifient la cohérence des sorties d’un modèle appris. Ces combinaisons sont prometteuses, mais encore loin d’être la norme : il faut les voir comme des outils à choisir selon le problème, pas comme une révolution acquise.

En résumé

Section intitulée « En résumé »
  • Datalog restreint Prolog (pas de termes composés, pas de coupure, négation stratifiée) et l’évalue de façon ascendante : il termine toujours et l’ordre des règles ne compte plus.
  • L’évaluation semi-naïve calcule le point fixe par tours, en ne combinant que les faits nouveaux.
  • Le SQL récursif (WITH RECURSIVE) écrit une fermeture transitive avec un cas de base, un UNION et un cas récursif ; UNION garantit la terminaison sur les cycles, UNION ALL non.
  • Un graphe de connaissances est un ensemble de triplets, donc de faits binaires ; l’héritage de catégories est une fermeture transitive, que SPARQL écrit avec un chemin de propriétés.
  • L’IA symbolique est exacte et explicable, l’apprentissage robuste au bruit et à la perception ; les approches neuro-symboliques cherchent à les combiner.

Exercices

Section intitulée « Exercices »

Exercice · Est-ce du Datalog ?

facile

Parmi ces programmes Prolog, lesquels sont du Datalog valide ? Justifiez.

  1. grand_parent(X, Y) :- parent(X, Z), parent(Z, Y).
  2. trajet(X, Y, par(Z, T)) :- liaison(X, Z), trajet(Z, Y, T).
  3. ancetre(X, Y) :- ancetre(X, Z), parent(Z, Y).
  4. tarif(P, T) :- etudiant(P), !, T = 7.
  5. connu(X, Y) :- personne(X).
Voir la solution
  1. Oui : que des constantes et des variables, et les variables de la tête (X et Y) apparaissent dans le corps.
  2. Non : par(Z, T) est un terme composé, interdit en Datalog.
  3. Oui, et c’est même là que Datalog brille : cette récursion à gauche ferait boucler Prolog, mais l’évaluation ascendante la calcule sans difficulté.
  4. Non : la coupure n’existe pas en Datalog.
  5. Non : la variable Y de la tête n’apparaît pas dans le corps. La règle n’est pas « sûre » : elle affirmerait connu(X, Y) pour toutes les valeurs possibles de Y, un ensemble non borné.

En code

% datalog(+Regle) : la règle respecte les trois contraintes de Datalog
datalog((Tete :- Corps)) :-
    buts(Corps, Buts),
    \+ (member(B, Buts), B == '!'),                  % pas de coupure
    \+ (member(A, [Tete|Buts]), A =.. [_|Args],
        member(Arg, Args), compound(Arg)),           % pas de terme composé
    term_variables(Tete, VT),
    term_variables(Corps, VC),
    \+ (member(V, VT), \+ (member(W, VC), W == V)).  % règle sûre


% buts(+Corps, -Buts) : la conjonction (A, B) mise sous forme de liste
buts((A, B), [A|L]) :- !, buts(B, L).
buts(A, [A]).


% ?- datalog((grand_parent(X, Y) :- parent(X, Z), parent(Z, Y))).          Yes
% ?- datalog((trajet(X, Y, par(Z, T)) :- liaison(X, Z), trajet(Z, Y, T))).  No
% ?- datalog((ancetre(X, Y) :- ancetre(X, Z), parent(Z, Y))).              Yes
% ?- datalog((tarif(P, T) :- etudiant(P), !, T = 7)).                      No
% ?- datalog((connu(X, Y) :- personne(X))).                                No

Exercice · Les ancêtres en SQL

moyen

La table parent(parent, enfant) contient les lignes (anne, bruno), (bruno, chloe) et (chloe, denis). Écrivez une requête SQL récursive qui calcule la relation ancetre(anc, descendant), puis donnez son résultat.

Voir la solution
WITH RECURSIVE ancetre(anc, descendant) AS (
    SELECT parent, enfant FROM parent
    UNION
    SELECT p.parent, a.descendant
    FROM parent AS p
    JOIN ancetre AS a ON p.enfant = a.anc
)
SELECT anc, descendant FROM ancetre ORDER BY anc, descendant;

C’est la traduction directe de ancetre(X, Y) :- parent(X, Z), ancetre(Z, Y). : la jointure p.enfant = a.anc joue le rôle de Z. Le résultat contient 6 couples : (anne, bruno), (anne, chloe), (anne, denis), (bruno, chloe), (bruno, denis) et (chloe, denis).

En code

parent(anne, bruno).
parent(bruno, chloe).
parent(chloe, denis).


ancetre(X, Y) :- parent(X, Y).
ancetre(X, Y) :- parent(X, Z), ancetre(Z, Y).


% ?- findall(A-D, ancetre(A, D), L0), sort(L0, L), length(L, N).
% L = [anne-bruno, anne-chloe, anne-denis, bruno-chloe, bruno-denis, chloe-denis]
% N = 6

Exercice · Dérouler un point fixe

difficile

Avec les trois faits parent/2 de l’exercice précédent et les règles

ancetre(X, Y) :- parent(X, Y).
ancetre(X, Y) :- ancetre(X, Z), parent(Z, Y).
  1. Déroulez l’évaluation semi-naïve : quels faits ancetre apparaissent à chaque tour, et quand le point fixe est-il atteint ?
  2. Pour une chaîne de n générations (n + 1 personnes, n faits parent), combien de faits ancetre obtient-on, et combien de tours productifs faut-il ?
  3. Que ferait Prolog avec la question ?- ancetre(denis, X). et ces règles ?
Voir la solution

  1. Tour 1 : la première règle copie les faits parent : ancetre(anne, bruno), ancetre(bruno, chloe), ancetre(chloe, denis). Tour 2 : on combine les faits nouveaux du tour 1 avec parent : ancetre(anne, chloe) et ancetre(bruno, denis). Tour 3 : à partir des nouveaux faits du tour 2, ancetre(anne, denis). Tour 4 : rien de nouveau, le point fixe est atteint avec 3 + 2 + 1 = 6 faits.

  2. Chaque couple (ancêtre, descendant) correspond à un choix de deux personnes distinctes sur la chaîne, l’ancêtre étant la plus ancienne : il y en a n(n + 1)/2. Le tour k produit les couples séparés par k générations, soit n − k + 1 faits : il faut n tours productifs, puis un tour vide pour constater le point fixe. Pour n = 3, on retrouve 6 faits en 3 tours productifs.

  3. Prolog boucle. La première clause échoue (Denis n’a pas d’enfant), la seconde appelle ancetre(denis, Z) avec les mêmes arguments, qui rappelle la seconde clause, et ainsi de suite : c’est la récursion à gauche du chapitre 4. Datalog, lui, répond immédiatement qu’il n’y a aucun fait ancetre(denis, …) dans le point fixe.

En code

% un tour semi-naïf : on combine les faits NOUVEAUX (Delta) avec parent/2
tour(Delta, Connus, Nouveaux) :-
    findall(X-Y, (member(X-Z, Delta), parent(Z, Y)), L0),
    sort(L0, L),
    findall(F, (member(F, L), \+ member(F, Connus)), Nouveaux).


point_fixe([], Connus, Connus).
point_fixe([F|Fs], Connus, Tout) :-
    tour([F|Fs], Connus, Nouveaux),
    append(Connus, Nouveaux, Connus2),
    point_fixe(Nouveaux, Connus2, Tout).


% ?- findall(X-Y, parent(X, Y), T1), point_fixe(T1, T1, Tout), length(Tout, N).
% tours : 3 faits, puis 2, puis 1, puis aucun (point fixe)
% Tout = [anne-bruno, bruno-chloe, chloe-denis, anne-chloe, bruno-denis, anne-denis]
% N = 6