site de Fabien Torre, université de Lille


Cadre PAC (Probably Approximately Correct)

Notes de cours sur le modèle PAC de Valiant.

Supports 2009-2010 (slides en PDF, 1 ou 4 ou 8 slides par page) : (1on1)(4on1)(8on1)

Origine

Le modèle PAC a défini par Leslie G. Valiant en 1984. L'une des motivations est de caractériser formellement les langages qui sont apprenables automatiquement à partir d'exemples, ceux qui ne le sont pas et également lequel de deux langages est plus facilement apprenable que l'autre.

On retrouve en fait dans la définition du modèle PAC une volonté de classifier les problèmes d'apprentissage comme on classe les problèmes en calculabilité et complexité.

Notations et protocole

  • $\cal X$ : l'espace de description des exemples ;
  • $x$ : un exemple particulier ;
  • $\cal C$ : une classe de concepts définis sur $\cal X$ ;
  • $c$ : un concept particulier ; on peut avoir deux vues d'un même concept :
    • une vue purement ensembliste où $c$ est l'ensemble des exemples appartenant au concept ($c \subseteq \cal X$) ;
    • une vue fonctionnelle où $c$ est une fonction booléenne sur les exemples

      
\begin{array}{rcll}
c & : & {\cal X} \rightarrow \{ -1, 1 \}...
...x{si $x$ est un contre-exemple du concept $c$} \\
\end{array}
  • $\cal D$ une distribution sur $\cal X$ ;
  • l'erreur d'une hypothèse $h$ par rapport à un concept cible $c$ est définie comme la probabilité de trouver un exemple sur lequel $c$ et $h$ sont en désaccord : \mbox{erreur}(h) = \mbox{Pr}_{x \in \cal D} \left[ c(x) \neq h(x) \right]
  • enfin, on suppose l'existence d'un orable noté $\mbox{EX}(c,{\cal D})$ ; à chaque appel, cet oracle tire un exemple de $\cal X$ suivant $\cal D$ et fournit cet exemple avec sa classe $\langle x , c(x) \rangle$.

Dans ce cadre, l'objectif est d'apprendre rapidement une hypothèse $h$ de faible erreur, avec peu d'appels à l'oracle.

Une instanciation possible :

dans R2

Notion d'apprenabilité (forte)

Définition 1   Une classe $\cal C$ est PAC-apprenable s'il existe un algorithme $L$ tel que
  • pour tout concept $c \in \cal C$,
  • pour toute distribution $\cal D$ sur $\cal X$,
  • pour tout $0 < \epsilon < \frac{1}{2}$,
  • pour tout $0 < \delta < \frac{1}{2}$,
$L$ fournit une hypothèse $h$ de $\cal C$ qui, avec une probabilité $1-\delta$, vérifie : \mbox{erreur}(h) \leq \epsilon

Remarques sur la définition d'apprenabilité :

  • $\epsilon$ est appelé paramètre d'erreur, $\delta$ paramètre de confiance ;
  • on veut pouvoir rendre $\epsilon$ et $\delta$ arbitrairement petits, à faible coût ;
  • l'hypothèse $h$ obtenue est Probablement Approximativement Correcte (d'où; le nom du modèle PAC) ;
  • $L$ doit fonctionner quelle que soit la distribution des exemples ; cela dit, $L$ perçoit cette distribution à travers l'oracle ;

En général, on ajoute une notion d'efficacité : $\cal C$ est dite efficacement PAC-apprenable si en plus des conditions précédentes, $L$ est polynmial en $\frac{1}{\epsilon}$ et $\frac{1}{\delta}$.

Une application

On va montrer ici que la classe des rectangles de ${\ensuremath{\rm I\!R}}^{2}$ parallèles aux axes est efficacement PAC-apprenable.

Proposition pour l'apprenant $L$ :

  • constituer un échantillon $S$ en tirant $m$ exemples à l'aide de l'oracle ;
  • construire $h$ comme le plus petit rectangle contenant tous les exemples positifs de $S$;
  • retourner $h$.

Il faut maintenant prouver que pour $m$ bien choisi et quels que soient le concept cible $c$, la distribution $\cal D$ et les paramètres $\epsilon$ et $\delta$, $L$ fournit une hypothèse $h$ qui vérifie $\mbox{erreur}(h) \leq \epsilon$ avec une probabilité $1-\delta$.

Intuitivement, plus $\epsilon$ et $\delta$ sont petits, plus le $m$ requis doit être grand. Il faudra vérifier que $m$ s'exprime comme un polynôme de $\frac{1}{\epsilon}$ et $\frac{1}{\delta}$.

... à suivre...

Notion d'apprenabilité faible

Définition 2   Une classe $\cal C$ est faiblement PAC-apprenable s'il existe un algorithme $L$ tel que
  • pour $0 < \epsilon_{0} < \frac{1}{2}$ fixé,
  • pour $0 < \delta_{0} < \frac{1}{2}$ fixé,
  • pour tout concept $c \in \cal C$,
  • pour toute distribution $\cal D$ sur $\cal X$,
$L$ fournit une hypothèse $h$ de $\cal C$ qui, avec une probabilité $1-\delta_{0}$, vérifie :  \mbox{erreur}(h) \leq \epsilon_{0}

Dans cette définition, on demande simplement que les hypothèses produites soient meilleures qu'un étiquetage purement aléaroire.

De manière assez inattendue, il a été prouvé que les deux notions d'apprenabilité sont équivalentes. Cela signifie que, dans le cadre PAC, un apprenant faible (un peu meilleur que l'aléatoire) peut être transformé en un apprenant fort (avec une erreur aussi proche de 0 que voulu), et ce en temps polynomial. Les preuves de ce résultat reposent sur la définition d'un apprenant fort opérant le boosting d'un apprenant faible.

Exercices

Prouver l'apprenabilité des rectangles parallèles aux axes dans Rn, quel que soit n.
Prouver l'apprenabilité des conjonctions de littéraux booléens.

Lectures

A. Blumer, A. Ehrenfeucht, D. Haussler, M. K. Warmuth
Learnability and the Vapnik-Chervonenkis dimension
Journal of the ACM, 36(4):929--965, 1989.
version pdf ]
D. Haussler, M. J. Kearns, N. Littlestone, M. K. Warmuth
Equivalence of Models for Polynomial Learnability
Information and Computation 95(2): 129-161, 1991.
version pdf ]
Fabien Torre Valid HTML5! Valid CSS!
Accueil > Enseignement > Cours > Intelligence Artificielle > Apprentissage automatique > Cadre PAC
(contenu mis à jour )
site de Fabien Torre, université de Lille

Description

Survoler un lien de navigation pour lire sa description ici...