Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Dimension de Vapnik-Chervonenkis
Résumé
Dans la théorie de l'apprentissage automatique, la dimension de Vapnik-Tchervonenkis ou dimension de Vapnik-Chervonenkis, aussi connue sous le nom de dimension VC (par emprunt à la translittération anglaise du russe), est une mesure de la capacité d'un algorithme de classification statistique. Elle est définie comme le cardinal du plus grand ensemble de points que l'algorithme peut pulvériser. C'est un concept central dans la théorie de Vapnik-Tchervonenkis. Il a été défini par Vladimir Vapnik et Alexeï Tchervonenkis.
De manière informelle, la capacité d'un modèle de classification correspond à sa complexité. Par exemple, considérons comme modèle de classification la fonction de Heaviside d'un polynôme de degré élevé : si en un point donné la valeur du polynôme est positive, ce point est étiqueté positif ; sinon, il est étiqueté négatif. Un polynôme de degré assez grand peut être très sinueux et bien correspondre à un échantillon de points d'apprentissage. Mais du fait de cette sinuosité élevée, on peut penser que ce modèle de classification donnera des évaluations fausses pour d'autres points. Un tel polynôme aura une capacité élevée. Si maintenant, nous remplaçons dans ce modèle ce polynôme de degré élevé par une fonction linéaire, le modèle obtenu peut ne pas bien correspondre à l'échantillon d'apprentissage, car sa capacité est faible. Nous décrivons cette notion de capacité de manière plus rigoureuse ci-dessous.
On se place dans un ensemble U. Soit H une famille (finie) de sous-ensembles (finis) de U, et C un sous-ensemble de U.
La trace de H sur le sous ensemble C de U est :
On dit que H pulvérise C si la trace de H sur C est égale à l'ensemble des parties de C, i.e:
ou de manière équivalente avec l'égalité des cardinaux .
La dimension VC de H est alors le cardinal de l'ensemble C le plus grand qui peut être pulvérisé par H.
On dit qu'un modèle de classification , prenant comme paramètre un vecteur θ, pulvérise un ensemble de données () si, pour tout étiquetage de cet ensemble de données, il existe un θ tel que le modèle ne fasse aucune erreur dans l'évaluation de cet ensemble de données.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.