Apprentissage PAC-Bayésien

Apprentissage PAC-bayésien

Type	Théorie, apprentissage PAC, inférence bayésienne

L'apprentissage PAC bayésien (probably approximately correct bayesian learning) est une branche de l'apprentissage statistique, et plus précisément de l'apprentissage PAC qui s'inspire de l'inférence bayésienne. Plus précisément, l'apprentissage PAC-bayésien a pour but de contrôler la capacité de généralisation d'un algorithme d'apprentissage ou, en d'autres termes, à quel point un algorithme entraîné sur un certain jeu de données d'apprentissage est capable d'être performant sur une donnée jamais vue auparavant. Pour ce faire, la théorie PAC-Bayésienne s'inspire de l'idée de l'inférence bayésienne de modéliser une connaissance a priori du problème d'interêt au sein du processus d'apprentissage puis de la transformer en fonction du jeu de données d'entraînement. Néanmoins, l'apprentissage PAC-Bayésien ne se base pas sur le théorème de Bayes, ce qui différencie explicitement les deux domaines.

Cadre théorique

Le cadre théorique requis pour l'apprentissage PAC-Bayésien est minimaliste. Un problème d'apprentissage est défini comme un tuple $({\mathcal {Z}},{\mathcal {H}},\ell )$ où ${\mathcal {Z}}$ est l'espace des données (typiquement ${\mathcal {Z}}={\mathcal {X}}\times {\mathcal {Y}}$ pour un problème de classification), ${\mathcal {H}}$ est l'espace des prédicteurs et $\ell :{\mathcal {H}}\times {\mathcal {Z}}\rightarrow [0,1]$ est la fonction de perte qui définit l'objectif d'apprentissage qu'un prédicteur $h$ doit satisfaire pour une donnée $z$.

Un jeu de données d'entraînement est supposé disponible $S=(z_{1},\cdots ,z_{m})$, ces données sont identiquement et independamment distribuées selon une mesure $\mu$. L'ensemble ${\mathcal {M}}_{1}({\mathcal {H}})$ désigne l'ensemble des mesures de probabilités sur ${\mathcal {H}}$. L'apprentissage PAC-Bayésien a pour but de construire une mesure a posteriori $Q\in {\mathcal {M}}_{1}({\mathcal {H}})$ à partir de $S,\ell$ et d'une mesure a priori $P$.

Pour attester de l'efficacité de l'entraînement, le critère théorique d'interêt est l' erreur de généralisation d'une mesure $Q\in {\mathcal {M}}_{1}({\mathcal {H}})$: $R(Q)=\mathbb {E} _{h\sim Q}\mathbb {E} _{z\sim \mu }[\ell (h,z)].$ Cette erreur de généralisation est l'erreur moyenne qu'effectue un prédicteur tiré selon $Q$ sur une nouvelle donnée $z$ indépendante de $S$. Pour contrôler cette erreur, l'apprentissage PAC-Bayésien exploitel'erreur d'entraînement empirique: ${\hat {R}}_{m}(Q)=\mathbb {E} _{h\sim Q}\left[{\frac {1}{m}}\sum _{i=1}^{m}\ell (h,z_{i})\right].$

Deux résultats classiques

Pour contrôler l'erreur de généralisation, l'apprentissage PAC-Bayésien se base sur des bornes supérieures empiriques. Deux résultats largement utilisés sont les bornes de McAllester et Catoni.

Borne de McAllester

Pour toute mesure a priori $P$ indépendante de $S$, avec probabilité au moins $1-\delta$ sur $S$, pour toute mesure a posteriori $Q$,

$R(Q)\leq {\hat {R}}_{m}(Q)+{\sqrt {\frac {KL(Q,P)+\ln(m/\delta )}{m}}}.$

$KL$ désigne la divergence de Kullback-Leibler. Cette borne a été légèrement raffinée par Maurer , transformant ainsi le facteur $\ln(m)$ en $\ln(2{\sqrt {m}})$.

