Apprentissage PAC

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 («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 ait une petite erreur, 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]