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 ;
: un exemple particulier ;
$\cal C$ : une classe de concepts définis sur $\cal X$ ;
: un concept particulier ; on peut avoir deux vues d'un même concept :
- une vue purement ensembliste où est l'ensemble des exemples appartenant au concept ( $c \subseteq \cal X$ ) ;
- une vue fonctionnelle où 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 par rapport à un concept cible est définie comme la probabilité de trouver un exemple sur lequel et 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 :

Notion d'apprenabilité (forte)

Définition 1 Une classe $\cal C$ est PAC-apprenable s'il existe un algorithme 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}$ ,

fournit une hypothèse 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 obtenue est Probablement Approximativement Correcte (d'où; le nom du modèle PAC) ;
doit fonctionner quelle que soit la distribution des exemples ; cela dit, 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 en tirant exemples à l'aide de l'oracle ;
construire comme le plus petit rectangle contenant tous les exemples positifs de ;
retourner .

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 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$ ,

fournit une hypothèse 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 Rⁿ, 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 ]

site de Fabien Torre