SL-2 - Apprentissage et Connaissance : EBL & RBL (C#)

Jumeau C# du notebook SL-2-KnowledgeBasedLearning.ipynb. Version Python ↔︎ Version C# (.NET Interactive) — parité pédagogique du marathon #4956. Algorithmes AIMA ch.19.3 (EBL) + 19.4 (RBL), implémentés from-scratch en C# pur.

Objectifs d’apprentissage

1. Distinguer les 4 contraintes d’apprentissage (induction pure, EBL, RBL, KBIL).
2. Implémenter la vérification par énumération de modèles (mini-monde propositionnel).
3. Exécuter le chaînage avant avec unification (moteur EBL).
4. Construire un arbre de preuve EBL (simplification arithmétique) + le variabiliser.
5. Extraire et réutiliser une règle apprise (matching à variables) et mesurer le speedup réel.
6. Mesurer le speedup d’un coût simulé (re-dérivation) vs mesuré (§4/§4bis).
7. Vérifier une détermination RBL (attributs déterminants).

Prérequis

• Notions de logique propositionnelle + chaînage avant.
• .NET 9.0 + dotnet-interactive (kernel .net-csharp).
• Avoir suivi SL-1-LogicalLearning-Csharp.ipynb (CBH / Version Space).

Durée estimée : 55 minutes

Références

• Russell & Norvig, AIMA (3e éd.), §19.3-19.4.
• Notebook Python : SL-2-KnowledgeBasedLearning.ipynb.

1. Les 4 contraintes d’apprentissage

AIMA distingue 4 façons dont la connaissance interagit avec l’apprentissage, selon ce qui est déjà connu avant l’apprentissage et ce que l’exemple doit apporter. La cellule ci-dessous les vérifie par énumération de modèles sur un mini-monde propositionnel à 3 atomes (pointu, perce, tue) — l’exemple du bâton de Zog : une flèche pointue perce une peau molle, et percer un être vivant le tue.

1. Induction pure (héritée de SL-1) : l’hypothèse H plus la description Desc entraînent la classification. Ici pointu => tue avec l’observation pointu implique tue — l’apprentissage à partir des données seules.
2. EBL (Explanation-Based Learning) : la connaissance de fond Background (les deux implications pointu => perce, perce => tue) entraîne déjà l’hypothèse pointu => tue. EBL ne découvre rien de nouveau : il compile une déduction que le fond rendait possible, pour l’accélérer ensuite.
3. RBL (Relevance-Based Learning) : le fond plus l’observation plus la classification entraînent l’hypothèse. L’exemple contraint la sélection : parmi les hypothèses compatibles avec le fond, celles qui expliquent l’observation.
4. KBIL (Knowledge-Based Inductive Learning) : le fond plus l’hypothèse plus la description entraînent la classification — l’hypothèse candidate est testée contre les données.

L’output affiche les 4 verdicts, tous True sur ce mini-monde : sur l’exemple de Zog, les 4 formes d’apprentissage sont toutes cohérentes avec la connaissance de fond. C’est le rôle différent de la connaissance de fond qui les distingue, pas le résultat final : EBL s’appuie sur le fond sans données, RBL et KBIL croisent fond et observation, l’induction pure ignore le fond.

using System.Linq;

// Mini-monde propositionnel : 3 atomes.
string[] ATOMS = {"pointu", "perce", "tue"};

// Une formule = une fonction modèle -> bool. Un modèle = dict atome -> bool.
bool Entails(List<Func<Dictionary<string,bool>,bool>> kb,
             Func<Dictionary<string,bool>,bool> query) {
    // KB |= query ssi query est vraie dans TOUS les modèles où KB est vraie.
    foreach (var values in AllAssignments(ATOMS.Length)) {
        var model = new Dictionary<string,bool>();
        for (int i = 0; i < ATOMS.Length; i++) model[ATOMS[i]] = values[i];
        if (kb.All(f => f(model)) && !query(model)) return false;
    }
    return true;
}

// Énumère les 2^n combinaisons booléennes (produit cartésien).
IEnumerable<bool[]> AllAssignments(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        var v = new bool[n];
        for (int i = 0; i < n; i++) v[i] = (mask & (1 << i)) != 0;
        yield return v;
    }
}

// Connaissance de fond : pointu => perce, perce => tue.
var background = new List<Func<Dictionary<string,bool>,bool>> {
    m => (!m["pointu"]) || m["perce"],
    m => (!m["perce"]) || m["tue"],
};
// Observation : Description = pointu ; Classification = tue.
Func<Dictionary<string,bool>,bool> description = m => m["pointu"];
Func<Dictionary<string,bool>,bool> classification = m => m["tue"];
// Hypothèse candidate H : pointu => tue.
Func<Dictionary<string,bool>,bool> hypothesis = m => (!m["pointu"]) || m["tue"];

Console.WriteLine("Contraintes d'apprentissage (AIMA 19.3-19.5) vérifiées par énumération");
Console.WriteLine(new string('=', 70));
Console.WriteLine();
Console.WriteLine("1. Induction pure (SL-1) : H ^ Desc |= Class");
Console.WriteLine($"   -> {Entails(new(){hypothesis, description}, classification)}");
Console.WriteLine();
Console.WriteLine("2. EBL : Background |= Hypothese");
Console.WriteLine($"   (pointu=>perce)^(perce=>tue) |= (pointu=>tue) ? -> {Entails(background, hypothesis)}");
Console.WriteLine("   H était déjà déductible : EBL ne découvre rien, il COMPILE.");
Console.WriteLine();
Console.WriteLine("3. RBL : Background ^ Desc ^ Class |= Hypothese");
var rblKb = new List<Func<Dictionary<string,bool>,bool>>{description, classification};
rblKb.AddRange(background);
Console.WriteLine($"   -> {Entails(rblKb, hypothesis)}");
Console.WriteLine();
Console.WriteLine("4. KBIL : Background ^ H ^ Desc |= Class");
var kbilKb = new List<Func<Dictionary<string,bool>,bool>>{hypothesis, description};
kbilKb.AddRange(background);
Console.WriteLine($"   -> {Entails(kbilKb, classification)}");

