Dimension VC et capacité
La dimension de Vapnik-Chervonenkis mesure la capacité d'une classe de modèles par le plus grand ensemble de points qu'elle peut étiqueter de toutes les manières possibles, quantifiant ainsi la complexité d'un apprenant.
Definition
La dimension de Vapnik-Chervonenkis d'une classe de classifieurs est le plus grand nombre de points que la classe peut étiqueter de toutes les manières possibles ; c'est une mesure de capacité qui borne la mesure dans laquelle la classe peut surapprendre et, par conséquent, la quantité de données nécessaires pour apprendre de manière fiable.
Scope
Ce sujet aborde les mesures de la richesse d'une classe d'hypothèses : la notion de « séparation » (shattering) d'un ensemble de points, la dimension de Vapnik-Chervonenkis comme taille du plus grand ensemble séparé, la fonction de croissance, et la manière dont ces mesures de capacité interviennent dans les bornes de généralisation. Il explique pourquoi la capacité, plutôt que le seul nombre de paramètres, régit la capacité de généraliser.
Core questions
- Que signifie pour une classe de modèles de « séparer » (shatter) un ensemble de points ?
- Comment la dimension de Vapnik-Chervonenkis est-elle définie et calculée ?
- Pourquoi la capacité plutôt que le nombre de paramètres régit-elle la généralisation ?
- Comment la capacité intervient-elle dans les bornes de l'écart entre l'erreur d'entraînement et l'erreur réelle ?
Key theories
- Séparation (Shattering) et capacité
- Une classe « sépare » (shatters) un ensemble de points si elle peut réaliser toutes les étiquetages possibles de ceux-ci ; le plus grand ensemble de ce type définit la dimension de Vapnik-Chervonenkis, une mesure indépendante de la distribution de la flexibilité de la classe.
- La capacité contrôle la convergence uniforme
- Une capacité finie garantit que l'erreur empirique converge vers l'erreur réelle uniformément sur la classe, de sorte qu'un apprenant avec une dimension de Vapnik-Chervonenkis bornée ne peut pas surapprendre arbitrairement à mesure que les données augmentent.
- Capacité versus nombre de paramètres
- La capacité, et non le nombre brut de paramètres, détermine la généralisation, de sorte que deux modèles ayant le même nombre de paramètres peuvent différer considérablement quant à la quantité de données qu'ils nécessitent.
Clinical relevance
La dimension de Vapnik-Chervonenkis constitue la mesure centrale de capacité de la théorie classique de l'apprentissage et justifie la pratique du contrôle de la complexité des modèles ; elle sous-tend l'analyse basée sur la marge des machines à vecteurs de support et encadre les efforts continus pour comprendre pourquoi certains modèles à très haute capacité généralisent néanmoins.
History
Vapnik et Chervonenkis ont introduit la dimension qui porte leurs noms dans des travaux de la fin des années 1960 et dans l'article de 1971 sur la convergence uniforme, établissant une théorie de la capacité indépendante de la distribution. Le concept est devenu fondamental pour les machines à vecteurs de support et pour l'analyse plus large de la généralisation.
Key figures
- Vladimir Vapnik
- Alexey Chervonenkis
Related topics
Seminal works
- vapnik1971
- vapnik1995
- hastie2009
Frequently asked questions
- Que signifie la « séparation » (shattering) ?
- Un ensemble de points est « séparé » (shattered) par une classe de modèles si, pour chaque assignation possible d'étiquettes à ces points, un modèle de la classe produit exactement cet étiquetage. La taille du plus grand ensemble séparable est la dimension de Vapnik-Chervonenkis.
- Un modèle avec plus de paramètres a-t-il toujours une capacité plus élevée ?
- Pas nécessairement. La capacité est mesurée par la dimension de Vapnik-Chervonenkis ou des quantités connexes, qui peuvent différer du nombre de paramètres. La bonne mesure de la complexité pour la généralisation est la capacité, et non simplement le nombre de paramètres d'un modèle.