Pulvérisation (mathématiques)

Soient C une classe d'ensembles et A un ensemble. 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.\,}$

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 }.

Par exemple, la classe ${\displaystyle C}$ des disques du plan (lorsqu'on se place dans un espace à deux dimensions) ne peut pas pulvériser tous les ensembles ${\displaystyle F}$ de quatre points, alors qu'en revanche la classe des ensembles convexes du plan pulvérise tout ensemble fini du cercle unité.

Exemple

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

Supposons un ensemble A de quatre points du cercle unité, et l'on voudrait savoir s'il est pulvérisé par la classe C de tous les cercles.

Pour cela, nous allons essayer de dessiner un cercle autour de chaque point de A. D'abord, dessinons un cercle autour de chaque isolé, chose facile. Ensuite, dessinons un cercle autour de chaque sous-ensemble composé de deux éléments de A ; c'est chose facile pour des points adjacents, mais impossible pour des points opposés.

• 
  Chaque point peut être isolé par un cercle (les quatre sont montrés).
• 
  Chaque sous ensemble de points adjacents peut être isolé par un cercle (un seul est montré).
• 
  Un sous-ensemble de points opposés ne peut pas être isolé par un cercle.

Comme certaines parties de A ne peuvent pas être isolées par les cercles de C, on peut en conclure que A n'est pas pulvérisé par C. Sans trop de difficultés, on peut aussi prouver qu'aucun ensemble A de quatre points ne peut l'être.

Mais si on redéfinit C comme l'ensemble des ellipses, on arrive à dissocier les points de chaque partie de A. Donc notre ensemble particulier de quatre points est pulvérisé par l'ensemble des ellipses.

• 
  Des points opposés de A sont maintenant dissociables (une montrée sur les deux).
• 
  Chaque sous-ensemble de trois points de A est aussi dissociable par une ellipse (une montrée sur quatre).

On peut généraliser que n'importe quel ensemble fini de points du cercle unité peut être pulvérisé par l'ensemble des ensembles convexes.

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.

• Portail des mathématiques
• Portail de l’informatique