SL-3 — Apprentissage Base sur la Pertinence (RBL Approfondi)

Navigation : Index | << SL-2 | SL-4 >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Formaliser les determinations et leurs proprietes mathematiques 2. Implementer et visualiser le treillis des determinations 3. Appliquer l’algorithme MINIMAL-CONSISTENT-DET sur des données réelles 4. Comparer la sélection d’attributs guidee par la connaissance (RBL) vs la sélection aveugle (sklearn) 5. Quantifier la reduction exponentielle de l’espace des hypotheses

Prerequis

• SL-1 (apprentissage logique, espaces d’hypotheses)
• SL-2 section 7 (introduction aux determinations)
• Bases de Python et structures de données

Duree estimee : 50 minutes

# Imports et configuration
from typing import Optional
from dataclasses import dataclass, field
from collections import defaultdict
import itertools
import math
import random

# Metadata du notebook
NOTEBOOK_INFO = {
    "title": "SL-3 - Apprentissage Base sur la Pertinence (RBL)",
    "series": "SymbolicLearning",
    "aima_chapters": ["19.4"],
    "date": "2026-05",
}

print(f"Notebook : {NOTEBOOK_INFO['title']}")
print(f"Chapitre AIMA : {', '.join(NOTEBOOK_INFO['aima_chapters'])}")

Notebook : SL-3 - Apprentissage Base sur la Pertinence (RBL)
Chapitre AIMA : 19.4

---

1. Introduction — Pourquoi la pertinence ?

Dans SL-2, nous avons introduit le concept de détermination. Ce notebook approfondit le cadre formel du Relevance-Based Learning (RBL, AIMA 19.4) : proprietes mathematiques, treillis, algorithme MINIMAL-CONSISTENT-DET et sélection d’attributs.

Le problème central

Soit un ensemble de \(n\) attributs decrivant chaque exemple. L’espace des hypotheses est de taille \(O(2^n)\) — il croit exponentiellement avec le nombre d’attributs.

La question cle : quels attributs sont pertinents pour prédire la cible ?

L’équation fondamentale du RBL

RBL repose sur la relation de consequence logique (entailment, AIMA Eq. 19.4) :

\[ \text{Background} \wedge \text{descriptions} \wedge \text{Classifications} \models \text{Hypothesis} \]

La différence avec EBL : dans EBL, Background explique complètement la classification. Dans RBL, Background contraint la forme de l’hypothese sans la déterminer entierement — il nous dit quels attributs considerer, mais pas la règle exacte.

Plan de ce notebook

Section	Contenu	Duree
2. Determinations	Formalisme, proprietes, vérification	10 min
3. Treillis des determinations	Visualisation, relations d’inclusion	10 min
4. Algorithme MINIMAL-CONSISTENT-DET	Implementation detaillee	10 min
5. sélection d’attributs guidee	RBL vs sklearn, comparaison	10 min
6. Determinations et sémantique web	Parallel RBL <-> OWL	5 min
7. Exercices	3 exercices pratiques	10 min

---

2. Determinations — Formalisme et proprietes

Definition formelle

Un ensemble d’attributs \(X = \{x_1, \ldots, x_k\}\) détermine l’attribut cible \(Y\) (note \(X > Y\)) si pour toute paire d’exemples qui ont les mêmes valeurs pour tous les attributs dans \(X\), ils ont aussi la même valeur pour \(Y\) :

\[ \forall e_1, e_2 \in D : \left(\forall x_i \in X : e_1[x_i] = e_2[x_i]\right) \Rightarrow e_1[Y] = e_2[Y] \]

Proprietes importantes

Monotonie : Si \(X > Y\) et \(X \subseteq X'\), alors \(X' > Y\). Ajouter des attributs a une détermination valide conserve sa validite.

Minimalite : Une détermination \(X > Y\) est minimale si aucun sous-ensemble strict de \(X\) ne détermine \(Y\). C’est la détermination la plus petite.

Unicite : La détermination minimale n’est pas forcement unique — il peut exister plusieurs ensembles minimaux différents.

Origine. Le formalisme logique des determinations (\(X > Y\)) comme base de l’apprentissage base sur la pertinence (RBL) vient de Davies, T. R. & Russell, S. J. (1987), A logical approach to reasoning by analogy, Proceedings of IJCAI-87 — qui montre comment une détermination connue rend l’apprentissage indépendant des attributs non-pertinents.

# Implementation : verification de determination avec diagnostic

@dataclass
class DeterminationResult:
    """Resultat de la verification d'une determination."""
    attrs: tuple[str, ...]
    target: str
    holds: bool
    violations: list[tuple[dict, dict]] = field(default_factory=list)
    coverage: int = 0  # nombre de groupes distincts

def check_determination(
    data: list[dict],
    det_attrs: list[str],
    target_attr: str
) -> DeterminationResult:
    """Verifie si det_attrs determinent target_attr avec diagnostic.
    
    Retourne un DeterminationResult avec les violations eventuelles.
    """
    groups: dict[tuple, list[dict]] = defaultdict(list)
    for row in data:
        key = tuple(row[a] for a in det_attrs)
        groups[key].append(row)
    
    violations = []
    for key, rows in groups.items():
        target_values = set(row[target_attr] for row in rows)
        if len(target_values) > 1:
            # Témoin = premier couple de lignes qui DIFFERENT sur la cible
            # (sinon le diagnostic exhibe deux lignes qui s'accordent).
            witness = None
            for i, row_a in enumerate(rows):
                for row_b in rows[i+1:]:
                    if row_a[target_attr] != row_b[target_attr]:
                        witness = (row_a, row_b)
                        break
                if witness:
                    break
            violations.append(witness)
    
    return DeterminationResult(
        attrs=tuple(det_attrs),
        target=target_attr,
        holds=len(violations) == 0,
        violations=violations,
        coverage=len(groups)
    )


# Exemple : proprietes chimiques et conductivite
# Quelle(s) propriete(s) determinent la conductivite electrique ?
copper_data = [
    {"metal": "Cu", "density": "high", "color": "orange", "state": "solid", "conductivity": "high"},
    {"metal": "Cu", "density": "high", "color": "orange", "state": "solid", "conductivity": "high"},
    {"metal": "Fe", "density": "high", "color": "gray",   "state": "solid", "conductivity": "medium"},
    {"metal": "Fe", "density": "high", "color": "gray",   "state": "solid", "conductivity": "medium"},
    {"metal": "Al", "density": "low",  "color": "silver", "state": "solid", "conductivity": "medium"},
    {"metal": "Al", "density": "low",  "color": "silver", "state": "solid", "conductivity": "medium"},
    {"metal": "Au", "density": "high", "color": "yellow", "state": "solid", "conductivity": "high"},
    {"metal": "Hg", "density": "high", "color": "silver", "state": "liquid", "conductivity": "low"},
    {"metal": "Na", "density": "low",  "color": "silver", "state": "solid", "conductivity": "medium"},
]

METAL_ATTRS = ["metal", "density", "color", "state"]

print("Donnees : proprietes metalliques et conductivite")
print("=" * 70)
print(f'{"Metal":6s} | {"Densite":8s} | {"Couleur":8s} | {"Etat":7s} | {"Conduct.":10s}')
print("-" * 70)
for row in copper_data:
    print(f"{row['metal']:6s} | {row['density']:8s} | {row['color']:8s} | {row['state']:7s} | {row['conductivity']:10s}")

print()
print("Verification des determinations :")
for attrs in [("metal",), ("density",), ("color",), ("state",), ("metal", "density"), ("density", "state")]:
    result = check_determination(copper_data, list(attrs), "conductivity")
    status = "OUI" if result.holds else "NON"
    print(f"  {str(attrs):30s} -> conductivity : {status} ({result.coverage} groupes)")
    for a, b in result.violations:
        print(f"        temoin : {a['metal']}({a['conductivity']}) vs {b['metal']}({b['conductivity']})")

Donnees : proprietes metalliques et conductivite
======================================================================
Metal  | Densite  | Couleur  | Etat    | Conduct.  
----------------------------------------------------------------------
Cu     | high     | orange   | solid   | high      
Cu     | high     | orange   | solid   | high      
Fe     | high     | gray     | solid   | medium    
Fe     | high     | gray     | solid   | medium    
Al     | low      | silver   | solid   | medium    
Al     | low      | silver   | solid   | medium    
Au     | high     | yellow   | solid   | high      
Hg     | high     | silver   | liquid  | low       
Na     | low      | silver   | solid   | medium    

Verification des determinations :
  ('metal',)                     -> conductivity : OUI (6 groupes)
  ('density',)                   -> conductivity : NON (2 groupes)
        temoin : Cu(high) vs Fe(medium)
  ('color',)                     -> conductivity : NON (4 groupes)
        temoin : Al(medium) vs Hg(low)
  ('state',)                     -> conductivity : NON (2 groupes)
        temoin : Cu(high) vs Fe(medium)
  ('metal', 'density')           -> conductivity : OUI (6 groupes)
  ('density', 'state')           -> conductivity : NON (3 groupes)
        temoin : Cu(high) vs Fe(medium)

Interprétation : Determinations sur les metaux

Attributs testes	détermine conductivite ?	Raison
metal	Oui	Chaque metal a une conductivite unique
density	Non	Cu et Fe ont tous deux density=high mais conductivites différentes
color	Non	Al et Hg ont tous deux color=silver mais conductivites différentes
state	Non	Cu et Na sont tous deux solid mais conductivites différentes
metal, density	Oui	Surensemble de metal seul, donc toujours valide (monotonie)

