Voir la source de Apprentissage PAC

{{Infobox Méthode scientifique}} 

L''''apprentissage PAC''' (pour '''''{{lang|en|probably approximately correct}}''''' en anglais) est un cadre théorique pour l'[[apprentissage automatique]]. Il permet notamment d'évaluer la difficulté d'un problème dans le contexte de l'[[apprentissage supervisé]]. Il a été proposé par [[Leslie Valiant]] en 1984.

== Principe ==
Dans le cadre de l'apprentissage PAC, l'algorithme «apprenant» reçoit des données d'apprentissage (« échantillons ») et doit choisir une fonction qui généralise ces données. Cette fonction est choisie parmi un ensemble préétabli. Elle est appelée «hypothèse». Le but est que la fonction en question classifie de nouvelles données inconnues (distribuées identiquement aux données d'apprentissage) avec une erreur minimale, et ceci avec forte probabilité.

== Cadre formel ==
Le cadre le plus simple est le suivant<ref>Voir [http://www.grappa.univ-lille3.fr/~torre/Enseignement/Cours/Apprentissage-Automatique/downloads/modele_pac_4on1.pdf Cours] de Fabien Torre sur le modèle d'apprentissage PAC.</ref>.

On considère un ensemble d'échantillons, c'est-à-dire de points d'un espace ''X'', étiquetés par «-1» ou «1». On dispose d'une [[loi de probabilité]] ''D'' sur ''X''. On dispose aussi d'un ensemble d'hypothèses, c'est-à-dire d'un espace ''H'', de fonctions de X vers {-1,1}. L'une d'elles est appelée le «concept» ''c'' : c'est la fonction inconnue que l'on veut apprendre. 

L'erreur d'une hypothèse ''h'' par rapport au concept ''c'' sur ''D'' est : <math>erreur(h)=Pr_{x\in D}[c(x)\neq h(x)]</math>.

On dit que ''H'' est PAC apprenable s'il existe un algorithme L tel que : 
* pour tout concept ''c'' de ''H'' ;
* pour toute loi ''D'' sur ''X'' ;
* pour tout paramètre d'erreur <math> 0<\epsilon<1/2 </math> ;
* pour tout paramètre de confiance <math> 0<\delta<1/2</math> ;
''L'' fournit une hypothèse qui vérifie avec une probabilité <math>(1-\delta)</math>, <math>erreur(h)\leq \epsilon</math>.

''L'' est efficace si sa [[complexité en temps]] est polynomiale en  <math>1/\delta</math> et <math>1/\epsilon</math>.

== Contexte et historique ==
[[Image:Leslie Valiant.jpg|vignette|Leslie Valiant en 2005]]
L'apprentissage PAC a été proposé en 1984 par [[Leslie Valiant]]<ref>{{en}} L.G. Valiant. ''[http://web.mit.edu/6.435/www/Valiant84.pdf A Theory of the Learnable]'', Communications of the ACM, 27(11), pp. 1134-1142, November 1984.</ref>. Ce cadre formel a permis de rapprocher la [[théorie de la complexité (informatique théorique)|théorie de la complexité]] de l'apprentissage, et a donné naissance à ce que l'on appelle la ''computational learning theory''<ref name=haussler>{{harvsp|Haussler|1990}}</ref>.

Ce modèle a été critiqué, notamment à cause du choix de l'analyse dans le pire cas et de l'hypothèse que les données ne sont pas bruitées. D'autres modèles plus complexes ont alors été proposés<ref name=haussler/>.

== Apprentissage PAC-Bayésien ==
{{Article détaillé|Apprentissage PAC-Bayésien}} 

=== Principe théorique ===

L'apprentissage PAC-Bayésien s'inspire de l'[[inférence bayésienne]] dans un cadre PAC. Plus précisément, le PAC-Bayésien étudie la capacité prédictive d'une mesure ''a posteriori'' <math>Q</math> sur l'espace des predicteurs <math>H</math> par rapport à une mesure de référence ''a priori'' <math>P</math> et au jeu de données disponible. Ces terminologies n'ont pas la même signification qu'en inférence Bayésienne car le PAC-Bayésien n'utilise pas nécessairement le [[théorème de Bayes]].  

L'apprentissage PAC-Bayésien se base sur des bornes supérieures empiriques qui contrôlent l'erreur de généralisation de <math>Q</math>: <math>erreur(Q)= \mathbb{E}_{h\sim Q}[erreur(h)]</math>. Cette quantité est une extension naturelle de la notion d'erreur introduite précédemment quand des mesures sur <math>H</math> sont considérées. Grâce à cette notion d'erreur sur des mesures, on peut alors définir une la notion de classe ''PAC-Bayésienne apprenable'' de façon analogue à une classe PAC-apprenable.

En supposant un accès à un jeu de données d'entraînement <math>\mathcal{S}=(x_1,\cdots,x_m)\in X^m</math>, un résultat classique de la théorie PAC-Bayésienne est la borne de McAllester <ref name=mcallester>{{harvsp|McAllester|2003}}</ref>, donnée ci-dessous dans le cadre particulier de la classification. Pour toute mesure a priori <math>P</math> indépendante de <math>\mathcal{S}</math>, avec probabilité au moins <math>1-\delta</math> sur <math>\mathcal{S}</math>, pour toute mesure a posteriori <math>Q</math>,

<math>erreur(Q)\leq \frac{1}{m} \sum_{i=1}^m \mathbb{1}\{h(x_i) \neq c(x_i)\} + \sqrt{\frac{KL(Q,P) + \log(m/\delta)}{m}}. </math>

<math>KL</math> désigne la [[divergence de Kullback-Leibler]]. 
La théorie PAC-Bayésienne est suffisamment flexible pour dépasser le cadre de l'apprentissage supervisé, ce qui permet de changer l'objectif d'apprentissage supervisé <math>\mathbb{1}\{h(x) \neq c(x)\}</math> pour <math>x\in X, h\in H</math> pour n'importe quelle fonction de perte <math>\ell(h,x)</math> à valeurs dans <math>[0,1]</math>, couvrant ainsi d'autres domaines tels que l'[[apprentissage par renforcement]] <ref name=fard>{{harvsp|Fard|2012}}</ref>

=== Algorithme PAC-Bayésien ===

Les bornes PAC-Bayésiennes sont majoritairement empiriques. Elles définissent ainsi des objectifs pratiques d'optimisation (et donc des algorithmes d'apprentissage) PAC-Bayésiens. Un exemple reconnu est l'objectif suivant, dérivé d'une borne d'Olivier Catoni<ref name=catoni>{{harvsp|Catoni|2007}}</ref>,  valide pour une mesure a priori <math>P</math> et une ''température inverse'' <math>\lambda >0</math> fixées:

