Apprentissage PAC

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

L'apprentissage PAC (pour 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 l'apprentissage supervisé. Il a été proposé par Leslie Valiant en 1984.

Principe[modifier | modifier le code]

Dans le cadre de l'apprentissage PAC, l'algorithme «apprenant» reçoit des données d'apprentissage («samples») 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 que les données d'apprentissage) avec une erreur minimale, et ceci avec forte probabilité.

Cadre formel[modifier | modifier le code]

Le cadre le plus simple est le suivant[1].

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 distribution 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'elle 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 : .

On dit que H est PAC apprenable si il existe un algorithme L tel que :

  • pour tout concept c de H ;
  • pour toute distribution D sur X ;
  • pour tout paramètre d'erreur  ;
  • pour tout paramètre de confiance  ;

L fournit une hypothèse qui vérifie avec une probabilité , .

L est efficace si sa complexité en temps est polynomiale en et .

Contexte et historique[modifier | modifier le code]

Leslie Valiant en 2005

L'apprentissage PAC a été proposé en 1984 par Leslie Valiant[2]. Ce cadre formel a permis de rapprocher la théorie de la complexité de l'apprentissage, et a donné naissance à ce que l'on appelle la computational learning theory[3].

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[3].

Notes et références[modifier | modifier le code]

  1. Voir Cours de Fabien Torre sur le modèle d'apprentissage PAC.
  2. (en) L.G. Valiant. A Theory of the Learnable, Communications of the ACM, 27(11), pp. 1134-1142, November 1984.
  3. a et b Haussler 1990

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • 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, (lire en ligne)

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]