Borne de Catoni

Pour toute mesure a priori $P$ indépendante de $S$, pour tout paramètre $\lambda >0$, avec probabilité au moins $1-\delta$ sur $S$, pour toute mesure a posteriori $Q$,

$R(Q)\leq {\hat {R}}_{m}(Q)+{\frac {KL(Q,P)+\ln(1/\delta )}{\lambda }}+{\frac {\lambda }{2m}}.$

Le résultat présenté est de facto une relaxation de la borne originale de Catoni. Elle suggère une procédure algorithmique présentée ci-dessous.

Des bornes de généralisation valides au cours de l'entraînement

Une approche statistique pour obtenir des garanties de généralisation sur des prédicteurs consiste à ne pas utiliser une partie des données d'entraînement pour s'en servir comme test après coup. Des inégalités de concentration permettent ainsi de déduire des garanties de généralisation à partir de l'erreur de test. Les bornes PAC-Bayésiennes permettent d'obtenir des garanties de généralisation directement à partir des données d'entraînement, sans sacrifier une partie des données.

Un algorithme d'apprentissage PAC-Bayésien

Lee caractère empirique des bornes de McAllester et Catoni définissent des objectifs pratiques d'optimisation (et donc des algorithmes d'apprentissage) PAC-Bayésiens. L'algorithme suivant est basé sur la borne de Catoni (plus facile à optimiser car linéaire en la divergence de Kullback Leibler et l'erreur empirique) et cherche à obtenir la distribution $P_{\lambda }^{*}$ définie ci-dessous pour une température inverse $\lambda >0$ et toute mesure a priori $P$ fixées:

$P_{\lambda }^{*}:=\operatorname {argmin} _{Q\in {\mathcal {M}}_{1}({\mathcal {H}})}{\hat {R}}_{m}(Q)+{\frac {KL(Q,P)}{\lambda }}.$

$P_{\lambda }^{*}$, appelée communément la mesure posterieure de Gibbs par rapport à $P$, possède une formulation explicite donnée par:

$dP_{\lambda }^{*}(h)={\frac {\exp \left(-{\frac {\lambda }{m}}\sum _{i=1}^{m}\ell (h,z_{i})\right)}{\mathbb {E} _{h\sim P}\left[\exp \left(-{\frac {\lambda }{m}}\sum _{i=1}^{m}\ell (h,z_{i})\right)\right]}}dP(h).$

Les mesures de Gibbs apparaissent au delà de l'apprentissage PAC-Bayésien, comme par exemple, en physique statistique. Malgré leur formulation mathématique explicite, leur estimation peut se révéler ardue et requiert, par exemple, des estimations basées sur la méthode de Monte-Carlo par chaînes de Markov. Si l'on considère une approximation de la postérieure de Gibbs au sein d'une sous-classe de mesures, la phase d'optimisation peut requérir d'autres type d'outils comme l'optimisation convexe pour la classe des fonctions gaussiennes quand la fonction de perte est convexe.

Extensions et applications

Choix de la mesure a priori

Pour obtenir des garanties de généralisation fines, il est essentiel de considérer une 'bonne' mesure a priori, c'est-à-dire une mesure qui est déjà informative sur le problème d'apprentissage d'interêt. Néanmoins, les bornes de McAllester et Catoni n'autorisent pas l'utilisation des données d'entraînement pour trouver une telle mesure. Des stratégies alternatives existent pour contourner ce problème.

Pré-entraîner la mesure a priori : Il est possible de couper le jeu de données ${\mathcal {S}}$ en deux jeux distincts ${\mathcal {S}}_{1},{\mathcal {S}}_{2}$. ${\mathcal {S}}_{1}$ permet de pré-entrainer une mesure a priori et ${\mathcal {S}}_{2}$ sert à l'entraînement PAC-Bayésien. La mesure obtenue a posteriori exploite l'entièreté des données de ${\mathcal {S}}$, mais les garanties de généralisation ne portent que sur ${\mathcal {S}}_{2}$.

