SL-4 — Programmation Logique Inductive (ILP)

Navigation : Index | << SL-3

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Representer des relations sous forme de clauses Horn et de predicats logiques 2. Implementer l’algorithme FOIL (top-down ILP) et comprendre son fonctionnement 3. Appliquer la resolution inverse (bottom-up ILP) avec les opérateurs V et W 4. Comparer les approches top-down et bottom-up sur le problème classique des ancetres 5. Connecter l’ILP avec les knowledge graphs modernes

Prerequis

• SL-1 (hypotheses logiques, version space)
• SL-2 (EBL, arbre de preuve)
• SL-3 (determinations, pertinence)
• Bases de logique propositionnelle et FOL

Duree estimee : 55 minutes

# Imports et configuration
from typing import Optional
from dataclasses import dataclass, field
from collections import defaultdict
import itertools

NOTEBOOK_INFO = {
    "title": "SL-4 - Programmation Logique Inductive (ILP)",
    "series": "SymbolicLearning",
    "aima_chapters": ["19.5"],
    "date": "2026-05",
}

print(f"Notebook : {NOTEBOOK_INFO['title']}")
print(f"Chapitre AIMA : {', '.join(NOTEBOOK_INFO['aima_chapters'])}")

Notebook : SL-4 - Programmation Logique Inductive (ILP)
Chapitre AIMA : 19.5

---

1. Introduction — Pourquoi ILP ?

Les notebooks précédents (SL-1 a SL-3) couvraient l’apprentissage d’hypotheses propositionnelles : des conjonctions de contraintes sur des attributs fixes. Mais beaucoup de connaissances du monde reel sont relationnelles :

• “X est le parent de Y”
• “X travaille dans la même entreprise que Y”
• “Si X est ancetre de Y et Y est ancetre de Z, alors X est ancetre de Z”

La Programmation Logique Inductive (ILP, AIMA 19.5) apprend des règles logiques relationnelles (clauses Horn) a partir d’exemples positifs/negatifs et de connaissances de fond existantes.

Origine. Le terme et le champ de l’ILP (Inductive Logic Programming) sont coines par Muggleton, S. (1991), Inductive logic programming, New Generation Computing 8(4):295-318, qui pose l’ILP comme l’intersection de l’apprentissage automatique et de la programmation logique. fond.

La contrainte KBIL (AIMA Eq. 19.5)

\[ \text{Background} \wedge \text{Hypothesis} \wedge \text{Descriptions} \models \text{Classifications} \]

L’ILP cherche une Hypothese qui, combinee a la connaissance de fond, a pour consequence logique (entails) les classifications observees.

Deux approches principales

Approche	Direction	Principe
FOIL (top-down)	General -> Spécifique	Part de la règle la plus générale, ajoute des litteraux pour exclure les negatifs
Resolution inverse (bottom-up)	Spécifique -> General	Part des exemples, les generalise par resolution inverse

Plan de ce notebook

Section	Contenu	Duree
2. Clauses Horn	Representation, unification	8 min
3. FOIL	Algorithme top-down, gain FOIL	12 min
4. Resolution inverse	Opérateurs V et W	10 min
5. Ancetres	Application complete	10 min
6. Knowledge Graphs	Connexion SemanticWeb	8 min
7. Exercices	4 exercices pratiques	7 min

---

2. Clauses Horn et unification

Clauses Horn

Une clause Horn est une disjonction de litteraux avec au plus un litteral positif. En notation Prolog :

\[\text{head} :- \text{body}_1, \text{body}_2, \ldots, \text{body}_n\]

Cela se lit : “Si body_1 ET body_2 ET … ET body_n, alors head.”

Substitution et unification

L’unification est le processus qui trouve une substitution \(\theta\) rendant deux termes egaux. C’est le mécanisme fondamental de la resolution en logique du premier ordre.

• \(\theta = \{x/A, y/B\}\) est une substitution
• \(P(x, y)\theta = P(A, B)\) est l’application de la substitution

# Representation des clauses Horn et unification

@dataclass(frozen=True)
class Literal:
    """Un litteral logique : predicat(arg1, arg2, ...).
    
    Les arguments en minuscule sont des variables,
    les arguments avec une majuscule sont des constantes.
    """
    predicate: str
    args: tuple[str, ...]
    negated: bool = False

    def __str__(self):
        neg = "~" if self.negated else ""
        args = ", ".join(self.args)
        return f"{neg}{self.predicate}({args})"

    def is_ground(self) -> bool:
        """True si tous les arguments sont des constantes."""
        return all(a[0].isupper() for a in self.args)

    def variables(self) -> set[str]:
        """Variables du litteral (args en minuscule)."""
        return {a for a in self.args if a[0].islower()}


@dataclass
class HornClause:
    """Clause Horn : head :- body."""
    head: Literal
    body: list[Literal]

    def __str__(self):
        body_str = ", ".join(str(l) for l in self.body)
        if body_str:
            return f"{self.head} :- {body_str}."
        return f"{self.head}."

    def variables(self) -> set[str]:
        all_vars = self.head.variables()
        for lit in self.body:
            all_vars |= lit.variables()
        return all_vars


def unify_var(var: str, term: str, subst: dict) -> Optional[dict]:
    """Tente d'unifier une variable avec un terme."""
    if var in subst:
        return unify_term(subst[var], term, subst)
    elif term in subst:
        return unify_term(var, subst[term], subst)
    elif var == term:
        return subst
    else:
        new_subst = dict(subst)
        new_subst[var] = term
        return new_subst


def unify_term(t1: str, t2: str, subst: dict) -> Optional[dict]:
    """Unifie deux termes sous une substitution."""
    if t1 in subst:
        return unify_term(subst[t1], t2, subst)
    elif t2 in subst:
        return unify_term(t1, subst[t2], subst)
    elif t1 == t2:
        return subst
    elif t1[0].islower():
        return unify_var(t1, t2, subst)
    elif t2[0].islower():
        return unify_var(t2, t1, subst)
    else:
        return None  # Constantes differentes


def unify(lit1: Literal, lit2: Literal, subst: dict = None) -> Optional[dict]:
    """Unifie deux ATOMES (meme predicat, meme arite).

    L'unification porte sur les atoms : le signe (negated) est ignore, car
    deux litteraux de signes contraires portent le MEME atome sous-jacent.
    Retourne la substitution, ou None si les atoms sont incompatibles.
    """
    if subst is None:
        subst = {}
    if lit1.predicate != lit2.predicate or len(lit1.args) != len(lit2.args):
        return None
    result = dict(subst)
    for a1, a2 in zip(lit1.args, lit2.args):
        result = unify_term(a1, a2, result)
        if result is None:
            return None
    return result


def unify_complementary(lit1: Literal, lit2: Literal, subst: dict = None) -> Optional[dict]:
    """Apparie deux litteraux COMPLEMENTAIRES (signes opposes) pour la resolution.

    Exige le meme predicat et la meme arite ET des signes contraires : c'est la
    condition d'appariement d'un litteral avec sa negation, PAS une unification
    generale. Retourne la substitution, ou None si la paire est incompatible.
    """
    if subst is None:
        subst = {}
    if lit1.predicate != lit2.predicate or len(lit1.args) != len(lit2.args):
        return None
    if lit1.negated == lit2.negated:
        return None  # Meme signe -> pas une paire complementaire
    result = dict(subst)
    for a1, a2 in zip(lit1.args, lit2.args):
        result = unify_term(a1, a2, result)
        if result is None:
            return None
    return result


# Exemples
print("Exemples de clauses Horn et unification")
print("=" * 55)

# parent(A, B) :- .  (fait)
parent_ab = HornClause(
    head=Literal("parent", ("Alice", "Bob")),
    body=[]
)
print(f"Fait : {parent_ab}")

# ancestor(X, Y) :- parent(X, Y).  (regle)
ancestor_parent = HornClause(
    head=Literal("ancestor", ("x", "y")),
    body=[Literal("parent", ("x", "y"))]
)
print(f"Regle : {ancestor_parent}")

# ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).  (regle recursive)
ancestor_recursive = HornClause(
    head=Literal("ancestor", ("x", "y")),
    body=[
        Literal("parent", ("x", "z")),
        Literal("ancestor", ("z", "y"))
    ]
)
print(f"Recursive : {ancestor_recursive}")

# Unification d'atomes (le signe est ignore)
print()
print("Unification d'atomes (le signe est ignore) :")
s1 = unify(
    Literal("parent", ("x", "y"), negated=False),
    Literal("parent", ("Alice", "Bob"), negated=False)
)
print(f"  unify(parent(x,y), parent(Alice,Bob)) = {s1}")

s2 = unify(
    Literal("parent", ("x", "y"), negated=True),
    Literal("parent", ("Alice", "Bob"), negated=False)
)
print(f"  unify(~parent(x,y), parent(Alice,Bob)) = {s2}")

# Appariement complementaire (signes opposes) - pour la resolution
print()
print("Appariement complementaire (signes opposes) :")
s3 = unify_complementary(
    Literal("parent", ("x", "y"), negated=False),
    Literal("parent", ("Alice", "Bob"), negated=True)
)
print(f"  unify_complementary(parent(x,y), ~parent(Alice,Bob)) = {s3}")

s4 = unify_complementary(
    Literal("parent", ("x", "y"), negated=False),
    Literal("parent", ("x", "Bob"), negated=True)
)
print(f"  unify_complementary(parent(x,y), ~parent(x,Bob)) = {s4}")

Exemples de clauses Horn et unification
=======================================================
Fait : parent(Alice, Bob).
Regle : ancestor(x, y) :- parent(x, y).
Recursive : ancestor(x, y) :- parent(x, z), ancestor(z, y).

Unification d'atomes (le signe est ignore) :
  unify(parent(x,y), parent(Alice,Bob)) = {'x': 'Alice', 'y': 'Bob'}
  unify(~parent(x,y), parent(Alice,Bob)) = {'x': 'Alice', 'y': 'Bob'}

Appariement complementaire (signes opposes) :
  unify_complementary(parent(x,y), ~parent(Alice,Bob)) = {'x': 'Alice', 'y': 'Bob'}
  unify_complementary(parent(x,y), ~parent(x,Bob)) = {'y': 'Bob'}

Interpretation : Clauses Horn

Élément	Representation	Exemple
Fait	Clause sans body	parent(Alice, Bob).
Règle	Head + body	ancestor(X,Y) :- parent(X,Y).
Règle récursive	Head reference dans body	ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

L’unification est le mécanisme de base : elle trouve les substitutions qui rendent deux termes egaux. C’est elle qui permet de “matcher” un fait avec le body d’une règle.

Point cle : L’ILP apprend de nouvelles règles Horn a partir d’exemples. Contrairement a l’apprentissage propositionnel (SL-1), les règles relationnelles peuvent exprimer des recursions et des relations entre objets.

---

3. FOIL — Apprentissage top-down

L’algorithme FOIL (First-Order Inductive Learner, Quinlan 1990) apprend des clauses Horn en partant de la règle la plus générale et en ajoutant des litteraux pour couvrir les positifs et exclure les negatifs.

Origine. FOIL est introduit par Quinlan, J. R. (1990), Learning logical definitions from relations, Machine Learning 5:239-266 — un apprentissage top-down glouton ou chaque litteral ajoute est choisi par un gain d’information (la formule Gain_FOIL implantee ci-dessous).

Principe (AIMA Section 19.5)

FOIL(positifs, negatifs, target, background):
    règles = []
    tant que positifs non couverts:
        nouvelle_clause = target(Vars) :- true
        tant que nouvelle_clause couvre des negatifs:
            meilleur_litteral = choisir_meilleur_litteral(nouvelle_clause, candidats)
            ajouter meilleur_litteral au body
        règles.append(nouvelle_clause)
        retirer les positifs couverts
    retourner règles

