Classe VC

Une classe de Vapnik-Tchervonenkis ou classe VC (suivant la translitération anglaise) est un sous-ensemble d'un ensemble donné dont la dimension VC est finie. Cette notion est utilisée en apprentissage machine (« machine learning ») puisqu'elle est une condition nécessaire et suffisante au principe de minimisation du risque empirique (principe MRE).

Définition

Classe VC d'ensemble

Soit ${\mathcal {C}}$ une classe de sous-ensembles d'un ensemble ${\mathcal {X}}$. Soit $\{x_{1},\dots ,x_{n}\}\in {\mathcal {X}}^{n}$ des éléments de ${\mathcal {X}}$. On dit que ${\mathcal {C}}$ prélève un sous-ensemble $A\subset \{x_{1},\dots ,x_{n}\}$ s'il existe $C\in {\mathcal {C}}$ tel que $A=C\cap \{x_{1},\dots ,x_{n}\}$. On dit que ${\mathcal {C}}$ pulvérise $\{x_{1},\dots ,x_{n}\}$ si tous les sous-ensembles de ce dernier sont prélevés par ${\mathcal {C}}$.

On appelle taille VC ou dimension VC de l'ensemble ${\mathcal {C}}$ le plus petit $n\in \mathbb {N} ^{*}$ pour laquelle aucun élément de ${\mathcal {X}}^{n}$ est pulvérisé par ${\mathcal {C}}$. Si ${\mathcal {C}}$ pulvérise tous les ensembles de tailles arbitraires, sa taille VC est infinie. Cette dimension est notée en général ${\mathcal {V}}({\mathcal {C}})$ ou $\mathrm {VCD} ({\mathcal {C}})$. De manière plus formelle, on introduit la taille des prélèvements $\Delta _{n}({\mathcal {C}};x_{1},\dots ,x_{n})$ qui correspond au nombre de sous-ensembles que $\{x_{1},\dots ,x_{n}\}$ que ${\mathcal {C}}$ peut prélever, et la taille VC d'une classe ${\mathcal {C}}$ par

${\begin{array}{rl}\Delta _{n}({\mathcal {C}};x_{1},\dots ,x_{n})&=\mathrm {card} \{C\cap \{x_{1},\dots ,x_{n}\}:C\in {\mathcal {C}}\}\\{\mathcal {V}}({\mathcal {C}})&=\inf \left\lbrace n\in \mathbb {N} ^{*}:\max _{x_{1},\dots ,x_{n}\in {\mathcal {X}}}\Delta _{n}({\mathcal {C}};x_{1},\dots ,x_{n})<2^{n}\right\rbrace .\end{array}}$

L'ensemble ${\mathcal {C}}$ est appelé classe de Vapnik-Tchervonenkis ou classe VC si sa taille VC est finie : ${\mathcal {V}}({\mathcal {C}})<+\infty$. On peut également préciser qu'il s'agit d'une classe VC d'ensembles.

Remarque : la définition de la taille VC peut être différente selon les sources. En effet, certains auteurs prennent comme définition le plus grand entier $n\in \mathbb {N} ^{*}$ pour lequel la classe de fonctions arrive à pulvériser tout échantillon de taille $n$. La différence entre ces deux définitions n'est que de 1.

Exemples :

