26 Apprentissage PAC agnostic
L’apprentissage PAC pour Probablement Approximativement Correct proposé par Valiant (1984) est limité au cas déterministe et souvent réalisable, où l’on s’attend à ce que l’erreur de généralisation du modèle tende vers zéro lorsque le nombre d’exemples augmente.
Cependant, ces hypothèses son très rarement vérifiées en pratique, notamment dès lors que l’étiquette Y prédite dépend de variables non mesurées et non présentes dans \boldsymbol{X}.
Pour palier à ce défaut, Kearns (1994) a proposé une version agnostic du cadre PAC. L’idée principale consiste à ne plus s’intéresser directement à la valeur du risque, mais plutôt à la différence entre le risque du modèle \hat{f} et le risque du meilleur modèle de la classe \mathcal{F} des modèles possibles (ce dernier pouvant être différent du meilleur modèle dans l’absolu).
26.1 Borne PAC agnostique
Dans ce qui suit, \mathcal{F} est une classe de fonctions (l’ensembe des modèles possibles) et S la base d’apprentissage.
Un algorithme \mathcal{A} : (\mathcal{F},S)\mapsto \hat{f} admet une borne PAC agnostique si pour toute loi jointe P du couple (\boldsymbol{X},Y)\in\mathcal{X}\times\mathcal{Y}, pour tout \delta\in (0,1), \textcolor{blue}{P^m}\left\{ \textcolor{red}{R(\hat{f}) - \min_{f\in\mathcal{F}} R(f) \leq \epsilon} \right\} \textcolor{blue}{\geq 1 - \delta}
Cette borne garantie que l’on ne résoud le problème que de manière probablement approximativement correcte :
- le modèle est Approximativement Correct : son risque est proche (à \epsilon près) du meilleur risque atteignable dans \mathcal{F} ;
- la borne n’est que probablement valide, avec une probabilité d’au moins 1-\delta (comme pour la borne PAC classique).
26.2 Complexité en échantillon agnostique (sample complexity)
La complexité en échantillon agnostique m(\epsilon,\delta) d’un algorithme est le plus petit m tel que la borne PAC agnostique ci-dessus soit valide.
Cette complexité nous indique le nombre d’exemples nécessaire pour pouvoir garantir que l’algorithme résolve le problème au sens où il se rapproche de la meilleure fonction qu’il aurait pu sélectionner parmi \mathcal{F}.
26.3 Apprenabilité
Un ensemble de fonctions \mathcal{F} est agnostiquement apprenable si il existe un algorithme \mathcal{A} : (\mathcal{F},S)\mapsto \hat{f} tel que la complexité en échantillon agnostique m(\epsilon,\delta) est polynomiale en 1/\epsilon et 1/\delta.
Autrement dit, un ensemble de modèles est considéré apprenable si le nombre d’exemples nécessaires à son apprentissage n’explose pas exponentiellement lorsque la performance désirée augmente ou lorsque que la confiance souhaitée dans les garanties théoriques augmente.
26.4 Apprenabilité et bornes uniformes
Considérons le meilleur modèle de la classe \mathcal{F} : f^* = \arg\min_{f\in\mathcal{F}} R(f)
L’erreur d’estimation est R(\hat{f}) - R(f^*) = R(\hat{f}) - \min_{f\in\mathcal{F}} R(f)
Pour l’algorithme ERM (qui minimise le risque empirique), \hat{f} = \arg\min_{f\in\mathcal{F}} R_{emp}(f), on a \begin{align*} R(\hat{f}) - R(f^*) &= R(\hat{f}) - R_{emp}(\hat{f}) + R_{emp}(\hat{f}) - R(f^*)\\ &\leq R(\hat{f}) - R_{emp}(\hat{f}) + R_{emp}(f^*) - R(f^*)\\ &\leq 2\sup_{f\in\mathcal{F}} |R(f) - R_{emp}(f)| \end{align*} Ainsi, une borne uniforme à \epsilon près du type : P^m \left\{\forall f\in\mathcal{F},\quad | R(f) - R_{emp}(f) | \leq \epsilon \right\} \geq 1-\delta borne aussi avec une forte probabilité l’erreur d’estimation à 2\epsilon près pour l’ERM, et fournit donc aussi une borne PAC agnostique. Une borne uniforme du type ci-dessus suffit donc à démontrer l’apprenabilité et est plus simple à dériver. L’avantage ici est que le terme |R(f) - R_{emp}(f)| est simplement la déviation entre la moyenne empirique et l’espérance de l’erreur d’une fonction et ne dépend pas de f^* qui est difficile à caractériser.
La borne uniforme ci-dessus est aussi appelée borne sur l’erreur de généralisation car elle permet de garantir les performances en généralisation à partir de l’erreur sur la base d’apprentissage.