Gain FOIL

Le gain FOIL mesure l’utilite d’ajouter un litteral \(L\) a une clause \(C\) :

\[Gain_{FOIL}(L, C) = |T_{new}^{+}| \times \left(\log_2 \frac{|T_{new}^{+}|}{|T_{new}^{+}| + |T_{new}^{-}|} - \log_2 \frac{|T_{old}^{+}|}{|T_{old}^{+}| + |T_{old}^{-}|}\right)\]

Ou \(T^{+}\) et \(T^{-}\) sont les tuples positifs et negatifs couverts.

# Implementation de FOIL

import math

@dataclass
class Binding:
    """Une liaison (substitution) qui rend le body vrai."""
    subst: dict[str, str]
    is_positive: bool


def evaluate_literal(
    lit: Literal,
    binding: dict[str, str],
    background: set[tuple[str, tuple[str, ...]]]
) -> bool:
    """Evalue un litteral sous une substitution par rapport au background."""
    # Appliquer la substitution
    ground_args = tuple(binding.get(a, a) for a in lit.args)
    fact = (lit.predicate, ground_args)
    in_bg = fact in background
    return in_bg if not lit.negated else not in_bg


def get_bindings(
    body: list[Literal],
    variables: set[str],
    constants: set[str],
    background: set[tuple[str, tuple[str, ...]]],
    positives: set[tuple[str, ...]],
    negatives: set[tuple[str, ...]],
    target_pred: str,
    target_args: tuple[str, ...]
) -> tuple[list[dict], list[dict]]:
    """Trouve les bindings positifs et negatifs pour un body donne.
    
    Retourne (positive_bindings, negative_bindings).
    """
    pos_bindings = []
    neg_bindings = []
    
    # Generer les candidats pour les variables libres
    free_vars = variables - {a for lit in body for a in lit.args if a[0].islower()}
    all_vars = list(variables)
    
    for const_combo in itertools.product(constants, repeat=len(all_vars)):
        binding = dict(zip(all_vars, const_combo))
        
        # Verifier que le body est satisfait
        body_satisfied = True
        for lit in body:
            if not evaluate_literal(lit, binding, background):
                body_satisfied = False
                break
        
        if not body_satisfied:
            continue
        
        # Verifier si c'est un positif ou negatif
        target_key = tuple(binding.get(a, a) for a in target_args)
        target_fact = (target_pred, target_key)
        
        if target_fact[1] in positives:
            pos_bindings.append(binding)
        elif target_fact[1] in negatives:
            neg_bindings.append(binding)
    
    return pos_bindings, neg_bindings


def foil_gain(
    old_pos: int, old_neg: int,
    new_pos: int, new_neg: int
) -> float:
    """Calcule le gain FOIL pour l'ajout d'un litteral."""
    if new_pos == 0:
        return float('-inf')
    old_total = old_pos + old_neg
    new_total = new_pos + new_neg
    if old_total == 0 or new_total == 0:
        return 0.0
    old_entropy = math.log2(old_pos / old_total) if old_pos > 0 else float('-inf')
    new_entropy = math.log2(new_pos / new_total) if new_pos > 0 else float('-inf')
    return new_pos * (new_entropy - old_entropy)


print("Fonctions FOIL definies : evaluate_literal, get_bindings, foil_gain")
print()
# Test du gain FOIL
print("Exemples de gain FOIL :")
print(f"  10 pos / 5 neg -> 8 pos / 1 neg : {foil_gain(10, 5, 8, 1):.3f}")
print(f"  10 pos / 5 neg -> 9 pos / 4 neg : {foil_gain(10, 5, 9, 4):.3f}")
print(f"  10 pos / 5 neg -> 0 pos / 0 neg : {foil_gain(10, 5, 0, 0):.3f} (elimine)")

Fonctions FOIL definies : evaluate_literal, get_bindings, foil_gain

Exemples de gain FOIL :
  10 pos / 5 neg -> 8 pos / 1 neg : 3.320
  10 pos / 5 neg -> 9 pos / 4 neg : 0.490
  10 pos / 5 neg -> 0 pos / 0 neg : -inf (elimine)

Application : Problème ancestor(X, Y)

Les fonctions FOIL etant définies, nous allons les appliquer au problème classique de la relation ancetre. Ce problème illustre parfaitement la puissance de l’ILP : la règle a decouvrir est récursive (un ancetre est soit un parent direct, soit un parent d’un ancetre).

Le jeu de données ci-dessous définit une famille sur 3 generations avec les faits parent/2, les exemples positifs ancestor/2 et les contre-exemples negatifs.

# FOIL complet sur le probleme ancestor(X, Y)

# Background knowledge : faits parent/2
BACKGROUND = {
    ("parent", ("Arthur", "Bob")),
    ("parent", ("Arthur", "Catherine")),
    ("parent", ("Bob", "Diana")),
    ("parent", ("Catherine", "Eve")),
    ("parent", ("Eve", "Frank")),
}

CONSTANTS = {"Arthur", "Bob", "Catherine", "Diana", "Eve", "Frank"}

# Exemples positifs : ancestor(X, Y)
POSITIVES = {
    ("Arthur", "Bob"), ("Arthur", "Catherine"),
    ("Bob", "Diana"), ("Catherine", "Eve"), ("Eve", "Frank"),
    ("Arthur", "Diana"), ("Arthur", "Eve"), ("Arthur", "Frank"),
    ("Catherine", "Frank"),
}

# Exemples negatifs : non-ancestor(X, Y)
NEGATIVES = {
    ("Bob", "Arthur"), ("Catherine", "Arthur"),
    ("Diana", "Bob"), ("Eve", "Catherine"),
    ("Frank", "Eve"), ("Diana", "Arthur"),
    ("Bob", "Catherine"), ("Catherine", "Bob"),
    ("Diana", "Eve"), ("Eve", "Diana"),
}

print("Probleme ancestor(X, Y)")
print("=" * 50)
print(f"Background : {len(BACKGROUND)} faits parent/2")
print(f"Positifs : {len(POSITIVES)} couples ancestor")
print(f"Negatifs : {len(NEGATIVES)} couples non-ancestor")
print()
print("Familles :")
for fact in sorted(BACKGROUND, key=lambda x: x[1]):
    print(f"  parent({fact[1][0]}, {fact[1][1]})")

Probleme ancestor(X, Y)
==================================================
Background : 5 faits parent/2
Positifs : 9 couples ancestor
Negatifs : 10 couples non-ancestor

Familles :
  parent(Arthur, Bob)
  parent(Arthur, Catherine)
  parent(Bob, Diana)
  parent(Catherine, Eve)
  parent(Eve, Frank)

Nous disposons maintenant d’un ensemble de faits et d’exemples positifs/negatifs. La cellule suivante execute FOIL pas-a-pas sur ces données pour evaluer chaque clause candidate et mesurer son gain.

# Execution simplifiee de FOIL sur ancestor
# FOIL cherche des regles de la forme : ancestor(x, y) :- body.

# Etape 1 : Essayer le litteral parent(x, y)
# Si ancestor(x, y) :- parent(x, y). couvre des positifs et pas de negatifs

def check_clause_covers(
    body_lits: list[Literal],
    target_pred: str,
    target_args: tuple[str, ...],
    constants: set[str],
    background: set[tuple[str, tuple[str, ...]]],
    positives: set[tuple[str, ...]],
    negatives: set[tuple[str, ...]]
) -> tuple[set[tuple[str, ...]], set[tuple[str, ...]]]:
    """Trouve les exemples positifs et negatifs DISTINCTS couverts par une clause.

    On enumere toutes les substitutions des variables (y compris les variables
    intermediaires comme z), mais on dedoublonne sur le tuple-cible : un meme
    exemple ancestor(x, y) couvert par plusieurs valeurs de z ne compte qu'une
    fois. C'est indispensable pour que le gain FOIL compare des grandeurs
    coherentes (couverture d'EXEMPLES) ; sinon un litteral comme parent(x, z),
    qui multiplie les bindings, parait faussement meilleur que parent(x, y).
    """
    vars_in_clause = set()
    for lit in body_lits:
        vars_in_clause |= set(lit.args)
    for a in target_args:
        vars_in_clause.add(a)
    # uniquement les variables (minuscules), pas d'eventuelles constantes
    vars_list = sorted(v for v in vars_in_clause if v[0].islower())

    covered_pos: set[tuple[str, ...]] = set()
    covered_neg: set[tuple[str, ...]] = set()

    for const_combo in itertools.product(constants, repeat=len(vars_list)):
        binding = dict(zip(vars_list, const_combo))

        # Verifier le body
        body_ok = all(evaluate_literal(lit, binding, background) for lit in body_lits)
        if not body_ok:
            continue

        # Extraire les arguments cibles (dedoublonnage via le set)
        target_vals = tuple(binding.get(a, a) for a in target_args)

        if target_vals in positives:
            covered_pos.add(target_vals)
        elif target_vals in negatives:
            covered_neg.add(target_vals)

    return covered_pos, covered_neg


print("FOIL --- Recherche de regles pour ancestor(x, y)")
print("=" * 55)
print()

# Clause candidate 1 : ancestor(x, y) :- parent(x, y).
body1 = [Literal("parent", ("x", "y"))]
cp1, cn1 = check_clause_covers(
    body1, "ancestor", ("x", "y"), CONSTANTS, BACKGROUND, POSITIVES, NEGATIVES
)
print(f"Clause : ancestor(x, y) :- parent(x, y).")
print(f"  Couvre {len(cp1)} positifs : {sorted(cp1)[:5]}...")
print(f"  Couvre {len(cn1)} negatifs : {sorted(cn1)[:5]}...")
print(f"  Gain FOIL : {foil_gain(len(POSITIVES), len(NEGATIVES), len(cp1), len(cn1)):.3f}")
print()

# Clause candidate 2 : ancestor(x, y) :- parent(x, z), parent(z, y).
body2 = [Literal("parent", ("x", "z")), Literal("parent", ("z", "y"))]
cp2, cn2 = check_clause_covers(
    body2, "ancestor", ("x", "y"), CONSTANTS, BACKGROUND, POSITIVES, NEGATIVES
)
print(f"Clause : ancestor(x, y) :- parent(x, z), parent(z, y).")
print(f"  Couvre {len(cp2)} positifs : {sorted(cp2)[:5]}...")
print(f"  Couvre {len(cn2)} negatifs : {sorted(cn2)[:5]}...")
print(f"  Gain FOIL : {foil_gain(len(POSITIVES), len(NEGATIVES), len(cp2), len(cn2)):.3f}")
print()

# Clause candidate 3 (recursive) : ancestor(x, y) :- parent(x, z), ancestor(z, y).
# Pour evaluer une regle recursive, on a besoin d'une definition (extension)
# de ancestor. Ici on illustre avec les seuls ancetres DIRECTS deja connus :
bg_with_direct_ancestors = BACKGROUND | {
    ("ancestor", pair) for pair in POSITIVES
    if pair in {("Arthur", "Bob"), ("Arthur", "Catherine"),
               ("Bob", "Diana"), ("Catherine", "Eve"), ("Eve", "Frank")}
}

body3 = [Literal("parent", ("x", "z")), Literal("ancestor", ("z", "y"))]
cp3, cn3 = check_clause_covers(
    body3, "ancestor", ("x", "y"), CONSTANTS, bg_with_direct_ancestors,
    POSITIVES, NEGATIVES
)
print(f"Clause : ancestor(x, y) :- parent(x, z), ancestor(z, y). [recursive]")
print(f"  Couvre {len(cp3)} positifs : {sorted(cp3)[:5]}...")
print(f"  Couvre {len(cn3)} negatifs : {sorted(cn3)[:5]}...")
print(f"  Gain FOIL : {foil_gain(len(POSITIVES), len(NEGATIVES), len(cp3), len(cn3)):.3f}")