• La classe des intervalles ${\mathcal {C}}=\{]-\infty ,t]:t\in \mathbb {R} \}$ est une classe VC de dimension VC 1. La classe ${\mathcal {C}}$ arrive à expulser un point mais pas deux points. En effet si $t_{1},t_{2}\in \mathbb {R}$ avec $t_{1}<t_{2}$ alors ${\mathcal {C}}$ n'arrive pas à prélever $\{t_{2}\}$ puisque $\forall t\geq t_{2},]-\infty ,t]\cap \{t_{1},t_{2}\}\neq \{t_{2}\}$.
• La classe des intervalles ${\mathcal {C}}=\{[a,b]:a,b\in \mathbb {R} \}$ est une classe VC de dimension VC 2. ${\mathcal {C}}$ n'arrive pas à expulser trois points : si $t_{1},t_{2},t_{3}\in \mathbb {R}$ avec $t_{1}<t_{2}<t_{3}$ alors ${\mathcal {C}}$ n'arrive pas à prélever $\{t_{1},t_{3}\}$. ${\mathcal {C}}$ arrive à expulser deux points : soient $t_{1},t_{2}\in \mathbb {R}$ avec $t_{1}<t_{2}$ alors si on pose $t\in ]t_{1},t_{2}[$,
  • $[t_{1},t]\cap \{t_{1},t_{2}\}=\{t_{1}\}$ ;
  • $[t,t_{2}]\cap \{t_{1},t_{2}\}=\{t_{2}\}$ ;
  • $[t_{1},t_{2}]\cap \{t_{1},t_{2}\}=\{t_{1},t_{2}\}$.
• La classe boules de $\mathbb {R}$, i.e. ${\mathcal {C}}=\{B(x,r):x\in \mathbb {R} ^{d},r>0\}$ est une classe VC de dimension $d+1$. Rappel : $B(x,r)=\{y\in \mathbb {R} ^{d}:||x-y||\leq r\}$ avec $||\cdot ||$ une distance donnée.
• La classe ${\mathcal {P}}$ des polygones du plan est de dimension VC infini, autrement dit ${\mathcal {P}}$ peut repousser au moins un ensemble de taille arbitraire. En effet, pour tout $n\in \mathbb {N} ^{*}$, on peut prendre $x_{1},\dots ,x_{n}$ des points appartenant à un même cercle, tel que le cercle unité. Alors tout sous-ensemble de $\{x_{1},\dots ,x_{n}\}$ forme les sommets d'un polygone et ce dernier ne contiendra pas les points de $\{x_{1},\dots ,x_{n}\}$ n'appartenant pas au sous-ensemble.

Classe VC de fonctions

Soit ${\mathcal {F}}$ une classe de fonctions mesurables définies sur ${\mathcal {X}}$ et à valeurs réelles. Si la classe des sous-graphes des fonctions de ${\mathcal {F}}$ (le sous-graphe de $f\in {\mathcal {F}}$ est $\Delta _{f}=\{(x,t):x\in {\mathcal {X}},t\leq f(x)\}$) forme une classe VC alors ${\mathcal {F}}$ est appelée classe VC (ou classe VC de sous-graphe).

Exemple :

• La classe des fonctions indicatrices ${\mathcal {F}}=\{\mathbf {1} _{]-\infty ,t]}:t\in \mathbb {R} \}$ est une classe VC de dimension 1.

Propriétés

Lemme de Sauer

Le lemme de Sauer borne le nombre de sous-ensemble d'un échantillon de taille fixée prélevée par une classe VC ${\mathcal {C}}$ que l'on peut avoir au maximum. Formellement, si ${\mathcal {C}}$ est une classe VC d'ensemble alors (cf. corollaire 2.6.3)

${\begin{array}{l}\forall n<{\mathcal {V}}({\mathcal {C}}),&\Delta ({\mathcal {C}};n)\leq \sum _{i=0}^{{\mathcal {V}}({\mathcal {C}})}{\binom {n}{i}}\\\forall n\geq {\mathcal {V}}({\mathcal {C}}),&\Delta ({\mathcal {C}};n)\leq \left({\frac {en}{{\mathcal {V}}({\mathcal {C}})}}\right)^{{\mathcal {V}}({\mathcal {C}})}=O(n^{{\mathcal {V}}({\mathcal {C}})})\end{array}}$

où $\Delta ({\mathcal {C}};n)=\max _{x_{1},\dots ,x_{n}\in {\mathcal {X}}}\Delta ({\mathcal {C}};x_{1},\dots ,x_{n})$.

Classe VC

Les classes VC vérifient des propriétés de stabilité. Autrement dit, des opérations de classes VC (comme l'union, l'intersection, ...) de classes VC est toujours une classe VC.

Classe VC d'ensembles

Soit ${\mathcal {C}}$ et ${\mathcal {D}}$ des classes VC d'un même ensemble ${\mathcal {X}}$ et $\phi :{\mathcal {X}}\to {\mathcal {Y}}$ et $\psi :{\mathcal {Z}}\to {\mathcal {X}}$ des fonctions. Alors (cf. lemme 2.6.17) :