Contraintes d'apprentissage (AIMA 19.3-19.5) vérifiées par énumération
======================================================================

1. Induction pure (SL-1) : H ^ Desc |= Class
   -> True

2. EBL : Background |= Hypothese
   (pointu=>perce)^(perce=>tue) |= (pointu=>tue) ? -> True
   H était déjà déductible : EBL ne découvre rien, il COMPILE.

3. RBL : Background ^ Desc ^ Class |= Hypothese
   -> True

4. KBIL : Background ^ H ^ Desc |= Class
   -> True

2. EBL : chaînage avant avec unification

EBL explique un exemple en rejouant la déduction à partir des règles de fond : au lieu d’apprendre un classifieur, il déroule la chaîne d’inférences qui relie les faits observés à la classification. On implémente un moteur de chaînage avant avec unification (pattern matching de prédicats à variables) jusqu’au point fixe. L’exemple : le bâton pointu de Zog.

Les règles de fond encodent le mécanisme causal : Pointu(x) => Perce(x), Perce(x) ^ PeauMolle(y) => TraversePeau(x,y), TraversePeau(x,y) ^ Vivant(y) => Hemorragie(y), Hemorragie(y) => Meurt(y). Les faits observés (Pointu(Baton), PeauMolle(Gibier), Vivant(Gibier)) sont des atomes clos ; les règles utilisent des variables (x, y en minuscules) que l’unification instancie par les faits.

L’output montre la trace d’inférence complète, de Pointu(Baton) jusqu’à Meurt(Gibier) en 4 dérivations. Chaque étape matérialise une règle de fond instanciée : la première (Pointu(Baton) => Perce(Baton)) lie x à Baton ; la seconde enchaîne avec PeauMolle(Gibier) en liant y à Gibier. La classification Meurt(Gibier) est finalement dérivée (True).

// Représentation : un atome = (prédicat, args). Variables en minuscules.
// Comparateur structurel (sinon string[] est comparé par référence => boucle infinie).
public class AtomEq : IEqualityComparer<(string,string[])> {
    public bool Equals((string,string[]) x, (string,string[]) y) =>
        x.Item1 == y.Item1 && x.Item2.SequenceEqual(y.Item2);
    public int GetHashCode((string,string[]) x) {
        int h = x.Item1.GetHashCode();
        foreach (var a in x.Item2) h = HashCode.Combine(h, a);
        return h;
    }
}

bool IsVar(string term) => term.Length > 0 && char.IsLower(term[0]);

// Unifie un atome-pattern (avec variables) avec un fait clos ; null si échec.
Dictionary<string,string> UnifyAtom((string,string[]) pattern, (string,string[]) fact,
                                     Dictionary<string,string> bindings) {
    if (pattern.Item1 != fact.Item1 || pattern.Item2.Length != fact.Item2.Length) return null;
    var b = new Dictionary<string,string>(bindings);
    for (int i = 0; i < pattern.Item2.Length; i++) {
        string p = pattern.Item2[i], f = fact.Item2[i];
        if (IsVar(p)) { if (b.TryGetValue(p, out var v) && v != f) return null; b[p] = f; }
        else if (p != f) return null;
    }
    return b;
}

// Chaînage avant jusqu'au point fixe. Retourne (faits dérivés, trace).
(HashSet<(string,string[])> facts, List<(List<(string,string[])> body, Dictionary<string,string> b, (string,string[]) head)> trace)
    ForwardChain(List<(List<(string,string[])> Body,(string,string[]) Head)> rules,
                 HashSet<(string,string[])> facts) {
    var trace = new List<(List<(string,string[])>, Dictionary<string,string>, (string,string[]))>();
    bool changed = true;
    while (changed) {
        changed = false;
        var snapshot = facts.OrderBy(f => f.Item1 + string.Join("", f.Item2)).ToList();
        foreach (var (body, head) in rules) {
            // DFS sur les atomes du body avec accumulations de liaisons.
            var stack = new Stack<(Dictionary<string,string>, int)>();
            stack.Push((new Dictionary<string,string>(), 0));
            while (stack.Count > 0) {
                var (bindings, k) = stack.Pop();
                if (k == body.Count) {
                    var newHead = (head.Item1, head.Item2.Select(a => bindings.TryGetValue(a, out var v) ? v : a).ToArray());
                    if (!facts.Contains(newHead)) {
                        facts.Add(newHead);
                        trace.Add((body.Select(b => (b.Item1, b.Item2.Select(a => bindings.TryGetValue(a,out var vv)?vv:a).ToArray())).ToList(), bindings, newHead));
                        changed = true;
                    }
                    continue;
                }
                foreach (var f in snapshot) {
                    var b2 = UnifyAtom(body[k], f, bindings);
                    if (b2 != null) stack.Push((b2, k + 1));
                }
            }
        }
    }
    return (facts, trace);
}

string Fmt((string,string[]) atom) => $"{atom.Item1}({string.Join(",", atom.Item2)})";

var RULES = new List<(List<(string,string[])> Body,(string,string[]) Head)> {
    (new(){("Pointu",new[]{"x"})}, ("Perce",new[]{"x"})),
    (new(){("Perce",new[]{"x"}),("PeauMolle",new[]{"y"})}, ("TraversePeau",new[]{"x","y"})),
    (new(){("TraversePeau",new[]{"x","y"}),("Vivant",new[]{"y"})}, ("Hemorragie",new[]{"y"})),
    (new(){("Hemorragie",new[]{"y"})}, ("Meurt",new[]{"y"})),
};
var FACTS = new HashSet<(string,string[])>(new AtomEq()) {
    ("Pointu", new[]{"Baton"}),
    ("PeauMolle", new[]{"Gibier"}),
    ("Vivant", new[]{"Gibier"}),
};