Point cle : {metal} est la plus petite détermination (niveau 1), mais elle n’est pas la seule minimale — la cellule suivante révèle trois déterminations minimales : {metal}, {color, density} et {color, state} (cf. propriété d’Unicité ci-dessus). La monotonie garantit que tout surensemble d’une détermination valide est aussi valide.

---

3. Treillis des determinations

L’ensemble des sous-ensembles d’attributs forme un treillis (ou ensemble partiellement ordonne) sous l’inclusion. Les determinations valides forment un up-set (filtre) dans ce treillis : si un ensemble est valide, tous ses surensembles le sont aussi.

Visualisation du treillis

Pour 4 attributs, le treillis a \(2^4 = 16\) noeuds. Chaque niveau correspond a la taille du sous-ensemble.

# Construction du treillis des determinations

def build_determination_lattice(
    data: list[dict],
    all_attrs: list[str],
    target_attr: str
) -> dict[frozenset, bool]:
    """Construit le treillis complet des determinations.
    
    Retourne un dictionnaire {frozenset(attrs) -> holds}.
    """
    lattice = {}
    for size in range(len(all_attrs) + 1):
        for subset in itertools.combinations(all_attrs, size):
            if size == 0:
                # L'ensemble vide ne determine rien (sauf si une seule valeur cible)
                target_vals = set(row[target_attr] for row in data)
                lattice[frozenset(subset)] = len(target_vals) == 1
            else:
                result = check_determination(data, list(subset), target_attr)
                lattice[frozenset(subset)] = result.holds
    return lattice


def display_lattice(
    lattice: dict[frozenset, bool],
    all_attrs: list[str]
) -> None:
    """Affiche le treillis des determinations par niveau."""
    for size in range(len(all_attrs) + 1):
        subsets = [s for s in lattice if len(s) == size]
        valid = [s for s in subsets if lattice[s]]
        invalid = [s for s in subsets if not lattice[s]]
        
        print(f"Niveau {size} ({len(subsets)} sous-ensembles) :")
        
        for s in sorted(valid, key=lambda x: sorted(x)):
            attrs_str = ", ".join(sorted(s)) if s else "(vide)"
            print(f"  [VALIDE]   {{{attrs_str}}}")
        for s in sorted(invalid, key=lambda x: sorted(x)):
            attrs_str = ", ".join(sorted(s)) if s else "(vide)"
            print(f"  [INVALIDE] {{{attrs_str}}}")
    
    total = len(lattice)
    valid_count = sum(1 for v in lattice.values() if v)
    print(f"\nTotal : {valid_count}/{total} sous-ensembles sont des determinations valides")
    
    # Determinations minimales
    minimal = []
    for s, holds in lattice.items():
        if holds and len(s) > 0:
            is_minimal = True
            for s2, holds2 in lattice.items():
                if holds2 and s2 < s:
                    is_minimal = False
                    break
            if is_minimal:
                minimal.append(s)
    
    min_strs = ['{' + ', '.join(sorted(m)) + '}' for m in minimal]
    print(f"Determinations minimales : {min_strs}")


# Construction et affichage du treillis pour les metaux
print("Treillis des determinations : metaux -> conductivite")
print("=" * 60)
print()

lattice = build_determination_lattice(copper_data, METAL_ATTRS, "conductivity")
display_lattice(lattice, METAL_ATTRS)

Treillis des determinations : metaux -> conductivite
============================================================

Niveau 0 (1 sous-ensembles) :
  [INVALIDE] {(vide)}
Niveau 1 (4 sous-ensembles) :
  [VALIDE]   {metal}
  [INVALIDE] {color}
  [INVALIDE] {density}
  [INVALIDE] {state}
Niveau 2 (6 sous-ensembles) :
  [VALIDE]   {color, density}
  [VALIDE]   {color, metal}
  [VALIDE]   {color, state}
  [VALIDE]   {density, metal}
  [VALIDE]   {metal, state}
  [INVALIDE] {density, state}
Niveau 3 (4 sous-ensembles) :
  [VALIDE]   {color, density, metal}
  [VALIDE]   {color, density, state}
  [VALIDE]   {color, metal, state}
  [VALIDE]   {density, metal, state}
Niveau 4 (1 sous-ensembles) :
  [VALIDE]   {color, density, metal, state}

Total : 11/16 sous-ensembles sont des determinations valides
Determinations minimales : ['{metal}', '{color, density}', '{color, state}']

Interprétation : Structure du treillis

Le treillis revele la structure de la connaissance de pertinence :

Propriete	Observation
Up-set	Tout surensemble de {metal} est aussi valide (monotonie)
déterminations minimales	trois : {metal} (niveau 1), {color, density} et {color, state} (niveau 2)
Attributs seuls	density, color, state seuls (niveau 1) sont invalides ; mais certaines paires sans metal ({color,density}, {color,state}) sont valides

Analogie mathematique : Le treillis des determinations est isomorphe a la relation d’inclusion sur \(\mathcal{P}(\{x_1, \ldots, x_n\})\). La connaissance de pertinence identifie un filtre dans ce treillis : les ensembles d’attributs a partir desquels on peut prédire la cible.

# Representation ASCII du treillis

def ascii_lattice(
    lattice: dict[frozenset, bool],
    all_attrs: list[str]
) -> None:
    """Dessine une representation ASCII du treillis."""
    # Trouver les determinations minimales
    minimal_dets = []
    for s, holds in lattice.items():
        if holds and len(s) > 0:
            is_min = True
            for s2, holds2 in lattice.items():
                if holds2 and s2 < s:
                    is_min = False
                    break
            if is_min:
                minimal_dets.append(s)
    
    print("Treillis des determinations (V= valide, X= invalide)")
    print("=" * 50)
    print()
    
    for size in range(len(all_attrs) + 1):
        subsets_of_size = sorted(
            [s for s in lattice if len(s) == size],
            key=lambda x: sorted(x)
        )
        
        level_strs = []
        for s in subsets_of_size:
            name = ",".join(sorted(s)) if s else "{}"
            marker = "V" if lattice[s] else "X"
            is_min = s in minimal_dets
            prefix = "*" if is_min else " "
            level_strs.append(f"{prefix}{marker} {{{name}}}")
        
        print(f"  Niveau {size} : {' | '.join(level_strs)}")
    
    print()
    print("  * = determination minimale")


ascii_lattice(lattice, METAL_ATTRS)

Treillis des determinations (V= valide, X= invalide)
==================================================

  Niveau 0 :  X {{}}
  Niveau 1 :  X {color} |  X {density} | *V {metal} |  X {state}
  Niveau 2 : *V {color,density} |  V {color,metal} | *V {color,state} |  V {density,metal} |  X {density,state} |  V {metal,state}
  Niveau 3 :  V {color,density,metal} |  V {color,density,state} |  V {color,metal,state} |  V {density,metal,state}
  Niveau 4 :  V {color,density,metal,state}

  * = determination minimale

---

4. Algorithme MINIMAL-CONSISTENT-DET

L’algorithme MINIMAL-CONSISTENT-DET (AIMA Figure 19.4) trouve la détermination minimale en explorant les sous-ensembles par taille croissante.

Principe

MINIMAL-CONSISTENT-DET(E, A, Y):
    Pour k = 1, 2, ..., |A|:
        Pour chaque sous-ensemble S de A de taille k:
            Si S détermine Y dans E:
                retourner S
    retourner None

Proprietes de complexite

Cas	Complexite	Explication
Pire cas	\(O(2^n)\)	Aucune détermination n’existe
détermination de taille \(d\)	\(O(n^d)\)	Arret après niveau \(d\)
\(d \ll n\)	Polynomiale	Gain majeur par rapport a l’exhaustion

Origine. L’idee de chercher la détermination minimale (moins d’attributs pertinents possible) et l’algorithme MIN-FEATURES/FOCUS sous-jacent sont dus a Almuallim, H. & Dietterich, T. G. (1991), Learning with many irrelevant features, Proceedings of AAAI-91, pp. 547-552 — qui demontrent le gain de complexite quand peu d’attributs sont pertinents.

# Implementation amelioree de MINIMAL-CONSISTENT-DET

@dataclass
class DetSearchResult:
    """Resultat de la recherche de determination minimale."""
    determination: Optional[tuple[str, ...]]
    subsets_tested: int
    levels_explored: int
    found_at_level: Optional[int]


def minimal_consistent_det(
    data: list[dict],
    all_attrs: list[str],
    target_attr: str,
    verbose: bool = True
) -> DetSearchResult:
    """Trouve le plus petit sous-ensemble d'attributs qui determine target.
    
    Explore les sous-ensembles par taille croissante et retourne
    le premier (plus petit) sous-ensemble valide trouve.
    """
    total_tested = 0
    
    for size in range(1, len(all_attrs) + 1):
        subsets_at_size = list(itertools.combinations(all_attrs, size))
        if verbose:
            print(f"  Niveau {size} : test de {len(subsets_at_size)} combinaisons...")
        
        for subset in subsets_at_size:
            total_tested += 1
            result = check_determination(data, list(subset), target_attr)
            if result.holds:
                if verbose:
                    print(f"    TROUVE : {{{', '.join(subset)}}} apres {total_tested} tests")
                return DetSearchResult(
                    determination=subset,
                    subsets_tested=total_tested,
                    levels_explored=size,
                    found_at_level=size
                )
    
    if verbose:
        print(f"  Aucune determination trouvee ({total_tested} tests)")
    return DetSearchResult(
        determination=None,
        subsets_tested=total_tested,
        levels_explored=len(all_attrs),
        found_at_level=None
    )


