Comprendre Dimension de Vapnik-Chervonenkis
Compter les hypotheses fonctionne pour une classe finie et s'effondre aussitot pour les classes usuelles : il y a une infinite d'intervalles sur une droite, une infinite d'hyperplans dans le plan. Or ce qui compte pour la generalisation n'a jamais ete le denombrement. C'est le nombre de comportements reellement distincts que la classe peut exhiber sur les donnees dont vous disposez, et ce nombre est fini meme quand la classe ne l'est pas.
Un ensemble de points est eclate par une famille lorsque chaque attribution d'etiquettes a ces points est realisee par un membre de la famille. La dimension VC est la taille du plus grand ensemble eclate. Les quantificateurs meritent attention : un ensemble de cette taille doit etre eclate, et aucun ensemble d'une unite plus grand ne doit l'etre. Etablir une valeur demande donc deux arguments, un exemple et une impossibilite, et c'est pourquoi le chiffre se cherche au lieu de se reciter.
Les intervalles sur une droite rendent la definition concrete. Deux points sont faciles : un intervalle peut contenir les deux, l'un ou l'autre, ou aucun. Trois points les mettent en echec : inclure les deux extremes force le point median a l'interieur, si bien que l'etiquetage (1, 0, 1) est inatteignable. Sept etiquetages sur huit sont realisables et la dimension vaut donc 2, retenue par un seul motif manquant. Les rectangles alignes eclatent les quatre points d'un losange et echouent sur cinq, car les extremes dans les quatre directions enferment ce qui reste.
La recompense est le lemme de Sauer : une classe de dimension VC d realise au plus la somme des coefficients binomiaux C(n, 0) a C(n, d) etiquetages sur n points, un polynome plutot que 2^n. Comme une borne uniforme de generalisation facture le logarithme du nombre de comportements distincts, ce polynome devient de l'ordre de d log n, assez petit pour que la garantie continue de se resserrer a mesure que les donnees s'accumulent. La capacite cesse ainsi d'etre un compte d'hypotheses pour devenir un compte de comportements.
Comment calculer
VC(H) = max{ k : some S with |S| = k is shattered }, |H|_S ≤ Σ_{i≤d} C(n, i)
où
- H
- la classe d'hypotheses : tous les intervalles, tous les rectangles, tous les hyperplans
- shattered
- eclate : chacun des 2^k etiquetages de S est realise par un membre de H
- d
- la dimension VC de H
- |H|_S
- le nombre d'etiquetages distincts que H peut produire sur un echantillon de taille n
Exemple : Dimension de Vapnik-Chervonenkis
Les seuils sur une droite ont la dimension VC 1 et les intervalles 2, les deux trouves en enumerant chaque etiquetage de chaque ensemble candidat plutot qu'a vue. Sur trois points, les intervalles realisent 7 des 8 etiquetages, et il manque exactement (1, 0, 1).
Les rectangles alignes eclatent le losange (0,1), (1,0), (2,1), (1,2) - les 16 etiquetages sont realises - et echouent des qu'on ajoute le centre (1,1), puisqu'un rectangle contenant les quatre extremes contient aussi le centre.
A la dimension VC 2, le compte des etiquetages atteignables vaut 4, 7, 16, 56, 211 pour n valant 2, 3, 5, 10, 20, contre 4, 8, 32, 1024 et 1 048 576 sans restriction. A n = 2 la borne autorise encore tout ; l'ecart s'ouvre immediatement apres.
Questions fréquentes
Une dimension VC plus elevee est-elle pire ?
C'est davantage de capacite, ce qui coute des donnees sans etre mauvais en soi. Une classe trop petite pour le probleme ne peut pas representer la verite du tout. La dimension dit ce que vous payez : elle accompagne donc l'arbitrage biais-variance au lieu de s'y opposer.
Une dimension VC finie garantit-elle de bonnes performances ?
Elle garantit que l'erreur d'apprentissage rejoint l'erreur vraie a mesure que les donnees s'accumulent, et rien sur le fait que l'une ou l'autre soit petite. Une classe peut generaliser parfaitement tout en se trompant uniformement, ce qui est la moitie « biais » de l'arbitrage.
Pourquoi les reseaux modernes generalisent-ils avec une capacite enorme ?
Les bornes VC classiques sont pessimistes sur toutes les distributions et tous les echantillons, et deviennent vides a ces nombres de parametres. L'explication est une question de recherche active, impliquant la regularisation implicite de l'optimiseur et des mesures fondees sur la marge, non un defaut de la definition.
En résumé
La dimension VC repond a une question que le denombrement ne peut pas traiter : ce qu'une classe d'une infinite d'hypotheses sait reellement faire sur les donnees presentes. Etablir une valeur demande deux arguments, un exemple qui eclate et une impossibilite un point plus loin, et c'est pourquoi elle se cherche au lieu de se reciter.