Probleme – La courbe du sur-apprentissage, mesurée

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

Énoncé

On veut voir la courbe que le cours dessine. On tire $120$ points $x$ dans $[0, 1]$ , on leur donne l'étiquette « $x > 0, 5$ », et l'on inverse l'étiquette avec probabilité $0, 10$ . On apprend un arbre de décision à seuils, de profondeur bornée par $p$ .

Que vaut l'erreur minimale qu'un modèle quelconque peut espérer sur ces données ?
Mesurer l'erreur d'entraînement et l'erreur de test pour $p = 1, \dots, 12$ , et commenter les deux courbes.
Comment choisir $p$ en pratique ?

Corrigé

1. Le plancher. Le meilleur modèle imaginable est la règle vraie, « $x > 0, 5$ ». Elle se trompe exactement quand l'étiquette a été inversée, soit avec probabilité $0, 10$ . Aucun modèle ne peut descendre sous $10 %$ d'erreur de test : c'est le bruit, il n'est pas prédictible. Toute méthode qui annoncerait $2 %$ sur ces données a mesuré autre chose que ce qu'elle croit.

2. Les deux courbes. Mesuré sur $120$ points d'entraînement et $4000$ points de test :

profondeur $p$	feuilles	erreur d'entraînement	erreur de test
$1$	$2$	$0, 0833$	$0, 1077$
$2$	$4$	$0, 0833$	$0, 1077$
$3$	$7$	$0, 0667$	$0, 1375$
$4$	$11$	$0, 0583$	$0, 1427$
$5$	$15$	$0, 0417$	$0, 1445$
$6$	$17$	$0, 0167$	$0, 1595$
$7$	$18$	$0, 0083$	$0, 1820$
$9$	$20$	$0, 0000$	$0, 1752$
sans limite	$20$	$0, 0000$	$0, 1752$

La colonne d'entraînement décroît sans exception jusqu'à $0$ : c'est ce que le cours annonce, et c'est mécanique — chaque niveau supplémentaire permet d'isoler quelques exemples de plus. La colonne de test remonte dès $p = 3$ , et croît de $69 %$ entre $p = 2$ ( $0, 1077$ ) et $p = 7$ ( $0, 1820$ ).

Les meilleurs arbres sont ceux de profondeur $1$ et $2$ , à égalité ; le premier n'a qu'un seul test. Son seuil, appris, vaut $0, 5113$ ; la vérité est $0, 5$ . Son erreur de test, $0, 1077$ , est à moins d'un point du plancher théorique $0, 10$ . Le modèle le plus simple est ici le meilleur possible, et les dix-neuf feuilles supplémentaires de l'arbre complet ne servent qu'à mémoriser douze étiquettes bruitées.

3. Choisir $p$ . Jamais sur la colonne d'entraînement, qui désignerait $p = 9$ . Jamais non plus sur la colonne de test, qu'on ne regarde qu'une fois. On réserve donc un troisième lot, dit de validation, on y mesure l'erreur pour chaque $p$ , on retient le $p$ qui la minimise, et l'on annonce enfin le chiffre obtenu sur le test. L'autre procédé, plus courant sur les arbres, est l'élagage : on construit l'arbre complet, puis on remonte en remplaçant par une feuille tout sous-arbre dont la suppression n'aggrave pas l'erreur de validation.

Ce que cette table démontre concrètement. Deux modèles, l'un à deux feuilles et l'autre à vingt, apprennent les mêmes $120$ points ; le second les classe tous correctement et le premier en rate dix. Sur des données nouvelles, c'est le premier qui gagne, et largement. L'erreur d'entraînement n'est pas une mesure dégradée de la qualité : c'est une mesure d'autre chose.

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.