var (derived, fcTrace) = ForwardChain(RULES, new HashSet<(string,string[])>(FACTS, new AtomEq()));
Console.WriteLine("Exemple EBL : le bâton pointu de Zog, chaînage avant");
Console.WriteLine(new string('=', 60));
Console.WriteLine("Faits observés : " + string.Join(" ; ", FACTS.OrderBy(f=>f.Item1).Select(Fmt)));
Console.WriteLine();
Console.WriteLine("Dérivations :");
foreach (var (body, b, head) in fcTrace)
    Console.WriteLine($"  {string.Join(" ^ ", body.Select(Fmt))}  =>  {Fmt(head)}");
Console.WriteLine();
var goal = ("Meurt", new[]{"Gibier"});
Console.WriteLine($"Classification expliquée : {Fmt(goal)} ?  {derived.Contains(goal)}");

Exemple EBL : le bâton pointu de Zog, chaînage avant
============================================================
Faits observés : PeauMolle(Gibier) ; Pointu(Baton) ; Vivant(Gibier)

Dérivations :
  Pointu(Baton)  =>  Perce(Baton)
  Perce(Baton) ^ PeauMolle(Gibier)  =>  TraversePeau(Baton,Gibier)
  TraversePeau(Baton,Gibier) ^ Vivant(Gibier)  =>  Hemorragie(Gibier)
  Hemorragie(Gibier)  =>  Meurt(Gibier)

Classification expliquée : Meurt(Gibier) ?  True

3. EBL sur la simplification arithmétique

Un 2e exemple d’EBL : simplifier 1*(0+x) en x. On représente les expressions comme des chaînes et les règles de fond comme des réécritures (1*u → u, 0+u → u). L’arbre de preuve explique chaque étape ; la variabilisation le généralise en une règle réutilisable.

La cellule définit d’abord le type RewriteRule (nom, pattern, résultat) et la notion de forme primitive : une expression sans aucun opérateur + - * /. Les tests affichés vérifient le prédicat : IsPrimitive('x') = True (une variable seule), IsPrimitive('0+x') = False (l’opérateur + est présent), IsPrimitive('42') = True (une constante seule).

SimplifyStep applique la première règle dont le pattern est contenu dans l’expression. Sur 1*(0+x), la règle 1*u → u (pattern 1*) s’applique immédiatement : le résultat affiché est ('(0+x)', 1*u -> u) — le 1* disparaît et l’expression restante (0+x) attend la règle 0+u → u à l’étape suivante. L’ordre des règles compte : la réécriture est dirigée, pas commutative.

// Règle de réécriture : pattern -> résultat (string-based pour lisibilité).
public record RewriteRule(string Name, string Pattern, string Result) {
    public string Apply(string expr) => expr.Contains(Pattern)
        ? expr.Replace(Pattern, Result)  // remplace 1re occurrence
        : null;
}

var REWRITE_RULES = new List<RewriteRule> {
    new RewriteRule("1*u -> u", "1*", ""),
    new RewriteRule("0+u -> u", "0+", ""),
};

bool IsPrimitive(string expr) {
    string s = expr.Trim();
    if (string.IsNullOrEmpty(s)) return false;
    string[] ops = {"+","-","*","/"};
    return !ops.Any(op => s.Contains(op));
}

// Une étape de simplification : (résultat, nom_règle, justification).
(string result, string rule, string justification) SimplifyStep(string expr) {
    foreach (var rule in REWRITE_RULES) {
        var r = rule.Apply(expr);
        if (r != null) return (r, rule.Name, $"Rewrite({expr} -> {r})");
    }
    if (IsPrimitive(expr)) return (expr, "primitive", $"Primitive({expr}) => Simplify({expr} -> {expr})");
    return (expr, "bloqué", "Aucune règle applicable");
}

Console.WriteLine("Règles de réécriture chargées :");
foreach (var r in REWRITE_RULES) Console.WriteLine($"  {r.Name}");
Console.WriteLine();
Console.WriteLine($"IsPrimitive('x')   = {IsPrimitive("x")}");
Console.WriteLine($"IsPrimitive('0+x') = {IsPrimitive("0+x")}");
Console.WriteLine($"IsPrimitive('42')  = {IsPrimitive("42")}");
Console.WriteLine();
var (res, ruleName, just) = SimplifyStep("1*(0+x)");
Console.WriteLine($"SimplifyStep('1*(0+x)') = ('{res}', {ruleName})");

Règles de réécriture chargées :
  1*u -> u
  0+u -> u

IsPrimitive('x')   = True
IsPrimitive('0+x') = False
IsPrimitive('42')  = True

SimplifyStep('1*(0+x)') = ('(0+x)', 1*u -> u)

3.1 Arbre de preuve + variabilisation

BuildProof applique SimplifyStep jusqu’à atteindre un primitif, en enregistrant chaque étape. VariabilizeProof remplace ensuite les constantes par des variables pour généraliser la règle.

Sur 1*(0+x), l’arbre de preuve affiché comporte 2 étapes : 1. 1*(0+x) → (0+x) par la règle 1*u → u ; 2. (0+x) → (x) par la règle 0+u → u.

L’expression finale (x) est primitive : la simplification s’arrête. C’est la trace de cette dérivation que EBL va compiler.

La variabilisation remplace les constantes par des variables selon un mapping (1 → a, 0 → b, x → c) : la preuve devient a*(b+c) → (b+c) → (c), et la règle compilée affichée est a*(b+c) -> c. Les constantes de l’exemple (1, 0, x) sont ainsi abstraites : la règle apprise ne dépend plus de l’exemple particulier qui l’a produite — c’est le cœur de l’apprentissage EBL.

public record ProofStep(int Step, string InputExpr, string OutputExpr, string RuleName, string Justification);

// Construit l'arbre de preuve pour la simplification complète.
List<ProofStep> BuildProof(string expr) {
    var proof = new List<ProofStep>();
    string current = expr; int step = 0;
    while (!IsPrimitive(current)) {
        var (result, rule, justification) = SimplifyStep(current);
        if (result == current) break;  // bloqué
        proof.Add(new ProofStep(++step, current, result, rule, justification));
        current = result;
    }
    return proof;
}