FOIL --- Recherche de regles pour ancestor(x, y)
=======================================================

Clause : ancestor(x, y) :- parent(x, y).
  Couvre 5 positifs : [('Arthur', 'Bob'), ('Arthur', 'Catherine'), ('Bob', 'Diana'), ('Catherine', 'Eve'), ('Eve', 'Frank')]...
  Couvre 0 negatifs : []...
  Gain FOIL : 5.390

Clause : ancestor(x, y) :- parent(x, z), parent(z, y).
  Couvre 3 positifs : [('Arthur', 'Diana'), ('Arthur', 'Eve'), ('Catherine', 'Frank')]...
  Couvre 0 negatifs : []...
  Gain FOIL : 3.234

Clause : ancestor(x, y) :- parent(x, z), ancestor(z, y). [recursive]
  Couvre 3 positifs : [('Arthur', 'Diana'), ('Arthur', 'Eve'), ('Catherine', 'Frank')]...
  Couvre 0 negatifs : []...
  Gain FOIL : 3.234

Interpretation : FOIL sur le problème ancestor

L’algorithme FOIL decouvre deux règles qui couvrent tous les positifs et aucun negatif :

ancestor(X, Y) :- parent(X, Y).           % base case
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).  % récursive case

Règle	Positifs couverts	Negatifs couverts	Rôle
parent(X,Y)	Les parents directs	0	Cas de base
parent(X,Z), ancestor(Z,Y)	Les ancetres indirects	0	Cas récursif

Point cle : FOIL decouvre une recursion — une règle qui se reference elle-même. C’est une capacite unique de l’ILP par rapport a l’apprentissage propositionnel. Le gain FOIL guide la sélection des litteraux : un bon litteral maximise les positifs couverts tout en minimisant les negatifs.

---

4. Resolution inverse (bottom-up)

La resolution inverse part des exemples et les generalise pour trouver des règles. C’est l’approche complementaire de FOIL.

Opérateur V (absorption)

L’opérateur V prend une clause et un fait du background pour simplifier/generaliser :

\[\frac{C \lor L \quad \quad D \lor \neg L}{C \lor D}\]

En pratique : si on a ancestor(A,B) :- parent(A,B) et parent(A,B) est dans le background, on peut generaliser.

Opérateur W (identification)

L’opérateur W combine deux clauses pour en produire une nouvelle plus générale :

\[\frac{C_1 \lor L_1 \quad \quad C_2 \lor \neg L_2 \quad (L_1\theta = L_2\theta)}{(C_1 \lor C_2)\theta}\]

L’opérateur W est plus puissant : il peut introduire de nouvelles variables.

# Implementation simplifiee de la resolution inverse

def apply_v_operator(
    clause: HornClause,
    background_fact: Literal
) -> Optional[HornClause]:
    """Applique l'operateur V (absorption).
    
    Si un litteral du body unifie avec le background fact (nie),
    on peut retirer ce litteral du body.
    """
    for i, body_lit in enumerate(clause.body):
        neg_bg = Literal(
            background_fact.predicate,
            background_fact.args,
            negated=not background_fact.negated
        )
        subst = unify_complementary(body_lit, neg_bg, {})
        if subst is not None:
            # Retirer le litteral unifie du body
            new_body = [lit for j, lit in enumerate(clause.body) if j != i]
            # Appliquer la substitution
            new_head_args = tuple(subst.get(a, a) for a in clause.head.args)
            new_head = Literal(clause.head.predicate, new_head_args)
            new_body_lits = []
            for lit in new_body:
                new_args = tuple(subst.get(a, a) for a in lit.args)
                new_body_lits.append(Literal(lit.predicate, new_args))
            return HornClause(head=new_head, body=new_body_lits)
    return None


def apply_w_operator(
    clause1: HornClause,
    clause2: HornClause
) -> list[HornClause]:
    """Applique l'operateur W (identification).
    
    Combine deux clauses en resolvant un litteral commun.
    """
    results = []
    # Essayer de resoudre chaque paire de litteraux
    for lit1 in [clause1.head] + clause1.body:
        for lit2 in [clause2.head] + clause2.body:
            subst = unify_complementary(
                Literal(lit1.predicate, lit1.args, negated=not lit1.negated),
                lit2,
                {}
            )
            if subst is not None:
                # Construire la clause resultante
                remaining1 = [l for l in [clause1.head] + clause1.body if l is not lit1]
                remaining2 = [l for l in [clause2.head] + clause2.body if l is not lit2]
                all_lits = remaining1 + remaining2
                
                # Appliquer la substitution
                new_lits = []
                for lit in all_lits:
                    new_args = tuple(subst.get(a, a) for a in lit.args)
                    new_lits.append(Literal(lit.predicate, new_args, lit.negated))
                
                # Separer head et body
                pos_lits = [l for l in new_lits if not l.negated]
                neg_lits = [l for l in new_lits if l.negated]
                
                if len(pos_lits) >= 1:
                    results.append(HornClause(
                        head=pos_lits[0],
                        body=[Literal(l.predicate, l.args, False) for l in neg_lits]
                    ))
    return results


# Demonstration sur le probleme ancestor
print("Resolution inverse (bottom-up) sur ancestor")
print("=" * 55)
print()

# Cas de base : a partir des faits
print("Etape 1 : Cas de base")
print("  Faits parent connus :")
for (pred, args) in sorted(BACKGROUND):
    print(f"    parent({args[0]}, {args[1]})")
print()
print("  Regle decouverte : ancestor(X, Y) :- parent(X, Y).")
print("  (Par generalisation : parent => ancestor)")
print()

# Operateur V : absorber un fait
print("Etape 2 : Operateur V (absorption)")
cl = HornClause(
    head=Literal("ancestor", ("Arthur", "Diana")),
    body=[Literal("parent", ("Arthur", "Bob")), Literal("parent", ("Bob", "Diana"))]
)
print(f"  Clause initiale : {cl}")
result_v = apply_v_operator(cl, Literal("parent", ("x", "y")))
if result_v:
    print(f"  Apres V-operator : {result_v}")
print()

# Operateur W : combiner deux clauses
print("Etape 3 : Operateur W (identification)")
c1 = HornClause(
    head=Literal("ancestor", ("Arthur", "Diana")),
    body=[Literal("parent", ("Arthur", "Bob")), Literal("ancestor", ("Bob", "Diana"))]
)
c2 = HornClause(
    head=Literal("ancestor", ("Bob", "Diana")),
    body=[Literal("parent", ("Bob", "Diana"))]
)
print(f"  Clause 1 : {c1}")
print(f"  Clause 2 : {c2}")
w_results = apply_w_operator(c1, c2)
for r in w_results:
    print(f"  W-operator result : {r}")

Resolution inverse (bottom-up) sur ancestor
=======================================================

Etape 1 : Cas de base
  Faits parent connus :
    parent(Arthur, Bob)
    parent(Arthur, Catherine)
    parent(Bob, Diana)
    parent(Catherine, Eve)
    parent(Eve, Frank)

  Regle decouverte : ancestor(X, Y) :- parent(X, Y).
  (Par generalisation : parent => ancestor)

Etape 2 : Operateur V (absorption)
  Clause initiale : ancestor(Arthur, Diana) :- parent(Arthur, Bob), parent(Bob, Diana).
  Apres V-operator : ancestor(Arthur, Diana) :- parent(Bob, Diana).

Etape 3 : Operateur W (identification)
  Clause 1 : ancestor(Arthur, Diana) :- parent(Arthur, Bob), ancestor(Bob, Diana).
  Clause 2 : ancestor(Bob, Diana) :- parent(Bob, Diana).
  W-operator result : ancestor(Arthur, Diana).

Interpretation : Resolution inverse

Opérateur	Direction	Effet	Puissance
V (absorption)	Simplification	Retire un litteral du body en l’absorbant	Faible (pas de nouvelles variables)
W (identification)	Combination	Fusionne deux clauses en generalisant	Fort (introduit de nouvelles variables)

Comparaison avec FOIL : La resolution inverse part des exemples spécifiques et generalise, tandis que FOIL part de la règle la plus générale et specialise. Les deux approches visent les mêmes règles mais par des chemins opposes.

PROGOL (Muggleton, 1995) combine les deux : il contraint la recherche bottom-up avec des bornes top-down, obtenant un espace de recherche plus petit.

---

5. Application complete — FOIL pas-a-pas

Revoyons FOIL en detail sur le problème ancestor, en montrant chaque étape de la sélection des litteraux.

# FOIL pas-a-pas avec trace detaillee (couverture d'EXEMPLES + litteral recursif)

def foil_step_by_step(
    target_pred: str,
    target_args: tuple[str, ...],
    constants: set[str],
    background: set[tuple[str, tuple[str, ...]]],
    positives: set[tuple[str, ...]],
    negatives: set[tuple[str, ...]],
    candidate_literals: list[Literal],
    max_rules: int = 4
) -> tuple[list[HornClause], set[tuple[str, ...]]]:
    """FOIL simplifie (sequential covering) avec trace detaillee.

    Deux ingredients rendent l'apprentissage de la recursion possible :
      - la couverture compte des EXEMPLES distincts (cf. check_clause_covers) ;
      - le litteral recursif ancestor(., .) est evalue contre l'EXTENSION connue
        de la cible (les exemples positifs), procede standard de FOIL pour les
        predicats recursifs.
    """
    # Extension de la cible pour evaluer les litteraux recursifs
    bg_rec = set(background) | {(target_pred, p) for p in positives}

    learned_rules: list[HornClause] = []
    remaining_pos = set(positives)

    rule_num = 0
    while remaining_pos and rule_num < max_rules:
        rule_num += 1
        print(f"\n--- Regle {rule_num} ---")
        print(f"Positifs restants : {len(remaining_pos)}")

        best_clause_body: list[Literal] = []
        covered_pos = set(remaining_pos)
        covered_neg = set(negatives)

        for depth in range(4):
            print(f"\n  Profondeur {depth} :")
            print(f"    Body actuel : {', '.join(str(l) for l in best_clause_body) or 'true'}")
            print(f"    Exemples pos couverts : {len(covered_pos)}, neg couverts : {len(covered_neg)}")

            if len(covered_neg) == 0:
                print(f"    -> Clause consistante !")
                break

            best_gain = float('-inf')
            best_lit = None
            best_cp: set = set()
            best_cn: set = set()

            for cand in candidate_literals:
                trial_body = best_clause_body + [cand]
                cp, cn = check_clause_covers(
                    trial_body, target_pred, target_args,
                    constants, bg_rec, remaining_pos, negatives
                )
                gain = foil_gain(len(covered_pos), len(covered_neg), len(cp), len(cn))
                if gain > best_gain:
                    best_gain = gain
                    best_lit = cand
                    best_cp = cp
                    best_cn = cn

            if best_lit is not None and best_gain > 0:
                print(f"    Meilleur litteral : {best_lit} (gain={best_gain:.3f})")
                best_clause_body.append(best_lit)
                covered_pos = best_cp
                covered_neg = best_cn
            else:
                print(f"    Pas d'amelioration possible")
                break

        # Garde de consistance : on n'apprend une clause que si elle couvre au
        # moins un positif ET aucun negatif (pas de regle inconsistante emise).
        if best_clause_body and covered_pos and len(covered_neg) == 0:
            rule = HornClause(
                head=Literal(target_pred, target_args),
                body=best_clause_body
            )
            learned_rules.append(rule)
            print(f"\n  Regle apprise : {rule}")
            remaining_pos -= covered_pos
        else:
            print(f"\n  Aucune clause consistante pour les {len(remaining_pos)} "
                  f"positifs restants : arret (pas de regle inconsistante emise).")
            break

    return learned_rules, remaining_pos


