Pulvérisation (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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[modifier | modifier le code]

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

 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 { UA | UC }.

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[modifier | modifier le code]

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.

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.

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[modifier | modifier le code]

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  s \subset  Ω, où Ω est un ensemble, on définit le nième coefficient de pulvérisation de  C par

 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.S_C(n)\leq 2^n pour tout n.
2. S_C(n)=2^n, 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^n pour tout 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).

Classe de Vapnik-Chervonenkis[modifier | modifier le code]

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

VC(C)=\min_n\{n:S_C(n)<2^n\} ou, de manière alternative, par : VC_0(C)=\max_n\{n:S_C(n)=2^n\}

On remarquera qu'on a : 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, 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.

Sources[modifier | modifier le code]

  • [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.