Apprentissage PAC

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 ${\displaystyle Q}$ sur l'espace des predicteurs ${\displaystyle H}$ par rapport à une mesure de référence a priori ${\displaystyle P}$ 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écéssairement 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 ${\displaystyle Q}$: ${\displaystyle erreur(Q)=\mathbb {E} _{h\sim Q}[erreur(h)]}$. Cette quantité est une extension naturelle de la notion d'erreur introduite précédemment quand des mesures sur ${\displaystyle H}$ 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 ${\displaystyle {\mathcal {S}}=(x_{1},\cdots ,x_{m})\in X^{m}}$, un résultat classique de la théorie PAC-Bayésienne est la borne de McAllester [4], donnée ci-dessous dans le cadre particulier de la classification. Pour toute mesure a priori ${\displaystyle P}$ indépendante de ${\displaystyle {\mathcal {S}}}$, avec probabilité au moins ${\displaystyle 1-\delta }$ sur ${\displaystyle {\mathcal {S}}}$, pour toute mesure a posteriori ${\displaystyle Q}$,

${\displaystyle 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}}}.}$

${\displaystyle KL}$ 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é ${\displaystyle \mathbb {1} \{h(x)\neq c(x)\}}$ pour ${\displaystyle x\in X,h\in H}$ pour n'importe quelle fonction de perte ${\displaystyle \ell (h,x)}$ à valeurs dans ${\displaystyle [0,1]}$, couvrant ainsi d'autres domaines tels que l'apprentissage par renforcement [5]

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[6], valide pour une mesure a priori ${\displaystyle P}$ et une température inverse ${\displaystyle \lambda >0}$ fixées:

${\displaystyle \operatorname {argmin} _{Q}{\frac {1}{m}}\sum _{i=1}^{m}\mathbb {1} \{h(x_{i})\neq c(x_{i})\}+{\frac {KL(Q,P)}{\lambda }}.}$

Cet objectif, lorsqu'il est minimisé sur l'ensemble des mesures sur ${\displaystyle H}$, possède une formulation explicite lié aux mesures de Gibbs (introduite, par exemple, dans le livre de Chafai et Malrieu [7]) 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.

• M. Kearns,U. Vazirani An Introduction to Computational Learning Theory. MIT Press, 1994.
• David Haussler, « Probably Approximately Correct Learning », dans Proceedings of the Eighth National Conference on Artificial Intelligence, 1990 (lire en ligne)
• David McAllester, « Simplified PAC-Bayesian margin bounds », dans Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop 2003. Proceedings, 2003 (lire en ligne)
• Djalil Chafai, « Mesures de Gibbs », dans Recueil de Modèles Aléatoires, 2016 (lire en ligne)
• Mahdi Milani Fard, « PAC-Bayesian policy evaluation for reinforcement learning », dans ArXiv, 2012 (lire en ligne)

• Olivier Catoni, « PAC-Bayesian supervised classification: the thermodynamics of statistical learning », dans ArXiv, 2007 (lire en ligne)

• Apprentissage automatique

• Cours de Fabien Torre sur le modèle d'apprentissage PAC
• D. Haussler. Overview of the Probably Approximately Correct (PAC) Learning Framework. Article de revue sur la PAC, ses critiques, et d'autres formalismes.
• (en) Jeremy Kun, « Probably Approximately Correct — a Formal Theory of Learning », sur Math ∩ Programming, 2 janvier 2014