# Litteraux candidats : parent/2 (toutes orientations) + litteraux RECURSIFs
# ancestor/2, indispensables pour atteindre les ancetres profonds (Arthur->Frank).
CANDIDATES = [
    Literal("parent", ("x", "y")),
    Literal("parent", ("y", "x")),
    Literal("parent", ("x", "z")),
    Literal("parent", ("z", "y")),
    Literal("parent", ("z", "x")),
    Literal("parent", ("y", "z")),
    Literal("ancestor", ("z", "y")),
    Literal("ancestor", ("x", "z")),
]

rules, uncovered = foil_step_by_step(
    "ancestor", ("x", "y"), CONSTANTS, BACKGROUND,
    POSITIVES, NEGATIVES, CANDIDATES
)

print("\n" + "=" * 55)
print("Regles apprises par FOIL :")
for r in rules:
    print(f"  {r}")
print(f"\nPositifs non couverts : "
      f"{sorted(uncovered) if uncovered else 'aucun (couverture complete)'}")

--- Regle 1 ---
Positifs restants : 9

  Profondeur 0 :
    Body actuel : true
    Exemples pos couverts : 9, neg couverts : 10
    Meilleur litteral : parent(x, y) (gain=5.390)

  Profondeur 1 :
    Body actuel : parent(x, y)
    Exemples pos couverts : 5, neg couverts : 0
    -> Clause consistante !

  Regle apprise : ancestor(x, y) :- parent(x, y).

--- Regle 2 ---
Positifs restants : 4

  Profondeur 0 :
    Body actuel : true
    Exemples pos couverts : 4, neg couverts : 10
    Meilleur litteral : parent(x, z) (gain=1.942)

  Profondeur 1 :
    Body actuel : parent(x, z)
    Exemples pos couverts : 4, neg couverts : 6
    Meilleur litteral : ancestor(z, y) (gain=5.288)

  Profondeur 2 :
    Body actuel : parent(x, z), ancestor(z, y)
    Exemples pos couverts : 4, neg couverts : 0
    -> Clause consistante !

  Regle apprise : ancestor(x, y) :- parent(x, z), ancestor(z, y).

=======================================================
Regles apprises par FOIL :
  ancestor(x, y) :- parent(x, y).
  ancestor(x, y) :- parent(x, z), ancestor(z, y).

Positifs non couverts : aucun (couverture complete)

Interpretation : FOIL pas-a-pas

La trace ci-dessus montre FOIL apprendre, par couverture séquentielle, la definition récursive complete de ancestor — deux règles qui couvrent tous les positifs et aucun negatif :

1. Règle 1 — cas de base. ancestor(x, y) :- parent(x, y). Des la profondeur 0, parent(x, y) a le meilleur gain (il couvre les 5 ancetres directs, 0 negatif) ; la clause est immediatement consistante.

2. Règle 2 — cas récursif. ancestor(x, y) :- parent(x, z), ancestor(z, y). Pour les 4 positifs restants (ancetres indirects, dont l’arriere-grand-parent ancestor(Arthur, Frank)), FOIL ajoute d’abord parent(x, z) puis le litteral récursif ancestor(z, y). La clause couvre alors les 4 et reste consistante : la recursion est apprise.

Comment la recursion devient apprenable. Deux ingredients, par rapport a une version naive : - on compte des exemples distincts, pas des bindings : un même positif couvert par plusieurs valeurs de l’intermediaire z ne compte qu’une fois. Sans ce dedoublonnage, un litteral comme parent(x, z) gonfle son compte et masque le bon litteral — c’est la subtilite “tuples vs exemples” de l’analyse FOIL d’AIMA 19.5.1, ici tranchee en faveur des exemples pour un apprentissage lisible ; - le litteral récursif ancestor(z, y) est evalue contre l’extension connue de la cible (les exemples positifs), procede standard de FOIL pour les predicats recursifs.

Garde de consistance. L’apprenant n’emet une clause que si elle couvre au moins un positif et aucun negatif : il prefere s’arreter honnetement plutot que de produire une règle inconsistante. Ici la couverture est complete, aucun positif ne reste.

Pour aller plus loin. Les systèmes ILP complets (FOIL original, Progol, Popper — section suivante) ajoutent l’elagage des litteraux redondants, la tolerance au bruit, et des biais de langage plus riches.

---

6. ILP et Knowledge Graphs

L’ILP a une connexion naturelle avec les graphes de connaissances (Knowledge Graphs, KGs) :

Concept ILP	Equivalent Knowledge Graph
Fait P(A, B)	Triple RDF (A, P, B)
Règle Horn	Règle SPARQL CONSTRUCT
Background knowledge	Ontologie T-Box
Exemples positifs/negatifs	Instances A-Box

Règles AMIE (Association Rule Mining under Incomplete Evidence)

AMIE3 est un système moderne qui mine des règles sur les KGs :

?a marriedTo ?b => ?b marriedTo ?a     (symetrie)
?a livesIn ?b, ?b locatedIn ?c => ?a livesIn ?c  (transitivite)

Connexion inter-series : Les notebooks SemanticWeb (SW-11 Knowledge Graphs, SW-4b SPARQL) couvrent les graphes RDF et SPARQL. L’ILP fournit le cadre théorique pour apprendre des règles sur ces graphes, tandis que SW-11/SW-4b montrent comment les interroger.

# Illustration : ILP sur un mini Knowledge Graph

# Un mini-KG en triples (sujet, predicat, objet)
KG_TRIPLES = {
    ("Alice", "marriedTo", "Bob"),
    ("Bob", "marriedTo", "Alice"),
    ("Alice", "livesIn", "Paris"),
    ("Bob", "livesIn", "Paris"),
    ("Paris", "locatedIn", "France"),
    ("Lyon", "locatedIn", "France"),
    ("Charlie", "livesIn", "Lyon"),
    ("Diana", "livesIn", "Paris"),
    ("Diana", "marriedTo", "Charlie"),
    ("Charlie", "marriedTo", "Diana"),
}

print("Mini Knowledge Graph")
print("=" * 50)
for s, p, o in sorted(KG_TRIPLES):
    print(f"  ({s}, {p}, {o})")

print()
print("Regles ILP potentielles sur ce KG :")
print()
print("1. Symetrie du mariage :")
print("   marriedTo(X, Y) :- marriedTo(Y, X).")
count_sym = 0
for s, p, o in KG_TRIPLES:
    if p == "marriedTo" and (o, "marriedTo", s) in KG_TRIPLES:
        count_sym += 1
print(f"   Couples verifiant la symetrie : {count_sym}")

print()
print("2. Transitivite de localisation :")
print("   livesIn(X, Z) :- livesIn(X, Y), locatedIn(Y, Z).")
count_trans = 0
for s1, p1, o1 in KG_TRIPLES:
    if p1 == "livesIn":
        for s2, p2, o2 in KG_TRIPLES:
            if p2 == "locatedIn" and s2 == o1:
                implied = (s1, "livesIn", o2)
                is_explicit = implied in KG_TRIPLES
                count_trans += 1
                status = "EXPLICITE" if is_explicit else "IMPLICITE (infere)"
                if count_trans <= 5:
                    print(f"   {s1} livesIn {o1}, {o1} locatedIn {o2} => {s1} livesIn {o2} [{status}]")
print(f"   Total inferences possibles : {count_trans}")

print()
print("3. Co-residence des epoux :")
print("   livesIn(X, L) :- marriedTo(X, Y), livesIn(Y, L).")
count_core = 0
for s1, p1, o1 in KG_TRIPLES:
    if p1 == "marriedTo":
        for s2, p2, o2 in KG_TRIPLES:
            if p2 == "livesIn" and s2 == o1:
                implied = (s1, "livesIn", o2)
                is_explicit = implied in KG_TRIPLES
                count_core += 1
                status = "EXPLICITE" if is_explicit else "NON VERIFIE"
                if count_core <= 5:
                    print(f"   {s1} marriedTo {o1}, {o1} livesIn {o2} => {s1} livesIn {o2} [{status}]")
print(f"   Total inferences : {count_core}")

Mini Knowledge Graph
==================================================
  (Alice, livesIn, Paris)
  (Alice, marriedTo, Bob)
  (Bob, livesIn, Paris)
  (Bob, marriedTo, Alice)
  (Charlie, livesIn, Lyon)
  (Charlie, marriedTo, Diana)
  (Diana, livesIn, Paris)
  (Diana, marriedTo, Charlie)
  (Lyon, locatedIn, France)
  (Paris, locatedIn, France)

Regles ILP potentielles sur ce KG :

1. Symetrie du mariage :
   marriedTo(X, Y) :- marriedTo(Y, X).
   Couples verifiant la symetrie : 4

2. Transitivite de localisation :
   livesIn(X, Z) :- livesIn(X, Y), locatedIn(Y, Z).
   Bob livesIn Paris, Paris locatedIn France => Bob livesIn France [IMPLICITE (infere)]
   Charlie livesIn Lyon, Lyon locatedIn France => Charlie livesIn France [IMPLICITE (infere)]
   Diana livesIn Paris, Paris locatedIn France => Diana livesIn France [IMPLICITE (infere)]
   Alice livesIn Paris, Paris locatedIn France => Alice livesIn France [IMPLICITE (infere)]
   Total inferences possibles : 4

3. Co-residence des epoux :
   livesIn(X, L) :- marriedTo(X, Y), livesIn(Y, L).
   Alice marriedTo Bob, Bob livesIn Paris => Alice livesIn Paris [EXPLICITE]
   Charlie marriedTo Diana, Diana livesIn Paris => Charlie livesIn Paris [NON VERIFIE]
   Bob marriedTo Alice, Alice livesIn Paris => Bob livesIn Paris [EXPLICITE]
   Diana marriedTo Charlie, Charlie livesIn Lyon => Diana livesIn Lyon [NON VERIFIE]
   Total inferences : 4

Interpretation : ILP et Knowledge Graphs

Règle ILP	Type	Verifiee sur le KG ?
Symetrie mariage	Axiome OWL SymmetricProperty	Oui (100%)
Transitivite localisation	Propriete composee (SPARQL property path)	Partiellement (implicite)
Co-residence epoux	Règle metier	Partiellement (depends des données)

Point cle : L’ILP peut decouvrir ces règles automatiquement a partir du KG, tandis qu’en SemanticWeb on les declare dans l’ontologie. Les deux approches sont complementaires : l’ILP decouvre, le Web Sémantique formalise.

AMIE3 (Lajus et al., 2020) est un système ILP moderne qui mine des règles sur des KGs contenant des millions de triples. Il utilise des mesures de confiance (PCA, standard) pour evaluer la qualite des règles.

---

La vraie librairie : Popper (Learning From Failures)

Le FOIL implemente ci-dessus date de 1990 : il construit ses clauses gloutonnement, litteral par litteral, guide par le gain d’information. L’ILP moderne pose le problème autrement.

Origine. Popper (Learning From Failures, LFF) est introduit par Cropper, A. & Morel, R. (2021), Learning programs by learning from failures, Machine Learning — qui reformule l’ILP comme un problème de satisfaction de contraintes dirige par les echecs, garantissant l’optimalite (programme le plus court).

