Classe VC

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

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

${\displaystyle {\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 ${\displaystyle {\mathcal {C}}}$ est appelé classe de Vapnik-Tchervonenkis ou classe VC si sa taille VC est finie : ${\displaystyle {\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 ${\displaystyle n\in \mathbb {N} ^{*}}$ pour lequel la classe de fonctions arrive à pulvériser tout échantillon de taille ${\displaystyle n}$. La différence entre ces deux définitions n'est que de 1.

Exemples :

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

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

Exemple :

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

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

${\displaystyle {\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ù ${\displaystyle \Delta ({\mathcal {C}};n)=\max _{x_{1},\dots ,x_{n}\in {\mathcal {X}}}\Delta ({\mathcal {C}};x_{1},\dots ,x_{n})}$.

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.

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

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

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

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

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

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

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

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

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[1]), il existe une constante universelle ${\displaystyle K}$ tel que pour tout classes VC ${\displaystyle {\mathcal {C}}}$, pour tout mesure de probabilité ${\displaystyle Q}$, pour tout ${\displaystyle r\geq 1}$ et ${\displaystyle 0<\varepsilon <1}$,

${\displaystyle 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[1]), il existe une constante universelle ${\displaystyle K}$ tel que pour toute classe VC de fonctions ${\displaystyle {\mathcal {F}}}$ avec une enveloppe mesurable ${\displaystyle F}$ et ${\displaystyle r\geq 1}$, on a pour toute mesure de probabilité ${\displaystyle Q}$ vérifiant ${\displaystyle ||F||_{Q,r}>0}$ et tout ${\displaystyle 0<\varepsilon <1}$,

${\displaystyle 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)}.}$