Profondeur d'un arbre de décision
l'erreur d'apprentissage descend toujours ; l'erreur de test, elle, finit par remonter
1 · CRITÈRE DE COUPURE (CART, GINI)
$$G(t)=1-\sum_{k}\hat p_k(t)^2,\qquad
(j^\star,s^\star)=\arg\max_{j,s}\ \Big[G(t)-\frac{n_L}{n_t}G(t_L)-\frac{n_R}{n_t}G(t_R)\Big]$$
\(t_L=\{x\in t:\ x_j\le s\}\), \(t_R=\{x\in t:\ x_j\gt s\}\) ; on coupe tant qu'un nœud n'est pas pur. L'arbre de profondeur \(D\) est l'arbre complet lu jusqu'au niveau \(D\).
$$\widehat{\mathrm{err}}_{\text{app}}(D)=\frac1n\sum_{i=1}^{n}\mathbf 1\{\hat f_D(x_i)\neq y_i\},\qquad
\widehat{\mathrm{err}}_{\text{test}}(D)=\frac1{m}\sum_{i=1}^{m}\mathbf 1\{\hat f_D(x'_i)\neq y'_i\}$$
2 · À TOI : FAIS VARIER LA PROFONDEUR D
données et régions de l'arbre de profondeur \(D\) ; trait vert : frontière de Bayes
erreurs en fonction de la profondeur : glisse pour changer \(D\)
Deux gaussiennes bivariées de covariances différentes, probabilités a priori égales : la frontière de Bayes est une conique, que l'arbre approche par des marches d'escalier parallèles aux axes. Test : \(m=4000\) nouveaux points de la même loi. Points cerclés de noir : points d'apprentissage mal classés.
3 · RAPPELS
- L'erreur d'apprentissage ne peut que baisser quand on coupe un nœud (le vote majoritaire de deux enfants se trompe au plus autant que celui du parent) ; sans limite, l'arbre isole chaque point et atteint 0.
- L'erreur de test dessine un U : à faible profondeur, l'arbre est trop grossier (biais) ; trop profond, il apprend le bruit de l'échantillon (variance). Le minimum se situe entre les deux.
- Aucune règle ne fait mieux que l'erreur de Bayes \(\mathrm{err}^\star=\mathbb E\big[\min_k \mathbb P(Y=k\mid X)\big]\) : c'est le plancher de l'erreur de test, pas de l'erreur d'apprentissage.
- En pratique on ne choisit pas \(D\) sur l'échantillon de test : CART fait pousser un grand arbre puis l'élague selon \(R_\alpha(T)=\widehat{\mathrm{err}}_{\text{app}}(T)+\alpha\,|T|\), avec \(\alpha\) choisi par validation croisée.
- Plus \(n\) est grand, plus l'arbre profond reste fiable : la meilleure profondeur augmente avec \(n\). Les arbres profonds ont une forte variance, d'où le bagging et les forêts aléatoires qui moyennent beaucoup d'arbres.