# Application : proprietes chimiques et activite biologique
# Quelles proprietes determinent si une molecule est active ?

molecule_data = [
    {"mw": "low",    "logp": "low",  "hbd": "low",  "hba": "low",  "activity": "inactive"},
    {"mw": "low",    "logp": "low",  "hbd": "low",  "hba": "high", "activity": "inactive"},
    {"mw": "medium", "logp": "high", "hbd": "low",  "hba": "high", "activity": "active"},
    {"mw": "medium", "logp": "high", "hbd": "high", "hba": "high", "activity": "active"},
    {"mw": "high",   "logp": "high", "hbd": "low",  "hba": "high", "activity": "active"},
    {"mw": "high",   "logp": "high", "hbd": "high", "hba": "high", "activity": "active"},
    {"mw": "high",   "logp": "low",  "hbd": "high", "hba": "low",  "activity": "inactive"},
    {"mw": "medium", "logp": "low",  "hbd": "high", "hba": "low",  "activity": "inactive"},
    {"mw": "low",    "logp": "high", "hbd": "low",  "hba": "low",  "activity": "inactive"},
    {"mw": "medium", "logp": "high", "hbd": "low",  "hba": "low",  "activity": "active"},
]

MOL_ATTRS = ["mw", "logp", "hbd", "hba"]

print("Donnees : proprietes moleculaires (simplifiees)")
print("=" * 65)
print(f'{"MW":8s} | {"LogP":6s} | {"HBD":5s} | {"HBA":6s} | {"Activite":10s}')
print("-" * 65)
for row in molecule_data:
    print(f"{row['mw']:8s} | {row['logp']:6s} | {row['hbd']:5s} | {row['hba']:6s} | {row['activity']:10s}")

print()
print("Recherche de determination minimale :")
mol_result = minimal_consistent_det(molecule_data, MOL_ATTRS, "activity")

if mol_result.determination:
    d = len(mol_result.determination)
    n = len(MOL_ATTRS)
    print(f"\nDetermination minimale : {{{', '.join(mol_result.determination)}}}")
    print(f"Sous-ensembles testes : {mol_result.subsets_tested} / {2**n - 1}")
    print(f"Reduction espace : O(2^{n}) -> O(2^{d}), facteur {2**(n-d)}")
else:
    print("\nAucune determination fonctionnelle trouvee.")
    print("-> Le concept est probablement disjonctif ou depend d'interactions.")

Donnees : proprietes moleculaires (simplifiees)
=================================================================
MW       | LogP   | HBD   | HBA    | Activite  
-----------------------------------------------------------------
low      | low    | low   | low    | inactive  
low      | low    | low   | high   | inactive  
medium   | high   | low   | high   | active    
medium   | high   | high  | high   | active    
high     | high   | low   | high   | active    
high     | high   | high  | high   | active    
high     | low    | high  | low    | inactive  
medium   | low    | high  | low    | inactive  
low      | high   | low   | low    | inactive  
medium   | high   | low   | low    | active    

Recherche de determination minimale :
  Niveau 1 : test de 4 combinaisons...
  Niveau 2 : test de 6 combinaisons...
    TROUVE : {mw, logp} apres 5 tests

Determination minimale : {mw, logp}
Sous-ensembles testes : 5 / 15
Reduction espace : O(2^4) -> O(2^2), facteur 4

Interprétation : Détermination moleculaire

Aspect	Valeur	Signification
détermination minimale	{mw, logp}	Il faut combiner la masse (mw) ET la lipophilite (logp)
Sous-ensembles testes	\(O(n^d)\)	Bien moins que \(2^n - 1 = 15\)
Reduction d’espace	\(O(2^4) \to O(2^2)\)	Facteur 4x

Point cle : ni logp ni mw ne suffit seul. L’examen des donnees le confirme : logp=high donne active quand mw est medium/high, mais inactive quand mw=low (ligne low | high | ... | inactive). L’activite resulte donc d’une interaction entre masse et lipophilite — une molecule doit etre a la fois suffisamment grosse ET lipophile. La determination minimale est {mw, logp} : on peut ignorer hbd et hba, mais pas mw. L’espace des hypotheses passe de \(2^4 = 16\) a \(2^2 = 4\).

Connexion moderne : En chimoinformatique, c’est l’idee de la règle de Lipinski (“Rule of Five”) : certaines proprietes moleculaires sont plus pertinentes que d’autres pour predire l’absorption orale. Le RBL formalise cette intuition — ici, logp (un critere de Lipinski) est necessaire mais non suffisant.

Cas d’échec : le concept disjonctif du restaurant

Reprenons les données du restaurant (SL-1, AIMA Table 19.1). Le concept cible est disjonctif : WillWait si Patrons=Some ou (Patrons=Full et Hungry=Yes). Une telle logique n’est une fonction d’aucun petit sous-ensemble d’attributs : que trouve MINIMAL-CONSISTENT-DET ?

# Cas d'echec : concept disjonctif du restaurant (donnees SL-1, AIMA Table 19.1)
restaurant_data = [
    {"Alternate": "Yes", "Bar": "No",  "Fri/Sat": "No",  "Hungry": "Yes", "Patrons": "Some", "Price": "$$$", "Raining": "No",  "Reservation": "Yes", "Type": "French",  "WaitEstimate": "0-10",  "WillWait": "Yes"},
    {"Alternate": "Yes", "Bar": "No",  "Fri/Sat": "No",  "Hungry": "Yes", "Patrons": "Full", "Price": "$",   "Raining": "No",  "Reservation": "No",  "Type": "Thai",    "WaitEstimate": "30-60", "WillWait": "Yes"},
    {"Alternate": "No",  "Bar": "Yes", "Fri/Sat": "No",  "Hungry": "No",  "Patrons": "Some", "Price": "$",   "Raining": "No",  "Reservation": "No",  "Type": "Burger",  "WaitEstimate": "0-10",  "WillWait": "No"},
    {"Alternate": "Yes", "Bar": "No",  "Fri/Sat": "Yes", "Hungry": "Yes", "Patrons": "Full", "Price": "$",   "Raining": "Yes", "Reservation": "No",  "Type": "Thai",    "WaitEstimate": "10-30", "WillWait": "Yes"},
    {"Alternate": "Yes", "Bar": "No",  "Fri/Sat": "Yes", "Hungry": "No",  "Patrons": "Full", "Price": "$$$", "Raining": "No",  "Reservation": "Yes", "Type": "French",  "WaitEstimate": ">60",   "WillWait": "No"},
    {"Alternate": "No",  "Bar": "Yes", "Fri/Sat": "No",  "Hungry": "Yes", "Patrons": "Some", "Price": "$$",  "Raining": "Yes", "Reservation": "Yes", "Type": "Italian", "WaitEstimate": "0-10",  "WillWait": "Yes"},
    {"Alternate": "No",  "Bar": "Yes", "Fri/Sat": "No",  "Hungry": "No",  "Patrons": "None", "Price": "$",   "Raining": "Yes", "Reservation": "No",  "Type": "Burger",  "WaitEstimate": "0-10",  "WillWait": "No"},
    {"Alternate": "No",  "Bar": "No",  "Fri/Sat": "No",  "Hungry": "Yes", "Patrons": "Some", "Price": "$$",  "Raining": "Yes", "Reservation": "Yes", "Type": "Thai",    "WaitEstimate": "0-10",  "WillWait": "Yes"},
    {"Alternate": "No",  "Bar": "Yes", "Fri/Sat": "Yes", "Hungry": "No",  "Patrons": "Full", "Price": "$",   "Raining": "Yes", "Reservation": "No",  "Type": "Burger",  "WaitEstimate": "10-30", "WillWait": "No"},
    {"Alternate": "Yes", "Bar": "Yes", "Fri/Sat": "Yes", "Hungry": "Yes", "Patrons": "Full", "Price": "$$$", "Raining": "No",  "Reservation": "Yes", "Type": "Italian", "WaitEstimate": "10-30", "WillWait": "No"},
    {"Alternate": "No",  "Bar": "No",  "Fri/Sat": "No",  "Hungry": "No",  "Patrons": "None", "Price": "$",   "Raining": "No",  "Reservation": "No",  "Type": "Thai",    "WaitEstimate": "0-10",  "WillWait": "No"},
    {"Alternate": "Yes", "Bar": "Yes", "Fri/Sat": "Yes", "Hungry": "Yes", "Patrons": "Full", "Price": "$",   "Raining": "No",  "Reservation": "No",  "Type": "Burger",  "WaitEstimate": "30-60", "WillWait": "Yes"},
]
RESTAURANT_ATTRS = ["Alternate", "Bar", "Fri/Sat", "Hungry", "Patrons",
                    "Price", "Raining", "Reservation", "Type", "WaitEstimate"]

print("MINIMAL-CONSISTENT-DET sur le restaurant (concept disjonctif)")
print("=" * 62)
print()
print("Recherche sur les 5 premiers attributs :")
rest5 = minimal_consistent_det(restaurant_data, RESTAURANT_ATTRS[:5], "WillWait")
print()
if rest5.determination is None:
    print("Aucune determination sur les 5 premiers attributs :")
    print("le concept disjonctif n'est une fonction d'aucun de ces sous-ensembles.")
print()
print("Recherche sur les 10 attributs :")
rest10 = minimal_consistent_det(restaurant_data, RESTAURANT_ATTRS, "WillWait", verbose=False)
if rest10.determination:
    print(f"  Determination 'trouvee' : {{{', '.join(rest10.determination)}}}"
          f" apres {rest10.subsets_tested} tests")
