Pulvérisation (mathématiques)

Expliquons le principe de la pulvérisation en prenant comme modèle de classification une droite dans le plan, où les données sont représentées par des points étiquetés par + ou - dans le plan. On étudie si une droite peut séparer les données positives (+) des données négatives (-). Si on prend 3 points non alignés, une droite peut les pulvériser. En effet, comme le montrent les trois images ci-dessous, on place une droite de façon que les données positives soient d'un côté et les données négatives de l'autre. 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).

Cependant, une droite ne peut pas pulvériser 4 points. En effet, on peut trouver un étiquetage des points de façon qu'aucune droite sépare les données positives et négatives. Il est important de noter que l'on peut choisir les positions des points qu'on va pulvériser avec une droite, mais qu'on ne peut pas ensuite modifier ces positions lorsqu'on permute leur étiquetage.

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

Dans la théorie VC, on dira que la dimension VC de la droite est de 3.

Soient C une classe d'ensembles et A un ensemble de points. On dit que C pulvérise A si et seulement si, pour tout sous-ensemble T de A, il existe un élément U appartenant à C tel que

${\displaystyle U\cap A=T.\,}$

Dans l'exemple des droites dans le plan, la classe ${\displaystyle C}$ est en fait l'ensemble des demi-plans. Dans la définition, le sous-ensemble T de A correspond à l'ensemble des points étiquetés positivement. L'égalité ${\displaystyle U\cap A=T}$ signifie que les points de A qui sont dans le demi-plan U sont exactement les exemples positifs.

Ceci équivaut encore à dire que C pulvérise A si et seulement si l'ensemble des parties de l'ensemble A, P(A), est égal à l'ensemble { U ∩ A | U ∈ C }.

L'ensemble A de quatre points du cercle unité (en mauve)

Fixons un ensemble A de quatre points du cercle unité. Par exemple, les quatre points bleu sur la figure de droite.

Pour mesurer la richesse d'une collection ${\displaystyle C}$ d'ensembles, on utilise le concept de « coefficients de pulvérisation » (également appelés « fonction de croissance »). Pour une collection ${\displaystyle C}$ d'ensembles ${\displaystyle s\subset }$ Ω, où Ω est un ensemble, on définit le n^ième coefficient de pulvérisation de ${\displaystyle C}$ par

${\displaystyle S_{C}(n)=\max _{x_{1},x_{2},\dots ,x_{n}\in \Omega }\operatorname {card} \{\,\{\,x_{1},x_{2},\dots ,x_{n}\}\cap s,s\in C\}}$

où « card » est le cardinal, c'est-à-dire, le nombre d'éléments d'un ensemble.

De cette définition découlent les propriétés suivantes :

1.${\displaystyle S_{C}(n)\leq 2^{n}}$ pour tout n.

2. ${\displaystyle S_{C}(n)=2^{n}}$, si et seulement s'il existe un ensemble de cardinal n pulvérisé par C.

3. S'il existe ${\displaystyle N>1}$ tel que ${\displaystyle S_{C}(N)<2^{N}}$, alors ${\displaystyle S_{C}(n)<2^{n}}$ pour tout ${\displaystyle n\geq N}$ (en d'autres termes, une classe d'ensembles qui ne peut pulvériser aucun ensemble à N éléments ne pourra pas non plus pulvériser d'ensemble plus grand).

La dimension VC d'une classe C est définie par

${\displaystyle VC(C)=\min _{n}\{n:S_{C}(n)<2^{n}\}}$ ou, de manière alternative, par : ${\displaystyle VC_{0}(C)=\max _{n}\{n:S_{C}(n)=2^{n}\}}$

On remarquera qu'on a : ${\displaystyle VC(C)=VC_{0}(C)+1}$.

On dira que la dimension VC d'une classe est infinie si pour tout n il existe un ensemble à n éléments pulvérisé par C (on a alors, pour tout entier naturel n, ${\displaystyle S_{C}(n)=2^{n}}$).

Les classes de dimension VC finie sont appelées classes de Vapnik-Chervonenkis ou classes VC. Une classe d'ensembles est une classe uniformément Glivenko-Cantelli si et seulement si c'est une classe VC.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Shattered set » (voir la liste des auteurs).

• [PDF] Cours sur la theorie de l’apprentissage statistique (selon V. Vapnik) de François Denis, de l'Équipe Bases de Données et Apprentissage du Laboratoire d’Informatique Fondamentale de Marseille
• (en) cours sur la dimension VC de Andrew Moore
• (en) V. Vapnik et A. Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities." (De la convergence uniforme des fréquences relatives des événements vers leur probabilité) Theory of Probability and its Applications, 16(2):264--280, 1971.
• (en) A. Blumer, A. Ehrenfeucht, D. Haussler, et M. K. Warmuth. "Learnability and the Vapnik-Chervonenkis dimension." (Capacité d'apprentissage et dimension de Vapnik-Chervonenkis) Journal of the ACM, 36(4):929--865, 1989.
• (en) Wencour, R.S., R.M. Dudley (1981), "Some special Vapnik-Chervonenkis classes"(Classes spéciales de Vapnik-Chervonenkis), Discrete Math, 33, 1981, 313-318.
• (en) Steele, J.M. (1975), "Combinatorial Entropy and Uniform Limit Laws"(Entropie Combinatoire et lois de convergence uniforme), thèse de doctorat de mathématiques de l'université Stanford.
• (en) Steele, J.M. (1978), "Empirical discrepancies and subadditive processes"(Divergences empiriques et processus sous-additifs), Annals of Probability, 6, 118--227.