Le gain nul du ou exclusif

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 26 — Apprentissage automatique

Énoncé

Quatre exemples, deux attributs booléens $a_{1}$ et $a_{2}$ , étiquette $y = a_{1} \oplus a_{2}$ :

	$a_{1}$	$a_{2}$	$y$
$e_{1}$	$0$	$0$	$0$
$e_{2}$	$0$	$1$	$1$
$e_{3}$	$1$	$0$	$1$
$e_{4}$	$1$	$1$	$0$

Calculer le gain d'information de chaque attribut. Que fait ID3 ? Existe-t-il pourtant un arbre binaire qui classe les quatre exemples sans erreur ?

Corrigé

$H (S) = 1$ ( $2$ « $0$ » et $2$ « $1$ »). Le test sur $a_{1}$ sépare ${e_{1}, e_{2}}$ (un $0$ , un $1$ ) et ${e_{3}, e_{4}}$ (un $1$ , un $0$ ) : les deux moitiés ont pour entropie $1$ , donc

$Gain (S, a_{1}) = 1 - \frac{1}{2} \cdot 1 - \frac{1}{2} \cdot 1 = 0,$

et par symétrie $Gain (S, a_{2}) = 0$ également.

ID3 est aveugle ici. Aucun test ne réduit l'entropie : le critère ne distingue plus rien, et selon la façon dont on départage les ex æquo, l'algorithme construit soit une feuille immédiate — d'étiquette majoritaire, donc fausse sur la moitié des exemples —, soit un arbre dont le premier test n'apprend rien.

Et pourtant l'arbre existe, de profondeur $2$ et sans aucune erreur :

Ce que cela dit d'ID3. C'est un glouton, au sens exact du chapitre chap:gloutons : il évalue chaque test isolément, et ne voit jamais qu'une paire de tests peut valoir beaucoup alors que chacun ne vaut rien. Le gain d'information est une heuristique de choix local, pas une mesure d'utilité ; et le ou exclusif est le contre-exemple minimal — deux attributs, quatre exemples, un gain nul et une solution parfaite à un test de distance.

La conséquence pratique : un gain nul ne justifie pas d'écarter un attribut. Il justifie seulement de ne pas le placer à cet endroit-là. C'est pourquoi la ligne if homogene exemples || tests = [] du cours n'arrête la récursion que sur l'homogénéité ou l'épuisement des tests, jamais sur un gain nul.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.