print()
print("ATTENTION : cette determination est FALLACIEUSE (spurious).")
print("Avec seulement 12 exemples et 10 attributs, de nombreux triplets")
print("d'attributs separent les exemples par pur hasard, sans rapport avec")
print("le vrai concept (qui depend de Patrons et Hungry).")

MINIMAL-CONSISTENT-DET sur le restaurant (concept disjonctif)
==============================================================

Recherche sur les 5 premiers attributs :
  Niveau 1 : test de 5 combinaisons...
  Niveau 2 : test de 10 combinaisons...
  Niveau 3 : test de 10 combinaisons...
  Niveau 4 : test de 5 combinaisons...
  Niveau 5 : test de 1 combinaisons...
  Aucune determination trouvee (31 tests)

Aucune determination sur les 5 premiers attributs :
le concept disjonctif n'est une fonction d'aucun de ces sous-ensembles.

Recherche sur les 10 attributs :
  Determination 'trouvee' : {Alternate, Fri/Sat, Price} apres 66 tests

ATTENTION : cette determination est FALLACIEUSE (spurious).
Avec seulement 12 exemples et 10 attributs, de nombreux triplets
d'attributs separent les exemples par pur hasard, sans rapport avec
le vrai concept (qui depend de Patrons et Hungry).

Interprétation : échec et détermination fallacieuse

Recherche	résultat	Lecture
5 premiers attributs (31 tests)	Aucune détermination	Le concept WillWait est disjonctif (Patrons=Some OU (Patrons=Full ET Hungry=Yes)) : ce n’est une fonction d’aucun petit sous-ensemble de ces attributs
10 attributs (66 tests)	{Alternate, Fri/Sat, Price}	détermination fallacieuse : de nombreux triplets “déterminent” la cible sur ce petit échantillon, par pure coincidence

Point cle : une détermination n’a de valeur que si l’échantillon est assez grand pour la contraindre. Sur 12 exemples, beaucoup de triplets d’attributs separent les exemples par coincidence — c’est l’analogue logique du sur-apprentissage. La comparaison statistique de la section 5 ci-dessous (information mutuelle, sklearn) aide précisément a détecter ce piège : les attributs d’une détermination fallacieuse ont des scores MI faibles.

Deux lecons : (1) l’absence de détermination signale un concept disjonctif ou bruite — il faut alors passer aux arbres de decision ou a l’ILP (SL-4) ; (2) la presence d’une détermination sur un petit échantillon ne prouve rien — il faut la valider statistiquement.

---

5. Sélection d’attributs guidee par la connaissance

Le RBL offre un cadre théorique pour la sélection d’attributs. Comparons trois approches :

1. Aveugle : Enumeration exhaustive de tous les sous-ensembles
2. Statistique : sélection par sklearn (mutual information, chi-squared)
3. Guidee (RBL) : utilisation de determinations comme contraintes

Nous allons mesurer l’impact sur un jeu de données synthetique ou seul un petit sous-ensemble d’attributs détermine réellement la cible.

# Generation de donnees synthetiques avec attributs pertinents et bruit

random.seed(42)

N_RELEVANT = 2    # attributs reellement determinants
N_NOISE = 8       # attributs de bruit
N_TOTAL = N_RELEVANT + N_NOISE
N_SAMPLES = 80

RELEVANT_VALUES = ["v1", "v2", "v3", "v4"]
NOISE_VALUES = ["a", "b", "c"]

# La cible Y est determinee par les N_RELEVANT premiers attributs
TARGET_MAP = {}
for i, v1 in enumerate(RELEVANT_VALUES):
    for j, v2 in enumerate(RELEVANT_VALUES):
        TARGET_MAP[(v1, v2)] = f"T{i*4+j+1}"

# Noms d'attributs
ATTR_NAMES = [f"R{i+1}" for i in range(N_RELEVANT)] + [f"N{i+1}" for i in range(N_NOISE)]

# Generation
synth_data = []
for _ in range(N_SAMPLES):
    r_vals = [random.choice(RELEVANT_VALUES) for _ in range(N_RELEVANT)]
    n_vals = [random.choice(NOISE_VALUES) for _ in range(N_NOISE)]
    
    row = {}
    for i, v in enumerate(r_vals):
        row[f"R{i+1}"] = v
    for i, v in enumerate(n_vals):
        row[f"N{i+1}"] = v
    
    target_key = tuple(r_vals)
    row["Y"] = TARGET_MAP[target_key]
    synth_data.append(row)

print(f"Donnees synthetiques : {N_SAMPLES} echantillons, {N_TOTAL} attributs")
print(f"  Pertinents : {ATTR_NAMES[:N_RELEVANT]}")
print(f"  Bruit : {ATTR_NAMES[N_RELEVANT:]}")
print(f"  Classes cibles : {len(set(row['Y'] for row in synth_data))}")
print()
print(f"Apercu des 5 premiers echantillons :")
header = " | ".join(f"{a:>4s}" for a in ATTR_NAMES[:4]) + " | Y"
print(f"  {header}")
for row in synth_data[:5]:
    vals = " | ".join(f"{row[a]:>4s}" for a in ATTR_NAMES[:4]) + f" | {row['Y']}"
    print(f"  {vals}")

Donnees synthetiques : 80 echantillons, 10 attributs
  Pertinents : ['R1', 'R2']
  Bruit : ['N1', 'N2', 'N3', 'N4', 'N5', 'N6', 'N7', 'N8']
  Classes cibles : 16

Apercu des 5 premiers echantillons :
    R1 |   R2 |   N1 |   N2 | Y
    v1 |   v1 |    c |    b | T1
    v1 |   v4 |    a |    a | T4
    v2 |   v4 |    a |    b | T8
    v3 |   v3 |    a |    a | T11
    v3 |   v3 |    a |    c | T11

Les données sont pretes, avec seulement 2 attributs pertinents parmi 10. La cellule suivante applique MINIMAL-CONSISTENT-DET pour retrouver automatiquement cette détermination.

# Approche RBL : recherche de determination minimale

print("Approche RBL : MINIMAL-CONSISTENT-DET")
print("=" * 50)
print()

rbl_result = minimal_consistent_det(synth_data, ATTR_NAMES, "Y")

print()
if rbl_result.determination:
    d = len(rbl_result.determination)
    n = N_TOTAL
    print(f"Determination minimale : {{{', '.join(rbl_result.determination)}}}")
    print(f"Dimension : d={d} sur n={n} attributs")
    print(f"Sous-ensembles testes : {rbl_result.subsets_tested} / {2**n - 1}")
    print(f"Espace hypothese : O(2^{n}) = {2**n} -> O(2^{d}) = {2**d}")
    print(f"Facteur de reduction : {2**(n-d)}x")
else:
    print("Aucune determination trouvee.")

Approche RBL : MINIMAL-CONSISTENT-DET
==================================================

  Niveau 1 : test de 10 combinaisons...
  Niveau 2 : test de 45 combinaisons...
    TROUVE : {R1, R2} apres 11 tests

Determination minimale : {R1, R2}
Dimension : d=2 sur n=10 attributs
Sous-ensembles testes : 11 / 1023
Espace hypothese : O(2^10) = 1024 -> O(2^2) = 4
Facteur de reduction : 256x

Sélection statistique : Information Mutuelle avec sklearn

L’approche RBL a identifié {R1, R2} comme détermination minimale avec une garantie logique (si détermination il y a, RBL la trouve). Mais que se passe-t-il si les données sont bruitees ou que la détermination exacte n’existe pas ?

L’information mutuelle (sklearn) mesure la dépendance statistique entre chaque attribut et la cible, sans exiger de détermination fonctionnelle exacte. La cellule suivante calcule ces scores et compare les attributs selectionnes par sklearn avec la détermination RBL.

# Approche 2 : Selection statistique avec sklearn
# Encodage des donnees categorielles pour sklearn

from sklearn.feature_selection import mutual_info_classif
from sklearn.preprocessing import OrdinalEncoder
import numpy as np

# Encoder les attributs et la cible
encoder = OrdinalEncoder()
X = encoder.fit_transform(
    np.array([[row[a] for a in ATTR_NAMES] for row in synth_data])
)
y = np.array([row["Y"] for row in synth_data])

# Calculer l'information mutuelle
mi_scores = mutual_info_classif(X, y, random_state=42)

# Afficher les scores
print("Selection statistique : Information Mutuelle")
print("=" * 45)
print()
print(f"{'Attribut':8s} | {'Info. Mutuelle':>14s} | Rang")
print("-" * 40)

# Trier par score decroissant
ranked = sorted(zip(ATTR_NAMES, mi_scores), key=lambda x: -x[1])
for rank, (attr, score) in enumerate(ranked, 1):
    relevance = "RELEVANT" if attr.startswith("R") else "noise"
    print(f"{attr:8s} | {score:14.4f} | #{rank} ({relevance})")

# Comparer les top-k de sklearn avec la determination RBL
sklearn_top = set(attr for attr, _ in ranked[:N_RELEVANT])
rbl_set = set(rbl_result.determination) if rbl_result.determination else set()
print(f"\nTop-{N_RELEVANT} sklearn : {sklearn_top}")
print(f"Determination RBL : {rbl_set}")
print(f"Concordance : {sklearn_top == rbl_set}")

Selection statistique : Information Mutuelle
=============================================

