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éfinitionModifier

Classe VC d'ensembleModifier

Soit   une classe de sous-ensembles d'un ensemble  . Soit   des éléments de  . On dit que   prélève un sous-ensemble   s'il existe   tel que  . On dit que   pulvérise   si tous les sous-ensembles de ce dernier sont prélevés par  .

On appelle taille VC ou dimension VC de l'ensemble   le plus petit   pour laquelle aucun élément de   est pulvérisé par  . Si   pulvérise tous les ensembles de tailles arbitraires, sa taille VC est infinie. Cette dimension est notée en général   ou  . De manière plus formelle, on introduit la taille des prélèvements   qui correspond au nombre de sous-ensembles que   que   peut prélever, et la taille VC d'une classe   par

 

L'ensemble   est appelé classe de Vapnik-Tchervonenkis ou classe VC si sa taille VC est finie :  . 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   pour lequel la classe de fonctions arrive à pulvériser tout échantillon de taille  . La différence entre ces deux définitions n'est que de 1.

Exemples :

  • La classe des intervalles   est une classe VC de dimension VC 1. La classe   arrive à expulser un point mais pas deux points. En effet si   avec   alors   n'arrive pas à prélever   puisque  .
  • La classe des intervalles   est une classe VC de dimension VC 2.   n'arrive pas à expulser trois points : si   avec   alors   n'arrive pas à prélever  .   arrive à expulser deux points : soient   avec   alors si on pose  ,
    •   ;
    •   ;
    •  .
  • La classe boules de  , i.e.   est une classe VC de dimension  . Rappel :   avec   une distance donnée.
  • La classe   des polygones du plan est de dimension VC infini, autrement dit   peut repousser au moins un ensemble de taille arbitraire. En effet, pour tout  , on peut prendre   des points appartenant à un même cercle, tel que le cercle unité. Alors tout sous-ensemble de   forme les sommets d'un polygone et ce dernier ne contiendra pas les points de   n'appartenant pas au sous-ensemble.

Classe VC de fonctionsModifier

Soit   une classe de fonctions mesurables définies sur   et à valeurs réelles. Si la classe des sous-graphes des fonctions de   (le sous-graphe de   est  ) forme une classe VC alors   est appelée classe VC (ou classe VC de sous-graphe).

Exemple :

  • La classe des fonctions indicatrices   est une classe VC de dimension 1.

PropriétésModifier

Lemme de SauerModifier

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

 

 .

Classe VCModifier

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'ensemblesModifier

Soit   et   des classes VC d'un même ensemble   et   et   des fonctions. Alors (cf. lemme 2.6.17[1]) :

  •   est une classe VC ;
  •   est une classe VC ;
  •   est une classe VC ;
  •   est une classe VC si   est injective ;
  •   est une classe VC.

Si   sont classes VC respectivement des ensembles   et   alors

  •   est une classe VC de  .

Si   est une classe de cardinal fini alors   est une classe VC de dimension VC bornée par

 

Classe VC de fonctionsModifier

Soient   et   des classes VC de fonctions d'un ensemble   et   et   des fonctions. Alors (cf. lemme 2.6.18[1])

  •   est une classe VC de fonctions (rappel :  ) ;
  •   est une classe VC de fonctions (rappel :  ) ;
  •   est une classe VC d'ensemble ;
  •   est une classe VC de fonctions ;
  •   est une classe VC de fonctions ;
  •   est une classe VC de fonctions ;
  •   est une classe VC de fonctions ;
  •   est une classe VC de fonctions si   est monotone.

Recouvrement polynomialModifier

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   tel que pour tout classes VC  , pour tout mesure de probabilité  , pour tout   et  ,

 

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   tel que pour toute classe VC de fonctions   avec une enveloppe mesurable   et  , on a pour toute mesure de probabilité   vérifiant   et tout  ,

 

RéférencesModifier

  1. a b c d et e (en) A. W. Van Der Vaart et J. A. Wellner, Weak Convergence and Empirical processes, Springer