SL-1 - Apprentissage Logique : CBH Search et Version Space

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Representer des hypotheses comme des formules logiques (conjonctions de predicats) 2. Définir la notion de consistance d’une hypothese (faux positifs / faux negatifs) 3. Implementer l’algorithme Current-Best-Hypothesis (CBH) search avec generalisation et specialisation 4. Implementer l’algorithme Version Space / Candidate Elimination avec G-set et S-set 5. Comprendre les limites de l’apprentissage par espace de versions (bruit, disjonctions) 6. Confronter notre implementation a la reference aima-python (hypotheses disjonctives, Figure 19.2)

Prerequis

Python 3.10+
Connaissances basiques en logique propositionnelle et predicats
Notions de generalisation / specialisation en apprentissage

Duree estimee : 50 minutes

References

Russell & Norvig, Artificial Intelligence: A Modern Approach, 3e ed., Chapitre 19.1
Tom Mitchell, Machine Learning, Chapitre 2 (Concept Learning)

1. Le problème restaurant (AIMA)

L’exemple classique de l’AIMA pour l’apprentissage logique est le problème du restaurant : etant donne un ensemble d’expériences de restaurant (decrites par des attributs), apprendre la règle WillWait qui predit si on attendra ou non pour une table.

Attributs du domaine

Attribut	Description	Valeurs possibles
`Alternate`	Autre restaurant a cote ?	Yes, No
`Bar`	Bar/salle d’attente ?	Yes, No
`Fri/Sat`	Vendredi ou samedi ?	Yes, No
`Hungry`	Faim ?	Yes, No
`Patrons`	Frequentation	None, Some, Full
`Price`	Prix	$, \[, \]$
`Raining`	Pleut-il ?	Yes, No
`Reservation`	Reservation ?	Yes, No
`Type`	Type de restaurant	French, Italian, Thai, Burger
`WaitEstimate`	Temps d’attente estime	0-10, 10-30, 30-60, >60

Hypotheses comme conjonctions

Une hypothese est une conjonction de contraintes sur les attributs. Chaque contrainte peut etre : - Une valeur spécifique : Patrons = Full - Un joker (?) : n’importe quelle valeur (attribut ignore) - Une valeur None : aucun exemple ne doit avoir cette valeur

L’hypothese la plus générale est (?, ?, ?, ?, ?, ?, ?, ?, ?, ?) — elle accepte tout. L’hypothese la plus spécifique est (None, None, None, None, None, None, None, None, None, None) — elle refuse tout.

# Definition du domaine : attributs et leurs valeurs possibles
ATTRIBUTES = [
    "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
]

ATTRIBUTE_VALUES = {
    "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"],
}

# Les 12 exemples du restaurant, adaptes de la Table 19.1 d'AIMA.
# Attention : les labels de X2 et X3 sont inverses par rapport au livre (et le
# WaitEstimate de X9 differe). Consequence pedagogique assumee : aucune clause
# conjonctive unique n'est consistante avec les 12 exemples, ce qui provoque
# l'effondrement du Version Space observe en section 5.
RAW_EXAMPLES = [
    # (Alternate, Bar, Fri/Sat, Hungry, Patrons, Price, Raining, Reservation, Type, WaitEstimate, 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),
]

def parse_example(raw: tuple) -> dict:
    """Convertit un tuple brut en dictionnaire avec attributs + label."""
    attrs = {ATTRIBUTES[i]: raw[i] for i in range(len(ATTRIBUTES))}
    attrs["WillWait"] = raw[len(ATTRIBUTES)]
    return attrs

EXAMPLES = [parse_example(ex) for ex in RAW_EXAMPLES]

print(f"Domaine : {len(ATTRIBUTES)} attributs")
print(f"Exemples : {len(EXAMPLES)} ({sum(1 for e in EXAMPLES if e['WillWait'])} positifs, "
      f"{sum(1 for e in EXAMPLES if not e['WillWait'])} negatifs)")

Domaine : 10 attributs
Exemples : 12 (6 positifs, 6 negatifs)

Interpretation : Domaine du restaurant

Élément	Valeur	Signification
Attributs	10	Description complete de chaque expérience restaurant
Exemples	12 (6 positifs, 6 negatifs)	Données d’apprentissage
Tâche	Classifier WillWait	Predire s’il faut attendre une table

Les exemples positifs (WillWait=True) sont des situations ou on a attendu avec satisfaction, les negatifs (WillWait=False) des situations ou l’attente n’en valait pas la peine.

Note : En comptant le joker ? et la valeur interdite None par attribut, l’espace syntaxique des hypotheses conjonctives compte prod(|valeurs_i| + 2) combinaisons, soit 4^6 * 5^2 * 6^2 = 3 686 400 (6 attributs binaires, 2 attributs a 3 valeurs, 2 attributs a 4 valeurs). L’espace sémantique (hypotheses distinctes en extension) est plus petit : toute hypothese contenant un None rejette tous les exemples, elles sont donc toutes equivalentes a une unique hypothese vide, d’ou prod(|valeurs_i| + 1) + 1 = 3^6 * 4^2 * 5^2 + 1 = 291 601. L’espace des hypotheses est borne mais immense au regard des 12 exemples.

2. Representation des hypotheses et consistance

Une hypothese est un tuple de contraintes, une par attribut. Trois valeurs possibles par position : - "?" (joker) : accepte n’importe quelle valeur - Une valeur spécifique (ex "Full") : accepte uniquement cette valeur - None : valeur speciale impossible (utilisee pour le S-set initial)

Consistance

Une hypothese est consistante avec un exemple si : - L’exemple est positif et l’hypothese le couvre (pas de faux negatif) - L’exemple est negatif et l’hypothese ne le couvre pas (pas de faux positif)

from typing import Optional

# Type alias pour les hypotheses
Hypothesis = tuple[Optional[str], ...]  # Chaque element : "?" | valeur | None

# Hypotheses extremes
G0: Hypothesis = ("?",) * len(ATTRIBUTES)   # La plus generale
S0: Hypothesis = (None,) * len(ATTRIBUTES)  # La plus specifique


def covers(h: Hypothesis, example: dict) -> bool:
    """Une hypothese couvre un exemple si chaque contrainte est satisfaite."""
    for i, attr in enumerate(ATTRIBUTES):
        if h[i] is None:
            # Contrainte impossible -> ne couvre rien
            return False
        if h[i] != "?" and h[i] != example[attr]:
            return False
    return True


def is_consistent(h: Hypothesis, examples: list[dict]) -> bool:
    """Verifie la consistance d'une hypothese avec tous les exemples."""
    for ex in examples:
        h_covers = covers(h, ex)
        if ex["WillWait"] and not h_covers:
            return False  # Faux negatif
        if not ex["WillWait"] and h_covers:
            return False  # Faux positif
    return True


def count_errors(h: Hypothesis, examples: list[dict]) -> tuple[int, int]:
    """Compte les faux positifs et faux negatifs."""
    fp = fn = 0
    for ex in examples:
        h_covers = covers(h, ex)
        if not ex["WillWait"] and h_covers:
            fp += 1
        if ex["WillWait"] and not h_covers:
            fn += 1
    return fp, fn


# Test sur les hypotheses extremes
print(f"G0 (plus generale) : {G0}")
print(f"  Couvre exemple 1 : {covers(G0, EXAMPLES[0])}")
print(f"  Faux positifs / Faux negatifs : {count_errors(G0, EXAMPLES)}")
print(f"  Consistante : {is_consistent(G0, EXAMPLES)}")
print()
print(f"S0 (plus specifique) : {S0}")
print(f"  Couvre exemple 1 : {covers(S0, EXAMPLES[0])}")
print(f"  Faux positifs / Faux negatifs : {count_errors(S0, EXAMPLES)}")
print(f"  Consistante : {is_consistent(S0, EXAMPLES)}")

G0 (plus generale) : ('?', '?', '?', '?', '?', '?', '?', '?', '?', '?')
  Couvre exemple 1 : True
  Faux positifs / Faux negatifs : (6, 0)
  Consistante : False

S0 (plus specifique) : (None, None, None, None, None, None, None, None, None, None)
  Couvre exemple 1 : False
  Faux positifs / Faux negatifs : (0, 6)
  Consistante : False

Interpretation : Consistance

Hypothese	Couvre	Faux positifs	Faux negatifs	Consistante
G0 (tout `?`)	Tout	6 (tous les negatifs)	0	Non
S0 (tout `None`)	Rien	0	6 (tous les positifs)	Non

G0 est trop générale : elle couvre tous les exemples, y compris les negatifs (6 faux positifs). S0 est trop spécifique : elle ne couvre aucun exemple, même pas les positifs (6 faux negatifs).

L’objectif des algorithmes CBH et Version Space est de trouver une hypothese entre les deux qui minimise ces erreurs.

3. Generalisation et specialisation

Les deux opérations fondamentales pour manipuler les hypotheses :

Generaliser : remplacer une contrainte spécifique par ? (accepter plus d’exemples)
Specialiser : remplacer un ? par une valeur spécifique (accepter moins d’exemples)

Hiérarchie de generalisation

(?, ?, ?, ...)           <- plus générale
  |                       (generalisation)
(Full, ?, ?, ...)
  |
(Full, $, ?, ...)        <- plus spécifique

Une hypothese h1 est plus générale que h2 (notation h1 >= h2) si h2 couvre un sous-ensemble des exemples couverts par h1.

def is_more_general_than(h1: Hypothesis, h2: Hypothesis) -> bool:
    """h1 est-elle plus generale que h2 ? (h1 >= h2)"""
    for i in range(len(ATTRIBUTES)):
        # h1[i] doit etre "?" ou egal a h2[i] pour chaque position
        if h1[i] != "?" and h1[i] != h2[i]:
            return False
    return True


def is_more_specific_than(h1: Hypothesis, h2: Hypothesis) -> bool:
    """h1 est-elle plus specifique que h2 ? (h1 <= h2)"""
    return is_more_general_than(h2, h1)


def generalize_for(h: Hypothesis, example: dict) -> Hypothesis:
    """Generalise h minimalement pour couvrir l'exemple positif."""
    result = list(h)
    for i, attr in enumerate(ATTRIBUTES):
        if result[i] is None or result[i] == example[attr]:
            result[i] = example[attr]
        elif result[i] != "?" and result[i] != example[attr]:
            result[i] = "?"
    return tuple(result)


def specialize_against(h: Hypothesis, example: dict) -> list[Hypothesis]:
    """Specialise h pour ne PAS couvrir l'exemple negatif.
    
    Retourne toutes les specialisations minimales possibles.
    """
    specializations = []
    for i, attr in enumerate(ATTRIBUTES):
        if h[i] == "?":
            # Remplacer "?" par chaque valeur possible SAUF celle de l'exemple negatif
            for val in ATTRIBUTE_VALUES[attr]:
                if val != example[attr]:
                    new_h = list(h)
                    new_h[i] = val
                    specializations.append(tuple(new_h))
    return specializations


# Demonstration
h_test = ("Yes", "No", "No", "Yes", "Full", "$", "No", "No", "Thai", "30-60")
print(f"Hypothese initiale : {h_test}")
print(f"Couvre exemple 2 (positif) : {covers(h_test, EXAMPLES[1])}")
print()

# Generaliser pour couvrir l'exemple 1 (qui differe sur Patrons et Price)
h_gen = generalize_for(h_test, EXAMPLES[0])
print(f"Apres generalisation pour ex1 : {h_gen}")
print(f"Couvre maintenant ex1 : {covers(h_gen, EXAMPLES[0])}")
print(f"Couvre toujours ex2 : {covers(h_gen, EXAMPLES[1])}")
print()

# Specialiser contre l'exemple 3 (negatif)
h_gen2 = generalize_for(S0, EXAMPLES[0])
h_gen2 = generalize_for(h_gen2, EXAMPLES[1])
print(f"Hypothese apres 2 positifs : {h_gen2}")
specs = specialize_against(h_gen2, EXAMPLES[2])
print(f"Specialisations contre ex3 (negatif) : {len(specs)}")
for s in specs[:5]:
    print(f"  {s}")