• ${\mathcal {C}}^{C}=\{C^{C}:C\in {\mathcal {C}}\}$ est une classe VC ;
• ${\mathcal {C}}\cap {\mathcal {D}}=\{C\cap D:C\in {\mathcal {C}},D\in {\mathcal {D}}\}$ est une classe VC ;
• ${\mathcal {C}}\cup {\mathcal {D}}=\{C\cup D:C\in {\mathcal {C}},D\in {\mathcal {D}}\}$ est une classe VC ;
• $\phi ({\mathcal {C}})$ est une classe VC si $\phi$ est injective ;
• $\psi ^{-1}({\mathcal {C}})$ est une classe VC.

Si ${\mathcal {C}},{\mathcal {D}}$ sont classes VC respectivement des ensembles ${\mathcal {X}}$ et ${\mathcal {Y}}$ alors

• ${\mathcal {C}}\times {\mathcal {D}}$ est une classe VC de ${\mathcal {X}}\times {\mathcal {Y}}$.

Si ${\mathcal {C}}$ est une classe de cardinal fini alors ${\mathcal {C}}$ est une classe VC de dimension VC bornée par

${\mathcal {V}}({\mathcal {C}})\leq \log _{2}|{\mathcal {C}}|.$

Classe VC de fonctions

Soient ${\mathcal {F}}$ et ${\mathcal {G}}$ des classes VC de fonctions d'un ensemble ${\mathcal {X}}$ et $g:{\mathcal {X}}\to \mathbb {R} ,\phi :\mathbb {R} \to \mathbb {R}$ et $\psi :{\mathcal {Z}}\to {\mathcal {X}}$ des fonctions. Alors (cf. lemme 2.6.18)

• ${\mathcal {F}}\wedge {\mathcal {G}}=\{f\wedge g:f\in {\mathcal {F}},g\in {\mathcal {G}}\}$ est une classe VC de fonctions (rappel : $a\wedge b=\min(a,b)$) ;
• ${\mathcal {F}}\vee {\mathcal {G}}=\{f\vee g:f\in {\mathcal {F}},g\in {\mathcal {G}}\}$ est une classe VC de fonctions (rappel : $a\vee b=\max(a,b)$) ;
• ${\mathcal {F}}^{+}=\{\{f>0\}:f\in {\mathcal {F}}\}$ est une classe VC d'ensemble ;
• $-{\mathcal {F}}$ est une classe VC de fonctions ;
• ${\mathcal {F}}+g=\{f+g:f\in {\mathcal {F}}\}$ est une classe VC de fonctions ;
• ${\mathcal {F}}\cdot g=\{fg:f\in {\mathcal {F}}\}$ est une classe VC de fonctions ;
• ${\mathcal {F}}\circ \psi =\{f(\psi ):f\in {\mathcal {F}}\}$ est une classe VC de fonctions ;
• $\phi \circ {\mathcal {F}}$ est une classe VC de fonctions si $\phi$ est monotone.

Recouvrement polynomial

Les classes VC sont des classes polynomiales, i.e. que le nombre de recouvrement est polynomiale. En effet (cf. théorème 2.6.4), il existe une constante universelle $K$ tel que pour tout classes VC ${\mathcal {C}}$, pour tout mesure de probabilité $Q$, pour tout $r\geq 1$ et $0<\varepsilon <1$,

$N({\mathcal {C}},\varepsilon ,L_{r}(Q))\leq K{\mathcal {V}}({\mathcal {C}})(4e)^{{\mathcal {V}}({\mathcal {C}})}\left({\frac {1}{\varepsilon }}\right)^{r({\mathcal {V}}({\mathcal {C}})-1)}.$

Les classes VC de fonctions vérifient également ce type de propriété. En effet (cf. théorème 2.6.7), il existe une constante universelle $K$ tel que pour toute classe VC de fonctions ${\mathcal {F}}$ avec une enveloppe mesurable $F$ et $r\geq 1$, on a pour toute mesure de probabilité $Q$ vérifiant $||F||_{Q,r}>0$ et tout $0<\varepsilon <1$,

$N({\mathcal {F}},\varepsilon ||F||_{Q,r},L_{r}(Q))\leq K{\mathcal {V}}({\mathcal {C}})(16e)^{{\mathcal {V}}({\mathcal {F}})}\left({\frac {1}{\varepsilon }}\right)^{r({\mathcal {V}}({\mathcal {F}})-1)}.$