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

modifier

Classe VC d'ensemble

modifier

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 fonctions

modifier

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

modifier

Lemme de Sauer

modifier

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 VC

modifier

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

modifier

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 fonctions

modifier

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 polynomial

modifier

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

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