Attribut | Info. Mutuelle | Rang
----------------------------------------
R2       |         2.6943 | #1 (RELEVANT)
R1       |         2.5523 | #2 (RELEVANT)
N6       |         0.3245 | #3 (noise)
N1       |         0.2953 | #4 (noise)
N3       |         0.1785 | #5 (noise)
N2       |         0.0000 | #6 (noise)
N4       |         0.0000 | #7 (noise)
N5       |         0.0000 | #8 (noise)
N7       |         0.0000 | #9 (noise)
N8       |         0.0000 | #10 (noise)

Top-2 sklearn : {'R2', 'R1'}
Determination RBL : {'R2', 'R1'}
Concordance : True

Interprétation : RBL vs sélection statistique

approche	méthode	Attributs selectionnes	Garantie
RBL	détermination fonctionnelle	Les attributs qui déterminent exactement la cible	Completude (si détermination existe)
sklearn (MI)	Information mutuelle	Les attributs les plus correles avec la cible	Statistique (pas de garantie fonctionnelle)

Avantages du RBL : - Garantie logique : si une détermination existe, RBL la trouve - Interpretabilite : le résultat est un ensemble d’attributs, pas un score flou - Parsimonie : trouve le plus petit ensemble

Limites du RBL : - Suppose une détermination fonctionnelle exacte (pas de bruit) - Casse en presence de bruit : un seul contre-exemple invalide une détermination - Complexite \(O(n^d)\) qui reste élevée pour \(d\) grand

Synthese : RBL et sklearn sont complementaires. RBL excelle quand on a des connaissances de domaine (determinations connues). Sklearn excelle quand les données sont bruitees ou que la détermination fonctionnelle n’existe pas.

# Quantification de l'avantage : nombre d'exemples necessaires

import math

# Borne PAC (espace d'hypotheses fini) :
#   m >= (1/epsilon) * (ln|H| + ln(1/delta)),  avec ici |H| = 2^n
epsilon = 0.1  # erreur toleree
delta = 0.05   # confiance


def pac_bound(n_attrs: int) -> int:
    """Nombre d'exemples suffisant (PAC) pour |H| = 2^n_attrs."""
    return math.ceil((1 / epsilon) * (n_attrs * math.log(2) + math.log(1 / delta)))


print("Analyse de complexite : RBL vs selection aveugle")
print("=" * 84)
print()
det_d = len(rbl_result.determination) if rbl_result.determination else N_TOTAL
print(f"Parametres : n={N_TOTAL} attributs, d={det_d} pertinents")
print(f"Borne PAC : epsilon={epsilon}, delta={delta}")
print()

print(f"{'n (total)':>10s} | {'d (pertinent)':>14s} | {'|H| sans RBL':>14s} | {'|H| avec RBL':>14s} | {'m sans':>7s} | {'m avec':>7s}")
print("-" * 84)

for n, d in [(5, 1), (10, 2), (20, 2), (20, 3), (50, 3), (100, 5)]:
    print(f"{n:10d} | {d:14d} | {2**n:14d} | {2**d:14d} | {pac_bound(n):7d} | {pac_bound(d):7d}")

print()
print("La reduction de l'espace des hypotheses est EXPONENTIELLE (2^n -> 2^d)")
print("et le nombre d'exemples requis devient LINEAIRE en d au lieu de n :")
print(f"pour n=100 et d=5, il faut {pac_bound(100)} exemples sans RBL"
      f" contre {pac_bound(5)} avec la determination.")

Analyse de complexite : RBL vs selection aveugle
====================================================================================

Parametres : n=10 attributs, d=2 pertinents
Borne PAC : epsilon=0.1, delta=0.05

 n (total) |  d (pertinent) |   |H| sans RBL |   |H| avec RBL |  m sans |  m avec
------------------------------------------------------------------------------------
         5 |              1 |             32 |              2 |      65 |      37
        10 |              2 |           1024 |              4 |     100 |      44
        20 |              2 |        1048576 |              4 |     169 |      44
        20 |              3 |        1048576 |              8 |     169 |      51
        50 |              3 | 1125899906842624 |              8 |     377 |      51
       100 |              5 | 1267650600228229401496703205376 |             32 |     724 |      65

La reduction de l'espace des hypotheses est EXPONENTIELLE (2^n -> 2^d)
et le nombre d'exemples requis devient LINEAIRE en d au lieu de n :
pour n=100 et d=5, il faut 724 exemples sans RBL contre 65 avec la determination.

Interprétation : Impact quantitatif

La connaissance de pertinence (sous forme de détermination) a un impact exponentiel sur l’apprentissage :

Dimension	Sans RBL	Avec RBL (d=3)	Gain
Espace hypotheses	\(2^{20} \approx 10^6\)	\(2^3 = 8\)	\(125\,000\)x
Espace hypotheses	\(2^{100} \approx 10^{30}\)	\(2^5 = 32\)	\(3 \times 10^{28}\)x

Point cle : C’est la raison fondamentale pour laquelle la connaissance de domaine est si precieuse en apprentissage automatique. La détermination agit comme un filtre exponentiel sur l’espace de recherche. En pratique, cette idee se retrouve dans le feature engineering moderne : sélectionner les bons attributs est souvent plus important que le choix de l’algorithme.

---

6. Determinations et sémantique web

Les determinations du RBL ont un parallèle direct dans les technologies du Web Sémantique :

Concept RBL	Equivalent Web Sémantique
détermination \(X > Y\)	Propriete fonctionnelle owl:FunctionalProperty
Attribut déterminant	Cle candidate (owl:hasKey)
Monotonie	Subpropriete (si \(X > Y\) et \(X \subset X'\), \(X' > Y\))

En OWL, declarer qu’une propriete est fonctionnelle equivaut a affirmer une détermination : pour un individu donne, il n’existe qu’une seule valeur. C’est la même intuition que RBL.

Précision : l’analogie se joue sur la multiplicité (un sujet ne doit pas porter deux valeurs pour une propriété fonctionnelle), pas sur une parité stricte avec un reasoner OWL. Pour une propriete d’objet fonctionnelle, deux objets distincts ne sont pas une inconsistance en soi : l’axiome les rend egaux, et un reasoner ne s’alerte que si leur difference est par ailleurs affirmee (DifferentIndividuals).

Connexion inter-series : Les notebooks SemanticWeb (SW-13) couvrent les reasoners OWL qui exploitent ces proprietes fonctionnelles pour inférer de nouveaux faits. Le RBL fournit le cadre théorique sous-jacent.

# Le parallele RBL <-> OWL, demontre computationnellement
# Cote OWL : un mini triple-store (sujet, predicat, objet) en pur Python.
# La determination  metal > conductivite  (RBL) correspond a declarer la
# propriete :aConductivite fonctionnelle (owl:FunctionalProperty) :
# chaque sujet a AU PLUS une valeur pour cette propriete.

TRIPLES = {(f":{row['metal']}", ":aConductivite", row["conductivity"])
           for row in copper_data}
TRIPLES.add((":aConductivite", "rdf:type", "owl:FunctionalProperty"))


def functional_violations(triples, prop):
    """Detecte les multiplicités d'une propriete declaree fonctionnelle.

    En RBL, une violation = deux lignes du meme groupe qui different sur la
    cible. Cote OWL, declarer une propriete *fonctionnelle* impose la meme
    contrainte : un sujet lie a deux objets distincts sur cette propriete.
    Le minimum que cette fonction verifie est donc la multiplicité.

    NB : ce n'est pas une parité stricte avec un reasoner OWL (HermiT,
    Pellet). Pour une propriete d'*objet* fonctionnelle, p(a,b) ^ p(a,c)
    n'est pas une inconsistance : l'axiome entraine b = c, et un reasoner
    n'en signale une que si DifferentIndividuals(b,c) est par ailleurs
    asserte. La multiplicité detectee ici est l'antescente RBL de cette
    contrainte, pas l'inference OWL elle-meme.
    """
    objects = defaultdict(set)
    for s, p, o in triples:
        if p == prop:
            objects[s].add(o)
    return {s: sorted(vals) for s, vals in sorted(objects.items())
            if len(vals) > 1}


print("Parallele RBL <-> Web Semantique : la MEME contrainte, deux formalismes")
print("=" * 72)
print()
print(f"Triples construits depuis copper_data : {len(TRIPLES)}")
print("Declaration :  :aConductivite rdf:type owl:FunctionalProperty .")
print()
viols_owl = functional_violations(TRIPLES, ":aConductivite")
det = check_determination(copper_data, ["metal"], "conductivity")
print(f"OWL : violations de la propriete fonctionnelle -> {viols_owl or 'aucune'}")
print(f"RBL : determination metal > conductivite       -> holds={det.holds}")
print()
# Injectons la MEME observation contradictoire des deux cotes :
# un echantillon de cuivre mauvais conducteur.
contradiction = {"metal": "Cu", "density": "high", "color": "orange",
                 "state": "solid", "conductivity": "low"}
data2 = copper_data + [contradiction]
triples2 = set(TRIPLES) | {(":Cu", ":aConductivite", "low")}

viols_owl2 = functional_violations(triples2, ":aConductivite")
det2 = check_determination(data2, ["metal"], "conductivity")
print("Apres injection d'une observation contradictoire (Cu -> low) :")
print(f"OWL : violations -> {viols_owl2}")
print(f"RBL : holds={det2.holds}, violations={len(det2.violations)}")
print()
print("Les deux detecteurs flaguent la MEME incoherence. Difference cle :")
print("RBL DECOUVRE la determination a partir des donnees, tandis qu'OWL")
print("la DECLARE explicitement dans l'ontologie (cf. SW-13, reasoners).")

