SL-10 — Apprentissage Actif d’Automates (L* d’Angluin) — twin C# .NET

Navigation : Index | twin Python | << SL-9 | SL-11 >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Distinguer apprentissage passif (exemples imposes, SL-1) et actif (l’apprenant pose des questions) 2. Formaliser le modèle MAT (Minimally Adequate Teacher) : requêtes d’appartenance et d’equivalence 3. Implementer la table d’observation d’Angluin (fermeture, consistance) 4. Derouler l’algorithme L* complet et apprendre un DFA inconnu 5. Relier la garantie de minimalite au theoreme de Myhill-Nerode 6. Mesurer ce qui se passe quand l’oracle d’equivalence devient approximatif (echantillonnage, PAC)

Prerequis

  • SL-1 (espaces d’hypotheses, apprentissage passif)
  • Notions d’automates finis déterministes (rappel complet en section 1)
  • Twin C# .NET 9 (BCL seule, 0 NuGet) – Prong B from-scratch (cf #4956, #3801)

Duree estimee : 60 minutes

Hommage — Stearns et la théorie des automates : LL(k), régularité, hiérarchies

Richard E. Stearns (1936–2026), co-lauréat du prix Turing 1993 pour avoir fondé la théorie de la complexité computationnelle, est aussi un artisan central de la théorie des langages formels que ce notebook met en pratique :

  • Lewis & Stearns, « Syntax-Directed Transduction » (JACM, 1968) a défini les grammaires LL(k) — la famille de parseurs descendants que la bibliographie ACM présente comme la première méthode d’analyse que les étudiants rencontrent ; les propriétés théoriques ont été établies avec Knuth puis Rosenkrantz & Stearns (1970).
  • Stearns, « A Regularity Test for Pushdown Machines » (1967) : si un langage régulier possède un DPDA de taille n, il possède un DFA de taille au plus n(n(n^O(n))) — un écart super-exponentiel mais calculable, resserré depuis par Valiant (2(2O(n))). C’est l’un des rares exemples où l’écart entre deux modèles de machines dépasse l’exponentiel sans devenir indécidable.
  • Stearns a aussi montré que les langages hors-contexte se reconnaissent en espace O(log² n) et établi une hiérarchie en espace — le pendant spatial de la hiérarchie en temps de Hartmanis–Stearns (1965).

Hommage complet (hiérarchie de Hartmanis–Stearns, série Complexity/) : issue #15949 ; autres résonances — paradoxe d’Arrow 1959 et jeux répétés à information incomplète (voir GameTheory/SocialChoice/ et GameTheory/game_theory_lean/README.md).

Sources : bibliographie officielle du prix Turing ACM ; blog Computational Complexity (Gasarch, 04/09/2026) ; CACM, In Memoriam.

1. Du passif a l’actif : le modèle MAT

Tous les algorithmes de la serie jusqu’ici sont passifs : l’apprenant recoit un jeu d’exemples qu’il n’a pas choisi (les 12 restaurants de SL-1, les triples du KG de SL-8) et doit s’en contenter. Or certains concepts sont exponentiellement plus faciles a apprendre si l’apprenant peut poser des questions.

Dana Angluin (1987) formalise cela avec le MAT (Minimally Adequate Teacher), un professeur qui repond a exactement deux types de requêtes :

Requête Question Reponse
Appartenance (MQ) « le mot \(w\) est-il dans le langage cible \(L\) ? » Oui / Non
Equivalence (EQ) « mon hypothese \(H\) est-elle exactement \(L\) ? » Oui, ou un contre-exemple \(w \in H \triangle L\)

La cible est ici un langage regulier : un ensemble de mots reconnu par un automate fini déterministe (DFA). C’est un objet pleinement symbolique — etats, transitions, etats acceptants — et le theoreme central d’Angluin est remarquable :

Theoreme (Angluin 1987). L* apprend le DFA minimal de tout langage regulier avec un nombre de requêtes polynomial en le nombre d’etats \(n\) du DFA minimal et la longueur \(m\) du plus long contre-exemple.

A titre de comparaison, apprendre un DFA passivement (trouver le plus petit DFA consistant avec un echantillon donne) est NP-difficile (Gold 1978). Le droit de poser des questions change la classe de complexite du problème.

Commencons par la cible : un DFA jouet que L* devra decouvrir sans jamais regarder sa structure, uniquement en l’interrogeant.

// Un DFA = (etats, alphabet, transitions, etat initial, etats acceptants)
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Dfa
{
    public HashSet<string> States { get; set; }
    public List<char> Alphabet { get; set; }
    public Dictionary<(string, char), string> Delta { get; set; }
    public string Start { get; set; }
    public HashSet<string> Accepting { get; set; }
    public Dfa(IEnumerable<string> states, IEnumerable<char> alphabet,
               IEnumerable<((string, char), string)> delta, string start, IEnumerable<string> accepting)
    {
        States = states.ToHashSet();
        Alphabet = alphabet.ToList();
        Delta = new Dictionary<(string, char), string>();
        foreach (var (k, v) in delta) Delta[k] = v;
        Start = start;
        Accepting = accepting.ToHashSet();
    }
    public bool Accepts(string word)
    {
        var q = Start;
        foreach (var ch in word) q = Delta[(q, ch)];
        return Accepting.Contains(q);
    }
    public int StateCount => States.Count;
    public override string ToString() => $"Dfa({States.Count} etats, {Accepting.Count} acceptants)";
}

// Langage cible (cache pour L*) : mots sur {a, b} avec un nombre PAIR de 'a'
// ET un nombre PAIR de 'b'. Etat = (parite des a, parite des b) -> 4 etats.
List<char> ALPHABET = new List<char> { 'a', 'b' };
string[] _states = { "ee", "eo", "oe", "oo" };  // (pair/impair a, pair/impair b)
var _delta = new List<((string, char), string)>();
foreach (var s in _states)
{
    char pa = s[0], pb = s[1];
    _delta.Add(((s, 'a'), (pa == 'e' ? "o" : "e") + pb.ToString()));
    _delta.Add(((s, 'b'), pa.ToString() + (pb == 'e' ? "o" : "e")));
}
Dfa TARGET = new Dfa(_states, ALPHABET, _delta, "ee", new[] { "ee" });

// L'apprenant n'aura acces qu'a cette fonction (la requete d'appartenance) :
bool MembershipQuery(string word) => TARGET.Accepts(word);