// Variabilisation : remplace chaque constante par une variable selon un mapping.
List<ProofStep> VariabilizeProof(List<ProofStep> proof, Dictionary<string,string> constToVar) {
    string Variabilize(string s) {
        foreach (var kv in constToVar) s = s.Replace(kv.Key, kv.Value);
        return s;
    }
    return proof.Select(p => p with {
        InputExpr = Variabilize(p.InputExpr),
        OutputExpr = Variabilize(p.OutputExpr)
    }).ToList();
}

var proof = BuildProof("1*(0+x)");
Console.WriteLine("Arbre de preuve pour Simplify(1*(0+x)) :");
Console.WriteLine($"{"Step",4} | {"Input",-10} | {"Output",-10} | {"Rule",12} | Justification");
Console.WriteLine(new string('-', 70));
foreach (var p in proof)
    Console.WriteLine($"{p.Step,4} | {p.InputExpr,-10} | {p.OutputExpr,-10} | {p.RuleName,12} | {p.Justification}");
Console.WriteLine();

// Variabilisation : 1->a, 0->b, x->c => règle générale.
var constMap = new Dictionary<string,string>{{"1","a"},{"0","b"},{"x","c"}};
var genProof = VariabilizeProof(proof, constMap);
Console.WriteLine("Preuve variabilisée (1->a, 0->b, x->c) :");
foreach (var p in genProof)
    Console.WriteLine($"  {p.InputExpr} -> {p.OutputExpr}  [{p.RuleName}]");
Console.WriteLine();
Console.WriteLine("Règle compilée par EBL : a*(b+c) -> c  (généralisée de 1*(0+x) -> x)");

Arbre de preuve pour Simplify(1*(0+x)) :
Step | Input      | Output     |         Rule | Justification
----------------------------------------------------------------------
   1 | 1*(0+x)    | (0+x)      |     1*u -> u | Rewrite(1*(0+x) -> (0+x))
   2 | (0+x)      | (x)        |     0+u -> u | Rewrite((0+x) -> (x))

Preuve variabilisée (1->a, 0->b, x->c) :
  a*(b+c) -> (b+c)  [1*u -> u]
  (b+c) -> (c)  [0+u -> u]

Règle compilée par EBL : a*(b+c) -> c  (généralisée de 1*(0+x) -> x)

4. Mesurer le speedup EBL

L’intérêt d’EBL : une fois les règles apprises (compilées), la simplification de nouvelles expressions est plus rapide car on évite de re-dériver la preuve. On compare le coût de simplification AVEC vs SANS les règles apprises.

