27 Bornes sur l’erreur de généralisation
Une borne sur l’erreur de généralisation permet de garantir les performances d’un modèle à partir de son comportement sur la base d’apprentissage.
La première borne calculée à partir de l’erreur de test est en effet limitée car
- elle demande de mettre des données de côté ;
- elle ne dépend pas du modèle f, ni de la classe de modèles \mathcal{F}, ni de l’algorithme utilisé, et ne peut donc pas nous aider à développer de nouveaux algorithmes ou à comprendre le comportement des algorithmes existants.
Ainsi, nous souhaitons ici obtenir une borne de la forme générale :
Avec une forte probabilité, pour toute fonction f \in \mathcal{F}, R(f) \leq R_{emp}(f) + \epsilon(m, \mathcal{F}) où
- R(f)=\mathbb{E}\ell(f, \boldsymbol{X}, Y) est le risque ;
- R_{emp}(f) = \frac{1}{m}\sum_{i=1}^m \ell(f, \boldsymbol{X}_i, Y_i) est le risque empirique ;
- \epsilon(m, \mathcal{F}) est un terme de contrôle ou « (semi)-intervalle » de confiance qui prend en compte la classe de modèles \mathcal{F}.
Nous présentons ici la borne la plus simple pour le cas avec un nombre fini de modèles possibles. Le cas des classes de fonctions infinies est traité ici.
27.1 Borne pour les classes de fonctions finies
Tout ce qui suit se place dans le cadre de la classification avec \ell(f, \boldsymbol{X}, Y) = \mathbf{1}(f(\boldsymbol{X})\neq Y).
Commençons par considérer un ensemble très simple ne contenant que 2 modèles : \mathcal{F}= \{f_1, f_2\}. Dans ce cas, l’inégalité de Hoeffding appliquée à f_1 donne P^m\{R(f_1) - R_{emp}(f_1) > \epsilon\} \leq \delta avec \delta = \exp\left(-2m \epsilon^2\right).
De même, pour f_2, P^m\{R(f_2) - R_{emp}(f_2) > \epsilon\} \leq \delta La probabilité d’observer un jeu de données S conduisant à une grande erreur pour f_1 ou f_2 est donc, en utilisant la borne de l’union (Équation B.1) : \begin{align*} P^m\{R(f_1) - R_{emp}(f_1) > \epsilon &\cup R(f_2) - R_{emp}(f_2) > \epsilon\} \\ &\leq P^m(R(f_1) - R_{emp}(f_1) > \epsilon) + P^m(R(f_2) - R_{emp}(f_2) > \epsilon) \\ &\leq 2\delta \end{align*}
De manière générale, pour une classe de fonctions \mathcal{F} finie avec |\mathcal{F}| = N < +\infty, le même raisonnement s’applique et \begin{align*} P^m\{\exists f_j \in \mathcal{F},\ R(f_j) - R_{emp}(f_j) > \epsilon\} &\leq \sum_{j=1}^N P^m\{R(f_j) - R_{emp}(f_j) > \epsilon\} \\ &\leq N\delta \end{align*} Ainsi, si l’on redéfinit \delta = N\exp\left(-2m \epsilon^2\right), et que l’on résoud cette équation pour obtenir \epsilon, on obtient le théorème suivant.
Théorème 27.1 Pour tout \delta>0, avec une probabilité égale ou supérieure à 1-\delta, \forall f\in \mathcal{F},\quad R(f) \leq R_{emp}(f) + \sqrt{\frac{\ln N + \ln \frac{1}{\delta}}{2m}}
Cette borne est
- valide simultanément pour toute fonction de \mathcal{F} et donc en particulier pour le classifieur \hat{f}\in\mathcal{F} sélectionné par un algorithme d’apprentissage.
- indépendante de la distribution des données P
- indépendante de l’algorithme utilisé pour choisir \hat{f}\in\mathcal{F}
27.1.1 Interprétation de la borne
La borne du Théorème 27.1 illustre le compromis entre la taille de la classe de fonctions et le risque empirique.
Soit deux classes de fonctions telles que \mathcal{F}_1 \subset \mathcal{F}_2, et donc avec des nombres de fonctions N_2 > N_1. En passant de \mathcal{F}_1 à \mathcal{F}_2 :
- l’erreur d’apprentissage du classifieur retenu par l’algorithme ERM diminue (une meilleure approximation des données peut être trouvée) car \min_{f\in \mathcal{F}_2} R_{emp}(f) \leq \min_{f\in \mathcal{F}_1} R_{emp}(f)
- mais la confiance dans cet algorithme diminue aussi.
Dis autrement, plus la taille de la classe de fonctions est grande, plus le nombre de données d’apprentissage doit être grand pour garantir que le risque reste proche du risque empirique et ainsi éviter le surapprentissage.
27.1.2 Complexité en échantillon
Le Théorème 27.1 permet de déterminer le nombre d’exemples nécessaires pour apprendre correctement, c’est-à-dire garantir (avec une probabilité d’au moins 1-\delta) un risque R(f) \leq R_{emp}(f) + \epsilon pour N, \epsilon et \delta fixés : m\geq \frac{\ln N + \ln \frac{1}{\delta}}{2\epsilon^2} = O\left( \frac{\ln \frac{N}{\delta}}{\epsilon^2}\right)
Pour une certitude de 95%, cela donne les nombres ci-dessous.
| Nombre de modèles N | avec \epsilon = 0.02 | avec \epsilon = 0.01 |
|---|---|---|
| 10 | 6623 | 26492 |
| 100 | 9502 | 38005 |
| 1000 | 12380 | 49518 |
| 100000 | 18136 | 72544 |
Ce tableau montre l’intérêt d’une complexité en échantillon logarithmique par rapport à la taille de \mathcal{F}. Cependant celle-ci a une limite… pour N infini, la borne devient inutile.
Pour traiter ce cas, il faudra trouver d’autres moyens de mesurer la complexité de la classe \mathcal{F}, comme par exemple avec la VC dimension.