if len(specs) > 5:
    print(f"  ... et {len(specs) - 5} autres")

Hypothese initiale : ('Yes', 'No', 'No', 'Yes', 'Full', '$', 'No', 'No', 'Thai', '30-60')
Couvre exemple 2 (positif) : True

Apres generalisation pour ex1 : ('Yes', 'No', 'No', 'Yes', '?', '?', 'No', '?', '?', '?')
Couvre maintenant ex1 : True
Couvre toujours ex2 : True

Hypothese apres 2 positifs : ('Yes', 'No', 'No', 'Yes', '?', '?', 'No', '?', '?', '?')
Specialisations contre ex3 (negatif) : 11
  ('Yes', 'No', 'No', 'Yes', 'None', '?', 'No', '?', '?', '?')
  ('Yes', 'No', 'No', 'Yes', 'Full', '?', 'No', '?', '?', '?')
  ('Yes', 'No', 'No', 'Yes', '?', '$$', 'No', '?', '?', '?')
  ('Yes', 'No', 'No', 'Yes', '?', '$$$', 'No', '?', '?', '?')
  ('Yes', 'No', 'No', 'Yes', '?', '?', 'No', 'Yes', '?', '?')
  ... et 6 autres

Interpretation : Generalisation et specialisation

Opération	Effet	Quand l’utiliser
Generaliser	Remplace les contraintes différentes par `?`	Quand un faux negatif est detecte (exemple positif non couvert)
Specialiser	Remplace un `?` par une valeur spécifique	Quand un faux positif est detecte (exemple negatif couvert)

Observations : - La generalisation est déterministe : une seule generalisation minimale - La specialisation est non déterministe : plusieurs specialisations possibles (une par valeur d’attribut eligible) - Le nombre de specialisations croit rapidement : pour un attribut binaire, 1 specialisation; pour un attribut a 4 valeurs, 3 specialisations

Point cle : Cette asymetrie entre generalisation (unique) et specialisation (multiple) est la raison pour laquelle CBH peut revenir en arriere (backtracking) tandis que le Version Space evite ce problème en gardant les deux frontieres.

Les deux sens de chaque opération : croissance vs reduction de l’enonce

La section ci-dessus a presente generaliser et specialiser chacune comme une seule opération. C’est suffisant pour faire tourner CBH (section 4) et le Version Space (section 5) sur une representation conjonctive. Mais le cours IAMA souligne une structure plus riche : chaque direction admet deux sens, selon qu’elle augmente ou reduit la taille de l’enonce logique.

Direction (declenchee par)	Sens « reduit l’enonce »	Sens « augmente l’enonce »
Generaliser (faux negatif : un positif n’est pas couvert)	enlever un conjoint : relacher une contrainte vers `?`. L’enonce raccourcit.	ajouter une exception positive par disjonction (`h OU nouveau_cas`). L’enonce grandit d’un disjonct.
Specialiser (faux positif : un negatif est couvert)	supprimer un disjonct, ou reduire l’espace couvert. L’enonce raccourcit.	ajouter une exception negative par conjonction (`h ET condition`). L’enonce grandit d’un conjoint.

Les sections 3 a 5 n’exercent que les deux cases « faciles » de la representation conjonctive : generaliser-reduire (relacher ?) et specialiser-augmenter (epingler ? vers une valeur).
Les deux autres cases exigent une representation disjonctive (une hypothese = une liste de conjonctions reliees par OU). Elles apparaissent en section 9, via l’algorithme de reference aima-python et son opération add_or.

Point cle pour la suite. Toute croissance de l’enonce (ajout d’une exception, positive ou negative) a un cout : un modèle plus long est plus fragile, il memorise au lieu de generaliser. Un algorithme prudent pese donc ce cout au moyen d’une metrique de complexite (la taille de l’enonce) et recommence les reductions chaque fois qu’elles restent possibles sans casser la consistance, car un modèle simple consistant generalise mieux (rasoir d’Occam / MDL). Ce principe est rendu operationnel en section 9, une fois la representation disjonctive disponible. Et il faut le souligner d’emblee : parfois l’exception est la seule facon de gagner la consistance ; dans ce cas la metrique ne l’interdit pas, elle la minimise.

4. Algorithme Current-Best-Hypothesis (CBH)

L’algorithme CBH (AIMA Figure 19.2) maintient une seule hypothese et l’ajuste incrementalement :

Commencer avec la première hypothese consistante avec les exemples vus
Pour chaque nouvel exemple :
- Si positif et non couvert -> generaliser l’hypothese
- Si negatif et couvert -> specialiser l’hypothese
- Si l’ajustement introduit des incoherences avec les exemples précédents -> backtracking

Pseudo-code (AIMA 19.2)

function CBH(examples) returns hypothesis
    h <- première hypothese consistante avec examples[0]
    for each example in examples[1:]:
        if example est positif:
            if h ne couvre pas example:
                h <- generaliser(h, example)  // minimale
                if h inconsistante avec exemples précédents:
                    BACKTRACK (pas de solution simple)
        else:  // exemple negatif
            if h couvre example:
                h <- specialiser(h, example)  // minimale
                if h inconsistante avec exemples précédents:
                    BACKTRACK
    return h

def current_best_hypothesis(
    examples: list[dict],
    verbose: bool = True
) -> tuple[Optional[Hypothesis], list[dict]]:
    """Algorithme Current-Best-Hypothesis (AIMA Figure 19.2).
    
    Maintient une seule hypothese et l'ajuste incrementalement.
    Retourne (hypothese, trace) ou trace est la liste des etapes.
    """
    trace = []
    
    # Trouver la premiere hypothese consistante avec le premier exemple
    first = examples[0]
    if first["WillWait"]:
        # Pour un positif : l'hypothese exacte de l'exemple
        h = tuple(first[attr] for attr in ATTRIBUTES)
    else:
        # Pour un negatif : on ne peut pas initialiser avec S0 (trop specifique)
        # On utilise G0 et on laisse les exemples suivants specialiser
        h = G0
    
    seen = [first]
    trace.append({"step": 0, "example": 0, "label": first["WillWait"],
                   "action": "init", "hypothesis": h})
    
    for idx in range(1, len(examples)):
        ex = examples[idx]
        h_covers = covers(h, ex)
        action = "keep"
        
        if ex["WillWait"] and not h_covers:
            # Faux negatif -> generaliser, puis verifier que la generalisation
            # ne couvre pas un negatif deja vu (AIMA : sinon backtrack)
            h = generalize_for(h, ex)
            if is_consistent(h, seen + [ex]):
                action = "generalize"
            else:
                action = "generalize (INCONSISTANT)"
        elif not ex["WillWait"] and h_covers:
            # Faux positif -> specialiser
            # Essayer chaque specialisation et garder la premiere consistante
            specs = specialize_against(h, ex)
            found_valid = False
            for spec in specs:
                if is_consistent(spec, seen):
                    h = spec
                    found_valid = True
                    break
            if not found_valid:
                action = "BACKTRACK (no valid specialization)"
            else:
                action = "specialize"
        else:
            action = "keep (consistent)"
        
        seen.append(ex)
        trace.append({"step": idx, "example": idx, "label": ex["WillWait"],
                       "action": action, "hypothesis": h})
    
    return h, trace


# Execution de CBH sur les exemples du restaurant
cbh_result, cbh_trace = current_best_hypothesis(EXAMPLES, verbose=True)

print("Trace CBH :")
print(f"{'Step':>4} | {'Label':>5} | {'Action':<25} | Hypothese")
print("-" * 80)
for step in cbh_trace:
    label = "+" if step["label"] else "-"
    h_str = str(step["hypothesis"])[:50]
    print(f"{step['step']:>4} | {label:>5} | {step['action']:<25} | {h_str}")

print(f"\nHypothese finale CBH : {cbh_result}")
fp, fn = count_errors(cbh_result, EXAMPLES)
print(f"Faux positifs : {fp}, Faux negatifs : {fn}")
print(f"Consistante : {is_consistent(cbh_result, EXAMPLES)}")