La cellule compare deux stratégies sur 8 expressions de test : - SANS règles apprises : on re-déroule la preuve complète à chaque fois, simulé par un facteur de coût 3× par étape (le coût de re-dériver). - AVEC règles apprises : on applique directement la règle compilée EBL: a*(b+c)->c (pattern 1*(0+) puis on finit avec les règles de base.

L’output affiche le coût agrégé sur les 8 expressions : 42 sans EBL contre 8 avec, soit un speedup de 42/8 = 5.25x. Le gain vient de la compilation : la chaîne de déduction (2 étapes dans l’exemple §3.1) est remplacée par une seule application de règle. EBL ne rend pas la connaissance plus vraie — il la rend plus rapide à utiliser.

using System.Diagnostics;

// Expressions de test (similaires mais non identiques à l'exemple d'apprentissage).
var testExprs = new List<string> {"1*(0+a)","1*(0+b)","1*(0+c)","1*(0+d)","1*(0+e)","1*f","0+g","1*(0+h)"};

// SANS règles apprises : on "re-déroule" la preuve complète à chaque fois
// (simulé par un facteur de coût supplémentaire = 3x Apply par étape).
long costWithoutEBL = 0;
foreach (var e in testExprs) {
    var cur = e; int steps = 0;
    while (!IsPrimitive(cur)) {
        var (r,_,_) = SimplifyStep(cur);
        if (r == cur) break;
        cur = r; steps++;
    }
    costWithoutEBL += steps * 3;  // coût "re-derive" = 3x
}

// AVEC règles apprises : applique directement la règle compilée.
var learnedRules = new List<RewriteRule> {
    new RewriteRule("EBL: a*(b+c)->c", "1*(0+", ""),
};
long costWithEBL = 0;
foreach (var e in testExprs) {
    int steps = 0; var cur = e;
    foreach (var lr in learnedRules) {
        var r = lr.Apply(cur);
        if (r != null) { cur = r; steps++; }
    }
    // étape finale si encore un '+' ou '*' résiduel via règles de base
    if (!IsPrimitive(cur)) { var (r2,_,_) = SimplifyStep(cur); if (r2 != cur) { cur = r2; steps++; } }
    costWithEBL += steps;
}

Console.WriteLine($"Speedup EBL sur {testExprs.Count} expressions de test :");
Console.WriteLine($"  Coût SANS règles apprises (re-derive) : {costWithoutEBL}");
Console.WriteLine($"  Coût AVEC règles apprises (compilé)   : {costWithEBL}");
Console.WriteLine($"  Speedup = {costWithoutEBL}/{costWithEBL} = {(double)costWithoutEBL/costWithEBL:F2}x");

Speedup EBL sur 8 expressions de test :
  Coût SANS règles apprises (re-derive) : 42
  Coût AVEC règles apprises (compilé)   : 8
  Speedup = 42/8 = 5,25x

4bis. EBL complet : extraction de règle et apprentissage réel

La section 4 mesurait le speedup avec une règle codée à la main (pattern "1*(0+"). On implémente ici le pipeline EBL complet — expliquer → variabiliser → extraire → apprendre → réutiliser — miroir des sections 4-6 du jumeau Python. Deux capacités nouvelles :

1. Extraction de règle : ExtractRule produit la règle généralisée avec ses préconditions non-tautologiques. Seules les conditions qui pourraient être fausses accompagnent la règle (ArithmeticUnknown(z)) ; les axiomes de la base (1*u → u, 0+u → u) sont toujours vrais et n’apparaissent pas.
2. Matching à variables : la règle apprise 1*(0+z) → (z) capture son sous-terme (groupe nommé) et s’applique à 1*(0+a), 1*(0+b)… — ce que la KB substring (§3) ne sait pas faire : elle ne sait que supprimer un littéral.

Nuance de variabilisation (différente du §3.1 qui abstrait tout) : l’EBL n’abstrait que la constante de l’exemple (x → z). Les constantes structurelles (1, 0) restent dans le pattern, car la preuve dépend précisément de leur présence — généraliser au-delà produirait une règle fausse.

using System.Text.RegularExpressions;

// Regle extraite par EBL.
public record LearnedRule(string OriginalExample, string Pattern, string Result,
                          string Precondition, int ProofLength);

// Implementation complete de l'EBL pour la simplification arithmetique :
// Explain -> Variabilize -> ExtractRule -> Learn -> SimplifyWithLearned.
public class ArithmeticEBL {
    public List<RewriteRule> KbRules { get; } = new() {
        new RewriteRule("1*u -> u", "1*", ""),
        new RewriteRule("0+u -> u", "0+", ""),
        // NB : "0*u -> 0" n'est pas exprimable dans ce schema substring
        // (il faudrait capturer u) ; MatchLearned montre comment faire mieux.
        new RewriteRule("u+0 -> u", "+0", ""),
        new RewriteRule("u*1 -> u", "*1", ""),
    };
    public List<LearnedRule> Learned { get; } = new();

    static bool IsPrim(string expr) {
        string s = expr.Trim();
        if (string.IsNullOrEmpty(s)) return false;
        string[] ops = {"+","-","*","/"};
        return !ops.Any(op => s.Contains(op));
    }

    (string result, string rule) SimplifyOneStep(string expr) {
        foreach (var rule in KbRules) {
            var r = rule.Apply(expr);
            if (r != null && r != expr) return (r, rule.Name);
        }
        if (IsPrim(expr)) return (expr, "primitive");
        return (expr, "bloque");
    }

    // Etape 1 : construit l'arbre de preuve pour l'expression.
    public List<ProofStep> Explain(string expr) {
        var proof = new List<ProofStep>();
        string current = expr; int n = 0;
        while (n < 20) {
            var (result, rule) = SimplifyOneStep(current);
            if (rule == "bloque" || result == current) break;
            n++;
            proof.Add(new ProofStep(n, current, result, rule, $"{current} -> {result} [{rule}]"));
            current = result;
        }
        return proof;
    }

    // Etape 2 : variabilise l'arbre de preuve (constantes d'exemple -> variables).
    public List<ProofStep> Variabilize(List<ProofStep> proof, Dictionary<string,string> constToVar) {
        string Apply(string s) {
            foreach (var kv in constToVar) s = s.Replace(kv.Key, kv.Value);
            return s;
        }
        return proof.Select(p => p with {
            InputExpr = Apply(p.InputExpr),
            OutputExpr = Apply(p.OutputExpr)
        }).ToList();
    }

    // Etape 3 : extrait la regle generalisee de la preuve variabilisee.
    public LearnedRule ExtractRule(List<ProofStep> genProof, Dictionary<string,string> constMap) {
        string pattern = genProof[0].InputExpr;
        string result = genProof[^1].OutputExpr;
        string preconditions = string.Join(" AND ",
            constMap.Values.Distinct().Select(v => $"ArithmeticUnknown({v})"));
        return new LearnedRule(genProof[0].InputExpr, pattern, result, preconditions, genProof.Count);
    }

    // Pipeline complet : expliquer -> variabiliser -> extraire -> stocker.
    public LearnedRule Learn(string example, Dictionary<string,string> constToVar, bool verbose = true) {
        var proof = Explain(example);
        if (proof.Count == 0) {
            if (verbose) Console.WriteLine($"  Aucune preuve trouvee pour {example}");
            return null;
        }
        var gen = Variabilize(proof, constToVar);
        var rule = ExtractRule(gen, constToVar);
        Learned.Add(rule);
        if (verbose) {
            Console.WriteLine($"  Exemple : {example}");
            Console.WriteLine($"  Preuve  : {proof.Count} etapes");
            Console.WriteLine($"  Regle   : {rule.Precondition} => Simplify({rule.Pattern}, {rule.Result})");
        }
        return rule;
    }

    // Matching a variables : le pattern "1*(0+z)" devient la regex 1\*\(0\+\(?<z>\w+\)\).
    // Chaque variable de la precondition capture un sous-terme ; le resultat est
    // reconstruit en substituant les captures. C'est ce qui permet a la regle
    // apprise sur x de s'appliquer a a, b, c...
    public string MatchLearned(LearnedRule rule, string expr) {
        var variables = Regex.Matches(rule.Precondition, @"ArithmeticUnknown\((\w+)\)")
                             .Select(m => m.Groups[1].Value).ToList();
        string regex = Regex.Escape(rule.Pattern);
        foreach (var v in variables) {
            int idx = regex.IndexOf(v);
            if (idx < 0) return null;
            regex = regex.Remove(idx, v.Length).Insert(idx, $"(?<{v}>\\w+)");
        }
        var m = Regex.Match(expr, regex);
        if (!m.Success) return null;
        string result = rule.Result;
        foreach (var v in variables) result = result.Replace(v, m.Groups[v].Value);
        return expr[..m.Index] + result + expr[(m.Index + m.Length)..];
    }

    // Simplifie avec les regles apprises d'abord (1 etape), puis la KB.
    public (string result, string method, int steps) SimplifyWithLearned(string expr) {
        foreach (var rule in Learned) {
            var matched = MatchLearned(rule, expr);
            if (matched != null)
                return (matched, $"learned({rule.Pattern}->{rule.Result})", 1);
        }
        var proof = Explain(expr);
        if (proof.Count > 0) return (proof[^1].OutputExpr, "kb", proof.Count);
        return (expr, "bloque", 0);
    }
}

// Demonstration : preuve de 1*(0+x), variabilisation de la SEULE constante
// d'exemple (x -> z), puis extraction de la regle.
var eblX = new ArithmeticEBL();
var proofX = eblX.Explain("1*(0+x)");

Console.WriteLine("Extraction de regle EBL");
Console.WriteLine("=" + new string('-', 48));
Console.WriteLine();
Console.WriteLine("Preuve concrete :");
foreach (var ps in proofX)
    Console.WriteLine($"  {ps.InputExpr,12} --[{ps.RuleName}]--> {ps.OutputExpr}");

var genProofX = eblX.Variabilize(proofX, new Dictionary<string,string> {{"x", "z"}});
Console.WriteLine();
Console.WriteLine("Preuve variabilisee (x -> z ; constantes structurelles 1 et 0 conservees) :");
foreach (var ps in genProofX)
    Console.WriteLine($"  {ps.InputExpr,12} --[{ps.RuleName}]--> {ps.OutputExpr}");

var ruleX = eblX.ExtractRule(genProofX, new Dictionary<string,string> {{"x", "z"}});
Console.WriteLine();
Console.WriteLine($"Regle extraite : {ruleX.Precondition} => Simplify({ruleX.Pattern}, {ruleX.Result})");
Console.WriteLine();

// Trois apprentissages successifs sur une instance fraiche.
var eblDemo = new ArithmeticEBL();
Console.WriteLine("Pipeline EBL complet");
Console.WriteLine("=" + new string('-', 48));
Console.WriteLine();
Console.WriteLine("Apprentissage 1 :");
eblDemo.Learn("1*(0+x)", new Dictionary<string,string> {{"x", "z"}});
Console.WriteLine();
Console.WriteLine("Apprentissage 2 :");
eblDemo.Learn("1*y", new Dictionary<string,string> {{"y", "v"}});
Console.WriteLine();
Console.WriteLine("Apprentissage 3 :");
eblDemo.Learn("0+u", new Dictionary<string,string> {{"u", "w"}});
Console.WriteLine();
Console.WriteLine($"Regles apprises : {eblDemo.Learned.Count}");
foreach (var (r, i) in eblDemo.Learned.Select((r, i) => (r, i)))
    Console.WriteLine($"  {i+1}. {r.Precondition} => Simplify({r.Pattern}, {r.Result})");

Extraction de regle EBL
=------------------------------------------------

Preuve concrete :
       1*(0+x) --[1*u -> u]--> (0+x)
         (0+x) --[0+u -> u]--> (x)

Preuve variabilisee (x -> z ; constantes structurelles 1 et 0 conservees) :
       1*(0+z) --[1*u -> u]--> (0+z)
         (0+z) --[0+u -> u]--> (z)

Regle extraite : ArithmeticUnknown(z) => Simplify(1*(0+z), (z))

Pipeline EBL complet
=------------------------------------------------

Apprentissage 1 :
  Exemple : 1*(0+x)
  Preuve  : 2 etapes
  Regle   : ArithmeticUnknown(z) => Simplify(1*(0+z), (z))

Apprentissage 2 :
  Exemple : 1*y
  Preuve  : 1 etapes
  Regle   : ArithmeticUnknown(v) => Simplify(1*v, v)

Apprentissage 3 :
  Exemple : 0+u
  Preuve  : 1 etapes
  Regle   : ArithmeticUnknown(w) => Simplify(0+w, w)

Regles apprises : 3
  1. ArithmeticUnknown(z) => Simplify(1*(0+z), (z))
  2. ArithmeticUnknown(v) => Simplify(1*v, v)
  3. ArithmeticUnknown(w) => Simplify(0+w, w)

// Speedup REEL : deux instances identiques, l'une vierge (KB seule), l'autre
// ayant appris 3 regles. Le cout est mesure en ETAPES de simplification
// (comptage effectif, pas un facteur simule comme en section 4).
var eblFresh = new ArithmeticEBL();   // pas de Learn()
var eblSmart = new ArithmeticEBL();
eblSmart.Learn("1*(0+x)", new Dictionary<string,string> {{"x", "z"}}, verbose: false);
eblSmart.Learn("1*y",    new Dictionary<string,string> {{"y", "v"}}, verbose: false);
eblSmart.Learn("0+u",    new Dictionary<string,string> {{"u", "w"}}, verbose: false);

var ebtExprs = new List<string> {
    "1*(0+a)", "1*(0+b)", "1*(0+c)", "1*(0+d)", "1*(0+e)",
    "1*f", "0+g", "1*(0+h)", "1*(0+i)", "1*(0+j)",
};

Console.WriteLine("Comparaison de performance : avec vs sans regles EBL");
Console.WriteLine("=" + new string('-', 59));
Console.WriteLine();
Console.WriteLine($"{"Expression",-12} | {"Sans EBL",20} | {"Avec EBL",20} | Gain");
Console.WriteLine(new string('-', 74));

int totalFresh = 0, totalSmart = 0;
foreach (var expr in ebtExprs) {
    var (_, methodF, stepsF) = eblFresh.SimplifyWithLearned(expr);
    var (_, methodS, stepsS) = eblSmart.SimplifyWithLearned(expr);
    totalFresh += stepsF; totalSmart += stepsS;
    int gain = stepsF - stepsS;
    string gainStr = gain > 0 ? $"-{gain}" : "=";
    Console.WriteLine($"{expr,-12} | {methodF,17} ({stepsF}e) | {methodS,17} ({stepsS}e) | {gainStr}");
}
Console.WriteLine(new string('-', 74));
Console.WriteLine($"{"TOTAL",-12} | {totalFresh,20} | {totalSmart,20} | -{totalFresh - totalSmart}");
Console.WriteLine();
double speedupX = (double)totalFresh / totalSmart;
double reductionX = (1 - (double)totalSmart / totalFresh) * 100;
Console.WriteLine($"Speedup moyen : {speedupX:F1}x");
Console.WriteLine($"Reduction d'etapes : {reductionX:F0}%");

Comparaison de performance : avec vs sans regles EBL
=-----------------------------------------------------------

Expression   |             Sans EBL |             Avec EBL | Gain
--------------------------------------------------------------------------
1*(0+a)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
1*(0+b)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
1*(0+c)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
1*(0+d)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
1*(0+e)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
1*f          |                kb (1e) |   learned(1*v->v) (1e) | =
0+g          |                kb (1e) |   learned(0+w->w) (1e) | =
1*(0+h)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
1*(0+i)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
1*(0+j)      |                kb (2e) | learned(1*(0+z)->(z)) (1e) | -1
--------------------------------------------------------------------------
TOTAL        |                   18 |                   10 | -8

Speedup moyen : 1,8x
Reduction d'etapes : 44%

Interprétation : EBL complet

Phase	Expression	Commentaire
Preuve concrète	1*(0+x) → (x)	Spécifique à l’exemple observé
Preuve variabilisée	1*(0+z) → (z)	Variable z remplace x
Règle extraite	ArithmeticUnknown(z) => Simplify(1*(0+z), (z))	Condition : z inconnu arithmétique

La condition ArithmeticUnknown(z) est la seule précondition non-tautologique : les règles 1*u -> u et 0+u -> u sont des axiomes de la base de connaissance — toujours vrais. (Les parenthèses résiduelles de (z) restent en l’état : notre mini-système ne réécrit que 1* et 0+.) La règle extraite est nouvelle par rapport à la base, mais déduite d’elle — EBL ne découvre rien, il compile.

La mesure réelle (étapes comptées, pas un facteur simulé comme en §4) confirme le compromis operationalité/généralité :

• Avantage : les expressions correspondant aux règles apprises sont simplifiées en 1 étape au lieu de 2 (lookup direct, matching à variables).
• Inconvénient : chaque règle apprise prend de l’espace et du temps de recherche.
• Quand EBL est efficace : quand les mêmes patterns de simplification reviennent souvent ; inefficace quand les expressions sont toutes différentes.

Point cle AIMA : « EBL converts first-principles theories into useful special-purpose knowledge. » La valeur d’EBL dépend entièrement de la fréquence de réutilisation — d’où le mécanisme de désapprentissage de l’Exercice 3.

5. RBL : vérification de détermination

RBL (Relevance-Based Learning) identifie les attributs déterminants : un ensemble det_attrs détermine target_attr si, pour chaque combinaison de valeurs de det_attrs, il existe exactement une valeur de target_attr dans les données. C’est une forme de découverte de dépendances fonctionnelles dans les données.

Sur le domaine restaurant (le classique WillWait d’AIMA), la cellule teste trois ensembles candidats : - (Patrons) -> WillWait ? False : la valeur de Patrons ne suffit pas — Some apparaît avec Yes et No dans les données. - (Type) -> WillWait ? True : chaque type de restaurant a une seule réponse (French → Yes, Thai → Yes, Burger → No, Italian → Yes). - (Patrons, Type) -> WillWait ? True : la combinaison détermine aussi la réponse.

Le résultat remarquable est que Type seul est déjà déterminant sur ce petit jeu (True) alors que Patrons seul ne l’est pas (False) : la détermination dépend des données observées, pas d’une intuition a priori. C’est ce que RBL cherche à extraire : l’ensemble minimal d’attributs qui prédit la cible.

// Vérifie si detAttrs déterminent targetAttr dans les données.
bool CheckDetermination(List<Dictionary<string,string>> data,
                         List<string> detAttrs, string targetAttr) {
    var groups = new Dictionary<string, HashSet<string>>();
    foreach (var row in data) {
        string key = string.Join("|", detAttrs.Select(a => row.GetValueOrDefault(a,"?")));
        if (!groups.ContainsKey(key)) groups[key] = new HashSet<string>();
        groups[key].Add(row.GetValueOrDefault(targetAttr, "?"));
    }
    return groups.Values.All(vals => vals.Count == 1);
}

// Jeu de données : détermine si (Patrons, Type) -> WillWait ?
var data = new List<Dictionary<string,string>> {
    new(){{"Patrons","Some"},{"Type","French"},{"WillWait","Yes"}},
    new(){{"Patrons","Full"},{"Type","Thai"},{"WillWait","Yes"}},
    new(){{"Patrons","Some"},{"Type","Burger"},{"WillWait","No"}},
    new(){{"Patrons","Full"},{"Type","Thai"},{"WillWait","Yes"}},
    new(){{"Patrons","Some"},{"Type","Italian"},{"WillWait","Yes"}},
    new(){{"Patrons","None"},{"Type","Burger"},{"WillWait","No"}},
    new(){{"Patrons","Some"},{"Type","Thai"},{"WillWait","Yes"}},
    new(){{"Patrons","Full"},{"Type","Burger"},{"WillWait","No"}},
};

Console.WriteLine("Détermination RBL sur le domaine restaurant :");
Console.WriteLine($"  (Patrons)        -> WillWait ? {CheckDetermination(data, new(){"Patrons"}, "WillWait")}");
Console.WriteLine($"  (Type)           -> WillWait ? {CheckDetermination(data, new(){"Type"}, "WillWait")}");
Console.WriteLine($"  (Patrons, Type)  -> WillWait ? {CheckDetermination(data, new(){"Patrons","Type"}, "WillWait")}");

Détermination RBL sur le domaine restaurant :
  (Patrons)        -> WillWait ? False
  (Type)           -> WillWait ? True
  (Patrons, Type)  -> WillWait ? True

Exercice : EBL sur la différentiation symbolique

Appliquez EBL à un nouveau domaine : la différentiation. Variabilisez la preuve de d/dx(x^2) = 2x en une règle générale d/dx(u^2) = 2u.

Contexte : vous avez vu en §2 le chaînage avant avec unification et en §3.1 l’arbre de preuve + variabilisation. Cet exercice transpose le même mécanisme (règles de réécriture + arbre de preuve + généralisation) aux règles de dérivation usuelles : d/dx(u^n) = n*u^(n-1), d/dx(const) = 0, d/dx(u+v) = du/dx + dv/dx.

Indices : - # Étape 1 : définir les règles de réécriture de différentiation (comme §3). - # Étape 2 : construire l’arbre de preuve de d/dx(x^2) avec BuildProof. - # Étape 3 : variabiliser (x → u, 2 → n) pour généraliser la règle. - # Indice : réutiliser RewriteRule, BuildProof et VariabilizeProof de §3.

// EXERCICE : EBL sur la différentiation symbolique
public List<ProofStep> EBL_Differentiation(string expr) {
    // TODO etudiant : construisez l'arbre de preuve pour d/dx(x^2) -> 2x
    // via les règles de fond : d/dx(u^n) = n*u^(n-1), d/dx(const) = 0, etc.
    // Etape 1 : définir les règles de réécriture de différentiation.
    // Etape 2 : construire la preuve.
    // Etape 3 : variabiliser (x -> u, 2 -> n) pour généraliser.
    return new List<ProofStep>();  // TODO etudiant
}

Console.WriteLine("Exercice à compléter (EBL différentiation).");

Exercice à compléter (EBL différentiation).

// EXERCICE 2 : RBL robuste au bruit (cf. cellule 15 : "RBL robuste au bruit").
// On ajoute un attribut bruite (Raining, valeur aleatoire) au jeu de donnees
// restaurant de la cellule 12, puis on verifie que (Patrons, Type) reste
// determinant malgre le bruit : RBL doit filtrer les attributs non pertinents.
// Indice : generer N jeux avec une colonne Raining aleatoire, et verifier que
//          CheckDetermination(data, ["Patrons","Type"], "WillWait") == true pour tous,
//          alors que CheckDetermination(data, ["Raining"], "WillWait") == false.

// TODO etudiant : definissez la fonction ci-dessous.
bool RBL_Robust_To_Noise(int nTrials) {
    // Etape 1 : reprendre le jeu de donnees de la cellule 12.
    // Etape 2 : ajouter une colonne "Raining" (valeur aleatoire "Yes"/"No").
    // Etape 3 : verifier sur nTrials jeux bruites que (Patrons, Type) reste determinant.
    // Etape 4 : verifier que (Raining) seul n'est PAS determinant (bruit filtre par RBL).
    return false;  // TODO etudiant : renvoyez true si (Patrons,Type) determine sur tous les essais
}

Console.WriteLine($"Exercice 2 a completer : RBL robuste au bruit (nTrials=10) -> {RBL_Robust_To_Noise(10)}.");

Exercice 2 a completer : RBL robuste au bruit (nTrials=10) -> False.

// EXERCICE 3 : Seuil de desapprentissage (cf. cellule 15 : "Seuil de desapprentissage").
// EBL peut sur-specialiser. On veut un mecanisme de "forgetting" : si une regle
// apprise ne s'applique jamais sur N nouveaux exemples, la retirer de la base.
// Indice : modele par une liste de reggles (string) + un compteur d'inutilisation
//          par regle ; a chaque nouvel exemple, incrementer les regles non declenchees,
//          et retirer celles dont le compteur depasse le seuil N.

// TODO etudiant : implementez la logique de desapprentissage.
List<string> Forget_Stale_Rules(List<string> learnedRules, int N) {
    // Etape 1 : pour chaque regle, compter sur N nouveaux exemples combien de fois elle s'applique.
    // Etape 2 : retirer les regles dont le compteur d'inutilisation > seuil.
    // Etape 3 : renvoyer la liste des reggles conservees.
    return learnedRules;  // TODO etudiant : appliquez le filtre de desapprentissage
}

Console.WriteLine($"Exercice 3 a completer : seuil de desapprentissage (N=5) -> {Forget_Stale_Rules(new List<string>{"d/dx(x^n) = n*x^(n-1)"}, 5).Count} regle(s) conservee(s).");

Exercice 3 a completer : seuil de desapprentissage (N=5) -> 1 regle(s) conservee(s).

Bilan

Ce notebook a présenté EBL et RBL from-scratch en C#, jumeau du notebook Python :

1. 4 contraintes d’apprentissage (induction / EBL / RBL / KBIL) vérifiées par énumération de modèles.
2. EBL = compilation : Background |= H (rien de nouveau, juste accélération).
3. Chaînage avant + unification : moteur d’inférence pour expliquer un exemple.
4. Arbre de preuve + variabilisation : généraliser une dérivation en règle.
5. EBL complet (§4bis) : extraction de règle (préconditions non-tautologiques), apprentissage réel et matching à variables — speedup mesuré en étapes réelles.
6. Speedup EBL (§4) : les règles compilées évitent de re-dériver.
7. RBL = détermination : identifier les attributs qui déterminent la cible.

Parité : jumeau C# de SL-2-KnowledgeBasedLearning.ipynb. Les deux implémentent les mêmes algorithmes from-scratch (pas de lib ML). Cf marathon parité (#4956), EPIC #3801 (Prong B).

Exercices supplémentaires

Exercice 2 : RBL robuste au bruit

Ajoutez un attribut bruité au jeu de données §5 (ex : Raining aléatoire). Vérifiez que (Patrons, Type) reste déterminant malgré le bruit (RBL filtre les attributs pertinents).

Exercice 3 : Seuil de désapprentissage

EBL peut sur-spécialiser. Implémentez un mécanisme de désapprentissage : si une règle apprise ne s’applique jamais sur N nouveaux exemples, la retirer.

Références

• Russell & Norvig, AIMA (3e éd.), §19.3-19.4.
• Mitchell, T. M. Machine Learning (1997), ch. 3-4.
• Notebook Python : SL-2-KnowledgeBasedLearning.ipynb.
• Marathon parité : #4956.