Popper (Cropper & Morel, 2021) formule l’apprentissage comme une recherche dans l’espace des programmes complets, dirigee par les echecs (Learning From Failures) : chaque hypothese testee qui echoue genere des contraintes qui elaguent definitivement des familles entieres de programmes. Popper garantit de trouver un programme optimal (taille minimale) couvrant tous les positifs et aucun negatif – la ou FOIL ne garantit qu’un optimum local glouton.

Sous le capot, Popper combine exactement les deux moteurs rencontres dans cette serie :

• clingo (ASP, utilise dans SL-8) enumere les hypotheses candidates comme modèles stables d’un encodage du langage d’hypotheses ;
• SWI-Prolog (via le pont janus_swi) teste chaque hypothese contre les exemples.

Note environnement : Popper s’appuie sur signal.SIGALRM, qui n’existe pas sous Windows. Ce notebook s’execute donc sur un kernel Python Linux (python3-wsl : WSL sous Windows ; kernel natif sous Linux/macOS). Le reste du notebook est en Python standard et tourne sur n’importe quel kernel. Versions epinglees : Popper v4.4.0 (la 5.0 exige Python >= 3.14), janus_swi (requiert SWI-Prolog >= 9.1.12, PPA ppa:swi-prolog/stable), setuptools < 81 (Popper importe encore pkg_resources).

# Environnement Popper : kernel Python Linux requis (SIGALRM absent de Windows)
import importlib.util, platform, shutil, subprocess, sys, warnings

HAS_POPPER = False
swipl = shutil.which("swipl")
print(f"Python : {sys.version.split()[0]} ({platform.system()})")
print(f"swipl  : {swipl or 'INTROUVABLE'}")

if platform.system() != "Linux":
    print("\nPopper requiert un OS Unix (SIGALRM) : basculer sur le kernel 'python3-wsl'")
    print("(Windows + WSL) ou un kernel Python natif Linux/macOS.")
elif swipl is None:
    print("\nSWI-Prolog manquant : sudo apt install swi-prolog")
    print("(version >= 9.1.12 requise par janus_swi -> PPA ppa:swi-prolog/stable).")
else:
    if importlib.util.find_spec("popper") is None:
        subprocess.check_call([sys.executable, "-m", "pip", "install", "-q",
                               "setuptools<81", "clingo",
                               "git+https://github.com/logic-and-learning-lab/Popper@v4.4.0"])
    warnings.filterwarnings("ignore", message=".*pkg_resources.*")
    import clingo
    import popper
    HAS_POPPER = True
    print(f"clingo : {clingo.__version__}")
    # La version de paquet Popper ment (setup.py jamais bumpé : 4.2.0 déclaré pour un install du tag
    # v4.4.0) -- la provenance honnête est direct_url.json (install git), sinon la version de
    # distribution, annoncée comme telle.
    import importlib.metadata as _imd
    try:
        import json as _json
        _du = _json.loads(_imd.distribution("popper_ilp").read_text("direct_url.json"))
        _ci = (_du.get("vcs_info") or {}).get("commit_id", "")
        _prov = _du.get("url", "?") + (f" @ {_ci[:10]}" if _ci else "")
        print(f"Popper : {_prov} -- pret")
    except Exception:
        try:
            print(f"Popper : v{_imd.version('popper_ilp')} (version de distribution) -- pret")
        except Exception:
            print("Popper : installé (provenance indisponible) -- pret")

Python : 3.12.3 (Linux)
swipl  : /usr/bin/swipl
clingo : 5.8.2
Popper : https://github.com/logic-and-learning-lab/Popper @ 860cd0deab -- pret

# Le probleme ancestor, cette fois resolu par Popper -- memes faits, memes exemples.
# Popper tourne dans un sous-processus : son testeur Prolog (janus) garde un etat
# global par processus, et deux apprentissages successifs dans le meme kernel
# cumuleraient les faits consultes (comptes d'exemples fausses).
import json, subprocess, sys, tempfile
from pathlib import Path

POPPER_RUNNER = r'''
import json, sys, warnings
warnings.filterwarnings("ignore")
from popper.util import Settings, format_prog
# Patch de compatibilite Popper v4.4.0 : en mode datalog, l'ordonnancement des
# litteraux ne connait pas le predicat de tete (recursif) -> pire score, donc
# ordonne en dernier, ce qui est le comportement voulu.
def tmp_score_(self, seen_vars, literal):
    pred, args = literal
    return self.recall.get((pred, tuple(1 if x in seen_vars else 0 for x in args)), float("inf"))
Settings.tmp_score_ = tmp_score_
from popper.loop import learn_solution
settings = Settings(kbpath=sys.argv[1], quiet=True)
prog, score, stats = learn_solution(settings)
print(json.dumps({"prog": format_prog(prog) if prog else None, "score": score}))
'''

def run_popper(kbpath: Path) -> dict:
    """Lance Popper sur un repertoire de tache (bias.pl, bk.pl, exs.pl), isole."""
    out = subprocess.run([sys.executable, "-c", POPPER_RUNNER, str(kbpath)],
                         capture_output=True, text=True, timeout=300)
    return json.loads(out.stdout.strip().splitlines()[-1])

if HAS_POPPER:
    task = Path(tempfile.mkdtemp(prefix="popper_ancestor_"))
    (task / "bk.pl").write_text(
        "".join(f"parent({p.lower()},{c.lower()}).\n" for _, (p, c) in sorted(BACKGROUND)))
    (task / "exs.pl").write_text(
        "".join(f"pos(ancestor({x.lower()},{y.lower()})).\n" for x, y in sorted(POSITIVES)) +
        "".join(f"neg(ancestor({x.lower()},{y.lower()})).\n" for x, y in sorted(NEGATIVES)))
    (task / "bias.pl").write_text(
        "max_vars(3).\nmax_body(2).\nmax_clauses(2).\n"
        "head_pred(ancestor,2).\nbody_pred(parent,2).\nenable_recursion.\n")

    result = run_popper(task)
    tp, fn, tn, fp, size = result["score"]
    print("Programme appris par Popper :\n")
    print(result["prog"])
    print(f"\nScore : {tp} tp, {fn} fn, {tn} tn, {fp} fp -- taille {size} litteraux")
else:
    result = None
    print("Popper indisponible : cellule sautee (voir instructions ci-dessus).")

Programme appris par Popper :

ancestor(V0,V1):- parent(V0,V1).
ancestor(V0,V1):- parent(V0,V2),ancestor(V2,V1).

Score : 9 tp, 0 fn, 10 tn, 0 fp -- taille 5 litteraux

Ablation et vérification indépendante : deux réflexes méthodologiques

La cellule suivante met en œuvre deux pratiques centrales en apprentissage automatique, et particulièrement en ILP :

1. L’ablation — retirer volontairement une capacité au système et mesurer ce qui se dégrade. Ici, on supprime enable_recursion du bias de Popper, puis on relance l’apprentissage sur le même problème ancestor. La récursivité est précisément ce qui distingue l’ILP de l’apprentissage propositionnel : sans elle, Popper retombe sur un fragment de Datalog incapable d’exprimer une relation transitive (qui se propage de parents en ancêtres). La question n’est donc pas « Popper réussit-il ? » mais « quelle part de sa puissance vient de la récursivité ? ». Si l’ablation dégrade fortement le score, la récursivité était nécessaire ; si elle ne change rien, elle était accessoire. C’est la différence entre constater qu’un outil marche et comprendre pourquoi.

2. La vérification indépendante — ré-exécuter le programme appris dans un moteur Prolog séparé (SWI-Prolog via janus), hors du contrôle de Popper. Popper produit un programme ; on ne le croit pas sur parole : on charge sa sortie dans un autre solveur et l’on vérifie qu’il dérive bien les positifs attendus et aucun négatif. Ce réflexe « trust-but-verify » protège contre une clause syntaxiquement valide mais sémantiquement fausse qui passerait inaperçue dans le score interne de Popper — démarche homologue à la validation croisée clingo de SL-6.

Ces deux réflexes incarnent la thèse de Popper, Learning From Failures : on apprend en accumulant les échecs, et l’ablation est la forme la plus directe de « faire échouer » pour isoler ce qui compte vraiment.

# 1) Ablation : que peut apprendre Popper SANS le droit a la recursion ?
# 2) Verification independante : le programme appris est execute en Prolog (janus),
#    hors de Popper -- meme esprit que la validation croisee clingo de SL-6.
if HAS_POPPER and result and result["prog"]:
    norec = Path(tempfile.mkdtemp(prefix="popper_norec_"))
    for f in ("bk.pl", "exs.pl"):
        (norec / f).write_text((task / f).read_text())
    (norec / "bias.pl").write_text(
        "max_vars(4).\nmax_body(3).\nmax_clauses(3).\n"
        "head_pred(ancestor,2).\nbody_pred(parent,2).\n")
    ablation = run_popper(norec)
    tp, fn, tn, fp, size = ablation["score"]
    print("Sans enable_recursion :\n")
    print(ablation["prog"])
    print(f"\nScore : {tp} tp, {fn} fn, {tn} tn, {fp} fp -- taille {size} litteraux")

    import janus_swi as janus
    janus.consult(str(task / "bk.pl"))
    janus.consult("learned", result["prog"] + "\n")
    derive = lambda x, y: janus.query_once(f"ancestor({x.lower()},{y.lower()})")["truth"]
    vp = sum(1 for x, y in POSITIVES if derive(x, y))
    vn = sum(1 for x, y in NEGATIVES if derive(x, y))
    print(f"\nVerification SWI-Prolog du programme recursif :")
    print(f"  {vp}/{len(POSITIVES)} positifs derives, {vn}/{len(NEGATIVES)} negatifs derives")
else:
    print("Popper indisponible : cellule sautee.")

Sans enable_recursion :

ancestor(V0,V1):- parent(V3,V1),parent(V0,V2),parent(V2,V3).
ancestor(V0,V1):- parent(V0,V1).
ancestor(V0,V1):- parent(V0,V2),parent(V2,V1).

Score : 9 tp, 0 fn, 10 tn, 0 fp -- taille 9 litteraux

Verification SWI-Prolog du programme recursif :
  9/9 positifs derives, 0/10 negatifs derives

Interpretation : ce que Popper change par rapport a FOIL

1. L’optimalite remplace la gloutonnerie. Popper retrouve le programme canonique (cas de base + cas récursif, 5 litteraux) en une fraction de seconde, et prouve qu’aucun programme plus court ne couvre les exemples : les contraintes accumulees a chaque echec elaguent l’espace au lieu de re-scorer des clauses une par une. FOIL, glouton, peut s’arreter sur des clauses correctes mais non minimales (comparez avec la trace pas-a-pas plus haut).

2. La recursion est la compression infinie. L’ablation sans enable_recursion le montre : Popper ne peut alors que deplier des chaînes parent de profondeur bornee (un programme presque deux fois plus gros), qui echouerait sur une genealogie plus profonde que le biais. Les deux clauses recursives, elles, couvrent une profondeur arbitraire – c’est exactement l’argument de la cellule FOIL récursive, mais ici la recursion est apprise et certifiee optimale, pas seulement proposee.

3. Un apprenant exact est aussi un verificateur de données. La toute première exécution de Popper sur ce notebook a refuse le score parfait : la paire ancestor(bob, frank), presente dans les exemples positifs depuis la creation du dataset, n’est pas derivable du background (la lignee de Frank passe par Catherine et Eve, pas par Bob). FOIL, qui ne cherche que des clauses a gain positif, n’avait jamais signale l’incoherence ; Popper, qui exige de couvrir tous les positifs, l’a exposee immediatement – le dataset a ete corrige (9 positifs). Pour des données reellement bruitees, Popper propose un mode noisy qui optimise le compromis couverture/taille au lieu d’exiger la perfection.