Trace CBH :
Step | Label | Action                    | Hypothese
--------------------------------------------------------------------------------
   0 |     + | init                      | ('Yes', 'No', 'No', 'Yes', 'Some', '$$$', 'No', 'Y
   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', '?', '?', '?', '?', '?', '?

Hypothese finale CBH : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')
Faux positifs : 1, Faux negatifs : 0
Consistante : False

Interpretation : Résultat CBH

L’algorithme CBH ajuste progressivement l’hypothese a chaque nouvel exemple :

Situation	Action	Effet
Exemple positif non couvert	Generaliser	Elargir l’hypothese pour couvrir
Exemple negatif couvert	Specialiser	Restreindre l’hypothese pour exclure
Déjà consistent	Garder	Aucun changement

Limites du CBH : 1. Backtracking : Quand aucune specialisation n’est consistante, il faut revenir en arriere (couteux) 2. Ordre-dépendance : Le résultat depend de l’ordre des exemples 3. Hypothese unique : On ne garde qu’une seule hypothese, pas l’espace complet

Note : CBH est un algorithme glouton qui ne retient qu’une seule hypothèse. Le Version Space (section 5) lève cette limite algorithmique en gardant toutes les hypothèses consistantes à la fois — mais il partage le même espace d’hypothèses conjonctif : sur les 12 exemples du restaurant, il s’effondre lui aussi (G et S deviennent vides). La limite de fond n’est donc pas l’algorithme mais la représentation ; c’est la section 9 (hypothèses disjonctives) qui la résout vraiment.

5. Algorithme Version Space / Candidate Elimination

L’algorithme Candidate Elimination (AIMA Figure 19.3) resout le problème du CBH en representant tout l’espace des hypotheses consistantes au moyen de deux frontieres :

G-set (General boundary) : hypotheses les plus générales encore consistantes
S-set (Specific boundary) : hypotheses les plus spécifiques encore consistantes

Toute hypothese consistante se situe entre G et S : pour tout h consistant, il existe g dans G et s dans S tels que g >= h >= s.

Origine. La théorie des version spaces et de l’algorithme Candidate Elimination (frontieres G/S) est formalisee par Mitchell, T. M. (1982), Generalization as search, Artificial Intelligence 18(2):203-226 — ou l’apprentissage de concept est vu comme une recherche dans l’espace des hypotheses.

Algorithme

G <- {G0}  (hypothese la plus générale)
S <- {S0}  (hypothese la plus spécifique)

for each example:
    if POSITIF:
        G <- retirer de G les hypotheses qui ne couvrent pas l'exemple
        Pour chaque s dans S qui ne couvre pas l'exemple:
            s <- generaliser(s) minimale pour couvrir l'exemple
            Retirer s si aucun élément de G n'est plus general ou egal a s
        Retirer de S les hypotheses doublons ou non minimales
    if NEGATIF:
        S <- retirer de S les hypotheses qui couvrent l'exemple (inchange)
        Pour chaque g dans G qui couvre l'exemple:
            Remplacer g par ses specialisations qui ne couvrent pas l'exemple
            Retirer celles qui sont plus spécifiques qu'un élément de S
        Retirer de G les hypotheses doublons ou non maximales

def candidate_elimination(
    examples: list[dict],
    verbose: bool = True
) -> tuple[set[Hypothesis], set[Hypothesis], list[dict]]:
    """Algorithme Candidate Elimination (AIMA Figure 19.3).
    
    Retourne (G_set, S_set, trace).
    """
    G: set[Hypothesis] = {G0}
    S: set[Hypothesis] = {S0}
    trace = []
    
    for idx, ex in enumerate(examples):
        if ex["WillWait"]:
            # --- Exemple POSITIF ---
            # G : retirer les hypotheses qui ne couvrent pas l'exemple
            G = {g for g in G if covers(g, ex)}
            
            # S : generaliser chaque hypothese qui ne couvre pas l'exemple
            new_S: set[Hypothesis] = set()
            for s in S:
                if covers(s, ex):
                    new_S.add(s)
                else:
                    s_gen = generalize_for(s, ex)
                    new_S.add(s_gen)
            
            # Retirer de S les hypotheses plus generales qu'une autre
            S = _remove_subsumed(new_S)
            
            # Retirer de S les hypotheses pas plus generales qu'un element de G
            S = {s for s in S if any(is_more_general_than(g, s) for g in G)}
            
        else:
            # --- Exemple NEGATIF ---
            # S : retirer les hypotheses qui couvrent le negatif (elles sont inchangees)
            S = {s for s in S if not covers(s, ex)}
            
            # G : specialiser chaque hypothese qui couvre le negatif
            new_G: set[Hypothesis] = set()
            for g in G:
                if not covers(g, ex):
                    new_G.add(g)  # Gardee telle quelle
                else:
                    # Specialiser et ne garder que les specialisations consistantes
                    for spec in specialize_against(g, ex):
                        if not covers(spec, ex):  # ne couvre pas le negatif
                            # Verifier plus generale qu'un element de S
                            if any(is_more_general_than(spec, s) for s in S):
                                new_G.add(spec)
            
            # Retirer de G les hypotheses plus specifiques qu'une autre
            G = _remove_subsumed_G(new_G)
        
        trace.append({
            "example": idx,
            "label": ex["WillWait"],
            "|G|": len(G),
            "|S|": len(S),
        })
    
    return G, S, trace


def _remove_subsumed(S: set[Hypothesis]) -> set[Hypothesis]:
    """Retire de S les hypotheses qui sont plus generales qu'une autre dans S.
    On garde les hypotheses les PLUS specifiques.
    """
    result = set()
    s_list = list(S)
    for i, s1 in enumerate(s_list):
        subsumed = False
        for j, s2 in enumerate(s_list):
            if i != j and is_more_general_than(s1, s2):
                # s1 est plus generale que s2 -> s1 est subsumee
                subsumed = True
                break
        if not subsumed:
            result.add(s1)
    return result


def _remove_subsumed_G(G: set[Hypothesis]) -> set[Hypothesis]:
    """Retire de G les hypotheses qui sont plus specifiques qu'une autre dans G.
    On garde les hypotheses les PLUS generales.
    """
    result = set()
    g_list = list(G)
    for i, g1 in enumerate(g_list):
        subsumed = False
        for j, g2 in enumerate(g_list):
            if i != j and is_more_general_than(g2, g1):
                # g2 est plus generale que g1 -> g1 est subsumee
                subsumed = True
                break
        if not subsumed:
            result.add(g1)
    return result


# Execution
G_final, S_final, vs_trace = candidate_elimination(EXAMPLES)

print("Trace Version Space :")
print(f"{'Ex':>3} | {'Label':>5} | {'|G|':>3} | {'|S|':>3}")
print("-" * 25)
for step in vs_trace:
    label = "+" if step["label"] else "-"
    print(f"{step['example']:>3} | {label:>5} | {step['|G|']:>3} | {step['|S|']:>3}")

print(f"\nG-set final ({len(G_final)} hypotheses) :")
for g in sorted(G_final):
    print(f"  {g}")

print(f"\nS-set final ({len(S_final)} hypotheses) :")
for s in sorted(S_final):
    print(f"  {s}")

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

G-set final (0 hypotheses) :

S-set final (0 hypotheses) :

Interpretation : Résultat du Version Space

L’algorithme Candidate Elimination converge vers un ensemble d’hypotheses consistantes bornees par G et S :

Ensemble	Rôle	Taille
G-set	Frontieres les plus générales	Variable
S-set	Frontieres les plus spécifiques	Variable
Version Space	Toutes les hypotheses entre G et S	Grand mais implicite

Proprietes : - Toute hypothese h telle que g >= h >= s pour un g dans G et un s dans S est consistante - Si G = S (frontieres identiques), une seule hypothese est consistante -> convergence - Si G ou S devient vide, l’espace de version est vide -> pas de hypothese consistante

Point cle : Le Version Space represente implicitement toutes les hypotheses consistantes. Même s’il y en a des milliers, seules les frontieres G et S sont stockees. Résultat observe ici : sur les exemples du restaurant, G et S s’effondrent au 10e exemple (|G| = |S| = 0, k=10) : aucune conjonction unique ne peut representer WillWait. Le concept reel (AIMA 19.3) est un arbre de decision, c’est-a-dire une combinaison disjonctive de cas — le biais de representation conjonctif est trop fort pour ce domaine. C’est un résultat pedagogique important, pas un bug : il motive les representations plus riches (arbres de decision, clauses multiples en SL-4). La section 6 contourne l’effondrement en apprenant le VS sur les 4 premiers exemples seulement — la ou il est encore large.

6. Prediction avec le Version Space

Pour classifier un nouvel exemple, on peut utiliser 3 stratégies :

Unanime : Predict positif si TOUTE hypothese dans VS couvre, negatif si AUCUNE ne couvre
Majorite : Vote majoritaire parmi les hypotheses du VS
Conservateur : Predict positif si S-set couvre, negatif si G-set ne couvre pas > Le VS appris sur les 12 exemples etant vide (effondrement, section 5), on > apprend ici les frontieres sur les 4 premiers exemples et on evalue sur les > 8 suivants, jamais vus (test). Pourquoi 4 et pas 9 ? A 9 exemples le VS a > déjà converge vers une hypothese unique : les trois stratégies deviendraient > identiques. A 4 exemples le VS est encore large (7 hypotheses) et les > stratégies divergent reellement — c’est ce qu’on veut observer.

# Le VS sur les 12 exemples s'est effondre (section 5), et apres 9 exemples
# il a deja converge vers une hypothese unique (strategies identiques).
# Pour comparer les strategies, on se place la ou le VS est encore LARGE :
# apres les 4 premiers exemples (|G|=3, cf. trace section 5). Les 8 exemples
# suivants servent de test.
N_TRAIN = 4
G_pred, S_pred, _ = candidate_elimination(EXAMPLES[:N_TRAIN], verbose=False)
print(f"VS appris sur {N_TRAIN} exemples : |G|={len(G_pred)}, |S|={len(S_pred)}")


def enumerate_version_space(
    G: set[Hypothesis],
    S: set[Hypothesis],
    examples: list[dict]
) -> list[Hypothesis]:
    """Enumere toutes les hypotheses consistantes du Version Space.

    Astuce : toute hypothese consistante h satisfait h >= s pour un s du S-set.
    On genere donc, pour chaque s, les hypotheses obtenues en relachant a '?'
    un sous-ensemble de ses contraintes specifiees, puis on ne garde que
    celles qui restent consistantes avec tous les exemples.
    """
    from itertools import combinations
    vs: set[Hypothesis] = set()
    for s in S:
        specified = [i for i, v in enumerate(s) if v != "?"]
        for r in range(len(specified) + 1):
            for combo in combinations(specified, r):
                h = tuple("?" if i in combo else v for i, v in enumerate(s))
                if h not in vs and is_consistent(h, examples):
                    vs.add(h)
    return sorted(vs)


VS_ALL = enumerate_version_space(G_pred, S_pred, EXAMPLES[:N_TRAIN])
print(f"Version Space complet : {len(VS_ALL)} hypotheses consistantes")


def predict_vs(
    example: dict,
    G: set[Hypothesis],
    S: set[Hypothesis],
    strategy: str = "unanimous",
    vs_all: list[Hypothesis] = None
) -> tuple[bool, str]:
    """Prediction avec le Version Space.

    Retourne (prediction, justification).
    """
    s_covers = any(covers(s, example) for s in S)
    g_covers = any(covers(g, example) for g in G)

    if strategy == "unanimous":
        if s_covers and g_covers:
            return True, "Toutes les hypotheses couvrent"
        elif not s_covers and not g_covers:
            return False, "Aucune hypothese ne couvre"
        else:
            return None, "Desaccord entre hypotheses"  # type: ignore
    elif strategy == "majority":
        votes = sum(1 for h in vs_all if covers(h, example))
        total = len(vs_all)
        verdict = votes * 2 > total
        return verdict, f"Majorite : {votes}/{total} hypotheses couvrent"
    elif strategy == "conservative":
        if s_covers:
            return True, "S-set couvre (conservateur)"
        elif not g_covers:
            return False, "G-set ne couvre pas (conservateur)"
        else:
            return None, "Incertain (entre G et S)"  # type: ignore
    else:
        return None, f"Strategie inconnue: {strategy}"  # type: ignore


# Evaluation : 4 exemples d'entrainement + 8 exemples de test (jamais vus)
print()
print("Evaluation du Version Space (train = 0-3, TEST = 4-11) :")
print(f"{'Ex':>3} | {'Role':>5} | {'Vrai':>5} | {'Unanime':>8} | {'Majorite':>8} | {'Conserv.':>8} | Attributs cles")
print("-" * 86)

results = []
for i, ex in enumerate(EXAMPLES):
    role = "train" if i < N_TRAIN else "TEST"
    true_label = ex["WillWait"]

    pred_u, _ = predict_vs(ex, G_pred, S_pred, "unanimous")
    pred_m, _ = predict_vs(ex, G_pred, S_pred, "majority", VS_ALL)
    pred_c, _ = predict_vs(ex, G_pred, S_pred, "conservative")
    results.append((role, true_label, pred_u, pred_m, pred_c))

    fmt = lambda p: "+" if p is True else ("-" if p is False else "?")
    print(f"{i:>3} | {role:>5} | {'+' if true_label else '-':>5} | {fmt(pred_u):>8} |"
          f" {fmt(pred_m):>8} | {fmt(pred_c):>8} | Patrons={ex['Patrons']}, Type={ex['Type']}")

print()
for role in ("train", "TEST"):
    subset = [r for r in results if r[0] == role]
    n = len(subset)
    for name, k in [("Unanime", 2), ("Majorite", 3), ("Conservateur", 4)]:
        correct = sum(1 for r in subset if r[k] == r[1])
        uncertain = sum(1 for r in subset if r[k] is None)
        print(f"  {name:12s} ({role:5s}) : {correct}/{n} corrects, {uncertain} incertains")

VS appris sur 4 exemples : |G|=3, |S|=1
Version Space complet : 7 hypotheses consistantes

Evaluation du Version Space (train = 0-3, TEST = 4-11) :
 Ex |  Role |  Vrai |  Unanime | Majorite | Conserv. | Attributs cles
--------------------------------------------------------------------------------------
  0 | train |     + |        + |        + |        + | Patrons=Some, Type=French
  1 | train |     + |        + |        + |        + | Patrons=Full, Type=Thai
  2 | train |     - |        - |        - |        - | Patrons=Some, Type=Burger
  3 | train |     + |        + |        + |        + | Patrons=Full, Type=Thai
  4 |  TEST |     - |        ? |        - |        ? | Patrons=Full, Type=French
  5 |  TEST |     + |        ? |        - |        ? | Patrons=Some, Type=Italian
  6 |  TEST |     - |        - |        - |        - | Patrons=None, Type=Burger
  7 |  TEST |     + |        ? |        - |        ? | Patrons=Some, Type=Thai
  8 |  TEST |     - |        - |        - |        - | Patrons=Full, Type=Burger
  9 |  TEST |     - |        ? |        - |        ? | Patrons=Full, Type=Italian
 10 |  TEST |     - |        ? |        - |        ? | Patrons=None, Type=Thai
 11 |  TEST |     + |        ? |        - |        ? | Patrons=Full, Type=Burger

  Unanime      (train) : 4/4 corrects, 0 incertains
  Majorite     (train) : 4/4 corrects, 0 incertains
  Conservateur (train) : 4/4 corrects, 0 incertains
  Unanime      (TEST ) : 2/8 corrects, 6 incertains
  Majorite     (TEST ) : 5/8 corrects, 0 incertains
  Conservateur (TEST ) : 2/8 corrects, 6 incertains

Interpretation : Prediction

Stratégie	Principe	Résultat (test, 8 ex.)	Avantage	Inconvenient
Unanime	Positif si tout le VS couvre, negatif si rien ne couvre	2/8 corrects, 6 incertains	Ne se prononce jamais a tort	Abstient des que le VS est large
Majorite	Vote des 7 hypotheses du VS	5/8 corrects, 0 incertain	Tranche toujours	Peut se tromper (ex. 5, 7 et 11 : vrais positifs predits negatifs)
Conservateur	S-set couvre -> positif ; G-set ne couvre pas -> negatif	2/8 corrects, 6 incertains	Bonne calibration	Mêmes abstentions que l’unanime ici

Observations :

Sur le train, les trois stratégies font 4/4 : toute hypothese du VS est consistante avec ces exemples par construction.
Sur le test, l’unanime et le conservateur ne se prononcent que sur les 2 negatifs flagrants (hors de portee même de G) — et ont raison. Les 6 autres exemples tombent dans la zone d’incertitude du VS.
La majorite tranche toujours, mais penche vers le “non” : la plupart des 7 hypotheses restent proches du S-set (très spécifiques), donc couvrent peu. Elle rate ainsi les positifs 5, 7 et 11.
Le compromis est classique : ne jamais se tromper (unanime) contre toujours repondre (majorite). Plus on ajoute d’exemples, plus le VS se resserre et plus les stratégies se rejoignent — ici, des 9 exemples, le VS converge vers une hypothese unique et les trois stratégies deviennent identiques.

7. Visualisation de l’evolution du Version Space

Observons comment les frontieres G et S evoluent au fil des exemples. L’ideal est une convergence rapide : G et S se rejoignent vers une hypothese unique.

# Evolution detaillee du Version Space
print("Evolution detaillee du Version Space :")
print("=" * 70)

G_run: set[Hypothesis] = {G0}
S_run: set[Hypothesis] = {S0}

for idx, ex in enumerate(EXAMPLES):
    label_str = "POSITIF" if ex["WillWait"] else "NEGATIF"
    attrs_short = f"Pat={ex['Patrons']}, Type={ex['Type']}, Price={ex['Price']}"
    
    # Sauvegarder l'etat avant
    g_before = len(G_run)
    s_before = len(S_run)
    
    # Mettre a jour
    if ex["WillWait"]:
        G_run = {g for g in G_run if covers(g, ex)}
        new_S = set()
        for s in S_run:
            if covers(s, ex):
                new_S.add(s)
            else:
                new_S.add(generalize_for(s, ex))
        S_run = _remove_subsumed(new_S)
        S_run = {s for s in S_run if any(is_more_general_than(g, s) for g in G_run)}
    else:
        S_run = {s for s in S_run if not covers(s, ex)}
        new_G = set()
        for g in G_run:
            if not covers(g, ex):
                new_G.add(g)
            else:
                for spec in specialize_against(g, ex):
                    if not covers(spec, ex):
                        if any(is_more_general_than(spec, s) for s in S_run):
                            new_G.add(spec)
        G_run = _remove_subsumed_G(new_G)
    
    delta_g = len(G_run) - g_before
    delta_s = len(S_run) - s_before
    
    print(f"\nEx {idx:>2} [{label_str:>7}] {attrs_short}")
    print(f"  G: {g_before} -> {len(G_run)} ({delta_g:+d})  |  S: {s_before} -> {len(S_run)} ({delta_s:+d})")
    
    if len(G_run) <= 5:
        for g in sorted(G_run):
            h_str = ", ".join(
                f"{ATTRIBUTES[i]}={g[i]}" for i in range(len(ATTRIBUTES)) if g[i] != "?"
            )
            print(f"    G: {h_str}")
    
    if len(S_run) <= 5:
        for s in sorted(S_run):
            h_str = ", ".join(
                f"{ATTRIBUTES[i]}={s[i]}" for i in range(len(ATTRIBUTES)) if s[i] is not None and s[i] != "?"
            )
            print(f"    S: {h_str}")
    
    if not G_run or not S_run:
        print("  ** VERSION SPACE VIDE **")
        break

Evolution detaillee du Version Space :
======================================================================

Ex  0 [POSITIF] Pat=Some, Type=French, Price=$$$
  G: 1 -> 1 (+0)  |  S: 1 -> 1 (+0)
    G: 
    S: Alternate=Yes, Bar=No, Fri/Sat=No, Hungry=Yes, Patrons=Some, Price=$$$, Raining=No, Reservation=Yes, Type=French, WaitEstimate=0-10

Ex  1 [POSITIF] Pat=Full, Type=Thai, Price=$
  G: 1 -> 1 (+0)  |  S: 1 -> 1 (+0)
    G: 
    S: Alternate=Yes, Bar=No, Fri/Sat=No, Hungry=Yes, Raining=No

Ex  2 [NEGATIF] Pat=Some, Type=Burger, Price=$
  G: 1 -> 3 (+2)  |  S: 1 -> 1 (+0)
    G: Hungry=Yes
    G: Bar=No
    G: Alternate=Yes
    S: Alternate=Yes, Bar=No, Fri/Sat=No, Hungry=Yes, Raining=No

Ex  3 [POSITIF] Pat=Full, Type=Thai, Price=$
  G: 3 -> 3 (+0)  |  S: 1 -> 1 (+0)
    G: Hungry=Yes
    G: Bar=No
    G: Alternate=Yes
    S: Alternate=Yes, Bar=No, Hungry=Yes

Ex  4 [NEGATIF] Pat=Full, Type=French, Price=$$$
  G: 3 -> 1 (-2)  |  S: 1 -> 1 (+0)
    G: Hungry=Yes
    S: Alternate=Yes, Bar=No, Hungry=Yes

Ex  5 [POSITIF] Pat=Some, Type=Italian, Price=$$
  G: 1 -> 1 (+0)  |  S: 1 -> 1 (+0)
    G: Hungry=Yes
    S: Hungry=Yes

Ex  6 [NEGATIF] Pat=None, Type=Burger, Price=$
  G: 1 -> 1 (+0)  |  S: 1 -> 1 (+0)
    G: Hungry=Yes
    S: Hungry=Yes

Ex  7 [POSITIF] Pat=Some, Type=Thai, Price=$$
  G: 1 -> 1 (+0)  |  S: 1 -> 1 (+0)
    G: Hungry=Yes
    S: Hungry=Yes

Ex  8 [NEGATIF] Pat=Full, Type=Burger, Price=$
  G: 1 -> 1 (+0)  |  S: 1 -> 1 (+0)
    G: Hungry=Yes
    S: Hungry=Yes

Ex  9 [NEGATIF] Pat=Full, Type=Italian, Price=$$$
  G: 1 -> 0 (-1)  |  S: 1 -> 0 (-1)
  ** VERSION SPACE VIDE **

Interpretation : Evolution du Version Space

L’evolution du Version Space suit un schema previsible :

Phase	Comportement	Cause
Debut	G grandit, S se generalise	Les premiers exemples posent les frontieres
Milieu	G se specialise, S se generalise	Les frontieres convergent
Fin	Stabilisation ou convergence	L’espace se resserre autour de la solution

Indicateurs : - Si |G| et |S| restent petits : l’espace est bien contraint - Si |G| explose : trop d’hypotheses générales possibles (besoin de plus d’exemples negatifs) - Si le VS devient vide : les données sont bruitees ou l’hypothese n’est pas representable en conjonction pure

8. Limites du Version Space conjonctif

Les sections 4 et 5 ont travaille sur une representation conjonctive des hypotheses. Cette section recense ses limites en distinguant deux natures :

des limites fondamentales, partagees par CBH et le Version Space, qui ont reellement motive le passage a d’autres familles de modèles (8.1, 8.3, 8.4 ci-dessous) ;
une limite de representation — l’impossibilite des disjonctions (8.2) — qui n’est pas une impasse : elle se leve en enrichissant le langage d’hypotheses, ce que fait déjà l’opération add_or introduite en section 3 et exercee en section 9.

8.1 Sensibilite au bruit

Un seul exemple mal etiquete peut vider le Version Space completement.

# Demonstration : ajout d'un exemple bruite
noisy_examples = EXAMPLES.copy()

# Creer un exemple bruite en inversant le label de l'exemple 0
noisy_ex = dict(EXAMPLES[0])
noisy_ex["WillWait"] = not noisy_ex["WillWait"]
noisy_examples.append(noisy_ex)

print(f"Exemple bruite ajoute : WillWait={noisy_ex['WillWait']} (inverse)")
print(f"Patrons={noisy_ex['Patrons']}, Type={noisy_ex['Type']}, Price={noisy_ex['Price']}")
print()

G_noisy, S_noisy, trace_noisy = candidate_elimination(noisy_examples)

if not G_noisy or not S_noisy:
    print("RESULTAT : Version Space VIDE !")
    print("Le bruit (un seul exemple mal etiquete) a detruit l'espace.")
else:
    print(f"G-set : {len(G_noisy)} hypotheses")
    print(f"S-set : {len(S_noisy)} hypotheses")

Exemple bruite ajoute : WillWait=False (inverse)
Patrons=Some, Type=French, Price=$$$

RESULTAT : Version Space VIDE !
Le bruit (un seul exemple mal etiquete) a detruit l'espace.

8.2 Incapacite de la representation conjonctive a exprimer les disjonctions

Une hypothese conjonctive unique (sections 4-5) ne peut pas exprimer un concept disjonctif comme “Patrons=Some OU (Patrons=Full ET Fri/Sat=Yes)”. C’est exactement ce qui effondre notre Version Space sur les 12 exemples du restaurant (section 5 : |G| = |S| = 0).

Mais c’est une limite du langage d’hypotheses, pas une impasse de l’apprentissage par generalisation/specialisation. Il suffit d’enrichir la representation : autoriser une hypothese a etre une liste de conjonctions reliees par OU, et ajouter l’opération add_or (le sens « augmenter l’enonce » de la generalisation, tableau de la section 3). La section 9 le verifie : avec cette seule extension, current_best_learning trouve une hypothese 100% consistante la ou le VS conjonctif s’effondrait. Le prix n’est donc pas l’impossibilite, mais le contrôle de la complexite — une representation disjonctive peut toujours memoriser les exemples au lieu de generaliser, d’ou la necessite du rasoir d’Occam / MDL (section 9).

# Demonstration : concept disjonctif
# Le vrai concept AIMA est disjonctif :
# WillWait si (Patrons=Some) OU (Patrons=Full ET Hungry=Yes)

print("Concept cible AIMA (disjonctif) :")
print("  WillWait si Patrons=Some")
print("            OU (Patrons=Full AND Hungry=Yes)")
print()

# Verifions combien d'exemples satisfont chaque clause
clause1 = sum(1 for e in EXAMPLES if e["Patrons"] == "Some" and e["WillWait"])
clause2 = sum(1 for e in EXAMPLES if e["Patrons"] == "Full" and e["Hungry"] == "Yes" and e["WillWait"])
total_pos = sum(1 for e in EXAMPLES if e["WillWait"])

print(f"Clause 1 (Patrons=Some) couvre : {clause1} positifs")
print(f"Clause 2 (Patrons=Full AND Hungry=Yes) couvre : {clause2} positifs")
print(f"Total positifs : {total_pos}")
print()
print("Le Version Space ne peut pas representer cette disjonction.")
print("Il represente la meilleure approximation sous forme de conjonction,")
print("ce qui explique pourquoi le Version Space s'effondre (|G| = |S| = 0).")
print()
print("Solutions possibles :")
print("  1. Arbres de decision (peuvent representer les disjonctions)")
print("  2. Apprentissage d'ensembles de regles (separate-and-conquer)")
print("  3. Modeles probabilistes (naive Bayes, regression logistique)")

Concept cible AIMA (disjonctif) :
  WillWait si Patrons=Some
            OU (Patrons=Full AND Hungry=Yes)

Clause 1 (Patrons=Some) couvre : 3 positifs
Clause 2 (Patrons=Full AND Hungry=Yes) couvre : 3 positifs
Total positifs : 6

Le Version Space ne peut pas representer cette disjonction.
Il represente la meilleure approximation sous forme de conjonction,
ce qui explique pourquoi le Version Space s'effondre (|G| = |S| = 0).

Solutions possibles :
  1. Arbres de decision (peuvent representer les disjonctions)
  2. Apprentissage d'ensembles de regles (separate-and-conquer)
  3. Modeles probabilistes (naive Bayes, regression logistique)

Interpretation : Limites du Version Space

Limite	Nature	Cause	Consequence	Reponse
Bruit	Fondamentale	Un seul exemple errone	VS vide	Modèles probabilistes (tolerance aux erreurs)
Disjonctions	Representation	Langage conjonctif (pas l’algorithme)	Effondrement du VS conjonctif (section 5)	Enrichir le langage : disjonctions + `add_or` (sections 3 et 9, resolu dans ce notebook), puis arbres de decision / règles pour la compacite
Explosion combinatoire	Fondamentale	Nombre de specialisations	G-set très grand	Heuristiques, attribution de probabilites
Attributs continus	Fondamentale	Besoin de seuils discrets	Non applicable directement	Arbres de decision avec seuils

Note historique : le Version Space reste un pilier conceptuel de l’apprentissage symbolique — frontieres G/S, ordre de generalite, convergence. Ses limites fondamentales (bruit, explosion, attributs continus) ont motive des familles plus robustes (arbres de decision ID3/C4.5, modèles probabilistes), tandis que sa limite de representation — les disjonctions — se leve directement en enrichissant le langage d’hypotheses, comme le montre la section 9.

9. L’implementation de reference : aima-python

Le depot officiel du livre, aima-python, contient toujours le code du chapitre 19 dans knowledge.py : current_best_learning (Figure 19.2), version_space_learning (Figure 19.3) et minimal_consistent_det (Figure 19.8). Un sous-ensemble auto-contenu (stdlib pure, licence MIT avec attribution) est vendore dans reference/aima_knowledge.py. FOIL (Figure 19.12) en est exclu : il depend de tout logic.py ; l’induction de clauses de Horn est traitee en SL-4.

La différence cle avec notre implementation des sections 4-5 : l’espace d’hypotheses d’AIMA est disjonctif. Une hypothese y est une liste de conjonctions (dictionnaires attribut -> valeur, avec '!' pour une valeur interdite), et la generalisation peut ajouter une disjonction (add_or) au lieu de seulement relacher des contraintes. Or la section 8 a montre que sur nos 12 exemples, aucune conjonction unique n’est consistante — c’est précisément ce qui effondre notre Version Space conjonctif. L’algorithme de la Figure 19.2, lui, devrait reussir.

Note d’honnetete intellectuelle : le vendoring a revele un bug dans le code upstream. Dans generalizations(), deux branches font hypotheses += h2 au lieu de hypotheses.append(h2) : la liste de candidats est etendue avec les disjoncts (dictionnaires) au lieu de recevoir l’hypothese (liste de dictionnaires), et guess_value() crashe ensuite sur les cles. Les tests du depot AIMA ne couvrent jamais ces branches. La copie vendoree est corrigee (commentaires CoursIA fix dans le fichier) — relire le code de reference qu’on importe n’est jamais du temps perdu.

# L'algorithme de la Figure 19.2 (depot AIMA) sur NOS 12 exemples
import random
import sys
import time

sys.path.insert(0, "reference")
from aima_knowledge import current_best_learning, guess_value

# Conversion : notre format (cle "WillWait") -> format AIMA (cle "GOAL")
aima_examples = [{**{k: v for k, v in e.items() if k != "WillWait"},
                  "GOAL": e["WillWait"]} for e in EXAMPLES]

# generalizations()/specializations() melangent leurs candidats (shuffle) :
# la recherche est stochastique, on fixe la graine pour la reproductibilite.
random.seed(42)

# Hypothese initiale = le premier exemple positif, comme notre CBH (section 4)
first_pos = next(e for e in aima_examples if e["GOAL"])
initial_h = [{k: v for k, v in first_pos.items() if k != "GOAL"}]

t0 = time.perf_counter()
h = current_best_learning(aima_examples, initial_h)
elapsed = time.perf_counter() - t0

print(f"Hypothese trouvee : {len(h)} disjonction(s) en {elapsed:.2f}s")
for i, d in enumerate(h, 1):
    print(f"  D{i}: {d}")

correct = sum(guess_value(e, h) == e["GOAL"] for e in aima_examples)
print(f"\nAccuracy sur les 12 exemples : {correct}/{len(aima_examples)}")

Hypothese trouvee : 5 disjonction(s) en 0.02s
  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'}

Accuracy sur les 12 exemples : 12/12

Interpretation : ce que la disjonction debloque

La ou notre Version Space conjonctif s’est effondre (section 5 : aucune conjonction unique n’est consistante avec les 12 exemples), current_best_learning trouve une hypothese 100% consistante en quelques disjonctions : l’exemple problematique qui eliminait toutes les conjonctions est simplement absorbe par une nouvelle disjonction (add_or), construite a partir de ses propres attributs.

Trois observations :

Le biais de representation etait la vraie limite. Le passage conjonctif -> disjonctif suffit : même stratégie de recherche (specialiser sur faux positif, generaliser sur faux negatif, backtracking), espace d’hypotheses plus riche. C’est la reponse directe a la limite n. 1 du tableau de la section 8.
Pas de biais d’Occam. L’algorithme retourne la première hypothese consistante trouvee, pas la plus simple : plusieurs disjonctions très spécifiques (proches d’un par-coeur des exemples positifs) plutot qu’une règle compacte. Une hypothese disjonctive consistante existe toujours — au pire, la liste des exemples positifs eux-mêmes. La compression (peu de disjonctions, chacune générale) est ce que viseront les arbres de decision (ID3/C4.5) et l’induction de règles.
Recherche stochastique. Le shuffle() interne rend le résultat dependant de la graine : changez random.seed(42) et vous obtiendrez une autre hypothese consistante — une illustration concrete du fait que l’espace contient beaucoup de solutions, sans préférence entre elles.

Complexite de l’enonce, rasoir d’Occam et MDL

La section 9 a montre que current_best_learning reussit la ou notre Version Space conjonctif s’effondrait. Mais relisez l’observation n. 2 ci-dessus : l’algorithme retourne la première hypothese consistante trouvee, sans biais de simplicite. C’est précisément le fil conducteur annonce en section 3 qu’il faut maintenant rendre operationnel.

Le cout d’une exception. Ajouter un conjoint (specialiser) ou un disjonct (generaliser par add_or) fait grandir l’enonce. Un enonce plus long couvre ses exemples d’entrainement en les memorisant plutot qu’en capturant la règle sous-jacente : il generalise mal. D’ou le principe du rasoir d’Occam (ou, plus formellement, de la longueur de description minimale, MDL) : parmi les hypotheses consistantes, preferer la plus simple.

Recommencer les reductions. Un algorithme qui tient ce biais ne se contente pas d’ajouter des exceptions : après chaque croissance, il recommence les reductions (enlever un conjoint, supprimer un disjonct) tant que la consistance est preservee. C’est ce que fait FOIL (AIMA 19.5, induction logique inductive top-down), dont l’heuristique de gain d’information penalise les clauses longues ; FOIL est traite en SL-4. La metrique statement_size ci-dessous en donne un echo minimal.

L’exception parfois inevitable. Et c’est ici que la nuance compte : la consistance peut forcer une exception. Le domaine du restaurant le demontre. La section 5 a montre qu’aucune conjonction unique n’est consistante avec les 12 exemples (le Version Space s’effondre) ; la section 9 vient de montrer que la seule voie vers une hypothese 12/12 consistante est d’ajouter des disjonctions. La metrique d’Occam n’interdit donc pas les exceptions, elle les minimise sous contrainte de consistance. En cas de conflit, la consistance l’emporte sur la simplicite (un modèle complexe mais juste bat un modèle simple mais faux) ; Occam sert alors a departager les hypotheses consistantes entre elles, en privilegiant celle qui emploie le moins d’exceptions.

# Complexite de l'enonce : un rasoir d'Occam operationnel (Minimum Description Length)
#
# Toute croissance de l'hypothese (ajout d'un conjoint ou d'un disjonct) a un cout :
# un modele plus long memorise plutot qu'il ne generalise. La metrique ci-dessous
# mesure la taille de l'enonce. CBH (section 4) et le Version Space (section 5)
# ne l'utilisent PAS : ils gardent la PREMIERE hypothese consistante, pas la plus
# simple. FOIL (AIMA 19.5, induction logique inductive top-down) l'integre au
# contraire pour penaliser les clauses longues.


def statement_size_conjunctive(h: Hypothesis) -> int:
    """Taille d'une hypothese conjonctive = nombre de conditions explicites.

    Chaque contrainte non-joker (ni '?', ni None) est une condition de l'enonce.
    Plus ce nombre est grand, plus l'enonce est long (plus d'exceptions negatives).
    """
    return sum(1 for v in h if v is not None and v != "?")


def statement_size_disjunctive(h: list) -> int:
    """Taille d'une hypothese disjonctive (format aima-python) = somme des
    conditions de chaque disjonction (branche).

    Le nombre de branches est aussi un cout : chaque disjonction est une
    exception positive ajoutee pour couvrir un exemple rebelle.
    """
    return sum(len(branch) for branch in h)


# (1) Sur le resultat CBH conjonctif de la section 4
print("CBH (section 4, representation conjonctive) :")
print(f"  Hypothese finale : {cbh_result}")
print(f"  statement_size   : {statement_size_conjunctive(cbh_result)} condition(s)")
print(f"  -> CBH a garde la PREMIERE hypothese consistante (ici 1 condition,")
print(f"     Hungry=Yes) ; il n'a pas cherche la plus simple parmi les consistantes,")
print(f"     il n'a simplement pas de rasoir.")
print()

# (2) Sur l'hypothese disjonctive AIMA de la section 9
print("AIMA current_best_learning (section 9, representation disjonctive) :")
print(f"  Hypothese : {len(h)} disjonction(s)")
print(f"  statement_size : {statement_size_disjunctive(h)} conditions au total")
print(f"  -> 5 disjonctions tres specifiques : croissance abusive. Le rasoir")
print(f"     d'Occam (MDL) chercherait l'hypothese consistante la plus compacte")
print(f"     (cf. exercice 5) : minimiser le nombre d'exceptions, pas les eliminer.")

CBH (section 4, representation conjonctive) :
  Hypothese finale : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')
  statement_size   : 1 condition(s)
  -> CBH a garde la PREMIERE hypothese consistante (ici 1 condition,
     Hungry=Yes) ; il n'a pas cherche la plus simple parmi les consistantes,
     il n'a simplement pas de rasoir.

AIMA current_best_learning (section 9, representation disjonctive) :
  Hypothese : 5 disjonction(s)
  statement_size : 28 conditions au total
  -> 5 disjonctions tres specifiques : croissance abusive. Le rasoir
     d'Occam (MDL) chercherait l'hypothese consistante la plus compacte
     (cf. exercice 5) : minimiser le nombre d'exceptions, pas les eliminer.

10. Exercices

Les exemples guides ci-dessous sont resolus et commentes ; les exercices sont a completer par vos soins. Chaque exercice reutilise les implementations du notebook (current_best_hypothesis, candidate_elimination, count_errors).

Exemple guidé : CBH conjonctif et l’ordre des exemples

CBH (section 4) construit son hypothèse exemple par exemple : l’ordre de présentation peut donc l’amener à explorer des chemins différents. On teste ici une question précise : le faux positif résiduel de la version conjonctive est-il un accident d’ordre, ou une limite structurelle ? On rejoue donc CBH en plaçant les exemples négatifs en premier, puis on compare au résultat de la section 4.

# Exemple guide : CBH avec un ordre different (negatifs d'abord)
positifs = [e for e in EXAMPLES if e["WillWait"]]
negatifs = [e for e in EXAMPLES if not e["WillWait"]]

reordered = negatifs + positifs

cbh_reord, trace_reord = current_best_hypothesis(reordered)

print(f"Hypothese CBH (negatifs d'abord) : {cbh_reord}")
fp_r, fn_r = count_errors(cbh_reord, EXAMPLES)
print(f"Faux positifs : {fp_r}, Faux negatifs : {fn_r}")
print(f"Consistante : {is_consistent(cbh_reord, EXAMPLES)}")

Hypothese CBH (negatifs d'abord) : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')
Faux positifs : 1, Faux negatifs : 0
Consistante : False

Interprétation : l’ordre ne sauve pas la représentation conjonctive

Avec les négatifs en premier, CBH retombe sur exactement le même résultat qu’avec l’ordre original (section 4) : l’hypothèse Hungry=Yes (tous les autres attributs en ?), avec 1 faux positif résiduel.

Aspect	Observation
Hypothèse finale	`('?', '?', '?', 'Yes', '?', ...)` — Hungry=Yes
Consistance	Non — 1 faux positif, irréductible
Effet de l’ordre	Aucun ici : le mur est atteint quel que soit l’ordre

Le point pédagogique n’est donc pas l’instabilité de CBH selon l’ordre, mais ce que cette stabilité-dans-l’échec révèle : le faux positif n’est pas un accident d’ordre, c’est la signature du biais de représentation conjonctif. Aucune conjonction unique ne sépare les 12 exemples — précisément l’effondrement diagnostiqué à la section 5 (Version Space vide) et formalisé au tableau de la section 8.

Et ce mur n’est pas une fatalité de l’algorithme : c’est une limite de l’espace d’hypothèses. La section 9 le franchit sans changer de stratégie de recherche — current_best_learning (Figure 19.2 d’AIMA) autorise les disjonctions (add_or) et atteint 100 % de consistance (12/12) sur ces mêmes 12 exemples. C’est le passage conjonctif → disjonctif, et non un réglage d’ordre ou un autre algorithme conjonctif comme le Version Space, qui résout réellement le problème.

Exemple guide 1 : CBH avec ordre aleatoire

Une intuition courante : comme CBH ne garde qu’une seule hypothese et l’ajuste au gre des exemples, son résultat pourrait dependre fortement de l’ordre d’arrivee. Verifions-le en relancant CBH sur trois ordres aleatoires (seeds distinctes) et en comparant les hypotheses finales. Le résultat est surprenant et revele la vraie limite de CBH sur ces données.

Étapes (resolues ci-dessous) : 1. Melangez les exemples avec import random; random.shuffle(shuffled) 2. Executez CBH sur les exemples melanges 3. Repetez 3 fois et comparez les résultats

import random

# Exemple guide : CBH avec ordre aleatoire -- intuition d'instabilite a l'epreuve
# Intuition : CBH ne gardant qu'UNE hypothese ajustee exemple par exemple,
# l'ordre d'arrivee devrait fortement changer le resultat. Verifions sur 3 ordres
# aleatoires (seeds distinctes) et confrontons a l'intuition.

print("CBH sur 3 ordres aleatoires (seeds 0, 7, 42) :")
print("=" * 64)

results = {}
for seed in (0, 7, 42):
    random.seed(seed)
    shuffled = EXAMPLES.copy()
    random.shuffle(shuffled)
    h, _trace = current_best_hypothesis(shuffled)
    fp, fn = count_errors(h, EXAMPLES)
    results[seed] = h
    print(f"seed={seed:>2} | hypothese finale : {h}")
    print(f"       | faux positifs={fp}, faux negatifs={fn}, consistante={is_consistent(h, EXAMPLES)}")
    print()

distinct = len(set(results.values()))
print(f"Hypotheses distinctes sur 3 seeds : {distinct}/3")
print()
print("Constat :")
print("- CBH converge vers la MEME hypothese sur 3 ordres differents : elle est STABLE")
print("  ici, contrairement a l'intuition d'instabilite.")
print("- MAIS cette hypothese n'est PAS consistante (1 faux positif).")
print("- Interpretation : le concept 'WillWait' n'est PAS representable par une seule")
print("  conjonction d'attributs. CBH (une seule conjonction) ne peut donc PAS")
print("  l'apprendre parfaitement, quel que soit l'ordre. C'est une limite de PUISSANCE")
print("  D'EXPRESSION de l'espace d'hypotheses, pas d'instabilite d'ordre.")
print()
print("Le Version Space (section 5) garde TOUTES les hypotheses consistantes : il")
print("caracterise exactement ce qu'une conjonction peut representer, et permet de")
print("mesurer si une seule conjonction suffit pour ce concept.")

CBH sur 3 ordres aleatoires (seeds 0, 7, 42) :
================================================================
seed= 0 | hypothese finale : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')
       | faux positifs=1, faux negatifs=0, consistante=False

seed= 7 | hypothese finale : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')
       | faux positifs=1, faux negatifs=0, consistante=False

seed=42 | hypothese finale : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')
       | faux positifs=1, faux negatifs=0, consistante=False

Hypotheses distinctes sur 3 seeds : 1/3

Constat :
- CBH converge vers la MEME hypothese sur 3 ordres differents : elle est STABLE
  ici, contrairement a l'intuition d'instabilite.
- MAIS cette hypothese n'est PAS consistante (1 faux positif).
- Interpretation : le concept 'WillWait' n'est PAS representable par une seule
  conjonction d'attributs. CBH (une seule conjonction) ne peut donc PAS
  l'apprendre parfaitement, quel que soit l'ordre. C'est une limite de PUISSANCE
  D'EXPRESSION de l'espace d'hypotheses, pas d'instabilite d'ordre.

Le Version Space (section 5) garde TOUTES les hypotheses consistantes : il
caracterise exactement ce qu'une conjonction peut representer, et permet de
mesurer si une seule conjonction suffit pour ce concept.

Exercice 1 (variation) : Taux de consistance de CBH

L’exemple guide compare 3 ordres et trouve une hypothese stable mais NON consistante. Generalisez la mesure : executez CBH sur 20 graines différentes et calculez le taux de consistance – la proportion de graines pour lesquelles CBH aboutit a une hypothese consistante (is_consistent vrai). Affichez aussi le nombre d’hypotheses distinctes produites.

Indices : 1. Boucle for seed in range(20) : random.seed(seed), copiez + melangez EXAMPLES, lancez current_best_hypothesis. 2. Comptez les is_consistent(h, EXAMPLES) vrais -> taux = nb_consistantes / 20. 3. Comptez les hypotheses distinctes avec un set. 4. Conclusion : un taux faible confirme que le concept depasse l’espace d’une seule conjonction – c’est alors le Version Space (section 5) qui le met en evidence.

# Exercice 1 (variation) : Taux de consistance de CBH
# TODO etudiant : executez CBH sur 20 graines, mesurez le taux de consistance
# Etape 1 : for seed in range(20): random.seed(seed); melangez EXAMPLES; current_best_hypothesis
# Etape 2 : comptez les hypotheses consistantes (is_consistent) -> taux = nb_consistantes / 20
# Etape 3 : comptez les hypotheses distinctes (len(set(...)))
# Indice : un taux faible confirme que le concept depasse l'espace d'une seule conjonction.
print("Exercice a completer : mesurez le taux de consistance de CBH sur 20 graines")

Exercice a completer : mesurez le taux de consistance de CBH sur 20 graines

Exemple guide 2 : Version Space sur un sous-ensemble

L’intuition naive dit qu’avec moins d’exemples, le Version Space est plus grand (moins contraint). Verifions-le : lancons Candidate Elimination sur les 6 premiers exemples seulement, puis comparons au résultat sur les 12. La surprise – que nous allons interpreter – est que le Version Space ne fait pas que retroceder : il peut converger (G == S) puis s’effondrer (G et S vides).

# Exemple guide 2 : Version Space sur un sous-ensemble
# On lance Candidate Elimination sur les 6 premiers exemples, puis on compare
# au resultat sur les 12 exemples (section precedente).
G_sub, S_sub, trace_sub = candidate_elimination(EXAMPLES[:6])

print("Candidate Elimination sur EXAMPLES[:6] (6 exemples) :")
print(f"  |G-set| = {len(G_sub)}    |S-set| = {len(S_sub)}")
for g in sorted(G_sub):
    print(f"  G : {g}")
for s in sorted(S_sub):
    print(f"  S : {s}")

# Les deux bornes ont converge vers la MEME hypothese.
print(f"\nG == S ? {sorted(G_sub) == sorted(S_sub)}")
print("=> Le Version Space s'est reduit a une hypothese unique : Hungry = Yes.")

# Comparaison avec les 12 exemples (section 5).
G_full, S_full, _ = candidate_elimination(EXAMPLES)
print(f"\nSur les 12 exemples : |G| = {len(G_full)}, |S| = {len(S_full)}")
if len(G_full) == 0:
    print("=> Le Version Space est VIDE : aucune conjonction n'est coherente avec les 12 exemples.")

# Tableau de convergence : |G| et |S| selon le nombre d'exemples k.
print("\nConvergence du Version Space selon le nombre d'exemples k :")
print("  k  | |G| | |S| | etat")
print(" " + "-" * 42)
for k in range(1, len(EXAMPLES) + 1):
    Gk, Sk, _ = candidate_elimination(EXAMPLES[:k])
    if len(Gk) == 0:
        etat = "VIDE (effondrement)"
    elif sorted(Gk) == sorted(Sk):
        etat = "converge (G == S)"
    else:
        etat = f"borne G={len(Gk)}, S={len(Sk)}"
    print(f" {k:2d} |   {len(Gk)} |   {len(Sk)} | {etat}")
# Indice : le Version Space converge DES k=6 (G == S = Hungry=Yes), puis
# s'effondre au 10e exemple (k=10). Le concept WillWait n'est PAS
# representable par une seule conjonction : meme limite d'expression que
# CBH (Ex1), mais Version Space la revele comme |G| = |S| = 0 (VS vide).

Candidate Elimination sur EXAMPLES[:6] (6 exemples) :
  |G-set| = 1    |S-set| = 1
  G : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')
  S : ('?', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')

G == S ? True
=> Le Version Space s'est reduit a une hypothese unique : Hungry = Yes.

Sur les 12 exemples : |G| = 0, |S| = 0
=> Le Version Space est VIDE : aucune conjonction n'est coherente avec les 12 exemples.

Convergence du Version Space selon le nombre d'exemples k :
  k  | |G| | |S| | etat
 ------------------------------------------
  1 |   1 |   1 | borne G=1, S=1
  2 |   1 |   1 | borne G=1, S=1
  3 |   3 |   1 | borne G=3, S=1
  4 |   3 |   1 | borne G=3, S=1
  5 |   1 |   1 | borne G=1, S=1
  6 |   1 |   1 | converge (G == S)
  7 |   1 |   1 | converge (G == S)
  8 |   1 |   1 | converge (G == S)
  9 |   1 |   1 | converge (G == S)
 10 |   0 |   0 | VIDE (effondrement)
 11 |   0 |   0 | VIDE (effondrement)
 12 |   0 |   0 | VIDE (effondrement)

Exercice 2 (variation) : Le Version Space depend-il de l’ordre des exemples ?

Current-Best-Hypothesis (Exercice 1) produit une hypothese unique qui peut dependre de l’ordre des exemples. Le Version Space, lui, conserve toutes les hypotheses coherentes. L’ensemble final est-il invariant quand on reordonnance les exemples ? Fixez une graine, melangez une copie de EXAMPLES, relancez candidate_elimination sur les 12 exemples melanges, et comparez la taille finale du Version Space au résultat en ordre original.

Indices : 1. random.seed(42) puis copiez EXAMPLES et random.shuffle la copie (ne mutez pas l’original). 2. Appelez candidate_elimination(shuffled) et lisez |G| final. 3. Refaites avec 2 autres graines. Que constatez-vous sur |G| final ? 4. Conclusion : l’ensemble des hypotheses coherentes est une propriete du jeu de données (intersection d’ensembles), pas de l’ordre de parcours – contrairement a CBH.

# Exercice 2 (variation) : Le Version Space depend-il de l'ordre des exemples ?
# TODO etudiant : melanger EXAMPLES (sur une COPIE), relancer candidate_elimination, comparer |G| final
import random
# Etape 1 : fixer une graine et melanger UNE COPIE de EXAMPLES
random.seed(42)
shuffled = None  # TODO etudiant : copier EXAMPLES puis random.shuffle la copie
# Etape 2 : executer Candidate Elimination sur la liste melangee
result_shuffled = None  # TODO etudiant : remplacer par candidate_elimination(shuffled)
# Etape 3 : afficher |G| final et conclure sur l'invariance par ordre
if result_shuffled is not None:
    G_sh, S_sh, _ = result_shuffled
    print(f"Version Space sur exemples melanges : |G| = {len(G_sh)}, |S| = {len(S_sh)}")
else:
    print("Exercice a completer : melangez EXAMPLES puis appelez candidate_elimination")
# Indice : l'ensemble des hypotheses coherentes avec un jeu de donnees est une
# propriete du JEU de donnees (intersection d'ensembles), pas de l'ordre.
# Comparez au comportement order-dependant de CBH (Ex1).

Exercice a completer : melangez EXAMPLES puis appelez candidate_elimination

Exemple guide 3 : Apprentissage de règles par couverture séquentielle

Jusqu’ici, CBH (section 4) et le Version Space (section 5) cherchent une seule hypothese conjonctive. Or la section 5 a montre qu’aucune conjonction unique n’est consistante avec nos 12 exemples : le Version Space s’effondre (ensemble vide). Comment apprendre malgre tout ? En relachant l’hypothese d’unicite : on apprend une disjonction de règles – c’est l’algorithme de couverture séquentielle (AIMA 19.5, famille de FOIL).

Principe. Une règle est une conjonction (une Hypothesis). L’apprenant : 1. Part de l’ensemble des exemples positifs. 2. Apprend une règle qui couvre des positifs et aucun negatif (règle pure), en demarrant de la règle la plus générale (G0) et en specialisant contre les negatifs couverts. 3. Retire les positifs couverts par cette règle, puis recommence (étape 2) tant qu’il reste des positifs.

L’union (disjonction) des règles produites couvre alors tous les positifs sans toucher les negatifs – la ou une conjonction unique echouait.

Indice (origine de la solution) : pour apprendre une règle, partez de G0 et appelez specialize_against contre chaque negatif couvert ; gardez la specialisation qui couvre le plus de positifs (couverture maximale), puis reiterez jusqu’a zero negatif couvert.

# Exemple guide 3 : Apprentissage de regles par couverture sequentielle
# Adaptation de l'algorithme de couverture sequentielle (AIMA 19.5 / FOIL) au
# domaine conjonctif du notebook. Une REGLE = une Hypothese (conjonction) ; la
# disjonction des regles couvre les positifs la ou une conjonction unique echoue.
from typing import Optional

Rule = tuple  # alias : une regle est une Hypothese (conjonction)


def learn_one_rule(positifs: list[dict], negatifs: list[dict]) -> Optional[Rule]:
    """Apprend UNE regle pure : couvre >=1 positif et 0 negatif.

    Strategie : partir de la regle la plus generale (G0 couvre tout), puis
    specialiser contre les NEGATIFS couverts jusqu'a n'en couvrir aucun.
    Tie-break : la specialisation qui couvre le plus de positifs (couverture max).
    """
    if not positifs:
        return None
    h = G0  # regle la plus generale
    for _ in range(len(ATTRIBUTES) + 1):  # garde-fou
        neg_couverts = [n for n in negatifs if covers(h, n)]
        if not neg_couverts:
            return h if any(covers(h, p) for p in positifs) else None
        # Specialiser contre le premier negatif couvert ; couverture positive max.
        cands = []
        for neg in neg_couverts:
            for spec in specialize_against(h, neg):
                if any(covers(spec, p) for p in positifs):  # garde au moins 1 positif
                    n_pos = sum(1 for p in positifs if covers(spec, p))
                    cands.append((n_pos, spec))
        if not cands:
            return None  # aucune specialisation ne preserve de positif
        _, h = max(cands, key=lambda t: t[0])
    return h


def sequential_covering(examples: list[dict], verbose: bool = True) -> list[Rule]:
    """Couverture sequentielle (AIMA 19.5) : une liste de regles dont l'union
    (disjonction) couvre TOUS les positifs et AUCUN negatif."""
    positifs = [e for e in examples if e["WillWait"]]
    negatifs = [e for e in examples if not e["WillWait"]]
    rules: list[Rule] = []
    restants = list(positifs)
    while restants:
        rule = learn_one_rule(restants, negatifs)
        if rule is None:
            if verbose:
                print(f"  ! Impossible d'apprendre une regle pure ({len(restants)} positif(s) restant(s)).")
            break
        couverts = [p for p in restants if covers(rule, p)]
        rules.append(rule)
        restants = [p for p in restants if not covers(rule, p)]
        if verbose:
            print(f"  Regle {len(rules)} : {rule}  -> couvre {len(couverts)} positif(s), reste {len(restants)}.")
    return rules


def human_rule(rule: Rule) -> str:
    """Decode une regle en condition lisible (conditions non '?'/'None')."""
    conds = [f"{ATTRIBUTES[i]}={rule[i]}" for i in range(len(ATTRIBUTES)) if rule[i] not in ("?", None)]
    return " ET ".join(conds) if conds else "(toujours vraie)"


# --- Execution sur les 12 exemples du restaurant ---
print("Apprentissage de regles par couverture sequentielle :")
print("=" * 64)
regles = sequential_covering(EXAMPLES, verbose=True)

print(f"\n{len(regles)} regle(s) apprise(s) :")
for i, r in enumerate(regles, 1):
    print(f"  R{i} : WillWait si ( {human_rule(r)} )")

# --- Evaluation : la disjonction couvre-t-elle exactement les positifs ? ---
def predicts(rules: list[Rule], example: dict) -> bool:
    """Prediction = union (disjonction) des regles : True si l'une couvre."""
    return any(covers(r, example) for r in rules)

tp = sum(1 for e in EXAMPLES if predicts(regles, e) and e["WillWait"])
fp = sum(1 for e in EXAMPLES if predicts(regles, e) and not e["WillWait"])
fn = sum(1 for e in EXAMPLES if not predicts(regles, e) and e["WillWait"])
tn = sum(1 for e in EXAMPLES if not predicts(regles, e) and not e["WillWait"])
print(f"\nEvaluation de l'ensemble de regles (union/disjonction) :")
print(f"  Vrais positifs : {tp}/6 | Faux positifs : {fp}/6 | Faux negatifs : {fn}/6 | Vrais negatifs : {tn}/6")
print(f"  Accuracy : {(tp + tn) / len(EXAMPLES):.3f}")
print(f"  => {len(regles)} regles suffisent la ou le Version Space (1 conjonction) s'effondrait.")

Apprentissage de regles par couverture sequentielle :
================================================================
  Regle 1 : ('?', 'No', '?', 'Yes', '?', '?', '?', '?', '?', '?')  -> couvre 4 positif(s), reste 2.
  Regle 2 : ('No', '?', '?', 'Yes', '?', '?', '?', '?', '?', '?')  -> couvre 1 positif(s), reste 1.
  Regle 3 : ('Yes', 'Yes', '?', '?', '?', '$', '?', '?', '?', '?')  -> couvre 1 positif(s), reste 0.

3 regle(s) apprise(s) :
  R1 : WillWait si ( Bar=No ET Hungry=Yes )
  R2 : WillWait si ( Alternate=No ET Hungry=Yes )
  R3 : WillWait si ( Alternate=Yes ET Bar=Yes ET Price=$ )

Evaluation de l'ensemble de regles (union/disjonction) :
  Vrais positifs : 6/6 | Faux positifs : 0/6 | Faux negatifs : 0/6 | Vrais negatifs : 6/6
  Accuracy : 1.000
  => 3 regles suffisent la ou le Version Space (1 conjonction) s'effondrait.

Interpretation : la disjonction debloque ce que la conjonction ne peut exprimer

L’algorithme apprend typiquement 3 règles dont l’union couvre les 6 positifs sans aucun faux positif (accuracy 1.000), par exemple :

R1 : Bar=No ET Hungry=Yes (couvre la majorite des positifs),
R2 : Alternate=No ET Hungry=Yes,
R3 : une conjonction plus fine pour les positifs restants.

C’est précisément la lecon annoncee en section 5 : aucune conjonction unique n’etait consistante avec les 12 exemples (le Version Space etait vide), mais une disjonction de quelques règles y parvient parfaitement. La couverture séquentielle relache l’hypothese d’unicite de l’hypothese – c’est le pont vers FOIL (AIMA 19.5) et l’apprentissage de règles en general.

Deux points de vigilance : 1. Biais de couverture : a chaque étape, on garde la specialisation qui couvre le plus de positifs. Ce greedy est rapide mais n’est pas optimal – un choix différent produirait un autre jeu de règles. C’est l’equivalent, pour les règles, du biais de simplicite absent de CBH (cf. section 9 et l’Exercice 5). 2. Surapprentissage : si l’on ancre chaque règle sur un seul positif (en partant de S0 au lieu de G0), on obtient 6 règles de 1 positif chacune – une memorisation inutile. Partir de G0 et specialiser produit des règles générales : c’est la différence entre apprendre un concept et recopier les données.

Exemple guide : Reflexion corrigee (synthese)

Pour conclure, voici une demonstration de la demarche attendue sur trois questions de synthese, avec leur correction. Observez la structure des reponses : un mécanisme précis (pas une generalite), puis sa consequence pratique. L’exercice 4 ci-dessous vous propose trois questions du même type — mais distinctes — a traiter de la même maniere.

Question	Reponse
Pourquoi CBH depend de l’ordre des exemples, mais pas le Version Space ?	Le VS maintient TOUTES les hypotheses consistantes, pas une seule. L’ordre n’affecte que la vitesse de convergence, pas le résultat final.
Pourquoi la prediction par vote majoritaire (section 6) peut-elle etre utile alors même que le Version Space n’a pas converge ?	Chaque hypothese consistante “vote” sur le nouvel exemple : si une large majorite predit la même classe, la prediction est fiable sans attendre la convergence. Seuls les cas partages (vote proche de 50/50) doivent etre refuses ou renvoyes a l’acquisition de nouveaux exemples.
Pourquoi le Version Space est-il fragile face au bruit ?	Un seul exemple contradictoire elimine TOUTES les hypotheses, vidant le VS. Pas de mécanisme de tolerance.

Exercice 4 : Reflexion

A votre tour, sur le modèle de l’exemple guide ci-dessus. Repondez aux questions suivantes en vous appuyant sur les algorithmes implementes plus haut (CBH, Candidate Elimination) : pour chaque reponse, identifiez le mécanisme en jeu, puis sa consequence pratique.

Question	Reponse
Donnez une sequence concrete d’exemples (positifs/negatifs) qui force CBH a backtracker, alors que le Version Space converge sans jamais revenir en arriere.	(a completer)
Un concept disjonctif comme “animal = chien OU chat” n’est pas capturable par une hypothese conjonctive unique. Pourquoi ? Que faudrait-il changer dans la representation des hypotheses pour le permettre ?	(a completer)
La complexite memoire du Version Space est O(\|G\| + \|S\|). Decrivez un cas ou \|G\| ou \|S\| explose, et la consequence pratique sur l’apprentissage.	(a completer)

Exemple guide 5 : La consistance sans Occam (mesure sur 20 graines)

La section 9 a montre que current_best_learning est stochastique (shuffle interne des candidats) et sans biais de simplicite : il retourne la première hypothese consistante trouvee. Transformons ces deux observations en mesure.

Principe. Pour 20 graines différentes : 1. Fixer random.seed(seed) – seul le shuffle interne change, initial_h (construit sur le premier positif) reste invariant d’une graine a l’autre. 2. Relancer current_best_learning(aima_examples, initial_h). 3. Mesurer la taille de l’hypothese via statement_size_disjunctive (somme des conditions de chaque disjonction) et le nombre de branches. 4. Verifier que chaque hypothese reste 12/12 consistante (via guess_value).

On obtient ainsi la distribution des tailles d’enonce parmi toutes les solutions que l’algorithme juge “aussi bonnes” – une mesure directe du vide laisse par l’absence de rasoir d’Occam.

# Exemple guide 5 : La consistance sans Occam (mesure sur 20 graines)
# On transforme les 2 observations de la section 9 (recherche stochastique + absence
# de biais de simplicite) en mesure : echantillonner current_best_learning sur 20 graines,
# mesurer la taille de l'enonce (statement_size_disjunctive), verifier la consistance 12/12.
# Indice : initial_h depend du premier positif, il ne change pas d'une graine a l'autre ;
#          seule la recherche (shuffle des candidats) change.

samples = []
for seed in range(20):
    random.seed(seed)  # seul le shuffle interne change ; initial_h (1er positif) est invariant
    h = current_best_learning(aima_examples, initial_h)
    # Taille = somme des conditions de chaque disjonction ; branches = nombre de disjonctions.
    taille = statement_size_disjunctive(h)
    n_branches = len(h)
    # Consistance : chaque exemple doit etre correctement classe par l'hypothese.
    correct = sum(guess_value(e, h) == e["GOAL"] for e in aima_examples)
    samples.append({"seed": seed, "branches": n_branches, "taille": taille, "correct": correct})

# --- Distribution des tailles d'enonce sur les 20 graines ---
tailles = [s["taille"] for s in samples]
branches = [s["branches"] for s in samples]
toutes_consistantes = all(s["correct"] == 12 for s in samples)

print("Echantillonnage de current_best_learning sur 20 graines :")
print("=" * 60)
print(f"{'Seed':>4} | {'Branches':>9} | {'Taille':>7} | {'Accuracy':>8}")
print("-" * 60)
for s in samples:
    print(f"{s['seed']:>4} | {s['branches']:>9} | {s['taille']:>7} | {s['correct']:>5}/12")

print()
print("Statistiques sur la taille de l'enonce (statement_size_disjunctive) :")
print(f"  Min : {min(tailles)} conditions")
print(f"  Max : {max(tailles)} conditions")
moyenne = sum(tailles) / len(tailles)
ecart_type = (sum((t - moyenne) ** 2 for t in tailles) / len(tailles)) ** 0.5
print(f"  Moyenne : {moyenne:.1f} conditions")
print(f"  Ecart-type : {ecart_type:.1f}")
print(f"  Toutes consistentes 12/12 : {toutes_consistantes}")

# L'hypothese la plus compacte trouvee par la recherche stochastique.
plus_compacte = min(samples, key=lambda s: (s["taille"], s["seed"]))
print(f"\nHypothese la plus compacte : seed={plus_compacte['seed']}, "
      f"{plus_compacte['branches']} branche(s), {plus_compacte['taille']} conditions.")

# Comparaison : le concept cible reel (section 8) est beaucoup plus compact.
print(f"\nConcept cible reel (section 8) : 2 clauses, 3 conditions au total.")
print(f"  => Occam prefererait cette forme compacte ; current_best_learning ne la cherche pas.")

Echantillonnage de current_best_learning sur 20 graines :
============================================================
Seed |  Branches |  Taille | Accuracy
------------------------------------------------------------
   0 |         4 |      25 |    12/12
   1 |         5 |      28 |    12/12
   2 |         5 |      31 |    12/12
   3 |         5 |      29 |    12/12
   4 |         6 |      38 |    12/12
   5 |         5 |      33 |    12/12
   6 |         6 |      30 |    12/12
   7 |         5 |      27 |    12/12
   8 |         6 |      44 |    12/12
   9 |         6 |      42 |    12/12
  10 |         6 |      31 |    12/12
  11 |         4 |      16 |    12/12
  12 |         5 |      31 |    12/12
  13 |         6 |      36 |    12/12
  14 |         6 |      38 |    12/12
  15 |         6 |      37 |    12/12
  16 |         6 |      33 |    12/12
  17 |         6 |      41 |    12/12
  18 |         6 |      38 |    12/12
  19 |         6 |      39 |    12/12

Statistiques sur la taille de l'enonce (statement_size_disjunctive) :
  Min : 16 conditions
  Max : 44 conditions
  Moyenne : 33.4 conditions
  Ecart-type : 6.5
  Toutes consistentes 12/12 : True

Hypothese la plus compacte : seed=11, 4 branche(s), 16 conditions.

Concept cible reel (section 8) : 2 clauses, 3 conditions au total.
  => Occam prefererait cette forme compacte ; current_best_learning ne la cherche pas.

Interpretation : toutes les solutions consistentes ne se valent pas

La mesure confirme quantitativement les deux observations de la section 9 :

Absence de biais de simplicite (observation n.2) : les 20 graines produisent 20 hypotheses TOUTES 12/12 consistantes, mais de tailles très différentes (typiquement de ~16 a ~44 conditions, soit un facteur ~3). L’algorithme n’en prefere aucune : il s’arrete a la première solution trouvee, sans chercher la plus compacte.
Recherche stochastique (observation n.3) : la dispersion de la taille (ecart-type non negligeable) illustre que le shuffle interne explore des regions différentes de l’espace des hypotheses a chaque graine – l’espace contient beaucoup de solutions, sans hiérarchie entre elles.

Ce qu’ajouterait le rasoir d’Occam (MDL). Le concept cible reel de la section 8 (Patrons=Some OU (Patrons=Full ET Hungry=Yes)) tient en 2 clauses / 3 conditions. L’hypothese la plus compacte trouvee ici fait ~16 conditions – soit ~5 fois plus. Un biais de simplicite (comme celui de FOIL, AIMA 19.5, ou des arbres de decision ID3/C4.5) chercherait explicitement la solution consistante la plus courte, au lieu de memoriser les exemples positifs sous forme de disjonctions très spécifiques.

Lien avec les exercices de reflexion (Ex4, Ex6). Cette mesure donne la matiere concrete pour repondre : la consistance seule est insuffisante – il faut un critere de sélection parmi les hypotheses consistantes, et Occam/MDL en est un. C’est aussi le pont avec la couverture séquentielle de l’Exemple guide 3, ou le tie-break “couverture maximale” etait une forme embryonnaire de ce biais.

Exercice 6 : Les quatre opérations et la tension Occam vs consistance

Repondez aux questions suivantes en vous appuyant sur le tableau des 4 opérations (section 3) et la discussion rasoir d’Occam / MDL (section 9). Pour chaque reponse, identifiez le mécanisme en jeu, puis sa consequence pratique — comme dans l’exemple guide de reflexion ci-dessus.

Question	Reponse
La section 5 montre qu’ajouter la condition `Hungry=Yes` (specialiser par conjonction) ne suffit pas a rendre une conjonction consistante. Selon le tableau des 4 opérations (section 3), a quel sens de la specialisation correspond cet ajout, et pourquoi cet echec pousse-t-il a recourir a l’autre sens (generaliser par disjonction, `add_or`) ?	(a completer)
Un etudiant propose d’eliminer toute erreur en ajoutant une exception (une disjonction) pour CHAQUE exemple positif mal classe. Quel est le cout de cette stratégie au sens du rasoir d’Occam (MDL) ? A partir de quand devient-elle neanmoins la seule option acceptable ?	(a completer)
CBH (section 4) et le Version Space (section 5) n’implantent aucun biais de simplicite. Donnez une situation concrete (sur le domaine du restaurant ou un autre) ou cela conduit a retenir une hypothese manifestement trop longue, et expliquez pourquoi FOIL (AIMA 19.5) l’eviterait.	(a completer)

11. Resume

Points cles

Concept	Description
Hypothese FOL	Conjonction de contraintes sur les attributs
Consistance	Pas de faux positifs ni de faux negatifs
Generalisation	Remplacer une contrainte par `?` (couvrir plus)
Specialisation	Remplacer `?` par une valeur (couvrir moins)
Generalisation/Specialisation : 2 sens	Chaque direction admet une opération qui reduit l’enonce et une qui l’augmente (exception positive par disjonction, negative par conjonction)
Rasoir d’Occam (MDL)	Parmi les hypotheses consistantes, preferer la plus simple ; minimiser les exceptions (cf. FOIL, AIMA 19.5), non les interdire
CBH	Maintient une seule hypothese, ajustee incrementalement
Version Space	Maintient G-set et S-set, represente toutes les hypotheses consistantes
Candidate Elimination	Algorithme pour mettre a jour G et S efficacement

Comparaison CBH vs Version Space

Critere	CBH	Version Space
Nombre d’hypotheses	1	Toutes (via frontieres)
Ordre-dépendance	Oui	Non
Backtracking	Possible	Jamais
Bruit	Robuste (peut revenir)	Fragile (VS vide)
Complexite memoire	O(1)	`O(\\|G\\| + \\|S\\|)`

Perspectives

Ce notebook a explore les méthodes d’apprentissage logique symbolique dans le cadre de la contrainte d’entrainement : trouver une hypothese H telle que H et les descriptions entrainent logiquement les classifications. L’algorithme CBH (Current-Best-Hypothesis) maintient une unique hypothese ajustee incrementalement par generalisation et specialisation, avec un risque de backtracking lorsque aucune specialisation consistante n’existe. L’algorithme Candidate Elimination resout ce problème en representant l’ensemble complet des hypotheses consistantes via les frontieres G-set et S-set, garantissant qu’aucune hypothese valide n’est oubliee. Cependant, les deux approches partagent des limites fondamentales : la fragilite face au bruit (un seul exemple mal etiquete vide le Version Space) et l’incapacite a representer des concepts disjonctifs avec des conjonctions pures.

Ces limites ont historiquement motive le passage a des modèles plus robustes : arbres de decision (ID3/C4.5) pour les disjonctions, modèles probabilistes (naive Bayes, regression logistique) pour la tolerance au bruit, et plus recemment les reseaux de neurones pour l’apprentissage de representations continues. Neanmoins, les concepts de generalisation, specialisation et espace de versions restent fondamentaux en apprentissage automatique symbolique et informent les méthodes avancees comme la programmation logique inductive (ILP) et l’apprentissage neuro-symbolique.

Le notebook suivant, SL-2 - Apprentissage et Connaissance, depasse le cadre inductif pur en integrant la connaissance prealable du domaine. Nous y decouvrirons l’apprentissage base sur les explications (EBL), qui extrait une règle générale d’un seul exemple par deduction, et l’apprentissage base sur la pertinence (RBL), qui reduit exponentiellement l’espace des hypotheses grace aux determinations.

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 (CBH, ordre personnalise)	Montrez deux ordres de presentation des exemples qui menent le CBH a des hypotheses finales différentes, puis changez la graine `random.seed(42)` de la section 9 (AIMA) : pourquoi l’hypothese change-t-elle alors que l’accuracy reste 12/12 ?
Ex. 2 (Version Space, sous-ensemble)	Sur votre sous-ensemble, identifiez l’exemple dont l’ajout reduit le plus le Version Space. Qu’est-ce qui rend un exemple informatif (raisonnez avec les frontieres S et G) ?
Ex. 3 (règles avec couverture)	Comparez vos règles a l’hypothese disjonctive AIMA de la section 9 : laquelle est la plus compacte ? Quel biais (rasoir d’Occam) ferait preferer l’une a l’autre, et lequel des deux algorithmes l’implemente ?
Ex. 4 (reflexion)	Donnez un domaine concret ou le biais conjonctif de ce notebook est le bon choix, et un ou il est catastrophique. Reliez votre reponse au theoreme no free lunch.
Ex. 5 (consistance sans Occam)	La section 8 prouve qu’aucune conjonction unique n’est consistante : la borne inferieure est donc 2 disjonctions. Votre echantillonnage de graines l’atteint-il ? Pourquoi un echantillonnage ne prouve jamais la minimalite, et quel type d’algorithme (exact, a la Popper de SL-4) fournirait ce certificat ?
Ex. 6 (4 opérations et tension Occam)	Parmi les 4 opérations du tableau de la section 3, lesquelles CBH (section 4) sait-il effectivement realiser avec sa representation conjonctive, et lesquelles lui sont interdites (d’ou son effondrement en section 5) ? Illustrez avec un exemple du restaurant ou la seule opération capable de restaurer la consistance est une croissance de l’enonce (une exception), et justifiez pourquoi le rasoir d’Occam l’accepte tout de même.

Ressources

Russell & Norvig, AI: A Modern Approach, 3e ed., Chapitre 19.1
Tom Mitchell, Machine Learning, Chapitre 2 (Concept Learning)
AIMA Python Code - Implementations de reference
Version Space - Wikipedia

Notebook suivant : SL-2 - Apprentissage et Connaissance

Retour : Index SymbolicLearning | SL-2 >>

Retour au sommet