# Installation silencieuse de rdflib
%pip install -q --disable-pip-version-check rdflibNote: you may need to restart the kernel to use updated packages.SL-8 - ILP Moderne et Knowledge Graphs
Navigation : Index | << NeuroSymbolic | LLM + Symbolic >>
Objectifs d’apprentissage
A la fin de ce notebook, vous saurez : 1. Manipuler des Knowledge Graphs avec rdflib (triples RDF, namespaces, serialisation) 2. Implementer un algorithme de rule mining simplifie inspire d’AMIE3 pour decouvrir des règles de Horn dans un KG 3. Distinguer support, confidence et PCA confidence pour evaluer la qualite des règles 4. Comprendre le lien entre règles d’association statistiques et règles logiques du premier ordre 5. Appliquer les règles minees pour inferer de nouveaux triples dans le graphe
Prerequis
- SL-4 (ILP : FOIL, resolution inverse) recommande
- SW-2b (RDF en Python avec rdflib) recommande
- Python 3.10+, rdflib 7.x
Duree estimee : 50 minutes
References
- Galarraga et al., “AMIE: Association Rule Mining under Incomplete Evidence in Ontological Knowledge Bases”, VLDB 2013
- Bordes et al., “Translating Embeddings for Modeling Multi-relational Data”, NeurIPS 2013
- Russell & Norvig, AI: A Modern Approach, 3e/4e ed., Chapitre 19
- rdflib Documentation
1. Introduction : ILP sur données structurees
Pourquoi les Knowledge Graphs sont naturels pour l’ILP ?
L’Inductive Logic Programming (ILP) apprend des règles logiques a partir de données. Traditionnellement, les données sont des ensembles de predicats logiques (ex : parent(X, Y)). Mais aujourd’hui, la plus grande source de données structurees est le Web Sémantique : des milliards de triples RDF forment des Knowledge Graphs (Wikidata, DBpedia, YAGO, etc.).
Un triple RDF (sujet, predicat, objet) est equivalent a un fait logique :
\[ \text{predicat}(\text{sujet}, \text{objet}) \]
Par exemple, le triple (Alice, parentOf, Bob) correspond au fait parentOf(Alice, Bob).
L’idee d’AMIE (Association Rule Mining under Incomplete Evidence) est d’appliquer le minage de règles d’association sur ces faits pour decouvrir des règles de Horn générales :
\[ p_1(X, Y) \wedge p_2(Y, Z) \Rightarrow p_3(X, Z) \]
C’est exactement le programme de l’ILP, mais a l’echelle des Knowledge Graphs.
| Aspect | ILP classique | ILP sur KG (AMIE) |
|---|---|---|
| Données | Faits logiques | Triples RDF |
| Variables | X, Y, Z | Noeuds du graphe |
| Règles | Clauses de Horn | Règles d’association RDF |
| Echelle | Milliers de faits | Milliards de triples |
| Outils | FOIL, Progol | AMIE3, AnyBURL |
2. Construction d’un Knowledge Graph avec rdflib
Nous allons créer un Knowledge Graph de relations familiales – un domaine classique en ILP qui permet de decouvrir des règles transitives (ex : “si X est parent de Y et Y est parent de Z, alors X est grand-parent de Z”).
Importation et construction du Knowledge Graph
La bibliotheque rdflib est la reference Python pour manipuler les graphs RDF. La cellule suivante importe les composants necessaires et construit un Knowledge Graph de relations familiales : parentOf, grandparentOf (incomplet), siblingOf et marriedTo. L’incompletude deliberee de grandparentOf est le moteur du rule mining – c’est ce que nous chercherons a completer automatiquement.
from rdflib import Graph, URIRef, Literal, Namespace, BNode
from rdflib.namespace import RDF, RDFS, XSD
from collections import defaultdict
from itertools import combinations
import random
# Define custom namespace for the family KG
FAM = Namespace("http://example.org/family/")
g = Graph()
g.bind("fam", FAM)
g.bind("rdf", RDF)
g.bind("rdfs", RDFS)
# Helper to create person URIs
def person(name: str) -> URIRef:
return URIRef(FAM + name)
# --- Define persons ---
persons = [
"Marie", "Pierre", "Jean", "Claire",
"Luc", "Sophie", "Paul", "Anne",
"Marc", "Lea", "Hugo", "Julie",
"Thomas", "Emma"
]
for p in persons:
g.add((person(p), RDF.type, FAM.Person))
# --- Define relations ---
# parentOf(X, Y) means X is a parent of Y
parent_triples = [
("Marie", "Jean"), # Marie -> Jean
("Marie", "Claire"), # Marie -> Claire
("Pierre", "Jean"), # Pierre -> Jean
("Pierre", "Claire"), # Pierre -> Claire
("Jean", "Luc"), # Jean -> Luc
("Jean", "Sophie"), # Jean -> Sophie
("Claire", "Paul"), # Claire -> Paul
("Claire", "Anne"), # Claire -> Anne
("Luc", "Marc"), # Luc -> Marc
("Luc", "Lea"), # Luc -> Lea
("Sophie", "Hugo"), # Sophie -> Hugo
("Sophie", "Julie"), # Sophie -> Julie
("Paul", "Thomas"), # Paul -> Thomas
("Paul", "Emma"), # Paul -> Emma
]
for parent, child in parent_triples:
g.add((person(parent), FAM.parentOf, person(child)))
# grandparentOf: we add a SUBSET of grandparent triples
# (simulates a KG where grandparentOf is incomplete -- ILP should discover the rule)
# True grandparent pairs = 14: Marie/Pierre -> Luc,Sophie,Paul,Anne (2x4=8),
# Jean -> Marc,Lea,Hugo,Julie (4), Claire -> Thomas,Emma (2).
# We add 5 of them, all for Marie/Pierre:
# standard confidence = 5/14 ~ 0.36 (penalisee par l'incompletude du KG)
# PCA confidence = 5/8 = 0.625 (seuls Marie et Pierre ont des head triples)
grandparent_triples = [
("Marie", "Luc"), # Marie -> Jean -> Luc
("Marie", "Sophie"), # Marie -> Jean -> Sophie
("Marie", "Paul"), # Marie -> Claire -> Paul
("Pierre", "Luc"), # Pierre -> Jean -> Luc
("Pierre", "Sophie"), # Pierre -> Jean -> Sophie
]
# Missing: Marie->Anne, Pierre->Paul, Pierre->Anne (3 missing triples)
for gp, gc in grandparent_triples:
g.add((person(gp), FAM.grandparentOf, person(gc)))
# siblingOf: a few sibling relationships
sibling_triples = [
("Jean", "Claire"),
("Claire", "Jean"),
("Luc", "Sophie"),
("Sophie", "Luc"),
("Paul", "Anne"),
("Anne", "Paul"),
("Marc", "Lea"),
("Lea", "Marc"),
("Hugo", "Julie"),
("Julie", "Hugo"),
("Thomas", "Emma"),
("Emma", "Thomas"),
]
for sib1, sib2 in sibling_triples:
g.add((person(sib1), FAM.siblingOf, person(sib2)))
# marriedTo
married_triples = [
("Marie", "Pierre"),
("Pierre", "Marie"),
]
for h, w in married_triples:
g.add((person(h), FAM.marriedTo, person(w)))
# Statistics
n_parent = len(list(g.triples((None, FAM.parentOf, None))))
n_gp = len(list(g.triples((None, FAM.grandparentOf, None))))
n_sib = len(list(g.triples((None, FAM.siblingOf, None))))
n_married = len(list(g.triples((None, FAM.marriedTo, None))))
n_person = len(list(g.triples((None, RDF.type, FAM.Person))))
print(f"Knowledge Graph cree avec rdflib")
print(f" Personnes : {n_person}")
print(f" parentOf : {n_parent} triples")
print(f" grandparentOf : {n_gp} triples")
print(f" siblingOf : {n_sib} triples")
print(f" marriedTo : {n_married} triples")
print(f" Total triples : {len(g)}")Knowledge Graph cree avec rdflib
Personnes : 14
parentOf : 14 triples
grandparentOf : 5 triples
siblingOf : 12 triples
marriedTo : 2 triples
Total triples : 47Interpretation : Knowledge Graph familial
Sortie obtenue : un graphe de 14 personnes avec 4 types de relations.
| Relation | Triples | Signification |
|---|---|---|
parentOf |
14 | Lien parent-enfant (complet) |
grandparentOf |
5 | Lien grand-parent (INCOMPLET – 5 sur 14 possibles) |
siblingOf |
12 | Lien fratrie (symetrique) |
marriedTo |
2 | Lien mariage (symetrique) |
Points cles : 1. grandparentOf est incomplet : seuls 5 triples sur les 14 possibles sont presents (les grands-parents de la generation 1 – Jean, Claire – n’ont aucun triple) 2. C’est exactement la situation ou le rule mining est utile : completer les données manquantes 3. Si on peut decouvrir la règle parentOf(X,Y) ^ parentOf(Y,Z) => grandparentOf(X,Z), on pourra inferer les 9 triples manquants
Note : Cette incompletude est typique des vrais Knowledge Graphs. Wikidata, par exemple, contient des millions de triples mais reste largement incomplet. Le rule mining est une technique cle pour la completion.
3. Extraction des données pour le rule mining
Avant de miner des règles, nous devons extraire les données du graphe dans un format exploitable. Le rule mining travaille sur des paires (sujet, objet) par predicat.
# Extract all relation data as dictionaries: predicate -> set of (subject, object) pairs
def extract_relations(graph: Graph) -> dict[str, set[tuple[str, str]]]:
"""Extract all FAM predicates and their (subject, object) pairs."""
relations = defaultdict(set)
for s, p, o in graph:
# Only consider FAM namespace predicates (skip rdf:type)
if str(p).startswith(str(FAM)) and p != RDF.type:
pred_name = str(p).replace(str(FAM), "")
subj_name = str(s).replace(str(FAM), "")
obj_name = str(o).replace(str(FAM), "")
relations[pred_name].add((subj_name, obj_name))
return dict(relations)
relations = extract_relations(g)
print("Relations extraites du graphe :")
for pred, pairs in sorted(relations.items()):
print(f" {pred}: {len(pairs)} paires")
# Show first 5 pairs
for s, o in sorted(pairs)[:5]:
print(f" {s} -> {o}")
if len(pairs) > 5:
print(f" ... ({len(pairs) - 5} autres)")
print()
# Also extract all entity pairs for co-occurrence analysis
all_entities = set()
for pred, pairs in relations.items():
for s, o in pairs:
all_entities.add(s)
all_entities.add(o)
print(f"Total entites uniques : {len(all_entities)}")
print(f"Total relations : {len(relations)}")Relations extraites du graphe :
grandparentOf: 5 paires
Marie -> Luc
Marie -> Paul
Marie -> Sophie
Pierre -> Luc
Pierre -> Sophie
marriedTo: 2 paires
Marie -> Pierre
Pierre -> Marie
parentOf: 14 paires
Claire -> Anne
Claire -> Paul
Jean -> Luc
Jean -> Sophie
Luc -> Lea
... (9 autres)
siblingOf: 12 paires
Anne -> Paul
Claire -> Jean
Emma -> Thomas
Hugo -> Julie
Jean -> Claire
... (7 autres)
Total entites uniques : 14
Total relations : 4Interpretation : Extraction des relations
L’extraction convertit le graphe RDF en dictionnaires de paires, le format naturel pour le rule mining.
| Concept | Dans rdflib | Pour le rule mining |
|---|---|---|
| Triple | (URIRef, URIRef, URIRef) |
(str, str) dans un set |
| Predicat | FAM.parentOf |
Cle du dictionnaire |
| Ensemble de faits | g.triples((None, p, None)) |
relations["parentOf"] |
Note : Le rule mining travaille sur des ensembles de paires, pas sur le graphe RDF directement. C’est une abstraction qui simplifie les calculs statistiques.
4. Rule Mining : decouvrir des règles de Horn
Nous implementons un algorithme simplifie inspire d’AMIE3. L’idee est d’enumerer des candidats de règles de la forme :
\[ r_1(A, B) \wedge r_2(B, C) \Rightarrow r_{head}(A, C) \]
C’est une règle de Horn binaire (2 atomes dans le corps, 1 atome en tete). Pour chaque candidat, on evalue le support et la confidence.
Metriques d’evaluation
| Metrique | Formule | Signification |
|---|---|---|
| Support | \(\lvert\{(a,c) : body(a,c) \wedge head(a,c)\}\rvert\) | Nombre de paires couvertes |
| Confidence standard | \(\frac{support}{\lvert\{(a,c) : body(a,c)\}\rvert}\) | Probabilite que head soit vrai si body est vrai |
| PCA confidence | \(\frac{support}{\lvert\{(a,c) : body(a,c) \wedge \exists z\, head(a,z)\}\rvert}\) | Ajuste pour l’incompletude du KG (denominateur restreint aux sujets ayant au moins un head connu) |
def compute_body_pairs(
r1_pairs: set[tuple[str, str]],
r2_pairs: set[tuple[str, str]]
) -> set[tuple[str, str]]:
"""Compute body = r1(A,B) JOIN r2(B,C), returning (A,C) pairs.
This is a relational JOIN: match the object of r1 with the subject of r2.
"""
# Index r2 by subject for efficient lookup
r2_by_subj = defaultdict(set)
for b, c in r2_pairs:
r2_by_subj[b].add(c)
result = set()
for a, b in r1_pairs:
if b in r2_by_subj:
for c in r2_by_subj[b]:
result.add((a, c))
return result
def evaluate_rule(
body_pairs: set[tuple[str, str]],
head_pairs: set[tuple[str, str]],
all_entities: set[str],
head_relation: set[tuple[str, str]]
) -> dict:
"""Evaluate a rule body => head with support, confidence, PCA confidence."""
# Support = body AND head
support_pairs = body_pairs & head_pairs
support = len(support_pairs)
body_size = len(body_pairs)
if body_size == 0:
return {"support": 0, "body_size": 0, "confidence": 0.0, "pca_confidence": 0.0}
# Standard confidence = support / body_size
confidence = support / body_size
# PCA confidence (Partial Completeness Assumption)
# Under PCA: if subject A has at least one head triple, we assume A's head
# triples are COMPLETE. So body pairs (A,C) where A has head triples but
# NOT to C are true negatives. Body pairs where A has NO head triples at all
# are excluded from the denominator (unknown).
head_by_subj = defaultdict(set)
for a, c in head_relation:
head_by_subj[a].add(c)
# PCA denominator: only count body pairs where A has at least one head triple
pca_denominator = 0
for a, c in body_pairs:
if a in head_by_subj or (a, c) in head_pairs:
# A has some head relation -> under PCA this is a definite example
pca_denominator += 1
pca_confidence = support / pca_denominator if pca_denominator > 0 else 0.0
return {
"support": support,
"body_size": body_size,
"confidence": confidence,
"pca_confidence": pca_confidence
}
# Test with a simple example
print("Test de compute_body_pairs :")
r1 = {("A", "B"), ("C", "D")}
r2 = {("B", "E"), ("D", "F")}
result = compute_body_pairs(r1, r2)
print(f" r1 = {r1}")
print(f" r2 = {r2}")
print(f" JOIN result = {result}")
print(f" Attendu : {('A', 'E'), ('C', 'F')}")
print(f" Correct : {result == {('A', 'E'), ('C', 'F')}}")Test de compute_body_pairs :
r1 = {('C', 'D'), ('A', 'B')}
r2 = {('B', 'E'), ('D', 'F')}
JOIN result = {('A', 'E'), ('C', 'F')}
Attendu : (('A', 'E'), ('C', 'F'))
Correct : TrueInterpretation : Jointure relationnelle et evaluation
La fonction compute_body_pairs realise une jointure relationnelle : elle apparie l’objet de la première relation avec le sujet de la seconde.
| Opération | Analogue SQL | Analogue logique |
|---|---|---|
compute_body_pairs(r1, r2) |
SELECT r1.s, r2.o FROM r1 JOIN r2 ON r1.o = r2.s |
Trouver A, C tels que \(r_1(A,B) \wedge r_2(B,C)\) |
support_pairs = body & head |
WHERE head.s = body.s AND head.o = body.o |
\(r_{body}(A,C) \wedge r_{head}(A,C)\) |
confidence = support / body_size |
Ratio de vrai positifs | \(P(head \mid body)\) |
Note : La PCA confidence differe de la confidence standard en excluant du denominateur les body pairs dont le sujet n’a aucun head triple. Si Marie n’a aucun
grandparentOfdans le KG, la paire(Marie, Luc)ne compte ni pour ni contre la règle.
5. Enumeration des candidats et minage de règles
Nous enumerons systematiquement les règles candidates de la forme \(r_1(A,B) \wedge r_2(B,C) \Rightarrow r_{head}(A,C)\) et evaluons chaque candidat.
def mine_rules(
relations: dict[str, set[tuple[str, str]]],
all_entities: set[str],
min_support: int = 1,
min_confidence: float = 0.3
) -> list[dict]:
"""Mine Horn rules from relation data (simplified AMIE-style).
Enumerates rules of the form:
r1(A, B) ^ r2(B, C) => r_head(A, C)
Also considers single-atom body rules:
r1(A, B) => r_head(A, B)
"""
pred_names = sorted(relations.keys())
discovered_rules = []
# --- Two-atom body rules: r1(A,B) ^ r2(B,C) => r_head(A,C) ---
for r1 in pred_names:
for r2 in pred_names:
body_pairs = compute_body_pairs(relations[r1], relations[r2])
if not body_pairs:
continue
for r_head in pred_names:
if r_head == r1 and r_head == r2:
continue # Skip trivial: r1 ^ r1 => r1
metrics = evaluate_rule(
body_pairs, relations[r_head], all_entities, relations[r_head]
)
if metrics["support"] >= min_support and metrics["confidence"] >= min_confidence:
discovered_rules.append({
"body": [r1, r2],
"head": r_head,
**metrics
})
# --- Single-atom body rules: r1(A,B) => r_head(A,B) ---
for r1 in pred_names:
for r_head in pred_names:
if r1 == r_head:
continue # Skip trivial: r1 => r1
body_pairs = relations[r1]
if not body_pairs:
continue
metrics = evaluate_rule(
body_pairs, relations[r_head], all_entities, relations[r_head]
)
if metrics["support"] >= min_support and metrics["confidence"] >= min_confidence:
discovered_rules.append({
"body": [r1],
"head": r_head,
**metrics
})
# Sort by confidence (descending), then by support (descending)
discovered_rules.sort(key=lambda r: (-r["confidence"], -r["support"]))
return discovered_rules
# Mine rules from the family KG
rules = mine_rules(relations, all_entities, min_support=1, min_confidence=0.3)
print(f"Regles decouvertes : {len(rules)}")
print()
header = f"{'Regle':<55} | {'Supp':>4} | {'Body':>4} | {'Conf':>6} | {'PCA':>6}"
print(header)
print("-" * 90)
for rule in rules:
if len(rule["body"]) == 2:
body_str = f"{rule['body'][0]}(A,B) ^ {rule['body'][1]}(B,C)"
head_str = f"{rule['head']}(A,C)"
else:
body_str = f"{rule['body'][0]}(A,B)"
head_str = f"{rule['head']}(A,B)"
rule_str = f"{body_str} => {head_str}"
print(f"{rule_str:<55} | {rule['support']:>4} | {rule['body_size']:>4} | {rule['confidence']:>6.2f} | {rule['pca_confidence']:>6.2f}")Regles decouvertes : 5
Regle | Supp | Body | Conf | PCA
------------------------------------------------------------------------------------------
parentOf(A,B) ^ siblingOf(B,C) => parentOf(A,C) | 14 | 14 | 1.00 | 1.00
marriedTo(A,B) ^ parentOf(B,C) => parentOf(A,C) | 4 | 4 | 1.00 | 1.00
grandparentOf(A,B) ^ siblingOf(B,C) => grandparentOf(A,C) | 4 | 5 | 0.80 | 0.80
marriedTo(A,B) ^ grandparentOf(B,C) => grandparentOf(A,C) | 4 | 5 | 0.80 | 0.80
parentOf(A,B) ^ parentOf(B,C) => grandparentOf(A,C) | 5 | 14 | 0.36 | 0.62Interpretation : Règles decouvertes
L’algorithme a decouvert 5 règles. Le classement par confidence standard reserve une surprise :
| Règle | Conf | PCA | Lecture |
|---|---|---|---|
parentOf ^ siblingOf => parentOf |
1.00 | 1.00 | Vraie par construction : les freres et soeurs partagent leurs parents |
marriedTo ^ parentOf => parentOf |
1.00 | 1.00 | Le conjoint d’un parent est aussi parent (vrai dans cette famille) |
grandparentOf ^ siblingOf => grandparentOf |
0.80 | 0.80 | Le grand-parent de X l’est aussi de sa fratrie |
marriedTo ^ grandparentOf => grandparentOf |
0.80 | 0.80 | Le conjoint d’un grand-parent est grand-parent |
parentOf ^ parentOf => grandparentOf |
0.36 | 0.62 | La règle cible… dernière du classement ! |
Point cle — c’est tout l’intérêt de la PCA confidence. La règle que l’on veut decouvrir est la moins bien notee en confidence standard : sur les 14 paires (grand-parent, petit-enfant) reelles, seules 5 sont dans le KG, donc 5/14 = 0.36. L’incompletude du KG punit la bonne règle. La PCA confidence (Partial Completeness Assumption) ne compte au denominateur que les paires dont le sujet a au moins un triple
grandparentOfconnu (Marie et Pierre, 8 paires) : 5/8 = 0.62. Sous OWA, c’est l’estimateur le plus fiable — AMIE classe ses règles par PCA confidence, pas par confidence standard.
6. Des règles d’association aux règles logiques
La distinction entre règles d’association (statistiques) et règles logiques (FOL) est subtile mais fondamentale.
# Analyze the best rules in detail
print("Analyse detaillee des meilleures regles")
print("=" * 60)
# Focus on the top rules
top_rules = rules[:min(10, len(rules))]
for i, rule in enumerate(top_rules):
print(f"\nRegle {i+1} :")
if len(rule["body"]) == 2:
r1, r2 = rule["body"]
rh = rule["head"]
print(f" FOL: {r1}(X,Y) ^ {r2}(Y,Z) => {rh}(X,Z)")
print(f" Datalog: {rh}(X,Z) :- {r1}(X,Y), {r2}(Y,Z)")
# Show the actual pairs
body_pairs = compute_body_pairs(relations[r1], relations[r2])
support_pairs = body_pairs & relations[rh]
print(f" Body pairs ({len(body_pairs)}): {sorted(body_pairs)[:6]}")
print(f" Support pairs ({len(support_pairs)}): {sorted(support_pairs)[:6]}")
# Identify inferred pairs (body but NOT in head)
inferred = body_pairs - relations[rh]
if inferred:
print(f" ** Nouveaux triples inferes ({len(inferred)}): {sorted(inferred)}")
else:
r1 = rule["body"][0]
rh = rule["head"]
print(f" FOL: {r1}(X,Y) => {rh}(X,Y)")
print(f" Datalog: {rh}(X,Y) :- {r1}(X,Y)")
print(f" Support={rule['support']}, Confidence={rule['confidence']:.2f}")
# Summary: focus on the grandparent rule
print("\n" + "=" * 60)
print("Analyse de la regle grandparentOf :")
body_gp = compute_body_pairs(relations["parentOf"], relations["parentOf"])
existing_gp = relations["grandparentOf"]
new_gp = body_gp - existing_gp
print(f"\n parentOf ^ parentOf JOIN result : {len(body_gp)} paires")
print(f" grandparentOf existants : {sorted(existing_gp)}")
print(f" Triples inferes (manquants) : {sorted(new_gp)}")
print(f" Gain : +{len(new_gp)} triples (de {len(existing_gp)} a {len(existing_gp) + len(new_gp)})")Analyse detaillee des meilleures regles
============================================================
Regle 1 :
FOL: parentOf(X,Y) ^ siblingOf(Y,Z) => parentOf(X,Z)
Datalog: parentOf(X,Z) :- parentOf(X,Y), siblingOf(Y,Z)
Body pairs (14): [('Claire', 'Anne'), ('Claire', 'Paul'), ('Jean', 'Luc'), ('Jean', 'Sophie'), ('Luc', 'Lea'), ('Luc', 'Marc')]
Support pairs (14): [('Claire', 'Anne'), ('Claire', 'Paul'), ('Jean', 'Luc'), ('Jean', 'Sophie'), ('Luc', 'Lea'), ('Luc', 'Marc')]
Support=14, Confidence=1.00
Regle 2 :
FOL: marriedTo(X,Y) ^ parentOf(Y,Z) => parentOf(X,Z)
Datalog: parentOf(X,Z) :- marriedTo(X,Y), parentOf(Y,Z)
Body pairs (4): [('Marie', 'Claire'), ('Marie', 'Jean'), ('Pierre', 'Claire'), ('Pierre', 'Jean')]
Support pairs (4): [('Marie', 'Claire'), ('Marie', 'Jean'), ('Pierre', 'Claire'), ('Pierre', 'Jean')]
Support=4, Confidence=1.00
Regle 3 :
FOL: grandparentOf(X,Y) ^ siblingOf(Y,Z) => grandparentOf(X,Z)
Datalog: grandparentOf(X,Z) :- grandparentOf(X,Y), siblingOf(Y,Z)
Body pairs (5): [('Marie', 'Anne'), ('Marie', 'Luc'), ('Marie', 'Sophie'), ('Pierre', 'Luc'), ('Pierre', 'Sophie')]
Support pairs (4): [('Marie', 'Luc'), ('Marie', 'Sophie'), ('Pierre', 'Luc'), ('Pierre', 'Sophie')]
** Nouveaux triples inferes (1): [('Marie', 'Anne')]
Support=4, Confidence=0.80
Regle 4 :
FOL: marriedTo(X,Y) ^ grandparentOf(Y,Z) => grandparentOf(X,Z)
Datalog: grandparentOf(X,Z) :- marriedTo(X,Y), grandparentOf(Y,Z)
Body pairs (5): [('Marie', 'Luc'), ('Marie', 'Sophie'), ('Pierre', 'Luc'), ('Pierre', 'Paul'), ('Pierre', 'Sophie')]
Support pairs (4): [('Marie', 'Luc'), ('Marie', 'Sophie'), ('Pierre', 'Luc'), ('Pierre', 'Sophie')]
** Nouveaux triples inferes (1): [('Pierre', 'Paul')]
Support=4, Confidence=0.80
Regle 5 :
FOL: parentOf(X,Y) ^ parentOf(Y,Z) => grandparentOf(X,Z)
Datalog: grandparentOf(X,Z) :- parentOf(X,Y), parentOf(Y,Z)
Body pairs (14): [('Claire', 'Emma'), ('Claire', 'Thomas'), ('Jean', 'Hugo'), ('Jean', 'Julie'), ('Jean', 'Lea'), ('Jean', 'Marc')]
Support pairs (5): [('Marie', 'Luc'), ('Marie', 'Paul'), ('Marie', 'Sophie'), ('Pierre', 'Luc'), ('Pierre', 'Sophie')]
** Nouveaux triples inferes (9): [('Claire', 'Emma'), ('Claire', 'Thomas'), ('Jean', 'Hugo'), ('Jean', 'Julie'), ('Jean', 'Lea'), ('Jean', 'Marc'), ('Marie', 'Anne'), ('Pierre', 'Anne'), ('Pierre', 'Paul')]
Support=5, Confidence=0.36
============================================================
Analyse de la regle grandparentOf :
parentOf ^ parentOf JOIN result : 14 paires
grandparentOf existants : [('Marie', 'Luc'), ('Marie', 'Paul'), ('Marie', 'Sophie'), ('Pierre', 'Luc'), ('Pierre', 'Sophie')]
Triples inferes (manquants) : [('Claire', 'Emma'), ('Claire', 'Thomas'), ('Jean', 'Hugo'), ('Jean', 'Julie'), ('Jean', 'Lea'), ('Jean', 'Marc'), ('Marie', 'Anne'), ('Pierre', 'Anne'), ('Pierre', 'Paul')]
Gain : +9 triples (de 5 a 14)Interpretation : Des statistiques a la logique
La règle parentOf(X,Y) ^ parentOf(Y,Z) => grandparentOf(X,Z) illustre la transition entre association et logique :
| Niveau | Formulation | Fondement |
|---|---|---|
| Association | Les paires (X,Z) ou X est parent de Y et Y est parent de Z coincident souvent avec grandparentOf(X,Z) | Statistique |
| Logique | \(\forall X,Y,Z : parentOf(X,Y) \wedge parentOf(Y,Z) \Rightarrow grandparentOf(X,Z)\) | Deductive |
| Pratique | Si confidence = 1.0, la règle est un axiome du domaine. Sinon, c’est une heuristique | Empirique |
Points cles : 1. La règle decouverte permet d’inferer de nouveaux triples manquants dans le KG 2. Si la confidence est 1.0, c’est une règle dure (toujours vraie). Sinon, c’est une règle probabiliste 3. Le PCA confidence ajuste pour l’incompletude : si on sait que Marie a des petits-enfants mais pas lesquels, la règle devrait compter ces cas
Note : Dans un vrai KG comme Wikidata, les règles ont rarement une confidence de 1.0. Par exemple,
bornIn(X,Y) ^ capitalOf(Y,Z) => nationality(X,Z)est souvent vraie mais pas toujours (bi-nationalite, changements de frontieres).
7. Application pratique : completer le Knowledge Graph
Utilisons les règles decouvertes pour inferer de nouveaux triples et les ajouter au graphe.
def apply_rules(
graph: Graph,
relations: dict[str, set[tuple[str, str]]],
rules: list[dict],
namespace: Namespace,
min_confidence: float = 0.5
) -> list[tuple]:
"""Apply discovered rules to infer new triples in the graph.
Le filtre porte sur la PCA confidence : sous Open World Assumption,
c'est elle qui estime la fiabilite d'une regle (cf. section 5). Filtrer
sur la confidence standard eliminerait la regle cible
parentOf ^ parentOf => grandparentOf (0.36 < 0.5) alors que sa PCA
confidence (0.62) la qualifie -- c'est le choix d'AMIE.
Returns list of inferred (subject, predicate, object) triples.
"""
inferred_triples = []
for rule in rules:
if rule["pca_confidence"] < min_confidence:
continue
head_pred = rule["head"]
head_uri = URIRef(namespace + head_pred)
if len(rule["body"]) == 2:
r1, r2 = rule["body"]
body_pairs = compute_body_pairs(relations[r1], relations[r2])
else:
body_pairs = relations[rule["body"][0]]
# New triples: body pairs not already in head relation
existing = relations[head_pred]
new_pairs = body_pairs - existing
for subj, obj in new_pairs:
s_uri = URIRef(namespace + subj)
o_uri = URIRef(namespace + obj)
triple = (s_uri, head_uri, o_uri)
if triple in graph:
continue # deja infere par une regle precedente
graph.add(triple)
inferred_triples.append((subj, head_pred, obj))
return inferred_triples
# Count triples before
n_before = len(g)
n_gp_before = len(list(g.triples((None, FAM.grandparentOf, None))))
print(f"AVANT application des regles :")
print(f" Total triples : {n_before}")
print(f" grandparentOf triples : {n_gp_before}")
print()
# Apply rules with PCA confidence >= 0.5
inferred = apply_rules(g, relations, rules, FAM, min_confidence=0.5)
# Count triples after
n_after = len(g)
n_gp_after = len(list(g.triples((None, FAM.grandparentOf, None))))
print(f"APRES application des regles (PCA conf >= 0.5) :")
print(f" Total triples : {n_after} (+{n_after - n_before})")
print(f" grandparentOf triples : {n_gp_after} (+{n_gp_after - n_gp_before})")
print()
# Show inferred triples
if inferred:
print("Triples inferes :")
for subj, pred, obj in sorted(inferred):
print(f" {subj} -- {pred} --> {obj}")
else:
print("Aucun nouveau triple infere avec les seuils actuels.")AVANT application des regles :
Total triples : 47
grandparentOf triples : 5
APRES application des regles (PCA conf >= 0.5) :
Total triples : 56 (+9)
grandparentOf triples : 14 (+9)
Triples inferes :
Claire -- grandparentOf --> Emma
Claire -- grandparentOf --> Thomas
Jean -- grandparentOf --> Hugo
Jean -- grandparentOf --> Julie
Jean -- grandparentOf --> Lea
Jean -- grandparentOf --> Marc
Marie -- grandparentOf --> Anne
Pierre -- grandparentOf --> Anne
Pierre -- grandparentOf --> PaulInterpretation : Completion du Knowledge Graph
Les règles qualifiees par leur PCA confidence ont permis d’inferer les 9 triples grandparentOf manquants : le graphe passe de 5 a 14 triples, couvrant les trois generations de grands-parents (Marie/Pierre, mais aussi Jean et Claire qui n’avaient aucun triple).
Le processus complet : 1. Extraction : Convertir le KG en ensembles de paires 2. Minage : Enumerer les candidats, calculer support/confidence/PCA 3. Filtrage : Garder les règles de haute PCA confidence (pas la confidence standard, qui aurait elimine la règle cible – cf. section 5) 4. Application : Inserer les nouveaux triples dans le graphe (avec deduplication, plusieurs règles pouvant inferer le même triple)
Note : Dans les vrais systèmes (AMIE3, AnyBURL), l’étape de minage est beaucoup plus sophistiquee avec des optimisations (pruning par support, enumeration fermee sous les specialisations). Notre implementation simplifiee a une complexite cubique en le nombre de predicats.
8. Visualisation du Knowledge Graph
Visualisons le graphe de familles pour mieux comprendre les relations decouvertes.
# Text-based visualization of the family tree
print("Arbre genealogique (relations parentOf) :")
print("=" * 50)
# Build parent -> children mapping
parent_map = defaultdict(list)
for parent_name, child_name in sorted(relations["parentOf"]):
parent_map[parent_name].append(child_name)
# Display as tree
def show_tree(name: str, indent: int = 0, max_depth: int = 3):
prefix = " " * indent + ("|-- " if indent > 0 else "")
print(f"{prefix}{name}")
if indent < max_depth and name in parent_map:
for child in sorted(parent_map[name]):
show_tree(child, indent + 1, max_depth)
# Show from root (grandparents)
all_children = set()
for children in parent_map.values():
all_children.update(children)
roots = [p for p in persons if p not in all_children]
for root in roots:
show_tree(root)
print()
# Show grandparentOf triples (original + inferred)
print("\nTriples grandparentOf (apres completion) :")
gp_triples = list(g.triples((None, FAM.grandparentOf, None)))
for s, p, o in sorted(gp_triples, key=lambda t: str(t[0])):
s_name = str(s).replace(str(FAM), "")
o_name = str(o).replace(str(FAM), "")
print(f" {s_name} -- grandparentOf --> {o_name}")
print(f"\nTotal : {len(gp_triples)} triples grandparentOf")Arbre genealogique (relations parentOf) :
==================================================
Marie
|-- Claire
|-- Anne
|-- Paul
|-- Emma
|-- Thomas
|-- Jean
|-- Luc
|-- Lea
|-- Marc
|-- Sophie
|-- Hugo
|-- Julie
Pierre
|-- Claire
|-- Anne
|-- Paul
|-- Emma
|-- Thomas
|-- Jean
|-- Luc
|-- Lea
|-- Marc
|-- Sophie
|-- Hugo
|-- Julie
Triples grandparentOf (apres completion) :
Claire -- grandparentOf --> Thomas
Claire -- grandparentOf --> Emma
Jean -- grandparentOf --> Hugo
Jean -- grandparentOf --> Julie
Jean -- grandparentOf --> Lea
Jean -- grandparentOf --> Marc
Marie -- grandparentOf --> Luc
Marie -- grandparentOf --> Sophie
Marie -- grandparentOf --> Paul
Marie -- grandparentOf --> Anne
Pierre -- grandparentOf --> Luc
Pierre -- grandparentOf --> Sophie
Pierre -- grandparentOf --> Paul
Pierre -- grandparentOf --> Anne
Total : 14 triples grandparentOfInterpretation : Arbre genealogique
La visualisation en arbre montre clairement la structure de la famille sur 4 generations :
- Generation 0 : Marie, Pierre (grands-parents)
- Generation 1 : Jean, Claire (parents)
- Generation 2 : Luc, Sophie, Paul, Anne (petits-enfants)
- Generation 3 : Marc, Lea, Hugo, Julie, Thomas, Emma (arrieres-petits-enfants)
Les triples grandparentOf couvrent maintenant les 14 paires (grand-parent, petit-enfant) du graphe : les 5 d’origine, plus les 9 inferes par les règles (generations 0, 1 et 2 confondues).
9. Proprietes logiques et composition
Certaines proprietes ont des caractéristiques logiques que le rule mining peut decouvrir.
# Analyze specific rule types
print("Analyse des proprietes logiques detectees :")
print("=" * 60)
# 1. Symmetry rules: r1(A,B) => r1(B,A)
print("\n1. SYMETRIE : r(A,B) => r(B,A)")
for pred in sorted(relations.keys()):
pairs = relations[pred]
reversed_pairs = {(b, a) for a, b in pairs}
overlap = pairs & reversed_pairs
if overlap:
symmetry = len(overlap) / len(pairs) if pairs else 0
print(f" {pred}: {len(overlap)}/{len(pairs)} paires symetriques (ratio={symmetry:.2f})")
print(f" Exemples : {sorted(overlap)[:3]}")
# 2. Transitivity: r1(A,B) ^ r1(B,C) => r1(A,C)
print("\n2. TRANSITIVITE : r(A,B) ^ r(B,C) => r(A,C)")
for pred in sorted(relations.keys()):
pairs = relations[pred]
body_pairs = compute_body_pairs(pairs, pairs)
if body_pairs:
support = len(body_pairs & pairs)
total = len(body_pairs)
if total > 0:
conf = support / total
status = "TRANSITIF" if conf == 1.0 else "NON transitif"
print(f" {pred}: support={support}/{total}, conf={conf:.2f} [{status}]")
if conf < 1.0 and conf > 0:
counter_examples = body_pairs - pairs
print(f" Contre-exemples : {sorted(counter_examples)[:3]}")
# 3. Composition rules: r1 ^ r2 => r3 (r3 different from r1, r2)
print("\n3. COMPOSITION : r1(A,B) ^ r2(B,C) => r3(A,C)")
composition_rules = [r for r in rules if len(r["body"]) == 2
and r["head"] not in r["body"]]
for rule in composition_rules:
r1, r2 = rule["body"]
rh = rule["head"]
print(f" {r1} ^ {r2} => {rh} (conf={rule['confidence']:.2f}, supp={rule['support']})")
if not composition_rules:
print(" Aucune composition non-triviale trouvee.")Analyse des proprietes logiques detectees :
============================================================
1. SYMETRIE : r(A,B) => r(B,A)
marriedTo: 2/2 paires symetriques (ratio=1.00)
Exemples : [('Marie', 'Pierre'), ('Pierre', 'Marie')]
siblingOf: 12/12 paires symetriques (ratio=1.00)
Exemples : [('Anne', 'Paul'), ('Claire', 'Jean'), ('Emma', 'Thomas')]
2. TRANSITIVITE : r(A,B) ^ r(B,C) => r(A,C)
marriedTo: support=0/2, conf=0.00 [NON transitif]
parentOf: support=0/14, conf=0.00 [NON transitif]
siblingOf: support=0/12, conf=0.00 [NON transitif]
3. COMPOSITION : r1(A,B) ^ r2(B,C) => r3(A,C)
parentOf ^ parentOf => grandparentOf (conf=0.36, supp=5)Interpretation : Proprietes logiques
| Propriete | Exemple detecte | Interpretation |
|---|---|---|
| Symetrie | siblingOf, marriedTo |
Relation reciproque |
| Transitivite | parentOf NON transitif |
Le parent d’un parent n’est pas un parent (c’est un grand-parent) |
| Composition | parentOf ^ parentOf => grandparentOf |
Nouvelle relation decouverte |
Points cles : 1. Le rule mining decouvre automatiquement les proprietes des relations (symetrie, transitivite) 2. En OWL, ces proprietes sont declarees manuellement (owl:SymmetricProperty, owl:TransitiveProperty). Le rule mining les apprend 3. La composition de relations est la decouverte la plus precieuse : elle créé de nouvelles relations
10. Comparaison ILP classique vs Rule Mining sur KG
Retour aux fondamentaux : comment le rule mining sur KG se compare-t-il a l’ILP classique (FOIL, Progol) ?
# Comparative analysis table
print("ILP Classique (SL-4) vs Rule Mining sur KG (SL-8)")
print("=" * 65)
print()
comparisons = [
("Donnees d'entree", "Facts + BK", "RDF triples"),
("Format des regles", "Clauses de Horn", "Regles d'association"),
("Apprentissage", "Inductif pur", "Statistique + Inductif"),
("Variables", "Logiques (X,Y,Z)", "Implicites (JOIN)"),
("Negation", "Negation as failure", "Absente (OWA)"),
("Recursion", "Supportee", "Non supportee"),
("Echelle", "Milliers de faits", "Milliards de triples"),
("Outils typiques", "FOIL, Progol, Aleph", "AMIE3, AnyBURL"),
("Evaluation", "Accuracy", "Support/Confidence/PCA"),
("Incompletude", "Pas de modele", "PCA (assumption)"),
]
for aspect, classic, kg in comparisons:
print(f" {aspect:<25s} | {classic:<20s} | {kg}")
print()
print("Le rule mining sur Knowledge Graphs peut etre vu comme une instance")
print("de l'ILP adaptee aux donnees du Web Semantique.")
print("Les differences principales sont:")
print(" 1. L'Open World Assumption (OWA) remplace le Closed World")
print(" 2. Les mesures statistiques remplacent la purete logique")
print(" 3. L'echelle impose des approximations et du pruning")ILP Classique (SL-4) vs Rule Mining sur KG (SL-8)
=================================================================
Donnees d'entree | Facts + BK | RDF triples
Format des regles | Clauses de Horn | Regles d'association
Apprentissage | Inductif pur | Statistique + Inductif
Variables | Logiques (X,Y,Z) | Implicites (JOIN)
Negation | Negation as failure | Absente (OWA)
Recursion | Supportee | Non supportee
Echelle | Milliers de faits | Milliards de triples
Outils typiques | FOIL, Progol, Aleph | AMIE3, AnyBURL
Evaluation | Accuracy | Support/Confidence/PCA
Incompletude | Pas de modele | PCA (assumption)
Le rule mining sur Knowledge Graphs peut etre vu comme une instance
de l'ILP adaptee aux donnees du Web Semantique.
Les differences principales sont:
1. L'Open World Assumption (OWA) remplace le Closed World
2. Les mesures statistiques remplacent la purete logique
3. L'echelle impose des approximations et du pruningInterpretation : ILP classique vs Rule Mining sur KG
| Dimension | ILP classique (FOIL) | Rule Mining (AMIE3) | Commun |
|---|---|---|---|
| Objectif | Apprendre des règles logiques | Apprendre des règles logiques | Identique |
| Representation | Clauses de Horn | Règles d’association RDF | Equivalent (Horn) |
| Données | Faits logiques + Base de connaissances | Triples RDF | Isomorphes |
| Monde | Closed World (CWA) | Open World (OWA) | Différent |
| Evaluation | Purete (0 erreurs) | Confidence statistique | Différent |
Note : La principale différence est l’Open World Assumption des KG. Dans un KG, l’absence d’un triple ne signifie pas que le fait est faux – il est simplement inconnu. C’est pourquoi la PCA confidence est importante : elle ajuste pour cette incompletude.
Exercices
Mettez en pratique les concepts appris avec ces exercices.
La vraie librairie : Answer Set Programming avec clingo
Tout ce notebook a manipule des règles de Horn avec du Python artisanal : compute_body_pairs fait la jointure, apply_rules fait une passe de chainage avant. C’est exactement le travail d’un moteur Datalog – et il existe une famille d’outils industriels qui font cela (et bien plus) : les solveurs ASP (Answer Set Programming) de la suite Potassco, dont clingo est le representant standard.
Origine. L’ASP (Answer Set Programming) et le solveur clingo sont presentes en detail par Gebser, M., Kaminski, R., Kaufmann, B. & Schaub, T. (2012), Answer Set Solving in Practice, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool (le livre de reference de la suite Potassco). Le cadre sémantique (answer sets, negation par echec, completion) remonte a Gelfond, M. & Lifschitz, V. (1988), The stable model semantics for logic programming, ICLP.
L’ASP generalise Datalog sur trois points qui nous concernent directement :
- Saturation au point fixe : clingo applique les règles jusqu’a ce que plus rien ne soit derivable, y compris pour des règles recursives (
ancestorOf) que notre mineur de règles fermees a 2 atomes ne peut même pas exprimer. - Contraintes d’integrite : une règle sans tete (
:- corps.) interdit un motif. Le solveur ne se contente pas de deriver, il verifie la coherence du graphe complete. - Negation par echec et règles de choix : au-dela de notre usage ici, l’ASP exprime des problemes combinatoires complets (planification, configuration).
Mutualisation avec la serie Tweety : la serie Tweety utilise déjà clingo – sous forme de binaire clingo.exe (installe par scripts/install_clingo.py) pilote par TweetyProject via la JVM (ClingoSolver, cf. Tweety-3). Ici nous utilisons le module Python clingo (pip install clingo) : c’est le même moteur Potassco, expose en librairie – pas de binaire externe, pas de JVM.
# Installation silencieuse de clingo (module Python officiel Potassco)
import importlib, subprocess, sys
if importlib.util.find_spec("clingo") is None:
subprocess.check_call([sys.executable, "-m", "pip", "install", "-q", "clingo"])
import clingo
print(f"clingo version : {clingo.__version__}")clingo version : 5.8.0Traduire le Knowledge Graph en programme ASP
La cellule suivante effectue la traduction en trois temps : (1) chaque paire (s, o) du KG devient un fait predicat("s","o")., (2) chaque règle minee dont la PCA confidence depasse 0.5 devient une clause de Horn tete(X,Y) :- corps(X,Z,Y)., puis (3) clingo grounde (instancie les variables) et calcule le modèle stable – l’ensemble des atomes vrais au point fixe. On recupere ce modèle pour le comparer a notre apply_rules Python et valider que les deux moteurs derivent la même chose.
# Traduction du KG et des regles minees en programme ASP, puis resolution.
# On repart des structures de ce notebook : `relations` (le KG AVANT completion),
# `rules` (les regles minees avec leur PCA confidence) et `inferred` (les triples
# ajoutes par notre apply_rules Python) -- la comparaison est donc a perimetre egal.
def asp_atom(pred: str, subj: str, obj: str) -> str:
"""Un atome ASP : predicat en minuscules, constantes entre guillemets."""
return f'{pred.lower()}("{subj}","{obj}")'
def kg_to_asp(relations: dict[str, set[tuple[str, str]]]) -> list[str]:
"""Chaque paire (s, o) du KG devient un fait ASP."""
return [asp_atom(pred, s, o) + "." for pred, pairs in sorted(relations.items())
for s, o in sorted(pairs)]
def rule_to_asp(rule: dict) -> str:
"""Traduit une regle minee (1 ou 2 atomes de corps, memes conventions que
compute_body_pairs : chainage X->Z->Y) en regle ASP."""
head = f'{rule["head"].lower()}(X,Y)'
if len(rule["body"]) == 2:
r1, r2 = rule["body"]
body = f'{r1.lower()}(X,Z), {r2.lower()}(Z,Y)'
else:
body = f'{rule["body"][0].lower()}(X,Y)'
return f"{head} :- {body}."
facts = kg_to_asp(relations)
asp_rules = [rule_to_asp(r) for r in rules if r["pca_confidence"] >= 0.5]
program = "\n".join(facts + asp_rules)
print(f"Programme ASP : {len(facts)} faits + {len(asp_rules)} regles")
for r in asp_rules:
print(f" {r}")
# Grounding + solving : le modele stable contient le KG sature
ctl = clingo.Control()
ctl.add("base", [], program)
ctl.ground([("base", [])])
model_atoms = set()
with ctl.solve(yield_=True) as handle:
for model in handle:
model_atoms = {str(a) for a in model.symbols(atoms=True)}
print(f"\nModele stable : {len(model_atoms)} atomes")Programme ASP : 33 faits + 5 regles
parentof(X,Y) :- parentof(X,Z), siblingof(Z,Y).
parentof(X,Y) :- marriedto(X,Z), parentof(Z,Y).
grandparentof(X,Y) :- grandparentof(X,Z), siblingof(Z,Y).
grandparentof(X,Y) :- marriedto(X,Z), grandparentof(Z,Y).
grandparentof(X,Y) :- parentof(X,Z), parentof(Z,Y).
Modele stable : 42 atomesVerification : clingo retrouve-t-il notre completion ?
Sur les mêmes faits et les mêmes règles qualifiees (les cinq règles dont la PCA >= 0.5, pas seulement la règle cible), clingo et notre apply_rules doivent deriver exactement les mêmes triplets. Le tableau ci-dessous compare predicat par predicat le KG initial, la completion Python et la saturation clingo : un verdict IDENTIQUE confirme que notre chainage avant artisanal etait bien un Datalog correct.
# Comparaison : clingo (saturation au point fixe) vs notre apply_rules (passe unique)
def model_pairs(pred: str) -> set[tuple[str, str]]:
"""Extrait du modele stable les paires (s, o) d'un predicat."""
out = set()
prefix = pred.lower() + '("'
for atom in model_atoms:
if atom.startswith(prefix):
inner = atom[len(pred) + 1:-1] # '"s","o"'
s, o = [t.strip('"') for t in inner.split('","')]
out.add((s, o))
return out
print(f"{'Predicat':18} {'KG initial':>10} {'+ Python':>9} {'+ clingo':>9} verdict")
print("-" * 62)
all_match = True
for pred in sorted(relations):
base = relations[pred]
python_final = base | {(s, o) for s, p, o in inferred if p == pred}
clingo_final = model_pairs(pred)
verdict = "IDENTIQUE" if clingo_final == python_final else "DIFFERENT"
all_match &= (verdict == "IDENTIQUE")
print(f"{pred:18} {len(base):>10} {len(python_final):>9} {len(clingo_final):>9} {verdict}")
if all_match:
print("\nLes deux moteurs derivent exactement la meme completion : notre")
print("apply_rules etait bien un chainage avant Datalog -- clingo le confirme.")
else:
print("\nDivergence : clingo sature au point fixe (les regles se nourrissent")
print("entre elles), la ou apply_rules ne fait qu'une seule passe.")Predicat KG initial + Python + clingo verdict
--------------------------------------------------------------
grandparentOf 5 14 14 IDENTIQUE
marriedTo 2 2 2 IDENTIQUE
parentOf 14 14 14 IDENTIQUE
siblingOf 12 12 12 IDENTIQUE
Les deux moteurs derivent exactement la meme completion : notre
apply_rules etait bien un chainage avant Datalog -- clingo le confirme.Au-dela de Datalog : recursion et contraintes d’integrite
L’equivalence ci-dessus est rassurante mais trompeuse : elle ne tient que parce que nos règles minees ne s’alimentent pas entre elles. Deux capacites de l’ASP restent inaccessibles a notre mineur de règles fermees a taille fixe :
- la recursion –
ancestorOfse définit par rapport a lui-même, un point fixe qu’aucune enumeration de corps de taille fixe ne peut exprimer ; - les contraintes d’integrite – une règle sans tete
:- corps.interdit un motif, et le solveur repondUNSATs’il ne peut le satisfaire, transformant la derivation en verification.
La cellule suivante active ces deux leviers sur notre KG, puis injecte un cycle comme contre-expérience pour montrer la contrainte d’integrite en action.
# Ce que l'ASP ajoute : recursion et contraintes d'integrite.
# 1) ancestorOf est RECURSIF -- inexprimable par nos regles fermees a 2 atomes
# (le mineur enumere des corps de taille fixe ; un point fixe ne s'enumere pas).
# 2) une contrainte d'integrite valide l'acyclicite du graphe familial.
extension = """
ancestorof(X,Y) :- parentof(X,Y).
ancestorof(X,Y) :- parentof(X,Z), ancestorof(Z,Y).
:- ancestorof(X,X).
"""
ctl2 = clingo.Control()
ctl2.add("base", [], program + extension)
ctl2.ground([("base", [])])
result_atoms = set()
sat = ctl2.solve(yield_=True)
with sat as handle:
satisfiable = False
for model in handle:
satisfiable = True
result_atoms = {str(a) for a in model.symbols(atoms=True)}
n_anc = sum(1 for a in result_atoms if a.startswith("ancestorof("))
n_par = len(relations["parentOf"])
print(f"Coherent (acyclique) : {satisfiable}")
print(f"ancestorOf derive : {n_anc} paires (a partir de {n_par} parentOf)")
# Contre-experience : on injecte un cycle (Emma serait parent de Marie)
ctl3 = clingo.Control()
ctl3.add("base", [], program + extension + 'parentof("Emma","Marie").')
ctl3.ground([("base", [])])
verdict = str(ctl3.solve())
print(f"\nAvec le fait cyclique parentof(Emma, Marie) : {verdict}")
print("UNSAT = le solveur REFUSE tout modele : la contrainte d'integrite")
print("transforme le KG complete en KG verifie.")Coherent (acyclique) : True
ancestorOf derive : 40 paires (a partir de 14 parentOf)
Avec le fait cyclique parentof(Emma, Marie) : UNSAT
UNSAT = le solveur REFUSE tout modele : la contrainte d'integrite
transforme le KG complete en KG verifie.Interpretation : du chainage artisanal au solveur industriel
Trois enseignements :
Validation croisee : sur les mêmes faits et les mêmes règles minees – les cinq règles qualifiées par la PCA, pas seulement la règle cible, dont deux qui reinjectent
grandparentOfdans leur propre corps – clingo dérive exactement la même completion que notreapply_rules. La saturation au point fixe coincide ici avec la passe unique parce que les derivations supplémentaires etaient déjà couvertes ; sur un KG plus dense, les règles qui s’alimentent entre elles auraient fait diverger les deux moteurs, et c’est le point fixe qui aurait eu raison. Notre implementation pedagogique etait correcte – mais elle ne tenait que parce que le problème etait restreint.La recursion change de classe :
ancestorOfdemande un calcul de point fixe que notre mineur ne peut ni exprimer (les règles fermees enumerees ont une taille fixe) ni evaluer. Pour clingo, c’est trivial. C’est la frontiere entre rule mining (decouvrir des règles plausibles, AMIE) et raisonnement (appliquer des règles exactes, ASP) : les deux outils sont complementaires, pas concurrents.La contrainte d’integrite inverse la charge de la preuve : au lieu de deriver puis d’inspecter, on declare l’invariant (
:- ancestorof(X,X)) et le solveur garantit que tout modèle le respecte – ou répond UNSAT. C’est exactement le rôle que l’oracle de validation jouera dans le capstone SL-11, et ce que le chainage avant nu ne fait pas.
Pour aller plus loin : l’apprentissage de programmes ASP (et non plus seulement leur exécution) est le domaine d’ILASP (Inductive Learning of Answer Set Programs) – voir par exemple asp-game-stratégies qui apprend des stratégies de jeu en ASP. Cote CoursIA, la serie Tweety (Tweety-3) montre l’ASP via TweetyProject/JVM, et Popper (integre dans SL-4) utilise clingo comme moteur de recherche d’hypotheses ILP : la boucle est bouclee.
Exemple guide 1 : Ajouter une nouvelle relation au KG
Bascule TP -> Exemple guide (See #2161). Solution demontree ci-dessous.
On ajoute la relation uncleOf (oncle/tante) au Knowledge Graph, puis on relance le rule mining pour voir si l’algorithme rediscover la règle definissante siblingOf(A,B) ^ parentOf(B,C) => uncleOf(A,C) (A est frere/soeur de B, B est parent de C, donc A est oncle/tante de C).
# Exemple guide 1 : Ajouter uncleOf et rediscover sa regle par le rule mining
# Resolution de l'Exercice 1 (See #2161) : solution demontree ci-dessous.
#
# uncleOf(A, C) :- siblingOf(A, B), parentOf(B, C).
# A est oncle/tante de C si A est frere/soeur d'un parent B de C.
# On enrichit le graphe `g` (deja complete par apply_rules en section 7) avec
# les triples uncleOf pour les paires bien definies, puis on relance le minage.
# Etape 1 : ajout des triples uncleOf. On couvre les paires (A,C) telles que
# A est sibling d'un parent de C -- c'est l'extension exacte de la regle.
uncle_triples = [
("Jean", "Paul"), ("Jean", "Anne"), # Jean sib Claire, Claire parent Paul/Anne
("Claire", "Luc"), ("Claire", "Sophie"), # Claire sib Jean, Jean parent Luc/Sophie
("Luc", "Hugo"), ("Luc", "Julie"), # Luc sib Sophie, Sophie parent Hugo/Julie
("Sophie", "Marc"), ("Sophie", "Lea"), # Sophie sib Luc, Luc parent Marc/Lea
("Anne", "Thomas"), ("Anne", "Emma"), # Anne sib Paul, Paul parent Thomas/Emma
]
for uncle, nephew in uncle_triples:
g.add((person(uncle), FAM.uncleOf, person(nephew)))
print(f"Etape 1 : {len(uncle_triples)} triples uncleOf ajoutes au graphe.")
# Etape 2 : re-extraction des relations (inclut maintenant uncleOf).
relations_ex1 = extract_relations(g)
print(f"Etape 2 : {len(relations_ex1)} relations dont "
f"uncleOf ({len(relations_ex1['uncleOf'])} paires).")
# Etape 3 : relance du rule mining sur le graphe enrichi.
rules_ex1 = mine_rules(relations_ex1, all_entities, min_support=1, min_confidence=0.3)
uncle_rules = [r for r in rules_ex1 if r["head"] == "uncleOf"]
# Etape 4 : verdict -- la regle definissante est-elle decouverte ?
print(f"\nEtape 3-4 : {len(uncle_rules)} regle(s) uncleOf decouverte(s) :")
for r in uncle_rules:
body = " ^ ".join(r["body"])
print(f" {body} => uncleOf "
f"[supp={r['support']}, body={r['body_size']}, "
f"conf={r['confidence']:.2f}, pca={r['pca_confidence']:.2f}]")
# Comparaison avec l'extension reelle de la regle.
body_pairs = compute_body_pairs(relations_ex1["siblingOf"], relations_ex1["parentOf"])
print(f"\nExtension siblingOf(A,B) ^ parentOf(B,C) : {len(body_pairs)} paires.")
print(f"uncleOf couvre {len(relations_ex1['uncleOf'] & body_pairs)}/{len(body_pairs)} "
f"de ces paires -> la regle definissante remonte a conf=1.00 (un axiome).")
print()
print('Lecture : le mineur rediscover BIEN la regle definissante '
'siblingOf ^ parentOf => uncleOf')
print('avec confidence 1.00 (relation completee exhaustivement -> axiome). Il')
print('remonte aussi une regle REDONDANTE uncleOf ^ siblingOf => uncleOf (le')
print('sibling dun oncle est aussi oncle) : meme extension, syntaxe differente.')
print('AMIE evite ce doublon en n enumerant que des regles FERMEES (closed rules).')
print()
print('Exemple guide 1 OK : uncleOf ajoute, regle definissante rediscover a conf 1.00.')Etape 1 : 10 triples uncleOf ajoutes au graphe.
Etape 2 : 5 relations dont uncleOf (10 paires).
Etape 3-4 : 2 regle(s) uncleOf decouverte(s) :
siblingOf ^ parentOf => uncleOf [supp=10, body=10, conf=1.00, pca=1.00]
uncleOf ^ siblingOf => uncleOf [supp=10, body=10, conf=1.00, pca=1.00]
Extension siblingOf(A,B) ^ parentOf(B,C) : 10 paires.
uncleOf couvre 10/10 de ces paires -> la regle definissante remonte a conf=1.00 (un axiome).
Lecture : le mineur rediscover BIEN la regle definissante siblingOf ^ parentOf => uncleOf
avec confidence 1.00 (relation completee exhaustivement -> axiome). Il
remonte aussi une regle REDONDANTE uncleOf ^ siblingOf => uncleOf (le
sibling dun oncle est aussi oncle) : meme extension, syntaxe differente.
AMIE evite ce doublon en n enumerant que des regles FERMEES (closed rules).
Exemple guide 1 OK : uncleOf ajoute, regle definissante rediscover a conf 1.00.Exercice 1 (variation) : Cousinage et la limite du mineur a 2 atomes
Ajoutez maintenant quelques triples cousinOf (cousins : enfants de freres/soeurs). La règle definissante est parentOf(A,B) ^ siblingOf(B,D) ^ parentOf(D,C) => cousinOf(A,C) – un corps a 3 atomes.
Étapes : 1. Ajouter 2-3 triples cousinOf (ex. Luc et Paul sont cousins : enfants de Jean et Claire qui sont siblings). 2. Re-extraire et relancer le rule mining. 3. La règle cousinOf est-elle decouverte ? Pourquoi le mineur a 2 atomes ne peut-il PAS l’exprimer ?
Indice : notre mine_rules n’enumere que des corps de 1 ou 2 atomes. Le cousinage demande d’enchainer 3 relations (parent, sibling, parent) – inaccessible a ce mineur. C’est précisément ce que l’Exercice 3 (règles a 3 atomes) viendra lever, et ce qu’AMIE contrôle par son paramètre de longueur maximale de corps.
# Exercice 1 (variation) : Cousinage et la limite du mineur a 2 atomes
# TODO etudiant : ajoutez cousinOf et constatez que le mineur a 2 atomes
# ne PEUT PAS rediscover sa regle (corps a 3 atomes).
# Etape 1 : ajouter 2-3 triples cousinOf
# g.add((person('Luc'), FAM.cousinOf, person('Paul'))) # Luc enfant de Jean,
# Paul enfant de Claire,
# Jean sib Claire
# Etape 2 : re-extraire et relancer mine_rules
# relations_c = extract_relations(g)
# rules_c = mine_rules(relations_c, all_entities, min_support=1, min_confidence=0.3)
# cousin_rules = [r for r in rules_c if r['head'] == 'cousinOf']
# Etape 3 : cousin_rules est vide -- pourquoi ? (corps a 3 atomes non enumerate)
print('Exercice a completer : ajoutez cousinOf et constatez labsence de regle decouverte')
print('Question : pourquoi le mineur a 2 atomes ne peut-il pas exprimer le cousinage ?')
# Indice : cousinOf demande parent ^ sibling ^ parent (3 atomes). Voir Exercice 3.
# result = None # TODO etudiant : nombre de regles cousinOf decouvertes (attendu : 0)Exercice a completer : ajoutez cousinOf et constatez labsence de regle decouverte
Question : pourquoi le mineur a 2 atomes ne peut-il pas exprimer le cousinage ?Exemple guide 2 : Reimplementer la PCA confidence
Bascule TP -> Exemple guide (See #2161). Solution demontree ci-dessous.
On reimplementede zero le calcul de la PCA confidence (Partial Completeness Assumption), sans recopier la section 4, puis on verifie qu’on retrouve exactement les valeurs de la section 5. L’idee : sous OWA, un sujet A qui a au moins un triple head(A,_) est suppose COMPLET, donc les body pairs (A,C) ou A a un head triple mais pas vers C sont de vrais contre-exemples ; les sujets sans aucun head triple sont exclus du denominateur (inconnus).
# Exemple guide 2 : Reimplementer la PCA confidence et verifier contre la section 5
# Resolution de l'Exercice 2 (See #2161) : solution demontree ci-dessous.
#
# PCA(body => head) = support / |{(a,c) in body : a a au moins un head triple}|
# Le denominateur exclut les body pairs dont le sujet n'a AUCUN head triple
# (inconnu sous OWA). On reimplemente ce calcul de zero, puis on le compare
# aux pca_confidence deja calculees par evaluate_rule (section 4/5).
def evaluate_rule_pca(
body_pairs: set[tuple[str, str]],
head_pairs: set[tuple[str, str]],
head_relation: set[tuple[str, str]]
) -> dict:
"""Reimplementation de zero : support, confidence standard, PCA confidence."""
support_pairs = body_pairs & head_pairs
support = len(support_pairs)
body_size = len(body_pairs)
if body_size == 0:
return {"support": 0, "body_size": 0, "confidence": 0.0, "pca_confidence": 0.0}
# Confidence standard : P(head | body) = support / body_size.
confidence = support / body_size
# PCA : denominateur restreint aux body pairs dont le sujet a au moins un
# head triple (sinon, sous OWA, on ne sait pas -> on exclut).
head_subjects = {a for a, _ in head_relation}
pca_denominator = sum(1 for a, c in body_pairs if a in head_subjects)
pca_confidence = support / pca_denominator if pca_denominator > 0 else 0.0
return {
"support": support,
"body_size": body_size,
"confidence": confidence,
"pca_confidence": pca_confidence,
}
# Verification : on recalcule chaque regle minee et on compare aux valeurs de
# la section 5 (stockees dans `rules` par mine_rules).
print("=== Verification de evaluate_rule_pca contre la section 5 ===")
all_match = True
for r in rules:
if len(r["body"]) == 2:
bp = compute_body_pairs(relations[r["body"][0]], relations[r["body"][1]])
else:
bp = relations[r["body"][0]]
m = evaluate_rule_pca(bp, relations[r["head"]], relations[r["head"]])
ok = (abs(m["confidence"] - r["confidence"]) < 1e-9
and abs(m["pca_confidence"] - r["pca_confidence"]) < 1e-9)
all_match &= ok
body = " ^ ".join(r["body"])
tag = "OK" if ok else "MISMATCH"
print(f" {body} => {r['head']:<14} "
f"conf {m['confidence']:.2f} (sec5 {r['confidence']:.2f}) | "
f"pca {m['pca_confidence']:.2f} (sec5 {r['pca_confidence']:.2f}) [{tag}]")
print()
print(f"Verdict : {'TOUTES les valeurs coincident avec la section 5.' if all_match else 'DIVERGENCE.'}")
print()
print("Lecture : la regle cible parentOf ^ parentOf => grandparentOf passe de")
print("conf 0.36 a pca 0.62. Sous confidence standard, l'incompletude du KG la")
print("punit (5/14 : seuls 5 des 14 grands-parents sont dans le KG). Sous PCA,")
print("le denominateur ne compte que les sujets ayant un head triple (Marie et")
print("Pierre, 8 paires) : 5/8 = 0.62. C'est l'estimateur fiable sous OWA --")
print("AMIE classe ses regles par PCA, pas par confidence standard.")
print()
print("Exemple guide 2 OK : PCA reimplementee de zero, verifiee contre la section 5.")=== Verification de evaluate_rule_pca contre la section 5 ===
parentOf ^ siblingOf => parentOf conf 1.00 (sec5 1.00) | pca 1.00 (sec5 1.00) [OK]
marriedTo ^ parentOf => parentOf conf 1.00 (sec5 1.00) | pca 1.00 (sec5 1.00) [OK]
grandparentOf ^ siblingOf => grandparentOf conf 0.80 (sec5 0.80) | pca 0.80 (sec5 0.80) [OK]
marriedTo ^ grandparentOf => grandparentOf conf 0.80 (sec5 0.80) | pca 0.80 (sec5 0.80) [OK]
parentOf ^ parentOf => grandparentOf conf 0.36 (sec5 0.36) | pca 0.62 (sec5 0.62) [OK]
Verdict : TOUTES les valeurs coincident avec la section 5.
Lecture : la regle cible parentOf ^ parentOf => grandparentOf passe de
conf 0.36 a pca 0.62. Sous confidence standard, l'incompletude du KG la
punit (5/14 : seuls 5 des 14 grands-parents sont dans le KG). Sous PCA,
le denominateur ne compte que les sujets ayant un head triple (Marie et
Pierre, 8 paires) : 5/8 = 0.62. C'est l'estimateur fiable sous OWA --
AMIE classe ses regles par PCA, pas par confidence standard.
Exemple guide 2 OK : PCA reimplementee de zero, verifiee contre la section 5.Exercice 2 (variation) : Un mini-KG ou la PCA est trompeuse
La PCA confidence repose sur l’hypothese que tout sujet ayant un head triple a ses head triples COMPLETS. Construisez un contre-exemple ou cette hypothese est violee : une règle FAUSSE qui obtient une PCA elevee.
Étapes : 1. Construisez un mini-KG (3-4 faits) ou un sujet A a un head triple mais ou ses head triples sont INCOMPLETS (il en manque de vrais). 2. Calculez la PCA confidence d’une règle fausse sur ce KG. 3. Quelle hypothese de completude partielle est violee ? Pourquoi la PCA surestime-t-elle alors la règle ?
Indice : si A a un seul head triple (A,C1) mais qu’en realite A est aussi lie a C2 (absent du KG), alors tout body pair (A,C2) est compte comme contre-exemple alors qu’il devrait etre support -> la PCA est biaisee vers le bas, OU inversement si le body evite (A,C2). La PCA n’est fiable que si la completude partielle tient.
# Exercice 2 (variation) : Un mini-KG ou la PCA est trompeuse
# TODO etudiant : construisez un KG ou la PCA surestime une regle fausse.
# Etape 1 : mini-KG (dictionnaire de paires) avec un sujet dont les head
# triples sont INCOMPLETS (hypothese PCA violee)
# mini_head = {('A','C1')} # A a un head triple, mais il en manque
# mini_body = {('A','C1'), ('A','C2')} # body couvre C1 (support) et C2
# Etape 2 : calculer evaluate_rule_pca(mini_body, mini_head, mini_head)
# m = evaluate_rule_pca(mini_body, mini_head, mini_head)
# Etape 3 : quelle hypothese de completude partielle est violee ?
print('Exercice a completer : construisez un KG piegeant la PCA')
print('Question : pourquoi la PCA peut-elle etre elevee pour une regle fausse ?')
# Indice : la PCA suppose les head triples complets DES qu'un sujet en a un.
# result = None # TODO etudiant : (regle, pca_obtenue, pourquoi_trompeuse)Exercice a completer : construisez un KG piegeant la PCA
Question : pourquoi la PCA peut-elle etre elevee pour une regle fausse ?Exemple guide 3 : Règles a 3 atomes
Bascule TP -> Exemple guide (See #2161). Solution demontree ci-dessous.
On etend le mineur pour enumerer des corps a 3 atomes \(r_1(A,B) \wedge r_2(B,C) \wedge r_3(C,D) \Rightarrow r_{head}(A,D)\) en enchainant deux jointures, puis on compare le nombre de candidats (et de règles validees) a celui du corps a 2 atomes.
# Exemple guide 3 : Minage de regles a 3 atomes
# Resolution de l'Exercice 3 (See #2161) : solution demontree ci-dessous.
#
# On etend compute_body_pairs en une variante a 3 atomes : on joint r1 x r2
# (comme d'habitude, resultat (A,C)), puis on joint le resultat avec r3 comme
# une relation (A,C) JOIN r3(C,D) -> (A,D). C'est exactement compute_body_pairs
# applique deux fois, en traitant le resultat intermediaire comme une relation.
def compute_body_pairs_3(
r1_pairs: set[tuple[str, str]],
r2_pairs: set[tuple[str, str]],
r3_pairs: set[tuple[str, str]]
) -> set[tuple[str, str]]:
"""Jointure 3 atomes : r1(A,B) JOIN r2(B,C) JOIN r3(C,D) -> (A,D)."""
body_2 = compute_body_pairs(r1_pairs, r2_pairs) # (A, C)
return compute_body_pairs(body_2, r3_pairs) # (A, C) JOIN r3(C,D) -> (A,D)
def mine_rules_3atoms(
relations: dict[str, set[tuple[str, str]]],
all_entities: set[str],
min_support: int = 1,
min_confidence: float = 0.3
) -> list[dict]:
"""Mine rules with a 3-atom body: r1(A,B) ^ r2(B,C) ^ r3(C,D) => r_head(A,D)."""
discovered = []
pred_names = sorted(relations.keys())
for r1 in pred_names:
for r2 in pred_names:
body_2 = compute_body_pairs(relations[r1], relations[r2])
if not body_2:
continue
for r3 in pred_names:
body_3 = compute_body_pairs(body_2, relations[r3])
if not body_3:
continue
for r_head in pred_names:
if r_head in (r1, r2, r3):
continue # skip trivial: head dans le corps
metrics = evaluate_rule(
body_3, relations[r_head], all_entities, relations[r_head])
if (metrics["support"] >= min_support
and metrics["confidence"] >= min_confidence):
discovered.append({
"body": [r1, r2, r3], "head": r_head, **metrics})
discovered.sort(key=lambda r: (-r["confidence"], -r["support"]))
return discovered
# Minage a 3 atomes (seuil conf 0.5 pour ne garder que les regles solides).
rules_3 = mine_rules_3atoms(relations, all_entities, min_support=1, min_confidence=0.5)
print(f"=== Etape 1-2 : {len(rules_3)} regle(s) a 3 atomes (conf >= 0.5) ===")
for r in rules_3:
body = " ^ ".join(r["body"])
print(f" {body} => {r['head']:<14} "
f"[supp={r['support']}, body={r['body_size']}, "
f"conf={r['confidence']:.2f}, pca={r['pca_confidence']:.2f}]")
# Etape 3 : comparaison du nombre de candidats 2 atomes vs 3 atomes.
n_pred = len(relations)
cand_2 = n_pred ** 3 # (r1, r2, head)
cand_3 = n_pred ** 4 # (r1, r2, r3, head)
print(f"\n=== Etape 3 : explosion combinatoire ===")
print(f" Predicats : {n_pred}")
print(f" Candidats corps a 2 atomes : {n_pred}^3 = {cand_2} (r1, r2, head)")
print(f" Candidats corps a 3 atomes : {n_pred}^4 = {cand_3} (r1, r2, r3, head)")
print(f" Rapport : x{cand_3 / cand_2:.0f} en passant de 2 a 3 atomes.")
print()
print("Lecture : sur ce KG, une seule regle a 3 atomes passe conf >= 0.5 :")
print("marriedTo ^ parentOf ^ parentOf => grandparentOf (conf 0.62). Elle")
print("reformule la regle cible a 2 atomes en ajoutant un atome marriedTo en")
print("tete de corps (le conjoint dun grand-parent lest aussi) -- plus precis")
print("mais plus rare. Le cout est lexplosion combinatoire : chaque atome")
print("supplementaire multiplie le nombre de candidats par le nombre de")
print("predicats. AMIE controle cela par (1) des regles FERMEES (closed rules,")
print("toute variable du corps apparait dans la tete) et (2) un pruning par")
print("support minimum des corps partiels.")
print()
print("Exemple guide 3 OK : minage 3 atomes implemente, 1 regle validee, explosion quantifiee.")=== Etape 1-2 : 1 regle(s) a 3 atomes (conf >= 0.5) ===
marriedTo ^ parentOf ^ parentOf => grandparentOf [supp=5, body=8, conf=0.62, pca=0.62]
=== Etape 3 : explosion combinatoire ===
Predicats : 4
Candidats corps a 2 atomes : 4^3 = 64 (r1, r2, head)
Candidats corps a 3 atomes : 4^4 = 256 (r1, r2, r3, head)
Rapport : x4 en passant de 2 a 3 atomes.
Lecture : sur ce KG, une seule regle a 3 atomes passe conf >= 0.5 :
marriedTo ^ parentOf ^ parentOf => grandparentOf (conf 0.62). Elle
reformule la regle cible a 2 atomes en ajoutant un atome marriedTo en
tete de corps (le conjoint dun grand-parent lest aussi) -- plus precis
mais plus rare. Le cout est lexplosion combinatoire : chaque atome
supplementaire multiplie le nombre de candidats par le nombre de
predicats. AMIE controle cela par (1) des regles FERMEES (closed rules,
toute variable du corps apparait dans la tete) et (2) un pruning par
support minimum des corps partiels.
Exemple guide 3 OK : minage 3 atomes implemente, 1 regle validee, explosion quantifiee.Exercice 3 (variation) : Règles fermees et expressivite
AMIE n’enumere que des règles fermees (closed rules) : toute variable du corps doit apparaitre dans la tete. C’est ce qui limite l’explosion.
Étapes : 1. Comptez les candidats a 2, 3, puis 4 atomes sur ce KG (extrapolez la formule n_pred^(k+1)). 2. Combien de ces candidats sont des règles fermees (variables du corps toutes presentes dans la tete r_head(A,D)) ? 3. Que perd-on en expressivite a n’enumerer que des règles fermees ?
Indice : une règle r1(A,B) ^ r2(B,C) => r_head(A,C) est fermee (A et C dans la tete), mais r1(A,B) ^ r2(B,C) => r_head(A,B) ne lest pas (C est libre dans le corps, absent de la tete -> projection existentielle). Les règles ouvertes sont plus expressives mais beaucoup plus nombreuses ; AMIE les sacrifie pour la scalabilite.
# Exercice 3 (variation) : Regles fermees et expressivite
# TODO etudiant : quantifiez le gain des regles fermees vs ouvertes.
# Etape 1 : extrapoler le nombre de candidats a k atomes
# for k in [2, 3, 4]:
# print(k, 'atomes :', len(relations), '**', k+1, '=', len(relations)**(k+1))
# Etape 2 : parmi les candidats a 2 atomes, combien sont FERMES ?
# Une regle r1(A,B)^r2(B,C)=>head(A,C) est fermee (A,C dans la tete).
# Etape 3 : que perd-on a nexaminer que les regles fermees ?
print('Exercice a completer : regles fermees vs ouvertes, expressivite perdue')
print('Question : pourquoi AMIE se restreint-il aux regles fermees ?')
# Indice : les regles ouvertes (variables libres dans le corps) sont plus
# expressives mais explosent en nombre. AMIE sacrifie lexpressivite pour la scalabilite.
# result = None # TODO etudiant : (candidats_2, candidats_3, candidats_4)Exercice a completer : regles fermees vs ouvertes, expressivite perdue
Question : pourquoi AMIE se restreint-il aux regles fermees ?Exemple guide 4 : Reparation minimale avec clingo
Bascule TP -> Exemple guide (See #2161). Solution demontree ci-dessous.
On injecte une arene erronee dans parentOf (celle qui ferme un cycle), on traduit le KG en ASP, et on demande a clingo de trouver la reparation minimale (au sens de la cardinalite) : le plus petit ensemble d’arenes a retirer pour restaurer l’acyclicite. C’est l’approche abductive de repair des KG.
# Exemple guide 4 : Reparation minimale d'un KG cyclique avec clingo
# Resolution de l'Exercice 4 (See #2161) : solution demontree ci-dessous.
#
# Plan :
# 1. Traduire le KG (relations["parentOf"]) en faits ASP parentof_raw/2.
# 2. Injecter UNE arene erronee (parentof_raw("Emma","Marie")) qui ferme un cycle.
# 3. Choix : pour chaque arene, decider de la garder ou la drop -> { drop(X,Y) }.
# 4. ancestorof/2 = fermeture transitive de parentof/2 (parentof = parentof_raw non droppe).
# 5. Contrainte d'integrite : :- ancestorof(X,X). (pas de cycle).
# 6. #minimize { 1,X,Y : drop(X,Y) } -> minimiser le NOMBRE d'arenes droppees.
# 7. --opt-mode=optN : enumerer TOUTES les reparation optimales (cout minimal).
# Etape 1-2 : faits + arene injectee.
parentof_facts = [f'parentof_raw("{s}","{o}").' for s, o in relations["parentOf"]]
injected = 'parentof_raw("Emma","Marie").' # ferme le cycle Emma -> Marie -> Claire -> Paul -> Emma
# Etape 3-6 : programme de reparation.
repair_rules = "\n".join([
"{ drop(X,Y) } :- parentof_raw(X,Y).", # choix: drop ou garder chaque arene
"parentof(X,Y) :- parentof_raw(X,Y), not drop(X,Y).", # parentof = brut non droppe
"ancestorof(X,Y) :- parentof(X,Y).", # base : parent = ancetre
"ancestorof(X,Y) :- parentof(X,Z), ancestorof(Z,Y).", # recursion : fermeture transitive
":- ancestorof(X,X).", # integrite : pas de cycle
"#minimize { 1,X,Y : drop(X,Y) }.", # minimiser le nombre de drops
"#show drop/2.", # ne montrer que les drops
])
asp_program = "\n".join(parentof_facts) + "\n" + injected + "\n" + repair_rules
# Etape 7 : resolution avec enumeration de TOUS les modeles optimaux.
ctl = clingo.Control(["--opt-mode=optN", "0"])
ctl.add("base", [], asp_program)
ctl.ground([("base", [])])
optimal_repairs = []
with ctl.solve(yield_=True) as handle:
for model in handle:
if model.optimality_proven:
drops = sorted(
f'{a.arguments[0]} -> {a.arguments[1]}'
for a in model.symbols(atoms=True) if a.name == "drop")
optimal_repairs.append((model.cost, drops))
print(f"=== Etape 1-7 : {len(optimal_repairs)} reparation(s) optimale(s) ===")
print(f" Cout minimal : {optimal_repairs[0][0] if optimal_repairs else '?'} "
f"(nombre d'arenes a retirer)")
for i, (cost, drops) in enumerate(optimal_repairs, 1):
print(f" Reparation {i} (cout={list(cost)}) : retirer {drops[0]}")
print()
print("Lecture : l'arene injectee Emma -> Marie ferme un cycle de longueur 4 :")
print(" Emma -> Marie -> Claire -> Paul -> Emma")
print("(les 3 autres arenes Marie -> Claire, Claire -> Paul, Paul -> Emma sont deja")
print("dans le KG). Pour restaurer l'acyclicite (contrainte :- ancestorof(X,X)), il")
print("suffit de retirer UNE des 4 arenes du cycle -> 4 reparations optimales au cout")
print("[1]. La minimisation #minimize { 1,X,Y : drop(X,Y) } selectionne les")
print("reparations de CARDINALITE minimale : clingo ne considere pas retirer 2+ arenes")
print("quand 1 suffit. C'est le critere parcimonieux (Occam) du repair abductif :")
print("preferer l'hypothese la plus simple (moins de faits remis en cause).")
print()
print("Exemple guide 4 OK : repair minimal implemente, 4 reparations optimales au cout [1].")=== Etape 1-7 : 4 reparation(s) optimale(s) ===
Cout minimal : [1] (nombre d'arenes a retirer)
Reparation 1 (cout=[1]) : retirer "Paul" -> "Emma"
Reparation 2 (cout=[1]) : retirer "Marie" -> "Claire"
Reparation 3 (cout=[1]) : retirer "Emma" -> "Marie"
Reparation 4 (cout=[1]) : retirer "Claire" -> "Paul"
Lecture : l'arene injectee Emma -> Marie ferme un cycle de longueur 4 :
Emma -> Marie -> Claire -> Paul -> Emma
(les 3 autres arenes Marie -> Claire, Claire -> Paul, Paul -> Emma sont deja
dans le KG). Pour restaurer l'acyclicite (contrainte :- ancestorof(X,X)), il
suffit de retirer UNE des 4 arenes du cycle -> 4 reparations optimales au cout
[1]. La minimisation #minimize { 1,X,Y : drop(X,Y) } selectionne les
reparations de CARDINALITE minimale : clingo ne considere pas retirer 2+ arenes
quand 1 suffit. C'est le critere parcimonieux (Occam) du repair abductif :
preferer l'hypothese la plus simple (moins de faits remis en cause).
Exemple guide 4 OK : repair minimal implemente, 4 reparations optimales au cout [1].Exercice 4 (variation) : Deux cycles et le cout du repair
On a minimise le nombre d’arenes retirees. Mais si le KG contient deux cycles independants, une seule suppression ne suffit plus.
Étapes : 1. Injectez UNE seconde arene qui créé un cycle indépendant du premier (ne partageant aucune arene avec Emma -> Marie -> Claire -> Paul -> Emma). 2. Predisez le cout minimal du repair (combien d’arenes a retirer minimum ?). 3. Combien de reparations optimales obtient-on alors ? Pourquoi le nombre explose-t-il (produit des choix par cycle) ?
Indice : deux cycles independants de longueurs \(k_1\) et \(k_2\) demandent au minimum 2 arenes retirees (une par cycle), et le nombre de reparations optimales est \(k_1 \times k_2\) (on choisit independamment une arene dans chaque cycle). C’est pourquoi la cardinalite minimale est une bonne heuristic mais pas toujours unique ni interpretable.
# Exercice 4 (variation) : Deux cycles independants et cout du repair
# TODO etudiant : injectez un second cycle et predisez le cout minimal.
# Etape 1 : second cycle independant (trouvez une arene qui ferme un autre cycle
# sans toucher au cycle Emma -> Marie -> Claire -> Paul -> Emma).
# second_injected = 'parentof_raw("Thomas","Paul").' # exemple a valider
# Etape 2 : predisez le cout minimal (1 ? 2 ? plus ?)
# Etape 3 : enumerez les reparations optimales avec clingo et comparez au produit k1*k2
print('Exercice a completer : deux cycles independants, cout minimal et multiplicite')
print('Question : pourquoi le nombre de reparations optimales est-il k1 x k2 ?')
# Indice : chaque cycle doit etre coupe au moins une fois ; les coupes sont
# independantes -> cardinalite minimale = nombre de cycles, multiplicite = produit.
# result = None # TODO etudiant : (cout_minimal, nombre_reparations)Exercice a completer : deux cycles independants, cout minimal et multiplicite
Question : pourquoi le nombre de reparations optimales est-il k1 x k2 ?11. Resume
Points cles
| Concept | Description |
|---|---|
| Knowledge Graph | Graphe oriente de triples RDF (sujet, predicat, objet) |
| rdflib | Bibliotheque Python de reference pour manipuler les KG |
| Rule Mining | Decouvrir des règles de Horn dans un KG (inspire d’AMIE3) |
| Support | Nombre de paires couvrant a la fois le corps et la tete de la règle |
| Confidence | Probabilite conditionnelle P(tete sachant corps) |
| PCA Confidence | Confidence ajustee pour l’Open World Assumption |
| Composition | Decouvrir de nouvelles relations par jointure (ex: parentOf ^ parentOf = grandparentOf) |
De l’ILP classique au Rule Mining
| Étape | ILP classique (SL-4) | Rule Mining (SL-8) |
|---|---|---|
| Données | Faits + BK explicite | Triples RDF |
| Espace de recherche | Clauses de Horn générales | Règles d’association fermees |
| Evaluation | Purete, couverture | Support, confidence, PCA |
| Scalabilite | Limitee (milliers) | Bonne (millions avec pruning) |
| Outils | FOIL, Progol, Aleph | AMIE3, AnyBURL |
Pont avec les autres series
| Serie | Lien avec SL-8 |
|---|---|
| SemanticWeb (SW) | rdflib, SPARQL, OWL, RDFS – les KG sont le coeur du Web Sémantique |
| Tweety | Logique propositionnelle et FOL – fondement des règles de Horn |
| SL-4 (ILP) | FOIL, resolution inverse – les règles de Horn sont les mêmes |
| SL-7 (NeuroSymbolic) | Embeddings (TransE) + règles – combinaison neuronal/symbolique |
Perspectives
Ce notebook a explore l’intersection entre la Programmation Logique Inductive (ILP) et les Knowledge Graphs, en montrant comment les techniques de minage de règles d’association s’adaptent aux données du Web Sémantique. La construction d’un Knowledge Graph familial avec rdflib a illustre la correspondance naturelle entre triples RDF (sujet, predicat, objet) et faits logiques predicat(sujet, objet). L’algorithme de rule mining inspire d’AMIE3 a decouvert automatiquement des règles de Horn dans ce graphe, notamment la règle compositionnelle parentOf(X,Y) ^ parentOf(Y,Z) => grandparentOf(X,Z) avec une confiance de 0.36 et une PCA confiance de 0.62.
La distinction entre confiance standard et PCA confiance est centrale dans le contexte des Knowledge Graphs. L’Open World Assumption (OWA) signifie que l’absence d’un triple ne signifie pas que le fait est faux – il est simplement inconnu. La PCA confiance corrige partiellement cette limitation en excluant du denominateur les paires dont le sujet n’a aucun triple de tete connu. L’application pratique des règles decouvertes a permis de completer le graphe en inferant 9 nouveaux triples grandparentOf manquants, passant de 5 a 14 triples – a condition de filtrer les règles par PCA confidence et non par confidence standard.
Les proprietes logiques detectees automatiquement (symetrie de siblingOf et marriedTo, composition parentOf ^ parentOf => grandparentOf) correspondent aux proprietes OWL declarees manuellement dans les ontologies formelles. Le rule mining les apprend directement des données, offrant une alternative scalable a la modelisation ontologique manuelle. Le notebook suivant, SL-9 - LLM + Symbolic Learning, prolonge cette reflexion en explorant comment les grands modèles de langage peuvent generer et valider des règles symboliques, ouvrant la voie a une cooperation entre approches statistiques a grande echelle et raisonnement formel.
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 (nouvelle relation au KG) | Votre nouvelle relation engendre-t-elle des règles redondantes avec les existantes (même extension, syntaxe différente) ? Comment un mineur comme AMIE evite-t-il d’enumerer ces doublons ? |
| Ex. 2 (PCA confidence) | Construisez un mini-KG ou la PCA confidence est trompeuse (règle fausse avec PCA elevee). Quelle hypothese de completude partielle est violee dans votre construction ? |
| Ex. 3 (règles a 3 atomes) | Comptez les candidats a 2 vs 3 atomes sur votre KG, extrapolez a 4. Pourquoi AMIE impose-t-il des règles fermees (closed rules), et que perd-on en expressivite a ce prix ? |
| Ex. 4 (reparation minimale) | Vos reparations optimales sont ex-aequo : toute arete du cycle coute 1. Comment departager ? Ponderez chaque fait par une confiance (par exemple la PCA confidence de la règle qui l’a derive, ou 1.0 pour un fait observe) et adaptez le #minimize : la reparation designe-t-elle maintenant le fait injecte ? |
Ressources
- Galarraga et al., “AMIE: Association Rule Mining under Incomplete Evidence in Ontological Knowledge Bases”, VLDB 2013
- Galarraga & Suchanek, “AMIE 3”, 2020
- Meilicke et al., “AnyBURL”, 2019
- Russell & Norvig, AI: A Modern Approach, 3e/4e ed., Chapitre 19
- rdflib Documentation
- AMIE3 GitHub
Notebook suivant : SL-9 - LLM + Symbolic Learning
Retour : Index SymbolicLearning | << SL-7 | SL-9 >>