Parallele RBL <-> Web Semantique : la MEME contrainte, deux formalismes
========================================================================

Triples construits depuis copper_data : 7
Declaration :  :aConductivite rdf:type owl:FunctionalProperty .

OWL : violations de la propriete fonctionnelle -> aucune
RBL : determination metal > conductivite       -> holds=True

Apres injection d'une observation contradictoire (Cu -> low) :
OWL : violations -> {':Cu': ['high', 'low']}
RBL : holds=False, violations=1

Les deux detecteurs flaguent la MEME incoherence. Difference cle :
RBL DECOUVRE la determination a partir des donnees, tandis qu'OWL
la DECLARE explicitement dans l'ontologie (cf. SW-13, reasoners).

---

7. Exercices

Tableau recapitulatif

Concept	Formule	Implementation
détermination	\(X > Y\) ssi \(\forall e_1, e_2 : X(e_1) = X(e_2) \Rightarrow Y(e_1) = Y(e_2)\)	check_determination()
Treillis	\(\mathcal{P}(A)\) avec inclusion	build_determination_lattice()
MINIMAL-CONSISTENT-DET	Parcourir par taille croissante	minimal_consistent_det()
Reduction d’espace	\(2^n \to 2^d\)	Analyse PAC

# Exemple guide 1 : Determinations dans un jeu de donnees meteorologiques
# Resolution de l'Exercice 1 (See #2161) : solution demontree ci-dessous.
#
# Objectif : quelles proprietes (season, humidity, wind, pressure) determinent
# le type de temps ? On reutilise check_determination (groupage + test de
# consistence) et minimal_consistent_det (recherche du plus petit sous-ensemble
# d'attributs qui determine la cible).

# Les donnees meteorologiques (10 observations synthetiques).
weather_data = [
    {"season": "summer", "humidity": "low",  "wind": "low",    "pressure": "high", "weather": "sunny"},
    {"season": "summer", "humidity": "low",  "wind": "high",   "pressure": "high", "weather": "sunny"},
    {"season": "summer", "humidity": "high", "wind": "low",    "pressure": "low",  "weather": "storm"},
    {"season": "summer", "humidity": "high", "wind": "high",   "pressure": "low",  "weather": "storm"},
    {"season": "winter", "humidity": "low",  "wind": "low",    "pressure": "high", "weather": "cloudy"},
    {"season": "winter", "humidity": "low",  "wind": "high",   "pressure": "low",  "weather": "rain"},
    {"season": "winter", "humidity": "high", "wind": "low",    "pressure": "low",  "weather": "rain"},
    {"season": "winter", "humidity": "high", "wind": "high",   "pressure": "low",  "weather": "storm"},
    {"season": "spring", "humidity": "low",  "wind": "low",    "pressure": "high", "weather": "sunny"},
    {"season": "spring", "humidity": "high", "wind": "low",    "pressure": "low",  "weather": "rain"},
]

WEATHER_ATTRS = ["season", "humidity", "wind", "pressure"]

# Etape 1 : aucun attribut pris isolement ne determine le temps.
print("Etape 1 : test de chaque attribut individuellement")
print("-" * 60)
for attr in WEATHER_ATTRS:
    res = check_determination(weather_data, [attr], "weather")
    status = "OUI" if res.holds else "NON"
    print(f"  {attr:10s} -> weather : {status}  ({res.coverage} groupes, {len(res.violations)} violations)")

# Etape 2 : recherche de la determination minimale (sous-ensembles par taille croissante).
print()
print("Etape 2 : recherche de la determination minimale")
print("-" * 60)
weather_det = minimal_consistent_det(weather_data, WEATHER_ATTRS, "weather", verbose=True)

# Etape 3 : interpretation du resultat.
print()
print("Etape 3 : interpretation")
print("-" * 60)
if weather_det.determination:
    found = set(weather_det.determination)
    excluded = set(WEATHER_ATTRS) - found
    print(f"  Determination minimale : {{{', '.join(weather_det.determination)}}}")
    print(f"  Trouvee au niveau {weather_det.found_at_level} ({weather_det.subsets_tested} sous-ensembles testes).")
    print(f"  Attribut(s) EXCLU(S) par RBL : {{{', '.join(sorted(excluded))}}} -- juge(s) non pertinent(s).")
    print()
    print("Lecture : aucun attribut seul ne determine le temps (par ex. season melange")
    print("sunny et storm en ete). Il faut COMBINER season + humidity + wind (niveau 3).")
    print("La PRESSION est REJETEE par la recherche minimale : deux jours de meme")
    print("(season, humidity, wind) ont le meme temps quelle que soit la pression.")
    print("C'est l'apport de RBL : identifier les variables pertinentes et eliminer")
    print("le bruit, SANS ajuster de modele statistique -- la structure logique suffit.")
else:
    print("  Aucune determination : le concept est disjonctif (cf. cas restaurant).")
print()
print("Exemple guide 1 OK : determination meteo = {season, humidity, wind}, pression excluse.")

Etape 1 : test de chaque attribut individuellement
------------------------------------------------------------
  season     -> weather : NON  (3 groupes, 3 violations)
  humidity   -> weather : NON  (2 groupes, 2 violations)
  wind       -> weather : NON  (2 groupes, 2 violations)
  pressure   -> weather : NON  (2 groupes, 2 violations)

Etape 2 : recherche de la determination minimale
------------------------------------------------------------
  Niveau 1 : test de 4 combinaisons...
  Niveau 2 : test de 6 combinaisons...
  Niveau 3 : test de 4 combinaisons...
    TROUVE : {season, humidity, wind} apres 11 tests

Etape 3 : interpretation
------------------------------------------------------------
  Determination minimale : {season, humidity, wind}
  Trouvee au niveau 3 (11 sous-ensembles testes).
  Attribut(s) EXCLU(S) par RBL : {pressure} -- juge(s) non pertinent(s).

Lecture : aucun attribut seul ne determine le temps (par ex. season melange
sunny et storm en ete). Il faut COMBINER season + humidity + wind (niveau 3).
La PRESSION est REJETEE par la recherche minimale : deux jours de meme
(season, humidity, wind) ont le meme temps quelle que soit la pression.
C'est l'apport de RBL : identifier les variables pertinentes et eliminer
le bruit, SANS ajuster de modele statistique -- la structure logique suffit.

Exemple guide 1 OK : determination meteo = {season, humidity, wind}, pression excluse.

Exercice 1 (variation) : Un attribut trompeur

RBL est censé écarter les attributs non-pertinents. Ajoutez un 5ᵉ attribut bruité (par ex. forecaster = le nom du météorologue, sans lien avec le temps) aux données et vérifiez que la détermination minimale l’exclut toujours.

Étapes : 1. Ajoutez forecaster (valeurs arbitraires) à chaque ligne de weather_data. 2. Relancez minimal_consistent_det sur les 5 attributs. 3. La détermination minimale change-t-elle ? Pourquoi RBL est-il robuste au bruit ?

Indice : un attribut non pertinent augmente le nombre de groupes sans réduire les violations — la recherche par taille croissante le saute naturellement.

# Exercice 1 (variation) : Un attribut trompeur
# TODO etudiant : ajoutez un attribut bruite et confirmez que RBL l'exclut.

# Etape 1 : ajouter 'forecaster' (valeurs sans lien avec weather)
# forecasters = ["Alice", "Bob", "Alice", "Bob", "Alice", "Bob", "Alice", "Bob", "Alice", "Bob"]
# weather_noisy = [dict(row, forecaster=f) for row, f in zip(weather_data, forecasters)]

# Etape 2 : relancer minimal_consistent_det sur les 5 attributs
# noisy_attrs = WEATHER_ATTRS + ["forecaster"]
# det_noisy = minimal_consistent_det(weather_noisy, noisy_attrs, "weather")

# Etape 3 : la determination change-t-elle ?
print('Exercice a completer : attribut bruite et robustesse de RBL')
print('Question : pourquoi RBL exclut-il naturellement les attributs non-pertinents ?')

# Indice : un attribut non-pertinent augmente le nombre de groupes sans reduire
# les violations ; la recherche par taille croissante le saute.
# result = None  # TODO etudiant : (determination_brute, determination_bruitee)

Exercice a completer : attribut bruite et robustesse de RBL
Question : pourquoi RBL exclut-il naturellement les attributs non-pertinents ?

L’exercice suivant compare l’approche RBL a une sélection aléatoire d’attributs pour mesurer concretement le benefice de la connaissance de pertinence.

# Exemple guide 2 : RBL vs selection aleatoire d'attributs
# Resolution de l'Exercice 2 (See #2161) : on mesure CONCRETEMENT le benefice
# de connaitre les attributs pertinents. Sur les donnees synthetiques de la
# section 4 (R1, R2 determinent Y ; N1..N8 sont du bruit), on compare la
# qualite de prediction obtenue avec :
#   (a) la determination minimale trouvee par RBL, et
#   (b) K attributs choisis AU HASARD (moyenne sur plusieurs tirages).
from collections import Counter

# Etape 1 : on reutilise les donnees synthetiques (synth_data, ATTR_NAMES,
# N_RELEVANT definis en section 4). Y est determine par (R1, R2) via TARGET_MAP.

# Etape 2 : decoupage train / test (60% / 40%), reproductible.
random.seed(7)
idx = list(range(len(synth_data)))
random.shuffle(idx)
cut = int(0.6 * len(synth_data))
train = [synth_data[i] for i in idx[:cut]]
test = [synth_data[i] for i in idx[cut:]]