// Verification rapide sur quelques mots
Console.WriteLine($"Cible : {TARGET}  (structure invisible pour l'apprenant)");
Console.WriteLine($"{"mot",8} | nb_a | nb_b | dans L ?");
Console.WriteLine(new string('-', 36));
foreach (var w in new[] { "", "a", "b", "ab", "aabb", "abab", "aab", "bbaa", "abba" })
{
    int na = w.Count(c => c == 'a'), nb = w.Count(c => c == 'b');
    Console.WriteLine($"{(w == "" ? "eps" : w),8} | {na,4} | {nb,4} | {(MembershipQuery(w) ? "OUI" : "non")}");
}
Cible : Dfa(4 etats, 1 acceptants)  (structure invisible pour l'apprenant)
     mot | nb_a | nb_b | dans L ?
------------------------------------
     eps |    0 |    0 | OUI
       a |    1 |    0 | non
       b |    0 |    1 | non
      ab |    1 |    1 | non
    aabb |    2 |    2 | OUI
    abab |    2 |    2 | OUI
     aab |    2 |    1 | non
    bbaa |    2 |    2 | OUI
    abba |    2 |    2 | OUI

Pourquoi ce langage ?

Le mot vide est accepte (0 est pair), ab est rejete (1 ‘a’, 1 ‘b’), aabb et abab sont acceptes. Le DFA minimal a exactement 4 etats — le produit des deux parites — et aucune conjonction d’attributs a la SL-1 ne peut le representer : l’appartenance depend d’un compteur modulaire, pas de la presence ou l’absence d’un motif. C’est un concept hors de portee des espaces d’hypotheses de SL-1, et parfaitement dans celui de L*.

L’apprenant ne voit que membership_query : une boite noire mot -> booléen. Tout l’enjeu est de reconstruire la structure (etats, transitions) a partir de reponses oui/non bien choisies.

Schema : le DFA cible (invisible pour l’apprenant)

Le langage cible – nombre pair de a et pair de b – est reconnu par le DFA minimal a 4 etats, un par couple (parite des a, parite des b). C’est cette structure (etats + transitions) que L* doit reconstruire a partir des seules reponses oui/non de l’oracle ; elle lui est cachee. La voici :

stateDiagram-v2
    direction LR
    [*] --> ee
    ee --> oe : a
    ee --> eo : b
    oe --> ee : a
    oe --> oo : b
    eo --> oo : a
    eo --> ee : b
    oo --> eo : a
    oo --> oe : b
    ee : ee (pair a, pair b)
    oe : oe (impair a, pair b)
    eo : eo (pair a, impair b)
    oo : oo (impair a, impair b)
    classDef accept fill:#d1e7dd,stroke:#0f5132,stroke-width:3px,color:#0a3622
    class ee accept

Lecture. L’etat initial ee (pair, pair) est aussi le seul etat acceptant (en vert) : un mot est dans le langage si, en le lisant lettre par lettre, on revient en ee. Chaque a bascule la parite des a (colonne gauche/droite), chaque b bascule celle des b – d’ou la symetrie en damier. Aucune conjonction d’attributs a la SL-1 ne capture ce compteur modulaire : c’est précisément ce qui place ce concept hors de portee de l’apprentissage passif et dans celui de L*.

2. La table d’observation

L* organise ses requêtes d’appartenance dans une table d’observation \((S, E, T)\) :

  • \(S\) : un ensemble de prefixes d’acces (chaque \(s \in S\) est un chemin candidat vers un etat du DFA) ;
  • \(E\) : un ensemble de suffixes distinguants (des « expériences » qui separent les etats) ;
  • \(T(s \cdot e) \in \{0, 1\}\) : la reponse de l’oracle a la requête \(s \cdot e \in L\) ?

La ligne d’un prefixe \(s\) est le vecteur \(row(s) = (T(s \cdot e))_{e \in E}\). L’intuition centrale : deux prefixes qui ont la même ligne menent (provisoirement) au même etat. C’est une approximation finie de la congruence de Myhill-Nerode : \(u \equiv_L v \iff \forall w,\; uw \in L \Leftrightarrow vw \in L\) — ici on ne teste pas tous les suffixes \(w\), seulement ceux de \(E\).

Pour pouvoir construire un DFA a partir de la table, deux proprietes sont requises :

Propriete Definition Si violee…
Fermeture \(\forall s \in S, a \in \Sigma\), \(row(s a)\) est la ligne d’un élément de \(S\) la transition \(row(s) \xrightarrow{a} {?}\) sort de la table : promouvoir \(sa\) dans \(S\)
Consistance \(row(s_1) = row(s_2) \Rightarrow \forall a, row(s_1 a) = row(s_2 a)\) deux etats fusionnes a tort : ajouter le suffixe \(a e\) qui les separe a \(E\) 
public class ObservationTable
{
    public List<char> A { get; set; }
    public Func<string, bool> Mq { get; set; }
    public List<string> S { get; set; } = new List<string> { "" };
    public List<string> E { get; set; } = new List<string> { "" };
    public Dictionary<string, bool> T { get; set; } = new Dictionary<string, bool>();
    public int NMq { get; set; } = 0;

    public ObservationTable(IEnumerable<char> alphabet, Func<string, bool> mq)
    {
        A = alphabet.ToList();
        Mq = mq;
        Fill();
    }

    public bool Ask(string w)
    {
        if (!T.ContainsKey(w)) { T[w] = Mq(w); NMq++; }
        return T[w];
    }

    public void Fill()
    {
        foreach (var s in S.Concat(S.SelectMany(s => A.Select(a => s + a))))
            foreach (var e in E) Ask(s + e);
    }

    // Ligne d'un prefixe = signature textuelle sur les colonnes E (comparable/hashable).
    public string Row(string s) => string.Join("", E.Select(e => Ask(s + e) ? "1" : "0"));

    public string FindUnclosed()
    {
        var rowsS = S.Select(s => Row(s)).ToHashSet();
        foreach (var s in S)
            foreach (var a in A)
                if (!rowsS.Contains(Row(s + a))) return s + a;
        return null;
    }

    public string FindInconsistency()
    {
        for (int i = 0; i < S.Count; i++)
            for (int j = i + 1; j < S.Count; j++)
            {
                if (Row(S[i]) != Row(S[j])) continue;
                foreach (var a in A)
                    foreach (var e in E)
                        if (Ask(S[i] + a + e) != Ask(S[j] + a + e)) return a + e;
            }
        return null;
    }

    public void Show()
    {
        string eps = "eps";
        var cols = E.Select(e => e == "" ? eps : e).ToList();
        int w = Math.Max(6, S.Max(s => s.Length) + 2);
        string Lab(string s) => (s == "" ? eps : s).PadRight(w);
        string RowStr(string s) => string.Join(" ", Row(s).Select(v => (v == '1' ? "1" : "0").PadLeft(4)));
        Console.WriteLine(new string(' ', w) + " | " + string.Join(" ", cols.Select(c => c.PadLeft(4))));
        Console.WriteLine(new string('-', w + 3 + 5 * cols.Count));
        foreach (var s in S) Console.WriteLine(Lab(s) + " | " + RowStr(s));
        Console.WriteLine(new string('-', w + 3 + 5 * cols.Count));
        var inS = S.ToHashSet();
        foreach (var s in S)
            foreach (var a in A)
            {
                var sa = s + a;
                if (inS.Contains(sa)) continue;
                Console.WriteLine(Lab(sa) + " | " + RowStr(sa));
            }
    }
}

// Table initiale : S = {epsilon}, E = {epsilon}
var table = new ObservationTable(ALPHABET, MembershipQuery);
Console.WriteLine("Table initiale (haut : S ; bas : les successeurs S.A) :\n");
table.Show();
var sa0 = table.FindUnclosed();
Console.WriteLine($"\nRequetes MQ posees : {table.NMq}");
Console.WriteLine($"Fermee ? {(sa0 == null ? "oui" : "NON : row(" + sa0 + ") absente de S")}");
Table initiale (haut : S ; bas : les successeurs S.A) :

       |  eps
--------------
eps    |    1
--------------
a      |    0
b      |    0

Requetes MQ posees : 3
Fermee ? NON : row(a) absente de S

Lecture de la table initiale

La ligne de \(\varepsilon\) vaut \((1)\) (le mot vide est dans \(L\)), mais celles de a et b valent \((0)\) : la table n’est pas fermee — l’automate conjecture aurait une transition vers un etat qui n’existe pas encore. Le remede est mecanique : promouvoir le prefixe fautif dans \(S\), ce qui créé l’etat manquant, puis re-remplir la table. L’algorithme L* n’est rien d’autre que la repetition disciplinee de ce geste, plus le traitement des contre-exemples.

3. L’algorithme L*

L*(alphabet, MQ, EQ):
    initialiser la table (S = E = {epsilon})
    repeter:
        tant que la table n'est pas fermee ou pas consistante:
            non fermee      -> promouvoir le prefixe s.a fautif dans S
            non consistante -> ajouter le suffixe a.e separateur a E
        H <- DFA conjecture a partir des lignes de la table
        si EQ(H) repond OUI : retourner H
        sinon (contre-exemple c) : ajouter TOUS les prefixes de c a S

La conjecture se lit directement dans la table : les etats sont les lignes distinctes de \(S\), l’etat initial est \(row(\varepsilon)\), un etat est acceptant si sa première colonne (\(e = \varepsilon\)) vaut 1, et la transition par \(a\) envoie \(row(s)\) sur \(row(sa)\) — la fermeture garantit que cette ligne existe, la consistance qu’elle ne depend pas du representant \(s\) choisi.

Dfa Conjecture(ObservationTable table)
{
    var reps = new Dictionary<string, string>();  // ligne (signature) -> prefixe representant
    foreach (var s in table.S)
        if (!reps.ContainsKey(table.Row(s))) reps[table.Row(s)] = s;
    var delta = new List<((string, char), string)>();
    foreach (var kv in reps)
    {
        var sig = kv.Key; var s = kv.Value;
        foreach (var a in table.A) delta.Add(((sig, a), table.Row(s + a)));
    }
    string start = table.Row("");
    var accepting = reps.Keys.Where(sig => sig[0] == '1').ToList();
    return new Dfa(reps.Keys, table.A, delta, start, accepting);
}

string FindCounterexample(Dfa hyp, Dfa target, IEnumerable<char> alphabet)
{
    var alph = alphabet.ToList();
    var start = (hyp.Start, target.Start);
    var seen = new HashSet<(string, string)>() { start };
    var queue = new Queue<(string w, string qh, string qt)>();
    queue.Enqueue(("", hyp.Start, target.Start));
    while (queue.Count > 0)
    {
        var (w, qh, qt) = queue.Dequeue();
        if (hyp.Accepting.Contains(qh) != target.Accepting.Contains(qt)) return w;
        foreach (var a in alph)
        {
            var nxt = (hyp.Delta[(qh, a)], target.Delta[(qt, a)]);
            if (seen.Add(nxt)) queue.Enqueue((w + a, nxt.Item1, nxt.Item2));
        }
    }
    return null;
}

(Dfa hyp, ObservationTable table, int nEq) Lstar(IEnumerable<char> alphabet, Func<string, bool> mq,
                                                  Func<Dfa, string> eq, bool verbose = true)
{
    var tbl = new ObservationTable(alphabet, mq);
    int nEq = 0, round_ = 0;
    while (true)
    {
        // 1. Stabiliser la table
        while (true)
        {
            var sa = tbl.FindUnclosed();
            if (sa != null) { tbl.S.Add(sa); tbl.Fill(); if (verbose) Console.WriteLine($"  table non fermee -> S += {sa}"); continue; }
            var ae = tbl.FindInconsistency();
            if (ae != null) { tbl.E.Add(ae); tbl.Fill(); if (verbose) Console.WriteLine($"  table non consistante -> E += {ae}"); continue; }
            break;
        }
        // 2. Conjecturer et interroger le professeur
        var hyp = Conjecture(tbl);
        nEq++; round_++;
        var cex = eq(hyp);
        if (verbose) Console.WriteLine($"Conjecture {round_} : {hyp.StateCount} etats -> {(cex == null ? "ACCEPTEE" : "contre-exemple " + cex)}");
        if (cex == null) return (hyp, tbl, nEq);
        // 3. Integrer le contre-exemple (tous ses prefixes dans S, Angluin 1987)
        for (int i = 1; i <= cex.Length; i++)
            if (!tbl.S.Contains(cex[..i])) tbl.S.Add(cex[..i]);
        tbl.Fill();
    }
}

Console.WriteLine("L* implemente : ObservationTable + conjecture + boucle de raffinement.");
L* implemente : ObservationTable + conjecture + boucle de raffinement.

4. Exécution complete sur le langage cible

Lancons L* contre la boite noire. L’oracle d’equivalence est ici exact (BFS sur l’automate produit) : un luxe possible seulement parce que nous connaissons la cible — la section 6 le remplacera par ce qu’on a vraiment en pratique.

var (learned, finalTable, nEqRun) = Lstar(ALPHABET, MembershipQuery,
    h => FindCounterexample(h, TARGET, ALPHABET));

Console.WriteLine($"\nDFA appris : {learned}");
Console.WriteLine($"Requetes d'appartenance : {finalTable.NMq}");
Console.WriteLine($"Requetes d'equivalence  : {nEqRun}");
string eList = string.Join(", ", finalTable.E.Select(e => "'" + e + "'"));
Console.WriteLine($"\nTable finale (S = {finalTable.S.Count} prefixes, E = {{ {eList} }} ) :\n");
finalTable.Show();

// Verification independante exhaustive jusqu'a la longueur 10
IEnumerable<string> AllWords(List<char> alphabet, int maxLen)
{
    yield return "";
    var frontier = new List<string> { "" };
    for (int _ = 0; _ < maxLen; _++)
    {
        var next = new List<string>();
        foreach (var w in frontier) foreach (var a in alphabet) next.Add(w + a);
        frontier = next;
        foreach (var w in frontier) yield return w;
    }
}
var allW = AllWords(ALPHABET, 10).ToList();
int mismatch = allW.Count(w => learned.Accepts(w) != TARGET.Accepts(w));
Console.WriteLine($"\nVerification exhaustive : {allW.Count - mismatch}/{allW.Count} mots (longueur <= 10) identiques");
  table non fermee -> S += a
Conjecture 1 : 2 etats -> contre-exemple ba
  table non consistante -> E += a
  table non consistante -> E += b
Conjecture 2 : 4 etats -> ACCEPTEE

DFA appris : Dfa(4 etats, 1 acceptants)
Requetes d'appartenance : 19
Requetes d'equivalence  : 2

Table finale (S = 4 prefixes, E = { '', 'a', 'b' } ) :

       |  eps    a    b
------------------------
eps    |    1    0    0
a      |    0    1    0
b      |    0    0    1
ba     |    0    0    0
------------------------
aa     |    1    0    0
ab     |    0    0    0
bb     |    1    0    0
baa    |    0    0    1
bab    |    0    1    0

Verification exhaustive : 2047/2047 mots (longueur <= 10) identiques

Interpretation : que s’est-il passe ?

  1. La première conjecture est minuscule et fausse. Avec \(S = E = \{\varepsilon\}\) stabilises, la table ne distingue que « accepte / rejette » : 2 etats. Le professeur repond par un contre-exemple court.

  2. Le contre-exemple force la croissance. Ses prefixes entrent dans \(S\), la consistance casse, des suffixes distinguants entrent dans \(E\) — chaque rejet d’une conjecture ajoute au moins un etat a la suivante. Comme le DFA minimal a 4 etats, il y a au plus 4 conjectures : la terminaison est garantie, pas seulement esperee.

  3. Le cout total est modeste : quelques dizaines de MQ et une poignee d’EQ pour identifier exactement un langage infini. Comparez avec SL-1 : 12 exemples imposes n’avaient pas suffi a stabiliser une simple conjonction. Le choix actif des questions est la source de l’efficacite — chaque requête de la table sert a trancher une distinction precise entre deux etats candidats.

5. Garanties : minimalite et complexite polynomiale

Le theoreme de Myhill-Nerode (1958) donne la borne inferieure structurelle : le nombre d’etats du DFA minimal de \(L\) est exactement le nombre de classes de la congruence \(u \equiv_L v \iff \forall w,\; uw \in L \Leftrightarrow vw \in L\).

Origine. L’exposition canonique du theoreme de Myhill-Nerode et de son rôle pour la minimalite des automates se trouve dans Hopcroft, J. E., Motwani, R. & Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (3e ed., Pearson/Addison-Wesley). Le theoreme (Myhill 1958, Nerode 1958) caracterise un langage regulier par sa congruence syntactique : deux prefixes sont equivalents s’ils ne peuvent etre distingues par aucun suffixe.

L* s’y adosse directement :

  • chaque paire de lignes distinctes de la table est un certificat de non-equivalence (un suffixe de \(E\) separe les deux prefixes), donc la conjecture n’a jamais plus d’etats que le DFA minimal ;
  • l’oracle d’equivalence fournit des contre-exemples tant qu’elle en a moins ;
  • l’algorithme s’arrete donc précisément sur le DFA minimal — il ne peut pas retourner autre chose.

Cote complexite : \(O(n)\) requêtes d’equivalence et \(O(|\Sigma| \cdot m \cdot n^2)\) requêtes d’appartenance, ou \(n\) est le nombre d’etats du minimal et \(m\) la longueur du plus long contre-exemple. Verifions empiriquement la croissance sur la famille \(L_k\) = « le nombre de ‘a’ est divisible par \(k\) » (DFA minimal a \(k\) etats) :

// Verification empirique 1 : les classes de Myhill-Nerode du langage cible
Dictionary<string, List<string>> NerodeClasses(Func<string, bool> mq, List<char> alphabet, int maxPrefix = 4, int maxSuffix = 4)
{
    var suffixes = AllWords(alphabet, maxSuffix).ToList();
    var sig = new Dictionary<string, List<string>>();
    foreach (var u in AllWords(alphabet, maxPrefix))
    {
        var key = string.Join("", suffixes.Select(w => mq(u + w) ? "1" : "0"));
        if (!sig.ContainsKey(key)) sig[key] = new List<string>();
        sig[key].Add(u);
    }
    return sig;
}

var classes = NerodeClasses(MembershipQuery, ALPHABET);
Console.WriteLine($"Classes de Myhill-Nerode empiriques (prefixes <= 4, suffixes <= 4) : {classes.Count}");
foreach (var kv in classes)
    Console.WriteLine($"  classe de {(kv.Value[0] == "" ? "eps" : ("'" + kv.Value[0] + "'")),8} : {kv.Value.Count} prefixes");

// Verification empirique 2 : croissance du cout en fonction de k
Console.WriteLine($"\n{"k",3} | etats appris | MQ | EQ");
Console.WriteLine(new string('-', 34));
for (int k = 2; k <= 6; k++)
{
    bool MqK(string word) => word.Count(c => c == 'a') % k == 0;
    var dkStates = Enumerable.Range(0, k).Select(i => i.ToString()).ToList();
    var dkDelta = new List<((string, char), string)>();
    foreach (var q in dkStates) { dkDelta.Add(((q, 'a'), ((int.Parse(q) + 1) % k).ToString())); dkDelta.Add(((q, 'b'), q)); }
    var dk = new Dfa(dkStates, ALPHABET, dkDelta, "0", new[] { "0" });
    var (h, tbl, neq) = Lstar(ALPHABET, MqK, h2 => FindCounterexample(h2, dk, ALPHABET), verbose: false);
    Console.WriteLine($"{k,3} | {h.StateCount,12} | {tbl.NMq,4} | {neq,2}");
}
Classes de Myhill-Nerode empiriques (prefixes <= 4, suffixes <= 4) : 4
  classe de      eps : 11 prefixes
  classe de      'a' : 5 prefixes
  classe de      'b' : 5 prefixes
  classe de     'ab' : 10 prefixes

  k | etats appris | MQ | EQ
----------------------------------
  2 |            2 |    5 |  1
  3 |            3 |   14 |  2
  4 |            4 |   23 |  2
  5 |            5 |   34 |  2
  6 |            6 |   47 |  2

Interpretation

Les classes empiriques de Myhill-Nerode sont bien au nombre de 4 — et L* a appris un DFA a 4 etats : la garantie de minimalite n’est pas un a-cote théorique, c’est le mécanisme même de l’algorithme. Sur la famille \(L_k\), le nombre d’etats appris suit exactement \(k\) et le nombre de requêtes croit polynomialement, très loin de l’explosion exponentielle qu’exigerait l’enumeration des DFA candidats.

A noter : c’est un des rares algorithmes de la serie a venir avec une garantie exacte (identification du concept, pas approximation). Le prix est le professeur : sans oracle d’equivalence fiable, la garantie s’evapore — voyons précisément comment.

6. L’oracle d’equivalence en pratique

Dans le monde reel (retro-ingenierie d’un protocole, test d’un composant boite noire), personne ne sait repondre exactement a « ton hypothese est-elle correcte ? ». On approxime l’EQ par echantillonnage : tirer \(N\) mots au hasard, comparer l’hypothese et le système, renvoyer le premier desaccord. S’il n’y en a aucun, declarer l’hypothese correcte… en croisant les doigts.

C’est exactement le cadre PAC (SL-3) : le DFA retourne est probablement approximativement correct — mais plus exactement correct. Et la nuance n’est pas academique : elle depend entierement de la densite des desaccords entre une hypothese fausse et la cible. Mesurons-la sur deux langages aux profils opposes : le langage des parites (ou une hypothese fausse se trompe sur environ un mot sur quatre) et un langage-aiguille, « les mots contenant le facteur aabbaabb », ou les mots discriminants sont rares.

using System.Globalization;
// Oracle d'equivalence approximatif : N mots aleatoires, premier desaccord.
Func<Dfa, string> MakeSamplingEq(Func<string, bool> mq, List<char> alphabet, int nSamples, int maxLen = 20, int seed = 0)
{
    var rng = new Random(seed);
    string Eq(Dfa hyp)
    {
        for (int _ = 0; _ < nSamples; _++)
        {
            int len = rng.Next(0, maxLen + 1);
            var sb = new StringBuilder();
            for (int i = 0; i < len; i++) sb.Append(alphabet[rng.Next(alphabet.Count)]);
            var w = sb.ToString();
            if (hyp.Accepts(w) != mq(w)) return w;
        }
        return null;
    }
    return Eq;
}

// Le langage-aiguille : mots contenant le facteur "aabbaabb".
// Son DFA minimal est l'automate de Knuth-Morris-Pratt du motif : 9 etats.
Dfa FactorDfa(string pattern, List<char> alphabet)
{
    int n = pattern.Length;
    var delta = new List<((string, char), string)>();
    for (int q = 0; q <= n; q++)
        foreach (var ch in alphabet)
        {
            string target;
            if (q == n) target = n.ToString();               // motif deja vu : etat absorbant
            else if (pattern[q] == ch) target = (q + 1).ToString();
            else
            {
                var s = pattern[..q] + ch;                   // repli KMP : plus long prefixe du motif encore suffixe
                int best = 0;
                for (int kk = s.Length; kk >= 0; kk--)
                    if (kk <= s.Length && s.EndsWith(pattern[..kk])) { best = kk; break; }
                target = best.ToString();
            }
            delta.Add(((q.ToString(), ch), target));
        }
    var states = Enumerable.Range(0, n + 1).Select(i => i.ToString());
    return new Dfa(states, alphabet, delta, "0", new[] { n.ToString() });
}

Dfa NEEDLE = FactorDfa("aabbaabb", ALPHABET);

foreach (var (name, mq, tgt) in new (string, Func<string, bool>, Dfa)[]
{
    ("parites (desaccords DENSES)", MembershipQuery, TARGET),
    ("contient 'aabbaabb' (desaccords RARES)", NEEDLE.Accepts, NEEDLE),
})
{
    Console.WriteLine($"Langage {name} :");
    Console.WriteLine($"{"N essais",9} | etats | DFA exact ?");
    foreach (var nSamples in new[] { 1, 10, 100, 1000 })
    {
        var (h, _t, _e) = Lstar(ALPHABET, mq, MakeSamplingEq(mq, ALPHABET, nSamples, seed: 7), verbose: false);
        bool exact = FindCounterexample(h, tgt, ALPHABET) == null;
        Console.WriteLine($"{nSamples,9} | {h.StateCount,5} | {(exact ? "OUI" : "NON")}");
    }
    Console.WriteLine();
}
Langage parites (desaccords DENSES) :
 N essais | etats | DFA exact ?
        1 |     2 | NON
       10 |     4 | OUI
      100 |     4 | OUI
     1000 |     4 | OUI

Langage contient 'aabbaabb' (desaccords RARES) :
 N essais | etats | DFA exact ?
        1 |     1 | NON
       10 |     1 | NON
      100 |     9 | OUI
     1000 |     9 | OUI

Interpretation : tout depend de la densite des desaccords

Sur les parites, les desaccords sont suffisamment denses pour que peu d’essais suffisent : des N=10, l’EQ trouve les 4 etats exacts. A N=1, un seul mot peut manquer le contre-exemple (l’approximation retourne un DFA a 2 etats non exact) — la garantie semble intacte, mais c’est une propriete du langage, pas de l’algorithme.

Sur le langage-aiguille, un mot aleatoire de longueur \(\le 20\) ne contient le facteur qu’avec une probabilite de quelques pourcents. A \(N = 1\) ou \(10\) essais, l’EQ approximatif ne voit jamais de desaccord et accepte la toute première conjecture : un DFA a un etat qui rejette tout. Le résultat est grossierement faux et rien dans l’exécution ne le signale — c’est le sens exact du PAC : correct avec probabilite \(1 - \delta\) sur la distribution d’echantillonnage, rien de plus. A \(N = 100\), le contre-exemple finit par sortir, et un seul suffit : ses prefixes injectent dans la table tout le materiel necessaire, et L* deroule les 9 etats sans aide supplementaire.

C’est la même lecon que SL-9, vue de l’autre cote : la-bas, un générateur faillible (le LLM) etait discipline par un oracle exact ; ici, un apprenant exact est fragilise par un oracle faillible. Dans un pipeline neuro-symbolique, identifier qui joue le rôle de l’oracle et ce qu’il garantit vraiment est la première question d’architecture.

7. Posterite : le model learning

L* n’est pas reste un résultat théorique. Sous le nom de model learning (Vaandrager, CACM 2017), ses descendants directs apprennent des machines a etats de systèmes reels, en branchant les MQ sur le système lui-même :

  • Retro-ingenierie de protocoles : les implementations de TLS, TCP, SSH ou des cartes bancaires ont ete apprises comme des machines de Mealy ; plusieurs violations de specification et failles ont ete trouvees en lisant le DFA appris (etats parasites, transitions interdites presentes).
  • LearnLib (open source, Java) industrialise L* et ses variantes modernes (TTT, Rivest-Schapire, ADT), avec des EQ approximatifs intelligents (W-method, echantillonnage dirige).
  • Verification : le DFA appris sert d’interface formelle d’un composant boite noire, sur laquelle un model checker peut ensuite prouver des proprietes (assume-guarantee reasoning).

Et la boucle se referme avec les LLM : des travaux recents utilisent un LLM comme professeur approximatif (repondre aux MQ sur un format textuel, proposer des contre-exemples) et L* comme apprenant exact qui en extrait un automate verifiable — la division générateur faillible / verificateur symbolique de SL-9, devenue protocole d’apprentissage.

8. Exercices

Tableau recapitulatif

Concept Definition Implementation
Requête MQ / EQ \(w \in L\) ? / \(H = L\) ? membership_query, find_counterexample
Table d’observation \((S, E, T)\), lignes = etats candidats ObservationTable
Fermeture \(row(sa)\) presente dans \(S\) find_unclosed()
Consistance lignes egales -> successeurs egaux find_inconsistency()
Conjecture DFA des lignes distinctes conjecture()
EQ approximatif echantillonnage, garantie PAC make_sampling_eq() 
// Exemple guide 1 : Apprendre le langage "contient 'abb' comme facteur"
// Etape 1 : requete d'appartenance -- une ligne suffit ("abb" in word)
bool MqAbb(string word) => word.Contains("abb");

// Etape 2 : lancer L* avec un oracle d'equivalence par echantillonnage
var (learnedAbb, finalTableAbb, nEqAbb) = Lstar(ALPHABET, MqAbb,
    MakeSamplingEq(MqAbb, ALPHABET, 2000), verbose: false);

Console.WriteLine($"DFA appris : {learnedAbb}");
Console.WriteLine($"  Conjectures (equivalences) : {nEqAbb}");
Console.WriteLine($"  |S| = {finalTableAbb.S.Count}, |E| = {finalTableAbb.E.Count}, MQ posees = {finalTableAbb.NMq}");

// Etape 3 : interpretation des etats (prediction theorique : 4 etats)
Console.WriteLine();
Console.WriteLine("Prediction theorique : 4 etats (rien vu / 'a' vu / 'ab' vu / 'abb' vu).");
Console.WriteLine($"-> observe : {learnedAbb.StateCount} etats "
    + (learnedAbb.StateCount == 4 ? "(confirme)" : "(a commenter)"));

// Etape 4 : verification sur 10 mots
var testWords = new[] { "", "a", "ab", "abb", "abbb", "babb", "aaabb", "abab", "abbabb", "bbabb" };
Console.WriteLine();
Console.WriteLine($"{"mot",10} | DFA | vrai | OK ?");
Console.WriteLine(new string('-', 34));
foreach (var w in testWords)
{
    bool pred = learnedAbb.Accepts(w), vrai = w.Contains("abb");
    Console.WriteLine($"{(w == "" ? "(eps)" : w),10} | {(pred ? 1 : 0),3} | {(vrai ? 1 : 0),4} | {(pred == vrai ? "OK" : "ECHEC")}");
}
DFA appris : Dfa(4 etats, 1 acceptants)
  Conjectures (equivalences) : 2
  |S| = 16, |E| = 3, MQ posees = 67

Prediction theorique : 4 etats (rien vu / 'a' vu / 'ab' vu / 'abb' vu).
-> observe : 4 etats (confirme)

       mot | DFA | vrai | OK ?
----------------------------------
     (eps) |   0 |    0 | OK
         a |   0 |    0 | OK
        ab |   0 |    0 | OK
       abb |   1 |    1 | OK
      abbb |   1 |    1 | OK
      babb |   1 |    1 | OK
     aaabb |   1 |    1 | OK
      abab |   0 |    0 | OK
    abbabb |   1 |    1 | OK
     bbabb |   1 |    1 | OK

Exercice 1 (variation) : Apprendre un autre langage-facteur

Reprenez la méthode de l’exemple guide pour apprendre par L* le langage des mots (sur {a, b}) qui contiennent la sous-chaîne “ba” (au lieu de “abb”). Combien d’etats le DFA minimal comporte-t-il, et pourquoi ?

Étapes : 1. Ecrire mq_ba(word) : appartenance au langage “contient ‘ba’ comme facteur” 2. Lancer L* avec make_sampling_eq(mq_ba, ALPHABET, 2000) 3. Donner le nombre d’etats du DFA appris et expliquer chacun (prediction théorique : 3 etats) 4. Verifier sur 8 mots de votre choix

// EXERCICE 1 (variation) : apprendre le langage "contient 'ba' comme facteur"
// TODO etudiant : reprenez l'exemple guide ci-dessus avec le motif "ba".
Console.WriteLine("Exercice a completer : apprenez le langage 'contient ba' par L*");
Console.WriteLine("Etape 1 : ecrivez MqBa(word) avec .Contains(\"ba\")");
Console.WriteLine("Etape 2 : lancez Lstar(ALPHABET, MqBa, MakeSamplingEq(..., 2000))");
Console.WriteLine("Etape 3 : donnez le nombre d'etats et expliquez chacun");
Console.WriteLine("Etape 4 : verifiez sur 8 mots");
// Indice : le motif "ba" est plus court que "abb" -> moins d'etats "amorce".
// Etape 1 : bool MqBa(string word) => word.Contains("ba");   // TODO etudiant
// Etape 2 : var (learnedBa, _, _) = Lstar(ALPHABET, MqBa, MakeSamplingEq(MqBa, ALPHABET, 2000), verbose: false);
// Etape 3 : Console.WriteLine($"DFA appris : {learnedBa} ...");   // prediction : 3 etats
// Etape 4 : boucle de verification sur 8 mots
Dfa learnedBa = null;  // TODO etudiant : le DFA appris (a remplir)
Console.WriteLine($"Resultat : {(learnedBa == null ? "(a completer)" : learnedBa.ToString())}");
Exercice a completer : apprenez le langage 'contient ba' par L*
Etape 1 : ecrivez MqBa(word) avec .Contains("ba")
Etape 2 : lancez Lstar(ALPHABET, MqBa, MakeSamplingEq(..., 2000))
Etape 3 : donnez le nombre d'etats et expliquez chacun
Etape 4 : verifiez sur 8 mots
Resultat : (a completer)

L’exercice suivant quantifie ce que la section 6 a montre qualitativement : la fiabilite de l’oracle d’equivalence par echantillonnage est une variable aleatoire, qui se mesure en repetant l’expérience.

// Exemple guide 2 : Fiabilite de l'oracle d'equivalence approximatif
// Etape 1 : taux de reussite sur n_seeds graines
double TauxFiabilite(Func<string, bool> mq, Dfa target, int nSamples, int nSeeds = 20)
{
    int corrects = 0;
    for (int seed = 0; seed < nSeeds; seed++)
    {
        var eq = MakeSamplingEq(mq, ALPHABET, nSamples, seed: seed);
        var (h, _t, _e) = Lstar(ALPHABET, mq, eq, verbose: false);
        if (FindCounterexample(h, target, ALPHABET) == null) corrects++;
    }
    return (double)corrects / nSeeds;
}

// Etape 2 : tableau n_samples -> taux de reussite (20 runs), NEEDLE vs TARGET
Console.WriteLine("Fiabilite de l'oracle d'equivalence par echantillonnage (20 graines)");
Console.WriteLine(new string('=', 64));
Console.WriteLine($"{"n_samples",10} | {"NEEDLE (desaccords rares)",26} | {"TARGET parites (denses)",24}");
Console.WriteLine(new string('-', 64));
foreach (var nSamples in new[] { 1, 10, 50, 100, 500 })
{
    double tNeedle = TauxFiabilite(NEEDLE.Accepts, NEEDLE, nSamples);
    double tTarget = TauxFiabilite(MembershipQuery, TARGET, nSamples);
    Console.WriteLine($"{nSamples,10} | {tNeedle.ToString("P0", CultureInfo.InvariantCulture),25} | {tTarget.ToString("P0", CultureInfo.InvariantCulture),23}");
}
Console.WriteLine();
Console.WriteLine("Lecture : le seuil de fiabilite (n_samples au-dela duquel le taux tend");
Console.WriteLine("vers 100%) depend fortement du langage. NEEDLE a des desaccords RARES --");
Console.WriteLine("il faut beaucoup d'echantillons pour tomber sur un mot revelateur. TARGET");
Console.WriteLine("(parite) a des desaccords DENSES -- donc peu d'echantillons suffisent.");
Fiabilite de l'oracle d'equivalence par echantillonnage (20 graines)
================================================================
 n_samples |  NEEDLE (desaccords rares) |  TARGET parites (denses)
----------------------------------------------------------------
         1 |                       0 % |                    25 %
        10 |                       5 % |                   100 %
        50 |                      55 % |                   100 %
       100 |                      80 % |                   100 %
       500 |                     100 % |                   100 %

Lecture : le seuil de fiabilite (n_samples au-dela duquel le taux tend
vers 100%) depend fortement du langage. NEEDLE a des desaccords RARES --
il faut beaucoup d'echantillons pour tomber sur un mot revelateur. TARGET
(parite) a des desaccords DENSES -- donc peu d'echantillons suffisent.

Exercice 2 (variation) : Fiabilite vs longueur des mots echantillonnes

Pour NEEDLE, le contre-exemple revelateur est un mot LONG (il faut un mot contenant “aabbaabb”). L’oracle echantillonne des mots de longueur <= max_len : que se passe-t-il si max_len < 8 (aucun mot genere ne peut contenir le motif) ? Mesurez le taux de fiabilite pour max_len dans [5, 8, 12, 20], a n_samples fixe.

Étapes : 1. Reutiliser taux_fiabilite en variant max_len (paramètre de make_sampling_eq) avec n_samples=200 fixe, sur NEEDLE 2. Tableau max_len -> taux de reussite (20 graines) 3. Pourquoi max_len < len(motif) annule-t-il la fiabilite même avec beaucoup d’echantillons ?

// EXERCICE 2 (variation) : fiabilite vs longueur des mots echantillonnes
// TODO etudiant : pour NEEDLE, la fiabilite depend de max_len (longueur max des mots tires).
Console.WriteLine("Exercice a completer : fiabilite vs longueur des mots echantillonnes");
Console.WriteLine("Etape 1 : reutilisez TauxFiabilite en variant max_len (n_samples=200 fixe)");
Console.WriteLine("Etape 2 : affichez le tableau max_len -> taux sur NEEDLE");
Console.WriteLine("Etape 3 : expliquez pourquoi max_len < 8 annule la fiabilite");
// Indice : si aucun mot genere ne peut contenir le motif 'aabbaabb',
// l'oracle ne trouvera JAMAIS de contre-exemple, meme avec n_samples infini.
// Etape 1 : double TauxFiabiliteMaxLen(int maxLen, int nSamples = 200, int nSeeds = 20) { ... }
//   (variation de TauxFiabilite passant maxLen a MakeSamplingEq)
// Etape 2 : foreach (var ml in new[] { 5, 8, 12, 20 }) Console.WriteLine($"  max_len={ml} : {TauxFiabiliteMaxLen(ml):P0}");
Dictionary<int, double> resultat2 = null;  // TODO etudiant : dict {max_len: taux}
Console.WriteLine($"Resultat : {(resultat2 == null ? "(a completer)" : string.Join(", ", resultat2.Select(kv => kv.Key + ":" + kv.Value.ToString("P0"))))}");
Exercice a completer : fiabilite vs longueur des mots echantillonnes
Etape 1 : reutilisez TauxFiabilite en variant max_len (n_samples=200 fixe)
Etape 2 : affichez le tableau max_len -> taux sur NEEDLE
Etape 3 : expliquez pourquoi max_len < 8 annule la fiabilite
Resultat : (a completer)

L’exercice suivant touche au coeur algorithmique : la maniere d’integrer le contre-exemple. Angluin ajoute tous ses prefixes a \(S\) ; la variante de Maler-Pnueli ajoute tous ses suffixes a \(E\) — même garantie, couts différents.

// Exemple guide 3 : Variante de traitement du contre-exemple (suffixes vs prefixes)
// L* variante Maler-Pnueli : integre le contre-exemple par ses SUFFIXES (ajoutes a E).
(Dfa hyp, ObservationTable table, int nEq) LstarSuffixes(IEnumerable<char> alphabet, Func<string, bool> mq,
                                                          Func<Dfa, string> eq, bool verbose = false)
{
    var tbl = new ObservationTable(alphabet, mq);
    int nEq = 0;
    while (true)
    {
        while (true)
        {
            var sa = tbl.FindUnclosed();
            if (sa != null) { tbl.S.Add(sa); tbl.Fill(); continue; }
            var ae = tbl.FindInconsistency();
            if (ae != null) { tbl.E.Add(ae); tbl.Fill(); continue; }
            break;
        }
        var hyp = Conjecture(tbl);
        nEq++;
        var cex = eq(hyp);
        if (cex == null) return (hyp, tbl, nEq);
        // 3. Maler-Pnueli : ajouter les SUFFIXES cex[i:] du contre-exemple a E
        for (int i = 0; i < cex.Length; i++)
        {
            var suf = cex[i..];
            if (!tbl.E.Contains(suf)) tbl.E.Add(suf);
        }
        tbl.Fill();
    }
}

// Deuxieme langage de comparaison : L_5 = mots de longueur divisible par 5.
var l5Delta = new List<((string, char), string)>();
for (int q = 0; q < 5; q++) foreach (var a in ALPHABET) l5Delta.Add(((q.ToString(), a), ((q + 1) % 5).ToString()));
Dfa L5 = new Dfa(Enumerable.Range(0, 5).Select(i => i.ToString()), ALPHABET, l5Delta, "0", new[] { "0" });

// Etape 2 : comparaison prefixes (Angluin) vs suffixes (Maler-Pnueli)
Console.WriteLine("Comparaison Angluin (prefixes -> S) vs Maler-Pnueli (suffixes -> E)");
Console.WriteLine(new string('=', 70));
Console.WriteLine($"{"Langage",-22} | {"Variante",-13} | {"|S|",4} | {"|E|",4} | {"|S|x|E|",7} | {"MQ",5} | {"EQ",3}");
Console.WriteLine(new string('-', 70));
var langages = new (string nom, Func<string, bool> mq, Dfa tgt)[]
{
    ("TARGET (parites)", MembershipQuery, TARGET),
    ("L_5 (longueur % 5)", L5.Accepts, L5),
};
foreach (var (nom, mq, tgt) in langages)
{
    Func<Dfa, string> eq = h => FindCounterexample(h, tgt, ALPHABET);
    foreach (var (variante, runner) in new (string, Func<IEnumerable<char>, Func<string, bool>, Func<Dfa, string>, bool, (Dfa, ObservationTable, int)>)[]
    {
        ("Angluin", (a, m, e, v) => Lstar(a, m, e, v)),
        ("Maler-Pnueli", (a, m, e, v) => LstarSuffixes(a, m, e, v)),
    })
    {
        var (h, tbl, nEq) = runner(ALPHABET, mq, eq, false);
        int taille = tbl.S.Count * tbl.E.Count;
        Console.WriteLine($"{nom,-22} | {variante,-13} | {tbl.S.Count,4} | {tbl.E.Count,4} | {taille,7} | {tbl.NMq,5} | {nEq,3}");
    }
}
Console.WriteLine();
Console.WriteLine("Lecture : les deux variantes echangent |S| contre |E|. Angluin ajoute des");
Console.WriteLine("PREFIXES a S ; Maler-Pnueli ajoute des SUFFIXES a E. La compacite globale");
Console.WriteLine("n'avantage aucune des deux variantes en general.")
Comparaison Angluin (prefixes -> S) vs Maler-Pnueli (suffixes -> E)
======================================================================
Langage                | Variante      |  |S| |  |E| | |S|x|E| |    MQ |  EQ
----------------------------------------------------------------------
TARGET (parites)       | Angluin       |    4 |    3 |      12 |    19 |   2
TARGET (parites)       | Maler-Pnueli  |    4 |    3 |      12 |    19 |   2
L_5 (longueur % 5)     | Angluin       |    6 |    4 |      24 |    34 |   2
L_5 (longueur % 5)     | Maler-Pnueli  |    5 |    6 |      30 |    41 |   2

Lecture : les deux variantes echangent |S| contre |E|. Angluin ajoute des
PREFIXES a S ; Maler-Pnueli ajoute des SUFFIXES a E. La compacite globale
n'avantage aucune des deux variantes en general.

Exercice 3 (variation) : Variante Rivest-Schapire (un seul suffixe, par dichotomie)

Angluin ajoute tous les prefixes, Maler-Pnueli tous les suffixes. La variante de Rivest-Schapire (1993) est plus parcimonieuse : par recherche dichotomique sur le contre-exemple, elle identifie un seul suffixe distinguant et l’ajoute a E. Implementez cette recherche.

Étapes : 1. Soit un contre-exemple c ou l’hypothese et la cible differentent : trouvez par dichotomie un indice i tel que le suffixe c[i:] separe la ligne d’acces correspondante de celle de la cible 2. Ajoutez ce seul suffixe c[i:] a E (pas tous les suffixes) 3. Comparez le nombre total de MQ avec la variante Maler-Pnueli (tous les suffixes) sur TARGET : Rivest ajoute-t-il moins de colonnes ?

// EXERCICE 3 (variation) : variante Rivest-Schapire (un seul suffixe par dichotomie)
// TODO etudiant : au lieu d'ajouter TOUS les suffixes du contre-exemple a E,
// n'en ajouter qu'UN, trouve par recherche dichotomique.
Console.WriteLine("Exercice a completer : variante Rivest-Schapire (un seul suffixe par dichotomie)");
Console.WriteLine("Etape 1 : ecrivez SuffixeDistinguantRivest(table, cex) (recherche dichotomique)");
Console.WriteLine("Etape 2 : ecrivez LstarRivest (copie de LstarSuffixes, ajout d'un seul suffixe)");
Console.WriteLine("Etape 3 : comparez n_mq et |E| avec Maler-Pnueli sur TARGET");
// Indice : la dichotomie exploite le fait que si la ligne d'acces hypothese != cible
// mais coincide a un certain decalage, il existe un point de bascule i ; cex[i:] est
// le suffixe cherche. O(log|cex|) ajout au lieu de |cex|.
// Etape 1 : string SuffixeDistinguantRivest(ObservationTable table, string cex) { ... }
// Etape 2 : (Dfa, ObservationTable, int) LstarRivest(...) { ... }   (copie LstarSuffixes)
// Etape 3 : comparer n_mq et |E| avec Maler-Pnueli sur TARGET
Dfa learnedRivest = null;  // TODO etudiant : le DFA appris par LstarRivest
Console.WriteLine($"Resultat : {(learnedRivest == null ? "(a completer)" : learnedRivest.ToString())}");
Exercice a completer : variante Rivest-Schapire (un seul suffixe par dichotomie)
Etape 1 : ecrivez SuffixeDistinguantRivest(table, cex) (recherche dichotomique)
Etape 2 : ecrivez LstarRivest (copie de LstarSuffixes, ajout d'un seul suffixe)
Etape 3 : comparez n_mq et |E| avec Maler-Pnueli sur TARGET
Resultat : (a completer)

Dernier exercice : la robustesse. Tous les algorithmes de la serie rencontrent tot ou tard cette question, et la reponse de L* est singuliere.

// Exemple guide 4 : Oracle d'appartenance bruite
// Oracle qui MENT avec probabilite p, de facon DETERMINISTE par mot (memoire par mot).
Func<string, bool> MakeNoisyMq(Func<string, bool> trueMq, double p = 0.05, int seed = 0)
{
    var rng = new Random(seed);
    var cache = new Dictionary<string, bool>();
    bool Noisy(string word)
    {
        if (!cache.ContainsKey(word))
        {
            bool truth = trueMq(word);
            bool lie = rng.NextDouble() < p;
            cache[word] = lie ? !truth : truth;
        }
        return cache[word];
    }
    return Noisy;
}

// L* borne : evite la boucle infinie si mq est inconsistant (oracle bruite).
(Dfa hyp, ObservationTable table, int nEq, bool stable) LstarBounded(IEnumerable<char> alphabet, Func<string, bool> mq,
                                                                     Func<Dfa, string> eq, int maxRounds = 8, int maxSteps = 60)
{
    var tbl = new ObservationTable(alphabet, mq);
    int nEq = 0;
    Dfa hyp = null;
    for (int round = 1; round <= maxRounds; round++)
    {
        int steps = 0;
        while (true)
        {
            var sa = tbl.FindUnclosed();
            if (sa != null) { tbl.S.Add(sa); tbl.Fill(); }
            else
            {
                var ae = tbl.FindInconsistency();
                if (ae != null) { tbl.E.Add(ae); tbl.Fill(); }
                else break;
            }
            steps++;
            if (steps > maxSteps) break;
        }
        if (tbl.FindUnclosed() != null || tbl.FindInconsistency() != null)
            return (hyp, tbl, nEq, false);   // non-stabilise
        hyp = Conjecture(tbl);
        nEq++;
        var cex = eq(hyp);
        if (cex == null) return (hyp, tbl, nEq, true);
        for (int i = 1; i <= cex.Length; i++)
            if (!tbl.S.Contains(cex[..i])) tbl.S.Add(cex[..i]);
        tbl.Fill();
    }
    return (hyp, tbl, nEq, false);
}

// Etape 2 : L* borne sous oracle bruite, pour p = 0.05, 0.01, 0.20
Console.WriteLine("Oracle d'appartenance bruite : comportement de L* (cible TARGET = 4 etats)");
Console.WriteLine(new string('=', 66));
foreach (var p in new[] { 0.05, 0.01, 0.20 })
{
    var noisy = MakeNoisyMq(MembershipQuery, p, seed: 0);
    var eqNoisy = MakeSamplingEq(noisy, ALPHABET, 300, seed: 1);
    var (hyp, _tbl, nEq, stable) = LstarBounded(ALPHABET, noisy, eqNoisy, maxRounds: 8);
    if (hyp == null) { Console.WriteLine($"p={p.ToString("F2", CultureInfo.InvariantCulture),4} : NON-STABILISE apres {nEq} conjectures"); continue; }
    var cexReal = FindCounterexample(hyp, TARGET, ALPHABET);
    bool exact = cexReal == null;
    string statut = stable ? "stable" : "max_rounds";
    string verdict = exact ? "EXACT vs TARGET" : "ecart (contre-ex " + cexReal + ")";
    Console.WriteLine($"p={p.ToString("F2", CultureInfo.InvariantCulture),4} : {hyp.StateCount,2} etats | {statut,10} | {nEq,2} EQ | {verdict}");
}
Console.WriteLine();
Console.WriteLine("Lecture : le resultat n'est PAS monotone en p -- il depend de QUELS mots");
Console.WriteLine("l'oracle ment. Un apprenant EXACT comme L* n'a AUCUNE degradation gracieuse");
Console.WriteLine("face au bruit : un seul mensonge memorise dans T cree un etat fantome permanent.");
Oracle d'appartenance bruite : comportement de L* (cible TARGET = 4 etats)
==================================================================
p=0.05 :  8 etats | max_rounds |  2 EQ | ecart (contre-ex abb)
p=0.01 :  4 etats | max_rounds |  3 EQ | EXACT vs TARGET
p=0.20 : 40 etats | max_rounds |  3 EQ | ecart (contre-ex aaaa)

Lecture : le resultat n'est PAS monotone en p -- il depend de QUELS mots
l'oracle ment. Un apprenant EXACT comme L* n'a AUCUNE degradation gracieuse
face au bruit : un seul mensonge memorise dans T cree un etat fantome permanent.

Exercice 4 (variation) : Robustesse par vote majoritaire

Le bruit de l’oracle d’appartenance casse l’hypothese d’exactitude de L. La parade classique : pour chaque mot, poser la requête K fois a l’oracle bruite et garder la reponse majoritaire (le vrai verdict ressort des que K est grand devant le taux de mensonges). Implementez ce robust_mq et montrez qu’il permet a L de retrouver le DFA exact.

Étapes : 1. Ecrire make_robust_mq(noisy_mq, K) : pour chaque mot, echantillonne K reponses bruitees et renvoie la majorite (memoire par mot, comme le bruite) 2. Lancer lstar_bounded avec robust_mq (K=21) sur un oracle bruite a p=0.05 3. Le DFA appris est-il exact vs TARGET ? Quel K minimal suffit pour p=0.05 ? pour p=0.20 ?

// EXERCICE 4 (variation) : robustesse par vote majoritaire
// TODO etudiant : diluez le bruit en posant K fois chaque requete et en gardant la majorite.
Console.WriteLine("Exercice a completer : robustesse par vote majoritaire");
Console.WriteLine("Etape 1 : ecrivez MakeRobustMq(noisyMq, K) (vote majoritaire par mot)");
Console.WriteLine("Etape 2 : lancez LstarBounded avec robustMq (K=21) sur un bruite p=0.05");
Console.WriteLine("Etape 3 : le DFA est-il exact vs TARGET ? K minimal pour p=0.05 ? p=0.20 ?");
// Indice : le vote majoritaire marche seulement si chaque appel bruite est INDEPENDANT.
// Il faut un oracle bruite NON memoise pour que K tirages soient independants.
// Etape 1 : Func<string,bool> MakeRobustMq(Func<string,bool> noisy, int K) { ... }
// Etape 2 : var robust = MakeRobustMq(noisy, 21); var (h,_,_,_) = LstarBounded(ALPHABET, robust, eqR, maxRounds:15);
// Etape 3 : exact vs TARGET ; K minimal
Dfa learnedRobust = null;  // TODO etudiant : le DFA robuste appris
Console.WriteLine($"Resultat : {(learnedRobust == null ? "(a completer)" : learnedRobust.ToString())}");
Exercice a completer : robustesse par vote majoritaire
Etape 1 : ecrivez MakeRobustMq(noisyMq, K) (vote majoritaire par mot)
Etape 2 : lancez LstarBounded avec robustMq (K=21) sur un bruite p=0.05
Etape 3 : le DFA est-il exact vs TARGET ? K minimal pour p=0.05 ? p=0.20 ?
Resultat : (a completer)

9. Pont vers Infer.NET : du DFA exact a la reconnaissance probabiliste de motifs

Les sections 6 et 7 ont etabli le talon d’Achille de L* : il est exact et donc fragile. L’exemple guide 4 (oracle d’appartenance bruite) l’a montre nettement – un seul mensonge memorise dans la table T créé un etat fantome permanent – et concluait par une promesse :

un apprenant EXACT comme L* n’a aucune degradation gracieuse face au bruit, la ou un classifieur statistique se degrade smoothment (loi des grands nombres).

Cette section construit ce classifieur statistique, et montre qu’il est le pendant probabiliste exact de l’automate appris par L*. C’est le pont vers la programmation probabiliste sur sequences d’Infer.NET (serie Probas/Infer).

Le changement de modèle

Automate exact (L*) Chaîne probabiliste (Infer.NET)
Objet DFA déterministe automate pondere / HMM
Verdict accepte / rejette (binaire) P(accepte) (probabilite calibree)
Bruit aucun modèle – un mensonge = une verite modèle de canal explicite (epsilon)
Inference parcours d’etat algorithme forward (somme-produit)

Au lieu d’un oracle qui ment sur l’appartenance (section 6), on adopte le cadre naturel de la reconnaissance de motifs : un canal d’observation bruite sur les symboles eux-mêmes (pensez OCR, parole, capteurs). Le mot vrai w passe dans un canal qui retourne chaque symbole correct avec probabilite 1 - epsilon et le corrompt avec probabilite epsilon. On observe w abime et l’on cherche P(w vrai appartient au langage | observation).

// Reconnaissance probabiliste : l'algorithme forward sur les etats du DFA.
// alpha_t[q] = masse des prefixes vrais finissant dans l'etat q, sachant o_1..o_t.
double ForwardAcceptProb(Dfa dfa, string observed, double epsilon)
{
    var A = dfa.Alphabet;
    int m = A.Count;
    double pFlip = m > 1 ? epsilon / (m - 1) : 0.0;   // masse repartie sur les mauvais symboles
    var alpha = dfa.States.ToDictionary(q => q, q => q == dfa.Start ? 1.0 : 0.0);
    foreach (var o in observed)
    {
        var nxt = dfa.States.ToDictionary(q => q, q => 0.0);
        foreach (var (q, mass) in alpha)
        {
            if (mass == 0.0) continue;
            foreach (var s in A)
            {
                double lik = s == o ? 1.0 - epsilon : pFlip;   // P(observer o | vrai s)
                nxt[dfa.Delta[(q, s)]] += mass * (1.0 / m) * lik;
            }
        }
        double Z = alphaSum(nxt);
        foreach (var q in dfa.States) nxt[q] = Z > 0 ? nxt[q] / Z : 0.0;
        alpha = nxt;
    }
    double Ztot = alphaSum(alpha);
    return Ztot > 0 ? dfa.Accepting.Sum(q => alpha[q]) / Ztot : 0.0;
}
double alphaSum(Dictionary<string, double> d) => d.Values.Sum();

// Garde-fou : a epsilon = 0, le canal est parfait -> le forward redonne le verdict exact.
foreach (var w in new[] { "", "a", "ab", "aabb", "abab", "aab", "bbaa", "abba" })
{
    double p0 = ForwardAcceptProb(TARGET, w, 0.0);
    bool mq = MembershipQuery(w);
    if ((p0 > 0.5) != mq || Math.Abs(p0 - (mq ? 1.0 : 0.0)) > 1e-9)
        Console.WriteLine($"ECHEC coherence epsilon=0 sur {w}");
}
Console.WriteLine("Coherence epsilon=0 : le forward redonne le verdict exact du DFA. OK\n");

string trueW = "aabb";
Console.WriteLine($"Mot vrai w = '{trueW}'  (appartient a L ? {MembershipQuery(trueW)})");
Console.WriteLine($"{"epsilon",7} | {"P(accepte | obs)",16} | lecture");
Console.WriteLine(new string('-', 52));
foreach (var eps in new[] { 0.0, 0.05, 0.10, 0.20, 0.35 })
{
    double p = ForwardAcceptProb(TARGET, trueW, eps);
    string note = p > 0.95 ? "certain" : (p > 0.5 ? "penche accepte" : "doute");
    Console.WriteLine($"{eps.ToString("F2", CultureInfo.InvariantCulture),7} | {p.ToString("F3", CultureInfo.InvariantCulture),16} | {note}");
}
Coherence epsilon=0 : le forward redonne le verdict exact du DFA. OK

Mot vrai w = 'aabb'  (appartient a L ? True)
epsilon | P(accepte | obs) | lecture
----------------------------------------------------
   0.00 |            1.000 | certain
   0.05 |            0.828 | penche accepte
   0.10 |            0.705 | penche accepte
   0.20 |            0.565 | penche accepte
   0.35 |            0.504 | penche accepte

Lecture : une probabilite calibree, pas un meilleur verdict

A partir d’une seule observation, la decision a seuil 0.5 du recognizer probabiliste coincide avec le parcours dur du DFA sur l’observation : pour epsilon < 0.5, le symbole le plus probable reste celui observe. Ce que le modèle probabiliste apporte d’emblee n’est donc pas une meilleure exactitude sur un coup, mais une confiance calibree : P(accepte) glisse doucement vers 0.5 quand le bruit monte – jamais le basculement catastrophique de L*, qui construisait un automate faux. La degradation est gracieuse.

Le vrai gain d’exactitude vient quand on dispose de plusieurs observations bruitees du même mot (plusieurs lectures OCR, plusieurs trames audio). C’est la version probabiliste – et correcte – du vote majoritaire de l’exercice 4.

// Agregation de preuves : k observations independantes du meme mot vrai.
double ForwardAcceptProbMulti(Dfa dfa, List<string> observations, double epsilon)
{
    var A = dfa.Alphabet;
    int m = A.Count;
    double pFlip = m > 1 ? epsilon / (m - 1) : 0.0;
    int T = observations[0].Length;
    var alpha = dfa.States.ToDictionary(q => q, q => q == dfa.Start ? 1.0 : 0.0);
    for (int i = 0; i < T; i++)
    {
        var column = observations.Select(o => o[i]).ToList();
        var nxt = dfa.States.ToDictionary(q => q, q => 0.0);
        foreach (var (q, mass) in alpha)
        {
            if (mass == 0.0) continue;
            foreach (var s in A)
            {
                double lik = 1.0;
                foreach (var oI in column) lik *= s == oI ? 1.0 - epsilon : pFlip;
                nxt[dfa.Delta[(q, s)]] += mass * (1.0 / m) * lik;
            }
        }
        double Z = nxt.Values.Sum(); if (Z == 0) Z = 1.0;
        foreach (var q in dfa.States) nxt[q] /= Z;
        alpha = nxt;
    }
    double Ztot = alpha.Values.Sum();
    return Ztot > 0 ? dfa.Accepting.Sum(q => alpha[q]) / Ztot : 0.0;
}

string Corrupt(string word, double eps, Random rng)
{
    var sb = new StringBuilder();
    foreach (var c in word) sb.Append(rng.NextDouble() >= eps ? c : (c == 'a' ? 'b' : 'a'));
    return sb.ToString();
}

(double hard1, double probK) BatchAccuracy(double eps, int k, int nWords = 3000, int seed = 7)
{
    var rng = new Random(seed);
    int hard1 = 0, probK = 0;
    for (int _ = 0; _ < nWords; _++)
    {
        int len = rng.Next(0, 13);
        var sb = new StringBuilder();
        for (int i = 0; i < len; i++) sb.Append(ALPHABET[rng.Next(ALPHABET.Count)]);
        var w = sb.ToString();
        bool y = MembershipQuery(w);
        var obs = new List<string>();
        for (int j = 0; j < k; j++) obs.Add(Corrupt(w, eps, rng));
        if (TARGET.Accepts(obs[0]) == y) hard1++;
        if ((ForwardAcceptProbMulti(TARGET, obs, eps) > 0.5) == y) probK++;
    }
    return ((double)hard1 / nWords, (double)probK / nWords);
}

Console.WriteLine("Recuperation par agregation de k observations (n=3000 mots) :");
Console.WriteLine($"{"k obs",6} | {"dur (1 obs)",11} | {"forward (k obs)",15}");
Console.WriteLine(new string('-', 40));
var ks = new[] { 1, 3, 5, 9, 15, 25 };
var curve20 = new List<double>(); var curve30 = new List<double>(); double hardRef = 0;
foreach (var k in ks)
{
    var (h20, p20) = BatchAccuracy(0.20, k);
    var (_h30, p30) = BatchAccuracy(0.30, k);
    curve20.Add(p20); curve30.Add(p30); hardRef = h20;
    Console.WriteLine($"{k,6} | {h20.ToString("F3", CultureInfo.InvariantCulture),11} | eps=.20 {p20.ToString("F3", CultureInfo.InvariantCulture)}  eps=.30 {p30.ToString("F3", CultureInfo.InvariantCulture)}");
}

// Visualisation ASCII : exactitude vs k (forward eps=.20 / eps=.30 + plafond DFA dur).
Console.WriteLine();
Console.WriteLine("Recuperation par evidence (ASCII) : exactitude vs nombre d'observations k");
int W = 46, H = 14;
char[,] g = new char[H, W];
for (int y = 0; y < H; y++) for (int x = 0; x < W; x++) g[y, x] = ' ';
Action<List<double>, char> Plot = (curve, mark) =>
{
    for (int i = 0; i < curve.Count; i++)
    {
        int x = (int)Math.Round((double)i / (curve.Count - 1) * (W - 1));
        int y = (int)Math.Round((1.0 - curve[i]) * (H - 1) / 0.3);  // plage 0.70-1.00
        if (y >= 0 && y < H) g[y, x] = mark;
    }
};
Plot(curve20, 'O'); Plot(curve30, 'X');
int yRef = (int)Math.Round((1.0 - hardRef) * (H - 1) / 0.3);
if (yRef >= 0 && yRef < H) for (int x = 0; x < W; x++) if (g[yRef, x] == ' ') g[yRef, x] = '-';
Console.WriteLine($"exact {1.0.ToString("F2", CultureInfo.InvariantCulture)} +");
for (int y = 0; y < H; y++) { Console.Write("       |"); for (int x = 0; x < W; x++) Console.Write(g[y, x]); Console.WriteLine(); }
Console.WriteLine($"exact {0.7.ToString("F2", CultureInfo.InvariantCulture)} +{new string('-', W)}  k -> {ks.Last()}");
Console.WriteLine("O = forward eps=0.20 ; X = forward eps=0.30 ; - = plafond DFA dur (1 obs).");
Recuperation par agregation de k observations (n=3000 mots) :
 k obs | dur (1 obs) | forward (k obs)
----------------------------------------
     1 |       0.784 | eps=.20 0.784  eps=.30 0.788
     3 |       0.782 | eps=.20 0.827  eps=.30 0.795
     5 |       0.774 | eps=.20 0.866  eps=.30 0.793
     9 |       0.782 | eps=.20 0.944  eps=.30 0.832
    15 |       0.806 | eps=.20 0.985  eps=.30 0.882
    25 |       0.795 | eps=.20 0.998  eps=.30 0.954

Recuperation par evidence (ASCII) : exactitude vs nombre d'observations k
exact 1.00 +
       |                                             O
       |                                    O         
       |                           O                 X
       |                                              
       |                                              
       |                                    X         
       |                  O                           
       |                           X                  
       |         O                                    
       |X--------X--------X---------------------------
       |                                              
       |                                              
       |                                              
       |                                              
exact 0.70 +----------------------------------------------  k -> 25
O = forward eps=0.20 ; X = forward eps=0.30 ; - = plafond DFA dur (1 obs).

Le pont : Infer.NET fait exactement cela, automatiquement

Trois faits reunis ferment la boucle :

  1. L’algorithme forward est du passage de messages. La recursion alpha_t[q'] = somme ... est l’algorithme somme-produit sur le graphe de facteurs en chaîne etat_0 -- etat_1 -- ... -- etat_T. C’est le même moteur qui calcule les marginales d’un HMM.

  2. Infer.NET (Microsoft Research) automatise ce passage de messages. On y declare le modèle generatif – un mot vrai tire d’un prior, un canal qui le bruite, des observations – et le moteur infere la posterieure. Surtout, Infer.NET sait raisonner directement sur des distributions de sequences (StringDistribution), c’est-a-dire des automates ponderes : la version probabiliste native du DFA que L* apprend.

  3. C’est la synthese neuro-symbolique de la serie. L* fournit la structure exacte (l’automate minimal, garanti) ; Infer.NET l’enveloppe d’une inference statistique robuste au bruit. Structure symbolique + inference probabiliste : ni l’exactitude fragile seule, ni le tout-statistique opaque.

Ou continuer dans le depot

Notebook Ce qu’il apporte au pont
Probas/Infer/Infer-14-Sequences distributions sur sequences = automates ponderes (le coeur du pont)
Probas/Infer-1b prise en main d’Infer.NET (programmation probabiliste .NET)
Probas/Infer/Infer-3-Factor-Graphs graphes de facteurs + passage de messages = le forward generalise
HMM Gaussian Alpha le même HMM gaussien, cote Python (hmmlearn)

Pour aller plus loin (exercice du pont)

Le canal ci-dessus est symetrique (même epsilon dans les deux sens). Beaucoup de capteurs reels sont asymetriques : confondre a en b est plus frequent que l’inverse. Reprenez forward_accept_prob avec une matrice de confusion P(observe | vrai) quelconque (2x2, lignes sommant a 1) au lieu du scalaire epsilon, puis verifiez que la coherence canal-parfait (matrice identite = verdict exact) tient toujours. Indice : seule la ligne lik = ... change.

// Exercice du pont : canal d'observation ASYMETRIQUE (matrice de confusion).
// confusion[(vrai, observe)] = P(observer 'observe' | vrai symbole 'vrai').
double ForwardAcceptProbConfusion(Dfa dfa, string observed, Dictionary<(char, char), double> confusion)
{
    // Indice : recopier ForwardAcceptProb et remplacer la ligne
    //   lik = (1 - epsilon) if s == o else p_flip
    // par
    //   lik = confusion[(s, o)]
    // TODO etudiant : implementer la passe forward avec la matrice de confusion.
    Console.WriteLine("Exercice du pont a completer : forward avec matrice de confusion.");
    return 0.0;  // TODO etudiant : remplacer par la probabilite calculee
}

// Verification attendue une fois implemente (canal parfait = identite -> verdict exact) :
// var identite = new Dictionary<(char,char),double>();
// foreach (var x in ALPHABET) foreach (var y in ALPHABET) identite[(x,y)] = x == y ? 1.0 : 0.0;
// foreach (var w in new[] { "aabb", "aab", "abba" }) {
//     double p = ForwardAcceptProbConfusion(TARGET, w, identite);
//     if ((p > 0.5) != MembershipQuery(w)) Console.WriteLine($"ECHEC canal identite sur {w}");
// }
Console.WriteLine("Exercice du pont : generalisez ForwardAcceptProb a une matrice de confusion.");
Exercice du pont : generalisez ForwardAcceptProb a une matrice de confusion.

Conclusion

Recapitulatif

  1. Le modèle MAT (Angluin 1987) donne a l’apprenant le droit de poser des questions : appartenance (MQ) et equivalence (EQ). Ce droit change la classe de complexite du problème — l’inference passive du plus petit DFA consistant est NP-difficile, l’inference active est polynomiale.

  2. La table d’observation \((S, E, T)\) approxime la congruence de Myhill-Nerode avec un ensemble fini de suffixes distinguants. Fermeture et consistance sont les deux conditions pour qu’elle definisse un DFA.

  3. L* alterne stabilisation de la table, conjecture, et integration du contre-exemple. Chaque conjecture rejetee gagne au moins un etat : terminaison et minimalite sont garanties, en au plus \(n\) equivalences.

  4. L’oracle d’equivalence exact n’existe pas en pratique : on echantillonne, et la garantie exacte devient garantie PAC. La fiabilite du résultat est plafonnee par celle du professeur.

  5. Le model learning industrialise tout cela (LearnLib, machines de Mealy, protocoles reels) — et la variante moderne « LLM comme professeur, L* comme apprenant » re-applique la division du travail de SL-9.

Position dans la serie

Méthode Type L’apprenant… Garantie
Version Space (SL-1) passif, symbolique subit les exemples convergence si realisable
FOIL (SL-4) passif, relationnel subit les exemples heuristique (gain)
LTN (SL-7) passif, neuro-symbolique subit les exemples satisfaction approchee
L* (SL-10) actif, symbolique choisit ses questions identification exacte, DFA minimal

Connexions

Direction Sujet Lien
Prerequis Espaces d’hypotheses, PAC SL-1, SL-3
Suite Resolution inverse, Progol SL-5
Capstone LLM professeur / oracle symbolique SL-11
Pont probabiliste Reconnaissance de sequences sous bruit Infer.NET, Infer-14-Sequences
Automates & verification Model checking Serie SymbolicAI

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 (langage ‘abb’) Verifiez que le DFA appris est minimal en exhibant, pour chaque paire d’etats, un suffixe qui les distingue (certificat de Myhill-Nerode). Pourquoi L* est-il structurellement incapable de retourner un DFA non minimal ?
Ex. 2 (fiabilite de l’EQ) Reliez votre taux de reussite empirique a la borne PAC : combien d’echantillons la théorie exige-t-elle pour \(\varepsilon = 0.01, \delta = 0.05\) ? Construisez une distribution de tirage qui fait echouer l’echantillonnage quel que soit \(N\) raisonnable.
Ex. 3 (prefixes vs suffixes) Exhibez le pire cas : une famille de langages ou les contre-exemples sont longs et ou la variante prefixes fait exploser $S$. La variante de Rivest-Schapire n’ajoute qu’UN suffixe trouve par dichotomie sur le contre-exemple : quel est son cout en MQ et pourquoi est-ce le bon compromis ?
Ex. 4 (oracle bruite) Peut-on reparer L* par vote majoritaire (poser chaque MQ 2k+1 fois) ? Calculez le surcout en requêtes et la probabilite residuelle d’erreur ; comparez avec la degradation graduelle d’un classifieur statistique sous le même bruit. Que conclure sur le contrat exactitude-contre-robustesse du symbolique ?

Ressources

  • D. Angluin, Learning Regular Sets from Queries and Counterexamples, Information and Computation 75(2), 1987
  • M. Kearns & U. Vazirani, An Introduction to Computational Learning Theory, ch. 8 (MIT Press, 1994)
  • F. Vaandrager, Model Learning, Communications of the ACM 60(2), 2017
  • R. Rivest & R. Schapire, Inference of Finite Automata Using Homing Sequences, Information and Computation 103(2), 1993
  • LearnLib — bibliotheque de reference du model learning
  • E. M. Gold, Complexity of Automaton Identification from Given Data, Information and Control 37, 1978

Retour : Index SymbolicLearning | << SL-9 | SL-11 >>

Retour au sommet