Utiliser une mesure a priori différentiellement confidentielle : La confidentialité différentielle est exploitable en apprentissage PAC-Bayésien pour utiliser des mesures a priori qui dépendent des données. La mesure postérieure de Gibbs, en particulier, est différentiellement confidentielle, ce qui permet d'avoir la borne suivante, dérivée de celle de McAllester. Pour toute température inverse $\lambda >0$ et toute mesure a priori $P$, avec probabilité au moins $1-\delta$:

$R(P_{\lambda }^{*})\leq {\hat {R}}_{m}(P_{\lambda }^{*})+{\sqrt {\frac {\ln(2m/\delta )}{m}}}+{\frac {4\lambda ^{2}}{m^{2}}}+{\frac {2\lambda }{m}}{\sqrt {\frac {\ln(2/\delta )}{m}}}.$

Cette borne montre que, comme les mesures de Gibbs sont différentiellements confidentielles, il est possible de supprimer la divergence de Kullback Leibler des bornes PAC-Bayésiennes, ce qui simplifie le calcul de la borne (et la raffine potentiellement).

Application aux réseaux de neurones

L'apprentissage PAC-Bayésien est utilisable en apprentissage profond pour obtenir des réseaux de neurones qui, une fois entraînés, possèdent des garanties de généralisation issues de la phase d'apprentissage. Un exemple de type de réseau de neurones entraînés de façon PAC-Bayésienne est le cas des réseaux de neurones probabilistes (où chacun des poids du réseau est associé à une loi de probabilité). Pour ce faire, le jeu de données ${\mathcal {S}}$ est séparé en deux jeux distincts ${\mathcal {S}}_{1},{\mathcal {S}}_{2}$ L'entraînement se fait en deux étapes:

Création d'un réseau de neurones probabiliste a priori : un réseau de neurones est pré-entrainé sur ${\mathcal {S}}_{1}$ de façon traditionnelle, par exemple en utilisant une descente de gradient stochastique couplée à de la rétro-propagation. Le réseau ainsi obtenu est alors la moyenne d'un réseau de neurones probabiliste a priori.

Entraînement PAC-Bayésien : le réseau probabiliste a priori est entraîné à son tour sur ${\mathcal {S}}_{2}$ via un algorithme PAC-Bayésien, cela fournit un réseau final a posteriori qui contient des garanties de généralisation impliquant le réseau probabiliste a priori ainsi que les données de ${\mathcal {S}}_{2}$

Voir aussi

Bibliographie

• Pascal Germain, « Généralisations de la théorie PAC-bayésienne pour l'apprentissage inductif, l'apprentissage transductif et l'adaptation de domaine. », dans Université Laval, 2015 (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)
• Olivier Catoni, « PAC-Bayesian supervised classification: the thermodynamics of statistical learning », dans ArXiv, 2007 (lire en ligne)
• Djalil Chafai, « Mesures de Gibbs », dans Recueil de Modèles Aléatoires, 2016 (lire en ligne)
• Andreas Maurer, « A note on the PAC Bayesian theorem. », dans ArXiv, 2004 (lire en ligne)
• Pierre Alquier, « User-friendly introduction to PAC-Bayes bounds », dans ArXiv, 2021 (lire en ligne)
• Gintare Karolina Dziugaite, « Data-dependent PAC-Bayes priors via differential privacy », dans Neural Information Processes Systems 2018, 2018 (lire en ligne)
• Gintare Karolina Dziugaite, « Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data », dans Association for Uncertainty in Artifical Intelligence, 2017 (lire en ligne)

Articles connexes

• Apprentissage automatique

Liens externes

• [1]Thèse de Pascal Germain qui introduit le cadre d'étude PAC-Bayésien dans sa section 'Mise en Contexte'.