25 Apprentissage PAC
L’apprentissage PAC pour Probablement Approximativement Correct a été proposé par Valiant (1984). On peut comprendre les définitions ci-dessous en faisant un parallèle avec le domaine de la complexité algorithmique, classiquement étudiée en informatique.
Dans ce domaine, on cherche à quantifier la complexité des algorithmes et des problèmes pour définir s’il est raisonnable ou non de tenter de les résoudre.
De même, nous chercherons ici à savoir s’il est raisonnable d’attaquer un « problème » par apprentissage.
En informatique, la complexité d’un problème est la plus petite complexité d’un algorithme qui résoud le problème.
En apprentissage, cette définition pose un souci : nous savons pertinemment qu’aucun algorithme ne résoud exactement un problème au sens où l’erreur de généralisation sera toujours non nulle.
La première étape consiste donc à définir ce que l’on entend par avoir un algorithme qui « résoud un problème », ce que nous traduirons par « admettre une borne PAC ».
Une autre différence concerne la définition du problème en lui-même. Ici, le « problème » que nous chercherons à résoudre sera celui de l’apprentissage au sens du choix d’un modèle parmi une classe de fonctions prédéfinie. Ainsi, différentes classes de fonctions auront des complexités différentes car il sera plus ou moins évident de choisir un bon modèle parmi elles.
Enfin, la complexité algorithmique se mesure (pour simplifier) en termes de « nombre d’opérations » minimal pour résoudre le problème. En apprentissage, le facteur limitant la qualité du résultat n’est pas la quantité de calculs mais le nombre d’exemples : un temps de calcul infini ne permet pas d’atteindre un risque nul si les données sont insufisantes. Nous mesurerons donc la « complexité en échantillon » qui compte le nombre d’exemples nécessaires pour « résoudre le problème ».
L’apprentissage PAC présenté ici se limite au cas déterministe : on suppose l’existence d’une fonction cible f^* telle que Y=f^*(X). Autrement dit, le risque de Bayes R(f_{Bayes}) est nul. L’apprentissage PAC agnostique permet de traiter le cas plus général.
25.1 Borne PAC
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 si pour toute fonction cible f^* et toute loi de probabilité P de (X,Y) telle que Y=f^*(X), pour tout \delta\in (0,1), \textcolor{blue}{P^m}\left\{ \textcolor{red}{R(\hat{f}) \leq \epsilon} \right\} \textcolor{blue}{\geq 1 - \delta} où P^m\{A\} fait référence à la probabilité de tirer un jeu de m données telles que A.
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 faible, inférieur à \epsilon, (car on ne peut pas s’attendre à un modèle qui donne des prédictions parfaites) ;
- la borne n’est que probablement valide, avec une probabilité d’au moins 1-\delta (car on ne peut pas être certain à 100% de quoi que ce soit sur le risque qui reste impossible à calculer).
25.2 Complexité en échantillon (sample complexity)
La complexité en échantillon m(\epsilon,\delta) d’un algorithme est le plus petit m tel que la borne PAC 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 de la borne PAC ci-dessus.
25.3 Apprenabilité
Un ensemble de fonctions \mathcal{F} est apprenable si il existe un algorithme \mathcal{A} : (\mathcal{F},S)\mapsto \hat{f} tel que la complexité en échantillon 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.
Nous nous plaçons ici dans le cas réalisable où le modèle optimal appartient à l’ensemble des modèles possibles pour l’algorithme : f^*\in\mathcal{F}.
Dans ce cas, la complexité en échantillon de l’algorithme ERM (qui minimise le risque empirique), \hat{f} = \arg\min_{f\in\mathcal{F}} R_{emp}(f) est bornée par m(\epsilon,\delta) = \frac{\log |\mathcal{F}| + \log \frac{1}{\delta}}{\epsilon} où |\mathcal{F}| est le nombre de fonctions composant \mathcal{F}.
Ainsi, dans le cas réalisable, m(\epsilon,\delta) est linéaire en 1/\epsilon et logarithmique en 1/\delta, et donc tout ensemble de classifieurs \mathcal{F} fini (avec un nombre fini de modèles) est apprenable.
Pour démontrer cela, notons que dans le cas réalisable, f^*\in\mathcal{F}, et déterminite, Y=f^*(X), le risque empirique du modèle optimal est R_{emp}(f^*) = 0. Pour l’algorithme ERM qui conduit à la plus petite erreur d’apprentissage, R_{emp}(\hat{f}) \leq R_{emp}(f^*), et cela signifie que
R_{emp}(\hat{f})=0 .
est toujours vérifiée. Ainsi,
P^m\left\{ R(\hat{f}) \leq \epsilon \right\} = 1 - P^m\left\{ R(\hat{f}) > \epsilon \right\}
= 1 - P^m\left\{ R_{emp}(\hat{f}) = 0\ et\ R(\hat{f}) > \epsilon \right\}
En utilisant (A\Rightarrow B) \Rightarrow P(A)\leq P(B) et P(C,D) \leq P(C|D) : \begin{align*}
P^m\left\{ R_{emp}(\hat{f}) = 0\ et\ R(\hat{f}) > \epsilon \right\} &\leq P^m\left\{ \exists f\in\mathcal{F}, \ R_{emp}(f) = 0\ et\ R(f) > \epsilon\right\} \\
&=P^m\left\{ \bigcup_{f\in\mathcal{F}} \ R_{emp}(f) = 0\ et\ R(f) > \epsilon\right\} \\
&\leq \sum_{f\in\mathcal{F}} P^m \left\{ R_{emp}(f) = 0\ et\ R(f) > \epsilon\right\} \\
&\leq \sum_{f\in\mathcal{F}} P^m \left\{ R_{emp}(f) = 0\ |\ R(f) > \epsilon\right\}
\end{align*} Si R(f) = P(f(X)\neq Y) > \epsilon, alors la probabilité que f classe correctement un exemple est 1-R(f)\leq 1-\epsilon et pour m exemples indépendants,
P^m \left\{ R_{emp}(f) = 0\ |\ R(f) > \epsilon\right\} = \prod_{i=1}^m P \left\{ f(X_i)=Y_i\ |\ R(f) > \epsilon\right\} \leq (1-\epsilon)^m \leq e^{-\epsilon m}
Donc, en posant \delta = |\mathcal{F}|e^{-\epsilon m},
P^m\left\{ R(\hat{f}) \leq \frac{1}{m}\left(\log |\mathcal{F}| + \log\frac{1}{\delta}\right)\right\} \geq 1-\delta
et il suffit d’avoir m\geq m(\epsilon,\delta) pour valider la borne avec un \epsilon donné.
25.4 Apprenabilité efficace
Il est aussi possible de considérer la complexité algorithmique de l’apprentissage en plus de la complexité en échantillon pour définir l’apprenabilité efficace. Une classe de fonctions est donc apprenable efficacement, si, en plus d’être apprenable, la complexité algorithme est aussi polynomiale.
Cependant, il faut rester vigilant face à un certain nombre de détails pour pouvoir définir cela correctement. En particulier :
- il faut équilibrer le temps de calcul entre l’apprentissage et la prédiction, sans quoi la plupart des calculs pourraient être « cachés » dans la fonction de prédiction qui referait l’apprentissage, et le temps de l’apprentissage serait nul ;
- il faut prendre en compte que la complexité en temps ne peut pas être uniquement une fonction du nombre d’exemples m, car pour m\geq m(\epsilon,\delta), l’algorithme peut ignorer tous les exemples supplémentaires (car les performances sont suffisantes pour la borne PAC) et calculer ainsi en temps constant par rapport à m>m(\epsilon,\delta), mais exponentiel par rapport à m(\epsilon,\delta).