Dimension de Vapnik-Chervonenkis
# Dimension de Vapnik-Chervonenkis

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.

## Présentation

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.

## Définition formelle

### Pour des ensembles

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 :

    $T_{H}(C):=\{h\cap C\mid h\in H\}$

On dit que H pulvérise C si la trace de H sur C est égale à l'ensemble des parties de C, i.e:

$P(C)=T_{H}(C)$ ou de manière équivalente avec l'égalité des cardinaux $|H\cap C|=2^{|C|}$.

La dimension VC de H est alors le cardinal de l'ensemble C le plus grand qui peut être pulvérisé par H.

### En apprentissage

On dit qu'un modèle de classification $f$, prenant comme paramètre un vecteur θ, pulvérise un ensemble de données ($x_{1},x_{2},\ldots ,x_{n}$) si, pour tout étiquetage de cet ensemble de données, il existe un θ tel que le modèle $f$ ne fasse aucune erreur dans l'évaluation de cet ensemble de données.

On appellera alors dimension VC d'un modèle $f$ le cardinal du plus grand ensemble pulvérisé par $f$.

En notant $D_{f}$ la dimension VC du modèle $f$, on a donc :

$D_{f}=\max\{k\,|\,card(S)=k{\text{ et }}f{\text{ pulverise }}S\}$

## Exemple

Par exemple, prenons comme modèle de classification une droite. On étudie si la ligne peut séparer les données positives (+) des données négatives (-). Si on prend 3 points non alignés, la ligne peut les pulvériser. Cependant, la ligne ne peut pas pulvériser 4 points. Ainsi, la dimension VC de la droite est de 3. Il est important de se rappeler qu'on peut choisir les positions des points qu'on va pulvériser avec la droite, mais qu'on ne peut pas ensuite modifier ces positions lorsqu'on permute leur étiquetage. Ci-dessous, pour la pulvérisation de 3 points, on montre seulement 3 des 8 étiquetages possibles (1 seule possibilité de les étiqueter tous les 3 positifs, 3 possibilités d'en étiqueter 2 sur 3 positifs, 3 possibilités d'en étiqueter 1 sur 3 positif, 1 possibilité de n'en étiqueter aucun positif).

| Pulvérisation de 3 points | Pulvérisation de 3 points | Pulvérisation de 3 points | Lorsqu'il y a 4 points, la pulvérisation est impossible |
| - | - | - | - |

## Applications

La dimension VC est utilisée en théorie de l'apprentissage automatique pour calculer la valeur de la marge d'erreur probable maximum d'un test de modèle de classification. Pour le test d'un modèle de classification sur des données extraites de l'échantillon d'apprentissage de manière indépendante et identiquement distribuée, cette valeur est calculée d'après la formule suivante :

Erreur d'apprentissage + ${\sqrt {h(\log(2N/h)+1)-\log(\eta /4) \over N}}$

avec la probabilité de $1-\eta$, où $h$ est la dimension VC du modèle de classification, et $N$ la taille de l'échantillon d'apprentissage. Cette formule n'est valide que lorsque $h<N$.