Pour aller plus loin : le depot Popper fournit des dizaines de tâches classiques (trains de Michalski, zendo, jeux IGGP) pretes a l’emploi. Cote apprentissage de programmes ASP, voir ILASP (mentionne dans SL-8) ; cote systèmes historiques, Aleph (Progol-like, voir SL-5) reste accessible via SWI-Prolog.

Tete-a-tete des moteurs reels. Popper est ici l’un des quatre moteurs ILP reels mis cote a cote dans SL-6 — Moteurs ILP modernes, face a Aleph (entailment inverse), Metagol (apprentissage meta-interpretatif, avec invention de predicat) et dILP (ILP differentiable, DeepMind) – les quatre apprennent la même relation récursive ancestor/2, chacun par une machinerie radicalement différente.

---

7. Exercices

Tableau recapitulatif

Concept	Formule	Implementation
Clause Horn	head :- body.	HornClause
Unification	\(\theta = \{x/A\}\)	unify()
Appariement complementaire	\(L\theta = \neg L'\theta\)	unify_complementary()
FOIL gain	\(\vert T^+_{new}\vert \times (\log_2 \frac{\vert T^+\vert }{\vert T\vert } - \ldots)\)	foil_gain()
Opérateur V	Absorption	apply_v_operator()
Opérateur W	Identification	apply_w_operator()

Exemple guidé : apprendre sibling avec FOIL

Avant de passer aux exercices, voici un exemple entièrement résolu qui réutilise l’implémentation de FOIL de la section 3 sur un nouveau concept : la relation frère/sœur sibling(x, y) :- parent(z, x), parent(z, y), neq(x, y).

L’exemple déroule les trois étapes attendues d’un problème ILP : (1) constituer le background — ici l’inégalité neq/2, FOIL n’ayant pas de \= natif ; (2) fournir les exemples positifs et négatifs ; (3) laisser FOIL sélectionner les littéraux du corps par gain d’information. La trace pas-à-pas montre notamment pourquoi le littéral neq(x, y) est indispensable pour exclure les paires (p, p). Chaque exercice « À votre tour » qui suit reprend ce schéma sur un autre concept.

# Exemple guide : Apprendre la regle "sibling" avec FOIL
# Objectif : retrouver sibling(x, y) :- parent(z, x), parent(z, y), neq(x, y).
# Etape 1 : background + inegalite. FOIL n'a pas de predicat builtin "\=" :
# on l'encode comme fait neq/2 dans le background.
SIB_BG = set(BACKGROUND)
for a in CONSTANTS:
    for b in CONSTANTS:
        if a != b:
            SIB_BG.add(("neq", (a, b)))
# Etape 2 : exemples. Deux personnes sont siblings ssi elles partagent un
# parent direct et sont distinctes. Dans la famille ci-dessus, seuls Bob et
# Catherine ont un parent commun (Arthur).
SIB_POS = {("Bob", "Catherine"), ("Catherine", "Bob")}
SIB_NEG = {
    ("Bob", "Diana"), ("Diana", "Bob"),
    ("Catherine", "Eve"), ("Eve", "Catherine"),
    ("Diana", "Frank"), ("Frank", "Diana"),
    ("Arthur", "Bob"), ("Bob", "Arthur"),
    ("Bob", "Bob"),
    ("Diana", "Eve"), ("Eve", "Diana"),
}
# Etape 3 : litteraux candidats et selection par gain FOIL.
target_args = ("x", "y")
candidats = [
    [Literal("parent", ("z", "x"))],
    [Literal("parent", ("z", "x")), Literal("parent", ("z", "y"))],
    [Literal("parent", ("z", "x")), Literal("parent", ("z", "y")), Literal("neq", ("x", "y"))],
]
print("Apprentissage de sibling(x, y) -- trace pas-a-pas FOIL")
print("=" * 58)
prev_pos, prev_neg = None, None
for body in candidats:
    cp, cn = check_clause_covers(body, "sibling", target_args, CONSTANTS, SIB_BG, SIB_POS, SIB_NEG)
    cp_set, cn_set = set(cp), set(cn)
    print(f"\nBody : {', '.join(str(l) for l in body)}")
    print(f"  couvre {len(cp_set)} positif(s) : {sorted(cp_set)}")
    print(f"  couvre {len(cn_set)} negatif(s) : {sorted(cn_set)}")
    if prev_pos is not None:
        g = foil_gain(prev_pos, prev_neg, len(cp_set), len(cp_set) + len(cn_set))
        print(f"  gain FOIL vs body precedent : {g:.3f}")
    prev_pos, prev_neg = len(cp_set), len(cp_set) + len(cn_set)
regle_sibling = HornClause(
    Literal("sibling", ("x", "y")),
    [Literal("parent", ("z", "x")), Literal("parent", ("z", "y")), Literal("neq", ("x", "y"))],
)
print("\n" + "=" * 58)
print(f"Regle apprise : {regle_sibling}")
final_pos, final_neg = check_clause_covers(
    regle_sibling.body, "sibling", target_args, CONSTANTS, SIB_BG, SIB_POS, SIB_NEG)
final_pos_set, final_neg_set = set(final_pos), set(final_neg)
print(f"\nVerification : {len(final_pos_set)} positif(s) couvert(s), "
      f"{len(final_neg_set)} negatif(s) couvert(s)")
assert final_pos_set == SIB_POS, f"Couverture positive incorrecte : {final_pos_set}"
assert final_neg_set == set(), f"La regle couvre un negatif : {final_neg_set}"
print("OK : la regle couvre exactement les siblings, sans faux positif.")
print("\nLecture : deux personnes sont siblings ssi elles partagent un parent")
print("ET sont distinctes -- neq(x, y) est indispensable pour exclure (Bob, Bob).")

Apprentissage de sibling(x, y) -- trace pas-a-pas FOIL
==========================================================

Body : parent(z, x)
  couvre 2 positif(s) : [('Bob', 'Catherine'), ('Catherine', 'Bob')]
  couvre 10 negatif(s) : [('Bob', 'Arthur'), ('Bob', 'Bob'), ('Bob', 'Diana'), ('Catherine', 'Eve'), ('Diana', 'Bob'), ('Diana', 'Eve'), ('Diana', 'Frank'), ('Eve', 'Catherine'), ('Eve', 'Diana'), ('Frank', 'Diana')]

Body : parent(z, x), parent(z, y)
  couvre 2 positif(s) : [('Bob', 'Catherine'), ('Catherine', 'Bob')]
  couvre 1 negatif(s) : [('Bob', 'Bob')]
  gain FOIL vs body precedent : 2.971

Body : parent(z, x), parent(z, y), neq(x, y)
  couvre 2 positif(s) : [('Bob', 'Catherine'), ('Catherine', 'Bob')]
  couvre 0 negatif(s) : []
  gain FOIL vs body precedent : 0.644

==========================================================
Regle apprise : sibling(x, y) :- parent(z, x), parent(z, y), neq(x, y).

Verification : 2 positif(s) couvert(s), 0 negatif(s) couvert(s)
OK : la regle couvre exactement les siblings, sans faux positif.

Lecture : deux personnes sont siblings ssi elles partagent un parent
ET sont distinctes -- neq(x, y) est indispensable pour exclure (Bob, Bob).

A votre tour : la règle “offspring” (inverse de parent) avec FOIL

Appliquez FOIL a la relation offspring (x est l’enfant de y) : c’est l’inverse exact de parent. Cet exercice consolide le fonctionnement de FOIL avant le passage aux opérateurs bottom-up (W) dans la section suivante.

# Exercice : Apprendre la regle "offspring" (x enfant de y) avec FOIL
# TODO etudiant : apprenez offspring(x, y) :- parent(y, x).
# Indice : un seul litteral suffit dans le body (l'inverse de parent).
# Etape 1 : definissez les positifs (couples (enfant, parent)) et negatifs
# Etape 2 : quel litteral candidat couvre exactement les positifs sans negatif ?
# Etape 3 : executez FOIL avec check_clause_covers et verifiez la couverture
print("Exercice a completer : regle offspring (inverse de parent)")
print("Etape 1 : listez les couples (enfant, parent) de la famille")
print("Etape 2 : proposez le body a un seul litteral")
print("Etape 3 : verifiez que la couverture est exacte (0 negatif)")

Exercice a completer : regle offspring (inverse de parent)
Etape 1 : listez les couples (enfant, parent) de la famille
Etape 2 : proposez le body a un seul litteral
Etape 3 : verifiez que la couverture est exacte (0 negatif)

L’exercice suivant change de perspective : au lieu d’utiliser FOIL (top-down), vous appliquerez l’opérateur W (bottom-up) pour generaliser des clauses spécifiques.

# Exemple guide : Operateur W (identification) sur un domaine de transport
# Objectif : combiner deux clauses via l'operateur W pour generaliser, comme la
# demo ancestor de la section precedente, mais sur un NOUVEAU domaine (un reseau
# de transports). On montre que l'identification est domain-agnostique.
# Domaine : direct(X, Y) = liaison directe ; connected(X, Y) = joignable (transitif).

# Etape 1 : le reseau de liaisons directes (background du domaine).
DIRECT = {
    ("direct", "Paris", "Brussels"),
    ("direct", "Brussels", "Berlin"),
    ("direct", "Berlin", "Warsaw"),
    ("direct", "Lyon", "Paris"),
}
print("Liaisons directes (background) :")
for (pred, a, b) in sorted(DIRECT):
    print(f"  {pred}({a}, {b})")
print()

# Etape 2 : deux clauses specifiques a combiner.
#   c1 (recursive) : connected(Paris, Berlin) :- direct(Paris, Brussels), connected(Brussels, Berlin)
#   c2 (cas de base) : connected(Brussels, Berlin) :- direct(Brussels, Berlin)
# L'operateur W resout le litteral commun connected(Brussels, Berlin) -- present
# dans le body de c1 ET en tete de c2 -- pour fusionner les deux clauses.
c1 = HornClause(
    head=Literal("connected", ("Paris", "Berlin")),
    body=[Literal("direct", ("Paris", "Brussels")),
          Literal("connected", ("Brussels", "Berlin"))],
)
c2 = HornClause(
    head=Literal("connected", ("Brussels", "Berlin")),
    body=[Literal("direct", ("Brussels", "Berlin"))],
)
print(f"Clause 1 (recursive) : {c1}")
print(f"Clause 2 (base)      : {c2}")
print()

# Etape 3 : application de l'operateur W (identification).
w_results = apply_w_operator(c1, c2)
print(f"Operateur W : {len(w_results)} clause(s) resultante(s)")
for r in w_results:
    print(f"  -> {r}")
print()

# Lecture : W a resolu connected(Brussels, Berlin) et renvoye la tete generalisee
# connected(Paris, Berlin). C'est l'etape d'identification de la resolution
# inverse : a partir de la regle recursive + le cas de base, on reconstruit le
# fait compose "Paris est connecte a Berlin". La version simplifiee du notebook
# retourne la tete seule ; un systeme complet (Progol) preserverait en plus le
# body non-resolu (direct(Paris, Brussels), direct(Brussels, Berlin)).
assert any(r.head.predicate == "connected"
           and tuple(r.head.args) == ("Paris", "Berlin") for r in w_results), \
    "le W-operator doit produire connected(Paris, Berlin)"
print("OK : connected(Paris, Berlin) reconstruit par identification (operateur W).")

Liaisons directes (background) :
  direct(Berlin, Warsaw)
  direct(Brussels, Berlin)
  direct(Lyon, Paris)
  direct(Paris, Brussels)

Clause 1 (recursive) : connected(Paris, Berlin) :- direct(Paris, Brussels), connected(Brussels, Berlin).
Clause 2 (base)      : connected(Brussels, Berlin) :- direct(Brussels, Berlin).

Operateur W : 1 clause(s) resultante(s)
  -> connected(Paris, Berlin).

OK : connected(Paris, Berlin) reconstruit par identification (operateur W).

A votre tour : opérateur W sur un tournoi (sport)

Changez de domaine pour verifier que l’identification est bien un mécanisme generique : appliquez l’opérateur W a un tournoi ou defeated(X, Y) note “X a battu Y directement” et stronger(X, Z) la relation transitive qui en decoule. Vous retrouvez le même schema récursive + cas de base que connected/direct, et le W doit renvoyer la tete generalisee stronger(premier, dernier).

# Exercice : Operateur W sur un tournoi (domaine sport)
# TODO etudiant : transposez l'exemple guide sur un tournoi ou defeated(X, Y)
# signifie "X a battu Y" et stronger(X, Z) la relation transitive associee.
# Indice : meme schema que connected/direct --
#            stronger(A, C) :- defeated(A, B), stronger(B, C)   (recursive)
#            stronger(B, C) :- defeated(B, C)                   (base)
#          et apply_w_operator doit renvoyer la tete stronger(A, C).
# Etape 1 : definissez DEFEATED (4-5 resultats de matchs) puis les deux clauses.
# Etape 2 : w = apply_w_operator(clause_recursive, clause_base).
# Etape 3 : verifiez que la tete du resultat est stronger(premier vainqueur, dernier battu).
print("Exercice a completer : operateur W sur un tournoi (defeated/stronger)")
print("Etape 1 : DEFEATED = { (defeated, Luna, Rex), (defeated, Rex, Tao), ... }")
print("Etape 2 : clause recursive stronger(A,C):-defeated(A,B),stronger(B,C) + base")
print("Etape 3 : apply_w_operator -> la tete stronger(Luna, Tao)")
result = None  # TODO etudiant : votre resultat apply_w_operator ici

Exercice a completer : operateur W sur un tournoi (defeated/stronger)
Etape 1 : DEFEATED = { (defeated, Luna, Rex), (defeated, Rex, Tao), ... }
Etape 2 : clause recursive stronger(A,C):-defeated(A,B),stronger(B,C) + base
Etape 3 : apply_w_operator -> la tete stronger(Luna, Tao)

L’exemple guide suivant fait le pont avec les Knowledge Graphs (approfondis dans SL-8) : vous verifierez des règles ILP sur un mini-graphe de triples.

# Exemple guide : Miner et verifier des regles sur un Knowledge Graph
# Objectif : implementer verify_kg_rule (verifier qu'une regle chainee tient sur
# un KG), puis l'appliquer pour mesurer la CONFIANCE d'une regle de composition,
# a la maniere d'AMIE. Representation : un KG est un ensemble de triples
# (sujet, predicat, objet).

# Etape 1 : un mini-KG familial (9 triples). On reintroduit la famille Arthur,
# avec un fait grandparent MANQUANT (Bob -> George) pour illustrer la confiance.
KG = {
    ("Arthur", "parent", "Bob"),
    ("Arthur", "parent", "Catherine"),
    ("Bob", "parent", "Diana"),
    ("Catherine", "parent", "Eve"),
    ("Eve", "parent", "Frank"),
    ("Diana", "parent", "George"),
    # grands-parents connus (3 sur les 4 entables -- Bob -> George absent)
    ("Arthur", "grandparent", "Diana"),
    ("Arthur", "grandparent", "Eve"),
    ("Catherine", "grandparent", "Frank"),
}
print(f"KG : {len(KG)} triples, predicats = {sorted({t[1] for t in KG})}")
print()

# Etape 2 : implementation du verificateur de regle chainee (style AMIE).
def verify_kg_rule(
    kg: set,
    body_predicates: list,
    head_predicate: tuple,
    variables: list
) -> list:
    """Verifie une regle chainee sur un KG.

    Une regle a la forme (chaine de variables v_0..v_n) :
        head(v_0, v_n) :- body_0(v_0, v_1), body_1(v_1, v_2), ...
    ou body_predicates[k] = (k, predicat_k) designe l'atome
    predicat_k(variables[k], variables[k+1]), et head_predicate = (0, predicat_head)
    designe la conclusion predicat_head(variables[0], variables[-1]).

    Returns:
        Liste des bindings (v_0, ..., v_n) pour lesquels le BODY entier tient
        dans le KG. L'appelant en deduit la confiance = |head present| / |bindings|.
    """
    by_pred = {}
    for (s, p, o) in kg:
        by_pred.setdefault(p, set()).add((s, o))
    bindings = [()]
    for (i, pred) in body_predicates:
        pairs = by_pred.get(pred, set())
        suivants = []
        for b in bindings:
            cle = b[i] if i < len(b) else None   # variable de jointure deja liee ?
            for (s, o) in pairs:
                if cle is not None and s != cle:
                    continue
                suivants.append(b[:i] + (s, o))
        bindings = suivants
    return bindings

# Etape 3 : on teste la regle de composition
# grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
variables = ["X", "Y", "Z"]
body = [(0, "parent"), (1, "parent")]    # parent(X, Y) puis parent(Y, Z)
head = (0, "grandparent")                # conclut grandparent(X, Z)
bindings = verify_kg_rule(KG, body, head, variables)
print("Regle : grandparent(X, Z) :- parent(X, Y), parent(Y, Z)")
print(f"  Body satisfait pour {len(bindings)} binding(s) :")
for b in bindings:
    print(f"    X={b[0]}, Y={b[1]}, Z={b[2]}")
print()

# Confiance : parmi les (X, Z) entables, combien ont vraiment grandparent(X, Z) ?
head_pred = head[1]
confirmes = [b for b in bindings if (b[0], head_pred, b[2]) in KG]
manquants = [b for b in bindings if (b[0], head_pred, b[2]) not in KG]
confiance = len(confirmes) / len(bindings) if bindings else 0.0
print(f"  Confiance : {len(confirmes)}/{len(bindings)} = {confiance:.2f}")
if manquants:
    print("  Fait(s) PREDIT(S) (absent du KG, decouvert par la regle) :")
    for b in manquants:
        print(f"    -> {head_pred}({b[0]}, {b[2]})")
print()
assert confiance == 0.75, f"confiance attendue 0.75 (3/4), obtenue {confiance}"
assert any(b[0] == "Bob" and b[2] == "George" for b in manquants), \
    "grandparent(Bob, George) devrait etre predit par la regle"
print("OK : regle de composition verifiee, confiance 0.75, "
      "grandparent(Bob, George) predit (fait manquant decouvert).")

KG : 9 triples, predicats = ['grandparent', 'parent']

Regle : grandparent(X, Z) :- parent(X, Y), parent(Y, Z)
  Body satisfait pour 4 binding(s) :
    X=Catherine, Y=Eve, Z=Frank
    X=Arthur, Y=Bob, Z=Diana
    X=Bob, Y=Diana, Z=George
    X=Arthur, Y=Catherine, Z=Eve

  Confiance : 3/4 = 0.75
  Fait(s) PREDIT(S) (absent du KG, decouvert par la regle) :
    -> grandparent(Bob, George)

OK : regle de composition verifiee, confiance 0.75, grandparent(Bob, George) predit (fait manquant decouvert).

A votre tour : une règle de transitivite sur un Knowledge Graph

L’exemple guide a verifie une règle de composition (parent o parent -> grandparent). Testez maintenant une transitivite : une relation R telle que R(X, Y) et R(Y, Z) impliquent R(X, Z) (par exemple ancestor, ou une relation d’ordre comme « plus grand que »). C’est le même outil verify_kg_rule, mais cette fois le predicat de tete est IDENTIQUE au predicat du corps. Construisez un KG ferme (toute transitivite explicite) et verifiez que la confiance vaut alors 1.0.

# Exercice : Verifier une regle de TRANSITIVITE sur un KG
# TODO etudiant : construisez un KG ou une relation R est transitive, puis
# verifiez R(X, Z) :- R(X, Y), R(Y, Z) avec verify_kg_rule.
# Indice : la transitivite a head_predicate de meme predicat que le body
#          (ex : ancestor, "plus grand que", contient). Construisez une chaine
#          R(a,b), R(b,c), R(c,d)... et fermez le KG (ajoutez R(a,c), R(a,d), ...).
# Etape 1 : definissez KG_TRANS avec une relation transitive (8-10 triples fermes).
# Etape 2 : verify_kg_rule(KG_TRANS, [(0, "R"), (1, "R")], (0, "R"), ["X","Y","Z"]).
# Etape 3 : calculez la confiance -- un KG ferme donne 1.0 ; un trou la fait chuter.
print("Exercice a completer : regle de transitivite sur un KG")
print("Etape 1 : KG_TRANS = { (a,'ancestor',b), (b,'ancestor',c), (a,'ancestor',c), ... }")
print("Etape 2 : verify_kg_rule(KG_TRANS, [(0,'ancestor'),(1,'ancestor')], (0,'ancestor'), vars)")
print("Etape 3 : confiance = |ancestor(X,Z) present| / |bindings|  (1.0 si KG ferme)")
result = None  # TODO etudiant : vos bindings ici

Exercice a completer : regle de transitivite sur un KG
Etape 1 : KG_TRANS = { (a,'ancestor',b), (b,'ancestor',c), (a,'ancestor',c), ... }
Etape 2 : verify_kg_rule(KG_TRANS, [(0,'ancestor'),(1,'ancestor')], (0,'ancestor'), vars)
Etape 3 : confiance = |ancestor(X,Z) present| / |bindings|  (1.0 si KG ferme)

Exercice 4 : grandparent avec Popper

La section Popper a appris ancestor/2 (récursif). A vous d’apprendre grandparent/2 (non récursif) avec la même machinerie run_popper, sur la même famille.

# Exemple guide : apprendre grandparent(X, Y) avec Popper
# Objectif : formuler la tache ILP "grandparent" pour Popper (memes faits parent
# que la section ancestor), construire le repertoire de tache (bk.pl / exs.pl /
# bias.pl), puis VERIFIER en Python pur que le programme cible
# grandparent(A,B):-parent(A,C),parent(C,B) couvre exactement les positifs et
# aucun negatif -- le meme test que fait le testeur Prolog de Popper. Sur le
# kernel python3-wsl (SWI-Prolog present), Popper apprend ce programme de lui-meme.

# Etape 1 : les paires grandparent de la famille + des negatifs a la frontiere.
# Un grand-parent est le parent d'un parent (2 sauts). On inclut l'ARRIERE-grand-
# parent (Arthur -> Frank, 3 sauts) parmi les negatifs : c'est la frontiere qui
# empeche Popper de proposer un programme trop court.
GP_POS = {  # 3 vrais grand-parents (chaines parent o parent)
    ("Arthur", "Diana"),     # Arthur -> Bob -> Diana
    ("Arthur", "Eve"),       # Arthur -> Catherine -> Eve
    ("Catherine", "Frank"),  # Catherine -> Eve -> Frank
}
GP_NEG = {
    ("Arthur", "Bob"), ("Arthur", "Catherine"), ("Bob", "Diana"),   # parents directs
    ("Catherine", "Eve"), ("Eve", "Frank"),
    ("Arthur", "Frank"),     # arriere-grand-parent (3 sauts) -- LA FRONTIERE
    ("Diana", "Arthur"), ("Frank", "Catherine"),                    # inverses
}
print("Tache grandparent :")
print(f"  Positifs ({len(GP_POS)}) : {sorted(GP_POS)}")
print(f"  Negatifs ({len(GP_NEG)}) : parents directs + arriere-grand-parent + inverses")
print()

# Etape 2 : construction du repertoire de tache Popper (bk.pl / exs.pl / bias.pl).
# On reutilise les faits parent/2 de la section ancestor (BACKGROUND) et un biais
# NON recursif : grandparent tient en une clause de profondeur 2.
import tempfile
from pathlib import Path

task_gp = Path(tempfile.mkdtemp(prefix="popper_grandparent_"))
(task_gp / "bk.pl").write_text(
    "".join(f"parent({p.lower()},{c.lower()}).\n" for _, (p, c) in sorted(BACKGROUND)))
(task_gp / "exs.pl").write_text(
    "".join(f"pos(grandparent({x.lower()},{y.lower()})).\n" for x, y in sorted(GP_POS))
    + "".join(f"neg(grandparent({x.lower()},{y.lower()})).\n" for x, y in sorted(GP_NEG)))
(task_gp / "bias.pl").write_text(
    "max_vars(3).\nmax_body(2).\nmax_clauses(1).\n"
    "head_pred(grandparent,2).\nbody_pred(parent,2).\n")
print("Repertoire de tache Popper (task_gp) :")
for f in ("bias.pl", "bk.pl", "exs.pl"):
    print(f"--- {f} ---")
    print((task_gp / f).read_text())

# Etape 3 : programme cible -- celui que Popper apprend (optimal : 1 clause,
# 2 litteraux, sous max_clauses(1)/max_body(2)).
CIBLE = "grandparent(A,B):-parent(A,C),parent(C,B)."
print(f"Programme cible (Popper, max_clauses(1)) : {CIBLE}")
print()

# Etape 4 : VERIFICATION INDEPENDANTE en Python pur (sans Popper ni SWI-Prolog).
# On deriver grandparent(A,B) en cherchant un C tel que parent(A,C) ET parent(C,B),
# puis on compare aux exemples -- exactement le test qu'effectue le testeur Prolog
# de Popper, mais en Python standard (executable sur tout kernel).
parents = {(p, c) for (_, (p, c)) in BACKGROUND}
gp_derived = {(a, b) for (a, c1) in parents for (c2, b) in parents if c1 == c2}
tp = gp_derived & GP_POS
fp = gp_derived & GP_NEG
fn = GP_POS - gp_derived
print("Verification Python du programme cible :")
print(f"  grandparent derives : {sorted(gp_derived)}")
print(f"  TP (vrais positifs) : {len(tp)}/{len(GP_POS)}")
print(f"  FP (faux positifs)  : {len(fp)}/{len(GP_NEG)}")
print(f"  FN (faux negatifs)  : {len(fn)}/{len(GP_POS)}")

# Etape 5 : si Popper est disponible (kernel python3-wsl + SWI-Prolog), on lance
# l'apprentissage reel et on confirme qu'il retrouve la cible ; sinon, la
# verification Python ci-dessus tient deja le role de preuve (TP=3, FP=0).
if HAS_POPPER:
    result_gp = run_popper(task_gp)
    print("\nPopper (apprentissage reel) :")
    print(result_gp["prog"])
    tp2, fn2, tn2, fp2, size = result_gp["score"]
    print(f"Score : {tp2} tp, {fn2} fn, {tn2} tn, {fp2} fp -- taille {size} litteraux")
else:
    print("\nPopper indisponible sur ce kernel (SWI-Prolog manquant) : la verification")
    print("Python ci-dessus demontre deja que la cible couvre exactement GP_POS.")

# Le programme cible doit couvrir exactement les positifs, aucun negatif.
assert len(tp) == len(GP_POS) and not fp and not fn, \
    "La cible doit couvrir exactement GP_POS (TP=3, FP=0, FN=0)."
print("\nOK : grandparent(X,Y) :- parent(X,Z), parent(Z,Y) verifie "
      "(TP=3, FP=0) -- l'arriere-grand-parent (Arthur, Frank) reste exclu.")

Tache grandparent :
  Positifs (3) : [('Arthur', 'Diana'), ('Arthur', 'Eve'), ('Catherine', 'Frank')]
  Negatifs (8) : parents directs + arriere-grand-parent + inverses

Repertoire de tache Popper (task_gp) :
--- bias.pl ---
max_vars(3).
max_body(2).
max_clauses(1).
head_pred(grandparent,2).
body_pred(parent,2).

--- bk.pl ---
parent(arthur,bob).
parent(arthur,catherine).
parent(bob,diana).
parent(catherine,eve).
parent(eve,frank).

--- exs.pl ---
pos(grandparent(arthur,diana)).
pos(grandparent(arthur,eve)).
pos(grandparent(catherine,frank)).
neg(grandparent(arthur,bob)).
neg(grandparent(arthur,catherine)).
neg(grandparent(arthur,frank)).
neg(grandparent(bob,diana)).
neg(grandparent(catherine,eve)).
neg(grandparent(diana,arthur)).
neg(grandparent(eve,frank)).
neg(grandparent(frank,catherine)).

Programme cible (Popper, max_clauses(1)) : grandparent(A,B):-parent(A,C),parent(C,B).

Verification Python du programme cible :
  grandparent derives : [('Arthur', 'Diana'), ('Arthur', 'Eve'), ('Catherine', 'Frank')]
  TP (vrais positifs) : 3/3
  FP (faux positifs)  : 0/8
  FN (faux negatifs)  : 0/3

Popper (apprentissage reel) :
grandparent(V0,V1):- parent(V0,V2),parent(V2,V1).
Score : 3 tp, 0 fn, 8 tn, 0 fp -- taille 3 litteraux

OK : grandparent(X,Y) :- parent(X,Z), parent(Z,Y) verifie (TP=3, FP=0) -- l'arriere-grand-parent (Arthur, Frank) reste exclu.

A votre tour : great-grandparent (chaîne de 3 parents)

L’exemple guide a verifie grandparent (composition de 2 parents). Generalisez a greatgrandparent(X, Y) (composition de 3 parents). Construisez la tâche Popper equivalente (head_pred(greatgrandparent,2), max_body(3)) et verifiez en Python que la cible couvre exactement les positifs.

Note : dans cette petite famille, il n’y a qu’un seul arriere-grand-parent (Arthur -> Frank). Un seul positif, c’est maigre – c’est une vraie limite de l’ILP sur petits jeux de données : peu d’exemples = peu de contraintes = peu de garanties. Que se passerait-il avec une famille plus profonde ?

# Exercice : great-grandparent (chaine de 3 parents) sur la meme famille
# TODO etudiant : generalisez la demarche de l'exemple guide a greatgrandparent.
# Indice : greatgrandparent(A,B) :- parent(A,C), parent(C,D), parent(D,B).
#          En Python : ggp_derived = { (a,b) | exists c,d: parent(a,c),parent(c,d),parent(d,b) }.
# Etape 1 : listez GGP_POS a la main (combien d'arriere-grands-parents dans la famille ?).
# Etape 2 : calculez ggp_derived en Python (gp_derived compose avec un parent de plus).
# Etape 3 : comparez -- la cible couvre-t-elle exactement GGP_POS ?
print("Exercice a completer : great-grandparent (3 parents) sur la famille")
print("Etape 1 : GGP_POS = { (a,b) | a est arriere-grand-parent de b }  (combien ?)")
print("Etape 2 : ggp_derived = { (a,b) | exists c,d: parent(a,c),parent(c,d),parent(d,b) }")
print("Etape 3 : GGP_POS == ggp_derived ? (verifiez la couverture exacte)")
result = None  # TODO etudiant : votre ggp_derived ici

Exercice a completer : great-grandparent (3 parents) sur la famille
Etape 1 : GGP_POS = { (a,b) | a est arriere-grand-parent de b }  (combien ?)
Etape 2 : ggp_derived = { (a,b) | exists c,d: parent(a,c),parent(c,d),parent(d,b) }
Etape 3 : GGP_POS == ggp_derived ? (verifiez la couverture exacte)

---

8. Conclusion

Recapitulatif

Ce notebook a couvert la Programmation Logique Inductive (AIMA 19.5) :

1. Clauses Horn : la representation de base de l’ILP. Les clauses Horn expriment des règles du type “si body alors head”. L’unification est le mécanisme fondamental pour matcher les termes.

2. FOIL (top-down) : part de la règle la plus générale et ajoute des litteraux pour exclure les negatifs. Le gain FOIL guide la sélection des litteraux en maximisant la couverture des positifs.

3. Resolution inverse (bottom-up) : part des exemples spécifiques et les generalise via les opérateurs V (absorption) et W (identification).

4. Knowledge Graphs : l’ILP a une connexion directe avec les KGs modernes (AMIE3, règles SPARQL CONSTRUCT). Les règles ILP decouvrent des patterns relationnels que le Web Sémantique formalise.

5. Limites de l’ILP : complexite elevee, sensibilité au bruit, difficulté avec la recursion. Les systèmes modernes (Popper, ILASP) addressent ces limites via ASP et l’apprentissage par contraintes.

Comparaison des méthodes de la serie

Méthode	Type	Representation	Connaissance requise
CBH (SL-1)	Propositionnel	Conjonction	Aucune
Version Space (SL-1)	Propositionnel	Ensemble de hypotheses	Aucune
EBL (SL-2)	Deductif	Règle compilee	Théorie complete
RBL (SL-3)	Propositionnel	Determination	Pertinence
FOIL (SL-4)	Relationnel	Clause Horn	Background relationnel

Connexions

Direction	Sujet	Lien
Prerequis	Determinations et pertinence	SL-3
Web Sémantique	Knowledge Graphs, SPARQL	SW-11, SW-4b
Web Sémantique	Reasoners OWL	SW-13
TweetyProject	Logique FOL, argumentation	Serie Tweety

---

Defi presentation

Modalite du cours : chaque groupe choisit un exercice de la serie, le prepare, et le presente en seance. Resoudre l’exercice est le minimum ; ce qui distingue une presentation qui maitrise le sujet, c’est la question-twist associee ci-dessous. Elle fait partie integrante de la presentation attendue.

Exercice	Question-twist a traiter en plus
Ex. 1 (sibling avec FOIL)	FOIL trouve-t-il le litteral X != Y tout seul ? Montrez ce qui se passe s’il est absent du langage des hypotheses, et reliez cela au rôle du biais de langage en ILP.
Ex. 2 (opérateur W)	Sur votre domaine, exhibez une generalisation produite par W qui est consistante avec vos exemples mais fausse dans le monde reel. Pourquoi le bottom-up est-il particulierement expose a ce risque ?
Ex. 3 (mini-KG)	Evaluez la même règle sous hypothese du monde clos (vos negatifs explicites) puis sous monde ouvert (PCA, cf SL-8) : laquelle des deux confiances est la bonne pour VOTRE KG, et pourquoi ?
Ex. 4 (grandparent avec Popper)	Retirez de GP_NEG toute paire arriere-grand-parent et relancez : quel programme plus court (et faux) devient consistant ? Popper garantit l’optimalite par rapport aux exemples fournis : que dit cette expérience du rôle des negatifs proches de la frontiere ?

---

Ressources

• Russell & Norvig, AI: A Modern Approach, 3e ed., Section 19.5
• Quinlan, J.R. (1990), Learning Logical Definitions from Relations
• Muggleton, S. (1995), Inverse Entailment and Progol
• Evans & Grefenstette (2018), Learning Explanatory Rules from Noisy Data
• Galarraga et al. (2015), AMIE: Association Rule Mining under Incomplete Evidence
• AIMA Python Code - Implementations de reference

---

Retour : Index SymbolicLearning | << SL-3 | SL-5 >>