SL-1 - Apprentissage Logique : CBH Search et Version Space (C#)

Jumeau C# du notebook SL-1-LogicalLearning.ipynb. Version Python ↔︎ Version C# (.NET Interactive) — parité pédagogique du marathon #4956. Algorithme AIMA ch.19 (Current-Best-Hypothesis + Candidate Elimination), implémenté from-scratch en C# pur (type system + HashSet<>, pas de solveur requis).

Objectifs d’apprentissage

1. Modéliser un domaine d’apprentissage (attributs, exemples, hypothèses conjonctives).
2. Définir la relation de couverture (covers) et la consistance d’une hypothèse.
3. Implémenter la hiérarchie de généralisation (more_general / more_specific).
4. Exécuter l’algorithme Current-Best-Hypothesis (CBH, AIMA Fig 19.2).
5. Exécuter l’algorithme Candidate Elimination (Version Space, AIMA Fig 19.3).
6. Comparer les deux stratégies et observer l’effondrement du VS sur 12 exemples.

Prérequis

• Notions de structures de données (ensembles, tuples).
• .NET 9.0 + dotnet-interactive (kernel .net-csharp).
• Concepts : aucune librairie externe requise.

Durée estimée : 50 minutes

Références

• Russell & Norvig, Artificial Intelligence: A Modern Approach (3e éd.), ch. 19.
• Mitchell, T. M. Machine Learning (1997), ch. 2 (Version Space).
• Notebook Python associé : SL-1-LogicalLearning.ipynb.

1. Le problème restaurant (AIMA)

Le problème canonique d’AIMA : décider si l’on attend une table dans un restaurant, à partir de 10 attributs descriptifs. L’objectif est d’apprendre la fonction cible WillWait à partir d’exemples étiquetés.

Attributs du domaine

Chaque restaurant est décrit par 10 attributs catégoriels (taille de domaine 2-4).

Hypothèses comme conjonctions

Une hypothèse est un tuple de 10 contraintes, une par attribut : - "?" = n’importe quelle valeur (contrainte relâchée — général), - une valeur spécifique (ex "Thai") = contrainte stricte, - null = aucune valeur acceptée (hypothèse vide — spécifique à l’extrême).

// Définition du domaine : attributs et leurs valeurs possibles.
var ATTRIBUTES = new[] {
    "Alternate",    // Yes, No
    "Bar",          // Yes, No
    "Fri/Sat",      // Yes, No
    "Hungry",       // Yes, No
    "Patrons",      // None, Some, Full
    "Price",        // $, $$, $$$
    "Raining",      // Yes, No
    "Reservation",  // Yes, No
    "Type",         // French, Italian, Thai, Burger
    "WaitEstimate", // 0-10, 10-30, 30-60, >60
};

var ATTRIBUTE_VALUES = new Dictionary<string, string[]> {
    {"Alternate",    new[]{"Yes","No"}},
    {"Bar",          new[]{"Yes","No"}},
    {"Fri/Sat",      new[]{"Yes","No"}},
    {"Hungry",       new[]{"Yes","No"}},
    {"Patrons",      new[]{"None","Some","Full"}},
    {"Price",        new[]{"$","$$","$$$"}},
    {"Raining",      new[]{"Yes","No"}},
    {"Reservation",  new[]{"Yes","No"}},
    {"Type",         new[]{"French","Italian","Thai","Burger"}},
    {"WaitEstimate", new[]{"0-10","10-30","30-60",">60"}},
};

// Les 12 exemples du restaurant, adaptés de la Table 19.1 d'AIMA.
// (Alternate, Bar, Fri/Sat, Hungry, Patrons, Price, Raining, Reservation,
//  Type, WaitEstimate, WillWait)
var RAW_EXAMPLES = new (string Alternate,string Bar,string FriSat,string Hungry,
    string Patrons,string Price,string Raining,string Reservation,string Type,
    string WaitEstimate,bool WillWait)[] {
    ("Yes","No","No","Yes","Some","$$$","No","Yes","French","0-10",  true),
    ("Yes","No","No","Yes","Full","$",  "No","No", "Thai",  "30-60", true),
    ("No", "Yes","No","No", "Some","$", "No","No", "Burger","0-10",  false),
    ("Yes","No","Yes","Yes","Full","$", "Yes","No","Thai",  "10-30", true),
    ("Yes","No","Yes","No", "Full","$$$","No","Yes","French",">60",  false),
    ("No", "Yes","No","Yes","Some","$$","Yes","Yes","Italian","0-10",true),
    ("No", "Yes","No","No", "None","$", "Yes","No", "Burger","0-10", false),
    ("No", "No","No","Yes","Some","$$","Yes","Yes","Thai",  "0-10",  true),
    ("No", "Yes","Yes","No", "Full","$", "Yes","No", "Burger","10-30",false),
    ("Yes","Yes","Yes","Yes","Full","$$$","No","Yes","Italian","10-30",false),
    ("No", "No","No","No", "None","$", "No","No", "Thai",  "0-10",  false),
    ("Yes","Yes","Yes","Yes","Full","$", "No","No", "Burger","30-60",true),
};

// Conversion en dictionnaires { attribut -> valeur }.
List<Dictionary<string,string>> EXAMPLES = RAW_EXAMPLES
    .Select(r => {
        var d = new Dictionary<string,string>();
        d["Alternate"]=r.Alternate; d["Bar"]=r.Bar; d["Fri/Sat"]=r.FriSat;
        d["Hungry"]=r.Hungry; d["Patrons"]=r.Patrons; d["Price"]=r.Price;
        d["Raining"]=r.Raining; d["Reservation"]=r.Reservation; d["Type"]=r.Type;
        d["WaitEstimate"]=r.WaitEstimate; d["WillWait"]=r.WillWait?"Yes":"No";
        return d;
    }).ToList();

int nPos = EXAMPLES.Count(e => e["WillWait"]=="Yes");
Console.WriteLine($"Domaine : {ATTRIBUTES.Length} attributs");
Console.WriteLine($"Exemples : {EXAMPLES.Count} ({nPos} positifs, {EXAMPLES.Count-nPos} négatifs)");

Domaine : 10 attributs
Exemples : 12 (6 positifs, 6 négatifs)

2. Représentation des hypothèses et consistance

Consistance

Une hypothèse est consistante avec un ensemble d’exemples si elle produit la bonne étiquette pour chacun : couvrir les positifs, ne pas couvrir les négatifs.

// Une hypothèse = tableau de 10 contraintes (string). null = aucune valeur; "?" = joker.
using Hypothesis = string[];

// Hypothèses extrêmes.
string[] G0 = ATTRIBUTES.Select(_ => "?").ToArray();   // la plus générale
string[] S0 = ATTRIBUTES.Select(_ => (string)null).ToArray(); // la plus spécifique

// Une hypothèse couvre un exemple si chaque contrainte non-"?" est satisfaite.
bool Covers(string[] h, Dictionary<string,string> example) {
    for (int i = 0; i < ATTRIBUTES.Length; i++) {
        if (h[i] == null) return false;            // S0 ne couvre rien
        if (h[i] != "?" && h[i] != example[ATTRIBUTES[i]]) return false;
    }
    return true;
}

// Compte les erreurs d'une hypothèse : (faux positifs, faux négatifs).
(int fp, int fn) CountErrors(string[] h, List<Dictionary<string,string>> examples) {
    int fp = 0, fn = 0;
    foreach (var ex in examples) {
        bool pred = Covers(h, ex);
        bool actual = ex["WillWait"]=="Yes";
        if (pred && !actual) fp++;
        if (!pred && actual) fn++;
    }
    return (fp, fn);
}

bool IsConsistent(string[] h, List<Dictionary<string,string>> examples) {
    var (fp, fn) = CountErrors(h, examples);
    return fp == 0 && fn == 0;
}

string HStr(string[] h) => "(" + string.Join(", ", h.Select(v => v ?? "∅")) + ")";

Console.WriteLine($"G0 (plus générale) : {HStr(G0)}");
Console.WriteLine($"  Couvre exemple 1 : {Covers(G0, EXAMPLES[0])}");
var (fp0, fn0) = CountErrors(G0, EXAMPLES);
Console.WriteLine($"  Faux positifs / Faux négatifs : ({fp0}, {fn0})");
Console.WriteLine($"  Consistante : {IsConsistent(G0, EXAMPLES)}");
Console.WriteLine();
Console.WriteLine($"S0 (plus spécifique) : {HStr(S0)}");
Console.WriteLine($"  Couvre exemple 1 : {Covers(S0, EXAMPLES[0])}");

G0 (plus générale) : (?, ?, ?, ?, ?, ?, ?, ?, ?, ?)
  Couvre exemple 1 : True
  Faux positifs / Faux négatifs : (6, 0)
  Consistante : False

S0 (plus spécifique) : (∅, ∅, ∅, ∅, ∅, ∅, ∅, ∅, ∅, ∅)
  Couvre exemple 1 : False

3. Généralisation et spécialisation

Hiérarchie de généralisation

Deux opérations asymétriques : - Généraliser (pour un faux négatif) : relâcher une contrainte spécifique → "?". - Spécialiser (pour un faux positif) : resserrer une contrainte "?" vers une valeur spécifique.

// h1 est-elle plus générale que h2 ? (h1 >= h2)
bool IsMoreGeneralThan(string[] h1, string[] h2) {
    for (int i = 0; i < ATTRIBUTES.Length; i++) {
        if (h1[i] != "?" && h1[i] != h2[i]) return false;
    }
    return true;
}
bool IsMoreSpecificThan(string[] h1, string[] h2) => IsMoreGeneralThan(h2, h1);

// Généralise h pour qu'elle couvre ex (relâche les contraintes contradictoires).
string[] GeneralizeFor(string[] h, Dictionary<string,string> ex) {
    var result = (string[])h.Clone();
    for (int i = 0; i < ATTRIBUTES.Length; i++) {
        if (result[i] == null) result[i] = ex[ATTRIBUTES[i]];       // S0 -> valeur exacte
        else if (result[i] != "?" && result[i] != ex[ATTRIBUTES[i]]) result[i] = "?";
    }
    return result;
}

// Énumère toutes les spécialisations de h qui ne couvrent plus ex
// (resserre un "?" vers chaque valeur possible SAUF celle de ex).
List<string[]> SpecializeAgainst(string[] h, Dictionary<string,string> ex,
                                  Dictionary<string,string[]> attrVals) {
    var specs = new List<string[]>();
    for (int i = 0; i < ATTRIBUTES.Length; i++) {
        if (h[i] == "?") {
            foreach (var val in attrVals[ATTRIBUTES[i]]) {
                if (val == ex[ATTRIBUTES[i]]) continue;  // on exclut la valeur fautive
                var spec = (string[])h.Clone();
                spec[i] = val;
                specs.Add(spec);
            }
        }
    }
    return specs;
}

var h1 = new string[]{"Yes","No","No","Yes","Full","$","No","No","Thai","30-60"};
Console.WriteLine($"Hypothèse initiale : {HStr(h1)}");
Console.WriteLine($"Couvre exemple 2 (positif) : {Covers(h1, EXAMPLES[1])}");
Console.WriteLine();
var g1 = GeneralizeFor(h1, EXAMPLES[0]);
Console.WriteLine($"Après généralisation pour ex1 : {HStr(g1)}");

Hypothèse initiale : (Yes, No, No, Yes, Full, $, No, No, Thai, 30-60)
Couvre exemple 2 (positif) : True

Après généralisation pour ex1 : (Yes, No, No, Yes, ?, ?, No, ?, ?, ?)

4. Algorithme Current-Best-Hypothesis (CBH)

Pseudo-code (AIMA 19.2)

CBH maintient une seule hypothèse h et l’ajuste incrémentalement à chaque exemple : - Faux négatif (positif non couvert) → généraliser h. - Faux positif (négatif couvert) → spécialiser h (première spécialisation consistante). - Sinon → conserver.

Si aucune spécialisation consistante n’existe → backtrack (échec).

// CBH (AIMA Figure 19.2). Retourne (hypothèse, trace).
(string[] h, List<(int step, bool label, string action, string[] hyp)> trace)
    CurrentBestHypothesis(List<Dictionary<string,string>> examples) {

    var trace = new List<(int,bool,string,string[])>();
    var first = examples[0];
    string[] h;
    if (first["WillWait"]=="Yes")
        h = ATTRIBUTES.Select(a => first[a]).ToArray();   // hypothèse exacte
    else
        h = (string[])G0.Clone();

    var seen = new List<Dictionary<string,string>>{ first };
    trace.Add((0, first["WillWait"]=="Yes", "init", h));

    for (int idx = 1; idx < examples.Count; idx++) {
        var ex = examples[idx];
        bool covers = Covers(h, ex);
        bool label = ex["WillWait"]=="Yes";
        string action = "keep (consistent)";

        if (label && !covers) {
            // Faux négatif -> généraliser.
            h = GeneralizeFor(h, ex);
            action = IsConsistent(h, seen.Append(ex).ToList()) ? "generalize" : "generalize (INCONSISTANT)";
        } else if (!label && covers) {
            // Faux positif -> spécialiser (première consistante).
            var specs = SpecializeAgainst(h, ex, ATTRIBUTE_VALUES);
            bool found = false;
            foreach (var spec in specs) {
                if (IsConsistent(spec, seen)) { h = spec; found = true; break; }
            }
            action = found ? "specialize" : "BACKTRACK (no valid specialization)";
        } else {
            action = "keep (consistent)";
        }
        seen.Add(ex);
        trace.Add((idx, label, action, h));
    }
    return (h, trace);
}

var (cbhResult, cbhTrace) = CurrentBestHypothesis(EXAMPLES);
Console.WriteLine("Trace CBH :");
Console.WriteLine($"{"Step",4} | {"Label",5} | {"Action",-25} | Hypothèse");
Console.WriteLine(new string('-', 80));
foreach (var (step, label, action, hyp) in cbhTrace) {
    Console.WriteLine($"{step,4} | {(label?"+":"-"),5} | {action,-25} | {HStr(hyp).Substring(0, Math.Min(45,HStr(hyp).Length))}");
}
var (fp, fn) = CountErrors(cbhResult, EXAMPLES);
Console.WriteLine($"\nHypothèse finale CBH : {HStr(cbhResult)}");
Console.WriteLine($"Faux positifs : {fp}, Faux négatifs : {fn}");
Console.WriteLine($"Consistante : {IsConsistent(cbhResult, EXAMPLES)}");

Trace CBH :
Step | Label | Action                    | Hypothèse
--------------------------------------------------------------------------------
   0 |     + | init                      | (Yes, No, No, Yes, Some, $$$, No, Yes, French
   1 |     + | generalize                | (Yes, No, No, Yes, ?, ?, No, ?, ?, ?)
   2 |     - | keep (consistent)         | (Yes, No, No, Yes, ?, ?, No, ?, ?, ?)
   3 |     + | generalize                | (Yes, No, ?, Yes, ?, ?, ?, ?, ?, ?)
   4 |     - | keep (consistent)         | (Yes, No, ?, Yes, ?, ?, ?, ?, ?, ?)
   5 |     + | generalize                | (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)
   6 |     - | keep (consistent)         | (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)
   7 |     + | keep (consistent)         | (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)
   8 |     - | keep (consistent)         | (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)
   9 |     - | BACKTRACK (no valid specialization) | (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)
  10 |     - | keep (consistent)         | (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)
  11 |     + | keep (consistent)         | (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)

Hypothèse finale CBH : (?, ?, ?, Yes, ?, ?, ?, ?, ?, ?)
Faux positifs : 1, Faux négatifs : 0
Consistante : False

5. Algorithme Candidate Elimination (Version Space)

Candidate Elimination maintient deux ensembles : - G (ensemble des frontières générales), - S (ensemble des frontières spécifiques),

et ajuste les deux à chaque exemple. La version space est l’ensemble des hypothèses comprises entre S et G.

// Candidate Elimination (AIMA Figure 19.3). Retourne (G_set, S_set, trace).
// Les hypothèses sont comparées/hachées via leur représentation string.
(string Gkey, string Skey, List<(int ex,bool label,int g,int s)> trace)
    CandidateElimination(List<Dictionary<string,string>> examples) {

    // On stocke G et S comme HashSet de string (sérialisation des hypothèses).
    string Ser(string[] h) => string.Join("|", h.Select(v => v ?? "∅"));
    string[] Deser(string s) => s.Split('|').Select(v => v=="∅"?null:v).ToArray();

    var G = new HashSet<string>{ Ser(G0) };
    var S = new HashSet<string>{ Ser(S0) };
    var trace = new List<(int,bool,int,int)>();

    for (int idx = 0; idx < examples.Count; idx++) {
        var ex = examples[idx];
        bool label = ex["WillWait"]=="Yes";

        if (label) {
            // --- Exemple POSITIF ---
            // S : généraliser chaque s qui ne couvre pas ex.
            var Snew = new HashSet<string>();
            foreach (var sk in S) {
                var s = Deser(sk);
                if (!Covers(s, ex)) s = GeneralizeFor(s, ex);
                Snew.Add(Ser(s));
            }
            // G : retirer ceux qui ne couvrent pas ex (incompatibles avec un positif).
            S = Snew;
            G.RemoveWhere(gk => !Covers(Deser(gk), ex));
        } else {
            // --- Exemple NÉGATIF ---
            // G : spécialiser chaque g qui couvre ex (faux positif).
            var Gnew = new HashSet<string>();
            foreach (var gk in G) {
                var g = Deser(gk);
                if (!Covers(g, ex)) { Gnew.Add(gk); continue; }  // déjà OK
                foreach (var spec in SpecializeAgainst(g, ex, ATTRIBUTE_VALUES)) {
                    // ne garder que les spécialisations plus spécifiques qu'au moins un g
                    if (G.Any(gk2 => IsMoreGeneralThan(Deser(gk2), spec)))
                        Gnew.Add(Ser(spec));
                }
            }
            // S : retirer ceux qui couvrent le négatif (incompatibles).
            G = Gnew;
            S.RemoveWhere(sk => Covers(Deser(sk), ex));
        }
        trace.Add((idx, label, G.Count, S.Count));
    }
    return (Ser(G0), Ser(S0), trace);
}

var (_, _, ceTrace) = CandidateElimination(EXAMPLES);
Console.WriteLine("Trace Version Space :");
Console.WriteLine($" {"Ex",2} | {"Label",5} | {"|G|",3} | {"|S|",3}");
Console.WriteLine(new string('-', 25));
foreach (var (ex, label, g, s) in ceTrace)
    Console.WriteLine($" {ex,2} | {(label?"+":"-"),5} | {g,3} | {s,3}");

Trace Version Space :
 Ex | Label | |G| | |S|
-------------------------
  0 |     + |   1 |   1
  1 |     + |   1 |   1
  2 |     - |  16 |   1
  3 |     + |   8 |   1
  4 |     - |  63 |   1
  5 |     + |   2 |   1
  6 |     - |  16 |   1
  7 |     + |   7 |   1
  8 |     - |   7 |   1
  9 |     - |  20 |   0
 10 |     - |  20 |   0
 11 |     + |   4 |   0

Interprétation : Version Space sur 12 exemples

Le VS s’effondre (|G|=0 ou |S|=0) avant la fin : aucune clause conjonctive unique n’est consistante avec les 12 exemples. C’est la limite fondamentale des hypothèses conjonctives pures — AIMA le souligne : le domaine restaurant réel nécessite soit une disjonction, soit une représentation plus riche. CBH, lui, garde une hypothèse (faute de mieux) mais reste inconsistante.

6. Comparaison CBH vs Version Space

Pour comparer les stratégies là où le VS est encore large (après 4 exemples, |G|=8), on entraîne sur les 4 premiers et on teste sur les 8 suivants.

// Comparaison : entraîner sur N_TRAIN=4, tester sur le reste.
int N_TRAIN = 4;
var (_, _, _) = CandidateElimination(EXAMPLES.Take(N_TRAIN).ToList());

// Reconstruction de G, S pour N_TRAIN=4 (Version Space encore large).
string Ser(string[] h) => string.Join("|", h.Select(v => v ?? "∅"));
string[] Deser(string s) => s.Split('|').Select(v => v=="∅"?null:v).ToArray();

// Version Space après 4 exemples (on recalcule G et S explicitement).
var G = new HashSet<string>{ Ser(G0) };
var S = new HashSet<string>{ Ser(S0) };
for (int idx = 0; idx < N_TRAIN; idx++) {
    var ex = EXAMPLES[idx];
    bool label = ex["WillWait"]=="Yes";
    if (label) {
        var Snew = new HashSet<string>();
        foreach (var sk in S) { var s = Deser(sk); if (!Covers(s,ex)) s = GeneralizeFor(s,ex); Snew.Add(Ser(s)); }
        S = Snew; G.RemoveWhere(gk => !Covers(Deser(gk), ex));
    } else {
        var Gnew = new HashSet<string>();
        foreach (var gk in G) { var g = Deser(gk); if (!Covers(g,ex)) { Gnew.Add(gk); continue; }
            foreach (var spec in SpecializeAgainst(g,ex,ATTRIBUTE_VALUES))
                if (G.Any(gk2 => IsMoreGeneralThan(Deser(gk2), spec))) Gnew.Add(Ser(spec)); }
        G = Gnew; S.RemoveWhere(sk => Covers(Deser(sk), ex));
    }
}

// CBH après 4 exemples.
var (cbh4, _) = CurrentBestHypothesis(EXAMPLES.Take(N_TRAIN).ToList());

// Accuracy sur le test set (exemples 4..11).
var testSet = EXAMPLES.Skip(N_TRAIN).ToList();
// Prédiction CBH : Covers(h, ex).
int cbhCorrect = testSet.Count(ex => Covers(cbh4, ex) == (ex["WillWait"]=="Yes"));
// Prédiction VS : vote majoritaire (toutes hypothèses entre S et G).
//   Approximation : si tous les s couvrent et aucun g ne couvre -> prédictible,
//   sinon : majorité sur un échantillon (hypothèses S et G directement).
int vsCorrect = 0;
foreach (var ex in testSet) {
    var sCov = S.Count(sk => Covers(Deser(sk), ex));
    var gCov = G.Count(gk => Covers(Deser(gk), ex));
    bool pred = (sCov + gCov) * 2 > (S.Count + G.Count);  // majorité
    if (pred == (ex["WillWait"]=="Yes")) vsCorrect++;
}

Console.WriteLine($"Après {N_TRAIN} exemples d'entraînement : |G|={G.Count}, |S|={S.Count}");
Console.WriteLine($"Test set : {testSet.Count} exemples");
Console.WriteLine($"  CBH accuracy            : {cbhCorrect}/{testSet.Count} = {100.0*cbhCorrect/testSet.Count:F1}%");
Console.WriteLine($"  Version Space (vote) accuracy : {vsCorrect}/{testSet.Count} = {100.0*vsCorrect/testSet.Count:F1}%");
Console.WriteLine();
Console.WriteLine("Hypothèse CBH : " + HStr(cbh4));
Console.WriteLine($"Frontières S ({S.Count}) : " + string.Join(" ; ", S.Take(3).Select(s => HStr(Deser(s)))));
Console.WriteLine($"Frontières G ({G.Count}) : " + string.Join(" ; ", G.Take(3).Select(g => HStr(Deser(g)))));

Après 4 exemples d'entraînement : |G|=8, |S|=1
Test set : 8 exemples
  CBH accuracy            : 5/8 = 62,5%
  Version Space (vote) accuracy : 4/8 = 50,0%

Hypothèse CBH : (Yes, No, ?, Yes, ?, ?, ?, ?, ?, ?)
Frontières S (1) : (Yes, No, ?, Yes, ?, ?, ?, ?, ?, ?)
Frontières G (8) : (Yes, ?, ?, ?, ?, ?, ?, ?, ?, ?) ; (?, No, ?, ?, ?, ?, ?, ?, ?, ?) ; (?, ?, Yes, ?, ?, ?, ?, ?, ?, ?)

6bis. Implémentation de référence : aima-python (pont PythonNet)

Le jumeau Python de cette série (section 9) confronte son CBH from-scratch à l’implémentation de référence d’aima-python (knowledge.py, Figure 19.2, vendordée dans reference/aima_knowledge.py). Cette section fait la même chose depuis C# : un pont PythonNet (.NET → CPython) invoque le même module de référence sur les mêmes 12 exemples, avec la même graine (42) et la même hypothèse initiale (le premier exemple positif) — la comparaison est reproductible entre les deux jumeaux.

Le pont est un plus, jamais un remplacement : les sections 4-6 gardent le CBH et le Candidate Elimination codés à la main (c’est le sujet du notebook) ; la référence externe joue le rôle d’arbitre, exactement comme la section 9 du jumeau Python.

#r "nuget: pythonnet, 3.0.5"
using Python.Runtime;

// Pont .NET -> CPython -> aima_knowledge (aima-python knowledge.py, Fig 19.2)
// -- la MEME implementation de reference que le jumeau Python (section 9).
// PYTHONNET_PYDLL (env) designe le CPython de la machine d'execution.
Runtime.PythonDLL = Environment.GetEnvironmentVariable("PYTHONNET_PYDLL")
    ?? @"C:\Python313\python313.dll";
PythonEngine.Initialize();
Console.WriteLine($"Runtime Python : {PythonEngine.Version}");

using (Py.GIL())
{
    // Reproduit la section 9 du jumeau Python : graine fixee (la recherche
    // generalizations/specializations de la reference est stochastique),
    // memes 12 exemples convertis au format AIMA (cle GOAL booleenne),
    // hypothese initiale = premier exemple positif.
    dynamic random = Py.Import("random");
    random.seed(42);
    dynamic sysMod = Py.Import("sys");
    sysMod.path.insert(0, "reference");
    dynamic aima = Py.Import("aima_knowledge");
    dynamic json = Py.Import("json");

    var aimaPayload = EXAMPLES.Select(e => {
        var d = e.Where(kv => kv.Key != "WillWait").ToDictionary(kv => kv.Key, kv => (object)kv.Value);
        d["GOAL"] = e["WillWait"] == "Yes";
        return d;
    });
    dynamic aimaExamples = json.loads(System.Text.Json.JsonSerializer.Serialize(aimaPayload));

    var firstPos = EXAMPLES.First(e => e["WillWait"] == "Yes");
    var h0 = firstPos.Where(kv => kv.Key != "WillWait").ToDictionary(kv => kv.Key, kv => kv.Value);
    dynamic initialH = json.loads(System.Text.Json.JsonSerializer.Serialize(new[] { h0 }));

    var watch = System.Diagnostics.Stopwatch.StartNew();
    dynamic h = aima.current_best_learning(aimaExamples, initialH);
    watch.Stop();

    int nDisj = 0; int i = 1;
    foreach (dynamic d in h) { nDisj++; Console.WriteLine($"  D{i++}: {d}"); }
    Console.WriteLine($"Hypothese trouvee : {nDisj} disjonction(s) en {watch.Elapsed.TotalSeconds:F2}s");

    int correct = 0;
    foreach (dynamic e in aimaExamples)
        if ((bool)aima.guess_value(e, h) == (bool)e["GOAL"]) correct++;
    Console.WriteLine($"\nAccuracy de la reference sur les 12 exemples : {correct}/{EXAMPLES.Count}");
}
Console.WriteLine("PONT .NET -> aima-python : OK");

Installed Packages

• pythonnet, 3.0.5

Runtime Python : 3.11.9 (tags/v3.11.9:de54cf5, Apr  2 2024, 10:12:12) [MSC v.1938 64 bit (AMD64)]
  D1: {'Alternate': 'Yes', 'Bar': 'No', 'Fri/Sat': 'No', 'Hungry': 'Yes'}
  D2: {'Alternate': 'Yes', 'Fri/Sat': 'Yes', 'Hungry': 'Yes', 'Price': '$', 'Raining': 'Yes', 'Type': 'Thai', 'WaitEstimate': '10-30'}
  D3: {'Alternate': 'No', 'Hungry': 'Yes', 'Patrons': 'Some', 'Raining': 'Yes', 'Reservation': 'Yes', 'Type': 'Italian', 'WaitEstimate': '0-10'}
  D4: {'Alternate': 'No', 'Fri/Sat': 'No', 'Patrons': 'Some', 'Raining': 'Yes', 'Reservation': 'Yes'}
  D5: {'Alternate': 'Yes', 'Bar': 'Yes', 'Patrons': 'Full', 'Type': 'Burger', 'WaitEstimate': '30-60'}
Hypothese trouvee : 5 disjonction(s) en 0,02s

Accuracy de la reference sur les 12 exemples : 12/12
PONT .NET -> aima-python : OK

Exercice : Variantes du domaine restaurant

Expérimentez avec le domaine pour comprendre la robustesse des deux algorithmes.

// EXERCICE : Modifier les labels pour rendre le VS consistant sur 12 exemples
public string[] FindConsistentSubspace(List<Dictionary<string,string>> examples) {
    // TODO etudiant : trouvez un sous-ensemble de 6-8 exemples pour lequel le
    // Version Space converge vers une frontière unique (|G|=|S|=1).
    // Indice : utilisez CandidateElimination sur des sous-ensembles et observez |G|, |S|.
    // Etape 1 : itérez sur les sous-ensembles (combinaisons C(12,6)).
    // Etape 2 : calculez |G|, |S| finaux pour chacun.
    // Etape 3 : retournez un sous-ensemble avec |G|=|S|=1.
    return null;  // TODO etudiant
}

Console.WriteLine("Exercice à compléter (sous-espace consistant).");

Exercice à compléter (sous-espace consistant).

Exercice 2 : Affinage de la frontière (nettoyage de G et S)

L’implémentation de CandidateElimination (§5) accumule parfois des hypothèses redondantes dans les frontières : un \(g \in G\) strictement moins général qu’un autre \(g' \in G\) n’apporte rien (\(g'\) couvre strictement plus, donc \(g\) est sous-sumée). Symétriquement pour \(S\). Un nettoyage systématique après chaque exemple maintient les frontières minimales.

Implémentez PruneFrontier(G, S) qui retire de \(G\) toute hypothèse strictement moins générale qu’une autre de \(G\), et de \(S\) toute hypothèse strictement plus spécifique qu’une autre de \(S\).

Indices : - Étape 1 : pour chaque paire \((g, g')\) de \(G\), si IsMoreGeneralThan(g', g) est vrai et IsMoreGeneralThan(g, g') est faux (inégalité stricte \(g' \sqsupset g\)), alors \(g\) est redondante → la retirer. - Étape 2 : opération symétrique sur \(S\) avec IsMoreSpecificThan. - Étape 3 : vérifier que \(|G|\) et \(|S|\) ne font que diminuer après chaque appel (invariant de minimalité), et que le pouvoir prédictif (cellule §6) est inchangé.

// EXERCICE 2 : Affinage de la frontiere — retirer les hypotheses redondantes de G et S.
// (Reprend Ser/Deser definies dans les cellules precedentes.)
public void PruneFrontier(HashSet<string> Gset, HashSet<string> Sset) {
    // TODO etudiant : nettoyer G (retirer tout g strictement moins general qu'un autre g') puis S.
    // Indice : IsMoreGeneralThan(g1, g2) == true signifie g1 >= g2.
    //          g est redondante dans G s'il existe g' dans G avec g' > g (strictement plus general).
    // Etape 1 : construire la liste des hypotheses a retirer de G (g tq existe g' != g, g' >= g et !(g >= g')).
    // Etape 2 : retirer de G. Puis operer symetriquement sur S (s redondante s'il existe s' < s strictement).
    // Etape 3 : verifier que |G| et |S| ne font que decroitre (invariant de minimalite).
}

// Test sur le VS a N_TRAIN=4 (G a 8 elements, certains redondants).
var G_prune = new HashSet<string>(G);
var S_prune = new HashSet<string>(S);
int gBefore = G_prune.Count, sBefore = S_prune.Count;
PruneFrontier(G_prune, S_prune);
Console.WriteLine($"Exercice 2 a completer : |G| {gBefore} -> {G_prune.Count}, |S| {sBefore} -> {S_prune.Count}");

Exercice 2 a completer : |G| 8 -> 8, |S| 1 -> 1

Exercice 3 : Prédiction par vote majoritaire (Version Space complet)

La comparaison §6 approxime le vote en ne regardant que les frontières \(S\) et \(G\). Ici, on veut le vote exact : énumérer (ou échantillonner) les hypothèses \(h\) du Version Space — celles telles que tout \(s \in S\) est plus spécifique que \(h\) et tout \(g \in G\) est plus général que \(h\) — et faire voter chacune sur l’exemple test.

C’est la capacité distinctive du Version Space : il ne livre pas une prédiction unique mais une distribution d’opinions, dont la majorité l’emporte. CBH n’a qu’une voix.

Implémentez PredictByMajorityVote(G, S, ex) retournant "Yes" ou "No".

Indices : - Étape 1 : pour un VS petit (\(|G|, |S|\) modestes), énumérer exhaustivement les \(h\) obtenues en relâchant des contraintes de \(s\) (le plus spécifique) tout en restant sous \(g\) (le plus général). - Étape 2 : compter voteYes = nombre de \(h\) qui couvrent ex, voteNo = nombre qui ne le couvrent pas. - Étape 3 : retourner "Yes" si voteYes >= voteNo, "No" sinon. - Étape 4 (si l’espace est grand) : borner en échantillonnant un sous-ensemble aléatoire fixé d’hypothèses (ex. 200) plutôt qu’en énumérant tout — l’étudiante documente alors le tirage.

// EXERCICE 3 : Prediction par vote majoritaire sur le Version Space complet.
// Contrairement a la cellule 13 (§6) qui n'utilise que les frontieres S et G,
// on enumere ici les hypotheses h du VS (s <= h <= g) et on fait voter chacune.
public string PredictByMajorityVote(HashSet<string> Gset, HashSet<string> Sset,
                                    Dictionary<string,string> ex) {
    // TODO etudiant : enumerer/echantillonner les hypotheses du VS et voter pour ex.
    // Indice : une hypothese h du VS verifie : pour tout s dans S, IsMoreGeneralThan(h, s) ;
    //          et pour tout g dans G, IsMoreGeneralThan(g, h).
    // Etape 1 : generer des candidats h (relacher des contraintes de s, bornees par g).
    // Etape 2 : compter voteYes = #{h : Covers(h, ex)}, voteNo = #{h : !Covers(h, ex)}.
    // Etape 3 : retourner "Yes" si voteYes >= voteNo, sinon "No".
    // (Etape 4 si grand : echantillonner <=200 hypotheses au lieu d'enumerer exhaustivement.)
    return null;  // TODO etudiant
}

// Test sur un exemple du test set (ex. exemple 5, label reel Yes).
var ex5 = EXAMPLES[5];
string vote5 = PredictByMajorityVote(G, S, ex5);
Console.WriteLine($"Exercice 3 a completer : vote VS pour exemple 5 (label reel {ex5["WillWait"]}) = {vote5 ?? "(a completer)"}");

Exercice 3 a completer : vote VS pour exemple 5 (label reel Yes) = (a completer)

Bilan

Ce notebook a présenté l’apprentissage logique from-scratch en C#, jumeau du notebook Python. Points clés :

1. Hypothèses conjonctives : tuples de contraintes ("?" / valeur / null).
2. Couverture & consistance : Covers(h, ex), IsConsistent(h, set).
3. Généralisation / spécialisation : deux opérations asymétriques sur les contraintes.
4. CBH : une seule hypothèse ajustée incrémentalement (avec backtrack possible).
5. Candidate Elimination : version space bornée par G (général) et S (spécifique).
6. Effondrement du VS sur les 12 exemples : limite des hypothèses conjonctives pures.

Parité : ce notebook C# est le jumeau de SL-1-LogicalLearning.ipynb. Les deux implémentent les mêmes algorithmes from-scratch (pas de lib ML), pour enseigner les internes. Cf marathon parité (#4956), EPIC #3801 (Prong B).

Exercices supplémentaires

Exercice 2 : Affinage de la frontière

Ajoutez une opération de nettoyage dans Candidate Elimination : retirer de G tout g moins général qu’un autre g' de G (idem pour S). Vérifiez que les frontières restent minimales après chaque exemple.

Exercice 3 : Prédiction par vote majoritaire

Étendez la comparaison §6 : pour chaque exemple de test, énumérez toutes les hypothèses entre S et G (pas seulement les frontières) et votez à la majorité.

Références

• Russell & Norvig, AIMA (3e éd.), ch. 19.
• Mitchell, T. M. Machine Learning (1997), ch. 2.
• Notebook Python : SL-1-LogicalLearning.ipynb.
• Marathon parité : #4956.