def predict_y(train_data, attrs, row):
    """Predit Y d'apres `attrs` : vote majoritaire parmi les lignes
    d'entrainement qui partagent les memes valeurs sur ces attributs.
    Cas non vu en entrainement -> classe majoritaire globale."""
    matches = [r for r in train_data if all(r[a] == row[a] for a in attrs)]
    pool = matches if matches else train_data
    return Counter(r["Y"] for r in pool).most_common(1)[0][0]


def accuracy(train_data, test_data, attrs):
    """Taux de bonnes predictions de Y sur le jeu de test."""
    ok = sum(1 for row in test_data if predict_y(train_data, attrs, row) == row["Y"])
    return ok / len(test_data)


# Etape 3a : RBL identifie les attributs pertinents (la determination minimale).
rbl_search = minimal_consistent_det(synth_data, ATTR_NAMES, "Y", verbose=False)
rbl_attrs = list(rbl_search.determination)
acc_rbl = accuracy(train, test, rbl_attrs)

# Etape 3b : K attributs tires au hasard (K = taille de la determination RBL),
# en moyennant sur de nombreux tirages pour estimer l'esperance.
K = len(rbl_attrs)
random.seed(123)
N_TRIALS = 300
acc_rand = [accuracy(train, test, random.sample(ATTR_NAMES, K)) for _ in range(N_TRIALS)]
mean_rand = sum(acc_rand) / N_TRIALS
best_rand = max(acc_rand)
# Probabilite qu'un tirage aveugle retombe exactement sur les attributs pertinents.
from math import comb
p_exact = 1.0 / comb(len(ATTR_NAMES), K)

print("Comparaison RBL vs selection aleatoire")
print("=" * 60)
print(f"Taille de la determination RBL : K = {K} -> {{{', '.join(rbl_attrs)}}}")
print(f"Probabilite de tirer CES K attributs au hasard : 1/C({len(ATTR_NAMES)},{K}) = {p_exact:.3%}")
print()
print(f"  RBL (attributs pertinents)        : accuracy = {acc_rbl:.3f}")
print(f"  Aleatoire (moyenne sur {N_TRIALS} tirages) : accuracy = {mean_rand:.3f}")
print(f"  Aleatoire (meilleur tirage)       : accuracy = {best_rand:.3f}")
print()
print("Lecture : RBL predit Y presque parfaitement car (R1, R2) DETERMINE Y.")
print("Un tirage aleatoire de 2 attributs tombe sur {R1, R2} dans seulement "
      f"{p_exact:.1%} des cas ; le reste du temps il inclut du bruit, et la prediction.")
print("retombe au niveau du hasard. Concretement, connaitre la pertinence (RBL)")
print(f"apporte ici un gain d'environ {acc_rbl - mean_rand:+.2f} d'accuracy moyenne.")
print()
print("Exemple guide 2 OK : RBL >> selection aleatoire (pertinence = performance).")

Comparaison RBL vs selection aleatoire
============================================================
Taille de la determination RBL : K = 2 -> {R1, R2}
Probabilite de tirer CES K attributs au hasard : 1/C(10,2) = 2.222%

  RBL (attributs pertinents)        : accuracy = 0.969
  Aleatoire (moyenne sur 300 tirages) : accuracy = 0.142
  Aleatoire (meilleur tirage)       : accuracy = 0.969

Lecture : RBL predit Y presque parfaitement car (R1, R2) DETERMINE Y.
Un tirage aleatoire de 2 attributs tombe sur {R1, R2} dans seulement 2.2% des cas ; le reste du temps il inclut du bruit, et la prediction.
retombe au niveau du hasard. Concretement, connaitre la pertinence (RBL)
apporte ici un gain d'environ +0.83 d'accuracy moyenne.

Exemple guide 2 OK : RBL >> selection aleatoire (pertinence = performance).

Exercice 2 (variation) : Robustesse quand le bruit est “presque” pertinent

L’écart RBL-vs-aléatoire dépend de la netteté du signal. Construisez un jeu synthétique avec 3 attributs pertinents et 7 de bruit, mais où l’un des attributs de bruit est faiblement corrélé à la cible (il partage une valeur sur la moitié des classes). Reprenez la comparaison accuracy(RBL) vs accuracy(aléatoire).

Étapes : 1. Générez un synth3 avec N_RELEVANT = 3 (R1, R2, R3) et un attribut N1 partiellement informatif. 2. Recalculez la détermination minimale RBL (RBL ignore-t-il N1 ?). 3. Mesurez l’accuracy RBL vs aléatoire : l’écart se réduit-il quand le bruit devient partiellement pertinent ? Pourquoi ?

Indice : RBL est logique (binaire : détermine ou non), pas statistique. Un attribut faiblement corrélé n’est PAS une détermination stricte, donc RBL l’écarte — même si une méthode statistique (information mutuelle) lui donnerait un score non nul. C’est la limite abordée à l’Exercice 3.

# Exercice 2 (variation) : bruit partiellement pertinent
# TODO etudiant : 3 attributs pertinents + 1 attribut de bruit faiblement lie a Y.

# Etape 1 : generation d'un jeu synth3 (N_RELEVANT=3, N_NOISE=7 dont N1 partiel)
# random.seed(42)
# synth3 = [... ]   # TODO etudiant : adaptez le schema de la section 4
# ATTR3 = ['R1','R2','R3'] + ['N1',...]  

# Etape 2 : determination minimale RBL sur synth3
# rbl3 = minimal_consistent_det(synth3, ATTR3, 'Y', verbose=False)
# print('Determination RBL :', rbl3.determination, '-- N1 exclu ?', 'N1' not in rbl3.determination)

# Etape 3 : accuracy RBL vs aleatoire (reutiliser predict_y / accuracy ci-dessus)
# ... 
print('Exercice a completer : mesurer lecart RBL vs aleatoire avec du bruit partiellement pertinent')
print('Question : pourquoi RBL ecarte-t-il un attribut faiblement, mais pas strictement, pertinent ?')

# result = None  # TODO etudiant : (accuracy_rbl, accuracy_aleatoire_moyenne)

Exercice a completer : mesurer lecart RBL vs aleatoire avec du bruit partiellement pertinent
Question : pourquoi RBL ecarte-t-il un attribut faiblement, mais pas strictement, pertinent ?

L’exercice suivant combine les determinations avec l’information mutuelle pour créer un selecteur d’attributs hybride, tirant parti des garanties logiques du RBL et de la robustesse statistique de sklearn.

# Exemple guide 3 : Selecteur d'attributs guide par la connaissance
# Resolution de l'Exercice 3 (See #2161) : on combine les deux familles vues
# dans le notebook -- la garantie LOGIQUE du RBL (check_determination) et la
# mesure STATISTIQUE de sklearn (information mutuelle). L'idee : parmi les
# sous-ensembles d'attributs qui sont des determinations VALIDES, garder le
# plus pertinent. L'execution va reveler un piege subtil (cf. lecture finale).

# Etape 1 : scores d'information mutuelle pour tous les attributs.
# (Reprise de l'approche sklearn de la section 5 ; self-contained.)
from sklearn.feature_selection import mutual_info_classif
from sklearn.preprocessing import OrdinalEncoder
import numpy as np

_encoder = OrdinalEncoder()
_X = _encoder.fit_transform(np.array([[row[a] for a in ATTR_NAMES] for row in synth_data]))
_y = np.array([row["Y"] for row in synth_data])
mi_scores = dict(zip(ATTR_NAMES, mutual_info_classif(_X, _y, random_state=42)))

print("Etape 1 : information mutuelle par attribut")
print("-" * 50)
for _attr in ATTR_NAMES:
    _role = "RELEVANT" if _attr.startswith("R") else "noise"
    print(f"  {_attr:5s} : MI = {mi_scores[_attr]:.4f}  ({_role})")


def knowledge_guided_selector(
    data: list[dict],
    all_attrs: list[str],
    target_attr: str,
    mi_scores: dict[str, float]
) -> Optional[tuple[str, ...]]:
    """Selectionne le sous-ensemble d'attributs qui est (1) une determination
    VALIDE pour target_attr et (2) le plus PARCIMONIEUX (plus petite taille),
    les ex aequo etant departages par la meilleure information mutuelle.

    Pourquoi la parcimonie, et non 'maximiser la MI totale' : l'information
    mutuelle estimee sur un echantillon fini attribue des scores PETITS MAIS
    POSITIFS a des attributs de bruit (correlations fortuites). Maximiser la
    somme des MI pousse donc a INCLURE ce bruit (selection degeneree, cf. le
    diagnostic ci-dessous). Exiger la PLUS PETITE determination valide le
    rejette -- c'est la contribution cles du RBL face a la statistique seule.

    Returns:
        Le plus petit sous-ensemble valide (MI max pour departager les ex aequo
        d'une meme taille), ou None si aucune determination n'existe.
    """
    for size in range(1, len(all_attrs) + 1):
        valid = []
        for subset in itertools.combinations(all_attrs, size):
            if check_determination(data, list(subset), target_attr).holds:
                valid.append(subset)
        if valid:
            # Plus petite taille trouvee : parmi ces determinations minimales,
            # on garde la plus informative (MI totale max).
            return max(valid, key=lambda s: sum(mi_scores[a] for a in s))
    return None


# Diagnostic : que donnerait le selecteur NAIF (max MI totale, sans parcimonie) ?
def _naive_max_mi_selector(data, all_attrs, target_attr, mi_scores):
    best, best_mi = None, -1.0
    for size in range(1, len(all_attrs) + 1):
        for subset in itertools.combinations(all_attrs, size):
            if check_determination(data, list(subset), target_attr).holds:
                tot = sum(mi_scores[a] for a in subset)
                if tot > best_mi:
                    best_mi, best = tot, subset
    return best, best_mi


