Comprendre Apprentissage PAC
Le cadre commence par admettre ce qu'on ne peut pas promettre. Un echantillon fini peut toujours induire en erreur, si bien qu'exiger avec certitude l'hypothese exactement correcte interdirait purement et simplement d'apprendre. PAC demande plutot une hypothese dont l'erreur vraie vaut au plus epsilon, et accepte une probabilite d'echec delta - l'echantillon peut n'etre pas representatif, et aucune methode ne l'empeche. Une classe est apprenable lorsque le nombre d'echantillons necessaire pour tenir les deux cibles s'ecrit en fonction d'epsilon et delta seuls.
Pour une classe finie, l'argument est un denombrement. L'inegalite de Hoeffding borne la chance qu'une hypothese fixee montre une erreur d'apprentissage eloignee de son erreur vraie ; la borne de l'union multiplie cela par le nombre d'hypotheses pour les couvrir toutes a la fois. En resolvant pour la taille d'echantillon, on obtient n de l'ordre de (log|H| + log(1/delta)) / epsilon au carre. Le logarithme est toute l'histoire : une classe de deux exige 220 echantillons pour epsilon 0,1 et 95 % de confiance, une classe de plus d'un million en exige 878.
L'uniformite n'est pas une subtilite technique. L'apprenant examine l'echantillon puis choisit : l'hypothese renvoyee est donc elle-meme fonction des donnees et n'est pas fixee a l'avance. Une borne ne valant que pour une hypothese specifiee d'avance ne dirait rien de celle reellement produite. Payer log|H| achete un enonce sur tous les membres simultanement, ce qui couvre necessairement la gagnante.
Ce qui se passe sans cela est mesurable. Sur des donnees ou chaque hypothese a une erreur vraie exactement egale a 0,5, une hypothese fixee montre une erreur d'apprentissage a 0,0002 de la verite, tandis que la meilleure de mille se situe 0,1149 en dessous. Aucune de ces mille n'est meilleure qu'une autre ; l'ecart est entierement le cout de la selection, et c'est pourquoi un score d'apprentissage n'est pas une estimation des performances futures.
Comment calculer
P( err(ĥ) ≤ min_h err(h) + ε ) ≥ 1 − δ, n ≥ (ln|H| + ln(2/δ)) / (2ε²)
où
- ε
- la tolerance : de combien au-dessus de la meilleure erreur possible on accepte d'etre
- δ
- la probabilite d'echec : a quelle frequence un echantillon non representatif peut mettre la garantie en defaut
- ĥ
- l'hypothese renvoyee par l'algorithme apres avoir vu l'echantillon
- ln|H|
- le prix de la recherche ; pour les classes infinies, la dimension VC le remplace
Exemple : Apprentissage PAC
A epsilon 0,1 et delta 0,05, les echantillons requis valent 220 pour une classe de 2, 300 pour 10, 530 pour 1 000 et 878 pour 1 048 576. Un demi-million de fois plus d'hypotheses coute 658 echantillons de plus, car l'exigence croit avec le nombre de chiffres de la taille de la classe.
L'effet de selection contre lequel la borne protege, sur du bruit pur ou chaque hypothese a une erreur vraie de 0,5 : la meilleure de 1 est 0,0002 sous la verite sur son echantillon, la meilleure de 10 est 0,0549 dessous, la meilleure de 100 est 0,0887 dessous et la meilleure de 1 000 est 0,1149 dessous.
Pour les classes infinies, le meme argument tourne avec la dimension VC a la place de log|H|, puisque le lemme de Sauer plafonne les comportements distincts sur n points par un polynome - a la dimension 2 et n = 20, 211 d'entre eux plutot que 1 048 576.
Questions fréquentes
Les bornes PAC servent-elles en pratique ?
Rarement comme nombres. Elles sont pessimistes sur toute distribution et exigent en general bien plus de donnees que ce qui fonctionne reellement. Leur valeur est structurelle : elles disent quelle quantite controle la generalisation, et c'est cela qui se transfere.
Que signifie « sans hypothese de distribution » ?
La borne tient quelle que soit la loi generant les donnees, ce qui explique qu'elle soit pessimiste et lache. Elle exige en revanche que apprentissage et test proviennent de la meme loi - une vraie hypothese, et la premiere a ceder en pratique.
L'apprentissage PAC dit-il comment trouver l'hypothese ?
Pas en soi. La complexite d'echantillon concerne l'information, non le calcul ; une classe peut etre apprenable avec peu de donnees tandis que la recherche d'une bonne hypothese reste hors d'atteinte.
En résumé
PAC vaut pour sa forme plutot que pour ses nombres. Il dit que la generalisation s'achete en limitant la recherche, facture cette limite comme un logarithme, et rend clair qu'un score d'apprentissage est un compte rendu sur une recherche et non une estimation de l'erreur future.