<math>\operatorname{argmin}_{Q}\frac{1}{m} \sum_{i=1}^m \mathbb{1}\{h(x_i) \neq c(x_i)\} + \frac{KL(Q,P)}{\lambda}. </math>

Cet objectif, lorsqu'il est minimisé sur l'ensemble des mesures sur <math>H</math>, possède une formulation explicite lié aux mesures de Gibbs (introduite, par exemple, dans le livre de Chafai et Malrieu <ref name=chafai>{{harvsp|Chafai|2016}}</ref>) et implique, par exemple la [[méthode de Monte-Carlo par chaînes de Markov]] pour une estimation pratique. Il peut être également considéré sur des sous-classes de cette collection de mesures et la phase d'optimisation peut requérir d'autres type d'outils comme l'optimisation convexe pour la classe des [[fonctions gaussiennes]] par exemple.

== Notes et références ==
<references />

== Voir aussi ==
=== Bibliographie ===
* M. Kearns,[[Umesh Vazirani|U. Vazirani]] ''An Introduction to Computational Learning Theory.'' [[MIT Press]], 1994.
* {{chapitre
 | titre chapitre = Probably Approximately Correct Learning
 | nom =Haussler | prénom = David
 | titre ouvrage =Proceedings of the Eighth National Conference on Artificial Intelligence
 | année =1990
 | lire en ligne = http://aaaipress.org/Papers/AAAI/1990/AAAI90-163.pdf
}}
* {{chapitre
 | titre chapitre = Simplified PAC-Bayesian margin bounds
 | nom =McAllester | prénom = David
 | titre ouvrage =Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop 2003. Proceedings
 | année =2003
 | lire en ligne= https://link.springer.com/chapter/10.1007/978-3-540-45167-9_16
}}
* {{chapitre
 | titre chapitre = Mesures de Gibbs
 | nom =Chafai| prénom = Djalil 
 | titre ouvrage =Recueil de Modèles Aléatoires
 | année =2016
 | lire en ligne= https://link.springer.com/chapter/10.1007/978-3-662-49768-5_5
}}
* {{chapitre
 | titre chapitre = PAC-Bayesian policy evaluation for reinforcement learning
 | nom =Fard| prénom = Mahdi Milani 
 | titre ouvrage = ArXiv
 | année =2012
 | lire en ligne= https://arxiv.org/abs/1202.3717
}}

* {{chapitre
 | titre chapitre = PAC-Bayesian supervised classification: the thermodynamics of statistical learning
 | nom =Catoni | prénom = Olivier
 | titre ouvrage = ArXiv
 | année =2007
 | lire en ligne= https://arxiv.org/abs/0712.0248
}}




=== Articles connexes ===
* [[Apprentissage automatique]]

=== Liens externes ===

* [https://fabien-torre.fr/Enseignement/Cours/Apprentissage-Automatique/pac.php Cours de Fabien Torre sur le modèle d'apprentissage PAC]
* D. Haussler. [http://www.cs.iastate.edu/~honavar/pac.pdf Overview of the Probably Approximately Correct (PAC) Learning Framework]. [[Article de revue]] sur la PAC, ses critiques, et d'autres formalismes.
* {{lien web|langue=en|url=https://jeremykun.com/2014/01/02/probably-approximately-correct-a-formal-theory-of-learning/|titre=Probably Approximately Correct — a Formal Theory of Learning|date=2 janvier 2014|auteur=Jeremy Kun|site=Math ∩ Programming}}

{{Palette|Apprentissage automatique}}
{{Portail|probabilités et statistiques|informatique théorique|données}}
[[Catégorie:Apprentissage automatique]]