# Etape 2 + 3 : comparaison des trois approches.
guided = knowledge_guided_selector(synth_data, ATTR_NAMES, "Y", mi_scores)
rbl_search = minimal_consistent_det(synth_data, ATTR_NAMES, "Y", verbose=False)
minimal = rbl_search.determination
naive_set, naive_mi = _naive_max_mi_selector(synth_data, ATTR_NAMES, "Y", mi_scores)

print()
print("Etape 2-3 : selecteur guide vs determination minimale vs selecteur naif")
print("-" * 60)
print(f"  Selecteur guide (validite + parcimonie) : {{{', '.join(guided)}}}")
print(f"  Determination minimale (RBL)            : {{{', '.join(minimal)}}}")
print(f"  Selecteur NAIF (max MI totale)          : {{{', '.join(naive_set)}}}  (MI={naive_mi:.3f})")
print(f"  Concordance guide <-> RBL : {set(guided) == set(minimal)}")
print()
print("Lecture : le selecteur GUIDE et le RBL pur convergent vers {R1, R2} -- la")
print("plus petite determination valide. MAIS le selecteur NAIF (maximiser la MI")
print("totale) renvoie un ensemble de 5 attributs {R1, R2, N1, N3, N6} ! Pourquoi ?")
print("Parce que l'information mutuelle estimee sur 80 echantillons donne des scores")
print("PETITS MAIS POSITIFS aux attributs de bruit N1/N3/N6 (correlations fortuites).")
print("Maximiser la MI totale les inclut -- degenerescence vers la sur-selection.")
print()
print("C'est le point cles : la STATISTIQUE seule (MI) sur-selectionne (fausses")
print("correlations en echantillon fini). La LOGIQUE du RBL (validite + parcimonie)")
print("rejette ce bruit et renvoie l'ensemble minimal pertinent. Le selecteur guide")
print("combine les deux : validite logique pour filtrer, parcimonie pour eviter la")
print("sur-selection, MI pour departager les ex aequo.")
print()
print("Exemple guide 3 OK : validite + parcimonie > MI naive (anti-sur-selection).")

Etape 1 : information mutuelle par attribut
--------------------------------------------------
  R1    : MI = 2.5523  (RELEVANT)
  R2    : MI = 2.6943  (RELEVANT)
  N1    : MI = 0.2953  (noise)
  N2    : MI = 0.0000  (noise)
  N3    : MI = 0.1785  (noise)
  N4    : MI = 0.0000  (noise)
  N5    : MI = 0.0000  (noise)
  N6    : MI = 0.3245  (noise)
  N7    : MI = 0.0000  (noise)
  N8    : MI = 0.0000  (noise)

Etape 2-3 : selecteur guide vs determination minimale vs selecteur naif
------------------------------------------------------------
  Selecteur guide (validite + parcimonie) : {R1, R2}
  Determination minimale (RBL)            : {R1, R2}
  Selecteur NAIF (max MI totale)          : {R1, R2, N1, N3, N6}  (MI=6.045)
  Concordance guide <-> RBL : True

Lecture : le selecteur GUIDE et le RBL pur convergent vers {R1, R2} -- la
plus petite determination valide. MAIS le selecteur NAIF (maximiser la MI
totale) renvoie un ensemble de 5 attributs {R1, R2, N1, N3, N6} ! Pourquoi ?
Parce que l'information mutuelle estimee sur 80 echantillons donne des scores
PETITS MAIS POSITIFS aux attributs de bruit N1/N3/N6 (correlations fortuites).
Maximiser la MI totale les inclut -- degenerescence vers la sur-selection.

C'est le point cles : la STATISTIQUE seule (MI) sur-selectionne (fausses
correlations en echantillon fini). La LOGIQUE du RBL (validite + parcimonie)
rejette ce bruit et renvoie l'ensemble minimal pertinent. Le selecteur guide
combine les deux : validite logique pour filtrer, parcimonie pour eviter la
sur-selection, MI pour departager les ex aequo.

Exemple guide 3 OK : validite + parcimonie > MI naive (anti-sur-selection).

Exercice 3 (variation) : Piège de la redondance

L’information mutuelle est additive : deux copies d’un même attribut pertinent ont chacune une MI élevée. Ajoutez un attribut redondant R1b (copie parfaite de R1) au jeu synthétique, puis comparez trois sélecteurs : (a) MI pure (top-K par MI, sans contrainte de validité), (b) détermination minimale RBL, (c) sélecteur guidé.

Étapes : 1. Ajoutez R1b = R1 à chaque ligne, reconstruisez mi_scores sur les 11 attributs. 2. Sélection MI pure top-2 : tombe-t-elle sur {R1, R1b} (redondant) ? 3. Les sélecteurs (b) et (c) évitent-ils la redondance ? Pourquoi la parcimonie (tie-break par taille) est-elle essentielle ici ?

Indice : sans contrainte de validité, MI pure préfère les doublons (MI×2). Le sélecteur guidé, en exigeant une détermination valide ET en cassant les égalités vers le plus petit sous-ensemble, rejette R1b dès que R1 suffit.

# Exercice 3 (variation) : piege de la redondance
# TODO etudiant : ajoutez R1b (copie de R1) et comparez MI pure / RBL / guide.

# Etape 1 : jeu avec attribut redondant
# synth_red = [dict(row, R1b=row['R1']) for row in synth_data]
# ATTR_RED = ATTR_NAMES[:2] + ['R1b'] + ATTR_NAMES[2:]  # R1, R2, R1b, N1..N8
# ... reencoder + mutual_info_classif -> mi_scores_red

# Etape 2 : MI pure top-2 (sans contrainte de validite)
# top2_mi = sorted(ATTR_RED, key=lambda a: -mi_scores_red[a])[:2]

# Etape 3 : RBL minimal vs selecteur guide
# rbl_red = minimal_consistent_det(synth_red, ATTR_RED, 'Y', verbose=False).determination
# guided_red = knowledge_guided_selector(synth_red, ATTR_RED, 'Y', mi_scores_red)
print('Exercice a completer : comparer MI pure / RBL / selecteur guide avec un attribut redondant')
print('Question : pourquoi le tie-break par parcimonie est-il indispensable des qu il y a redondance ?')

# result = None  # TODO etudiant : (top2_mi, rbl_red, guided_red)

Exercice a completer : comparer MI pure / RBL / selecteur guide avec un attribut redondant
Question : pourquoi le tie-break par parcimonie est-il indispensable des qu il y a redondance ?

---

8. Conclusion

Recapitulatif

Ce notebook a approfondi le cadre du Relevance-Based Learning (AIMA 19.4) :

1. Determinations : un ensemble d’attributs \(X\) détermine \(Y\) si connaitre \(X\) suffit pour déterminer \(Y\) sans ambiguite. La propriete de monotonie garantit que tout surensemble d’une détermination est aussi une détermination.

2. Treillis des determinations : l’ensemble des sous-ensembles d’attributs forme un treillis sous l’inclusion. Les determinations valides forment un filtre (up-set) dans ce treillis.

3. MINIMAL-CONSISTENT-DET : algorithme qui trouve la détermination minimale en explorant par taille croissante. Complexite \(O(n^d)\) quand la détermination est de taille \(d\).

4. Reduction exponentielle : la connaissance de pertinence réduit l’espace des hypotheses de \(O(2^n)\) a \(O(2^d)\), un gain exponentiel quand \(d \ll n\).

5. RBL vs sklearn : RBL offre des garanties logiques mais exige des données propres (pas de bruit). Sklearn est robuste au bruit mais sans garantie fonctionnelle. Les deux approches sont complementaires.

Connexions

Direction	Sujet	Lien
Suite de la serie	ILP (Inductive Logic Programming)	SL-4
Prerequis	EBL & introduction RBL	SL-2
Web Sémantique	Proprietes fonctionnelles OWL	SW-13 Reasoners
Machine Learning	Feature sélection moderne	sklearn.feature_selection

---

Defi présentation

Modalite du cours : chaque groupe choisit un exercice de la serie, le prepare, et le présente en seance. résoudre l’exercice est le minimum ; ce qui distingue une présentation qui maitrise le sujet, c’est la question-twist associee ci-dessous. Elle fait partie integrante de la présentation attendue.

Exercice	Question-twist a traiter en plus
Ex. 1 (determinations meteo)	Ajoutez UNE observation bruitee a vos données : quelle détermination minimale survit ? Qu’est-ce que cela illustre de la fragilite du cadre logique face au cadre statistique ?
Ex. 2 (RBL vs sélection aléatoire)	Faites varier le ratio attributs-bruit / attributs-pertinents jusqu’au point de croisement ou la sélection statistique bat le RBL. Ou est ce point sur vos données, et qu’est-ce qui le détermine ?
Ex. 3 (selecteur hybride)	Votre selecteur hybride herite-t-il des garanties logiques des determinations, de la robustesse de l’information mutuelle, des deux, ou d’aucune ? Justifiez avec un contre-exemple construit.

---

Ressources

• Russell & Norvig, AI: A Modern Approach, 3e ed., Section 19.4
• T. Mitchell, Machine Learning, Chapitre 11 (Computational Learning Theory)
• M. Kearns & U. Vazirani, An Introduction to Computational Learning Theory
• AIMA Python Code - Implementations de référence

---

Retour : Index SymbolicLearning | << SL-2 | SL-4 >>