Pulvérisation (mathématiques)

Pour les articles homonymes, voir Pulvérisation.

Le concept de pulvérisation d'un ensemble de points joue un rôle important dans la théorie de Vapnik-Chervonenkis, également connue sous le nom de théorie VC. La pulvérisation et la théorie VC sont utilisées dans l'étude des processus empiriques ainsi qu'en théorie de l'apprentissage automatique statistique.

Le terme a été introduit en 1975 par J. M. Steele dans sa thèse de doctorat, à l'université Stanford.

Définition

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

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 C des disques du plan (lorsqu'on se place dans un espace à deux dimensions) ne peut pas pulvériser tous les ensembles 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 point 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é 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 ellipse.

• 

  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.

Coefficient de pulvérisation

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

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. pour tout n.

2. S_C(n) = 2ⁿ, si et seulement s'il existe un ensemble de cardinal n pulvérisé par C.

3. S'il existe N > 1 tel que S_C(N) < 2^N, alors S_C(n) < 2ⁿ pour tout (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).

Classe de Vapnik-Chervonenkis

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

VC(C) = min _n{n:S_C(n) < 2ⁿ} ou, de manière alternative, par : VC₀(C) = max _n{n:S_C(n) = 2ⁿ}

On remarquera qu'on a : VC(C) = VC₀(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, S_C(n) = 2ⁿ).

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.

Sources

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Shattering » (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 (Théorie de la probabilité et ses 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