Pulvérisation
1699052
28092707
2008-04-02T01:45:36Z
Alecs.bot
265428
ortho, Replaced: si il → s'il
{{Projet:Traduction/{{PAGENAME}}|Paramètre=Cacher}}
Le terme de '''pulvérisation''' a été introduit en [[1975]] par J. M. Steele dans sa [[thèse]] de [[doctorat]], à l'[[université de Stanford]].
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 empirique]]s ainsi qu'en [[théorie de l'apprentissage automatique]] statistique.
==Définition==
Soient ''C'' une [[Classe (mathématiques)|classe]] d'[[ensemble]]s 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
: <math> U \cap A = T.\,</math>
Ceci équivaut encore à dire que ''C'' pulvérise ''A'' si et seulement si l'[[ensemble des parties d'un ensemble|ensemble des parties de l'ensemble]] ''A'', ''P''(''A''), est égal à l'ensemble { ''U'' ∩ ''A'' | ''U'' ∈ ''C'' }.
Par exemple, la classe <math> C </math> des [[Disque (géométrie)|disques]] du [[Plan (mathématiques)|plan]] (lorsqu'on se place dans un espace à deux [[Dimension d'un espace vectoriel|dimensions]]) ne peut pas pulvériser tous les ensembles <math>F</math> de quatre points, alors qu'en revanche la classe des [[ensemble convexe|ensembles convexe]]s du plan pulvérise tout ensemble fini du [[cercle unité]].
==Coefficient de pulvérisation==
Pour mesurer la richesse d'une collection <math> C </math> d'ensembles, on utilise le concept de ''coefficients de pulvérisation'' (également appelés ''fonction de croissance''). Pour une collection <math> C </math> d'ensembles <math> s \subset </math> Ω, où Ω est un ensemble, on définit le ''n''<sup>ième</sup> ''coefficient de pulvérisation'' de <math> C </math> par
:<math> 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 \}</math>
où "card" signifie [[Nombre cardinal|cardinal]], c'est-à-dire, le nombre d'éléments d'un ensemble.
De cette définition découlent les [[propriété]]s suivantes :
:1.<math>S_C(n)\leq 2^n</math> pour tout ''n''.
:2. <math>S_C(n)=2^n</math>, si et seulement s'il existe un ensemble de cardinal ''n'' pulvérisé par ''C''.
:3. S'il existe <math>N>1</math> tel que <math>S_C(N)<2^N</math>, alors <math>S_C(n)<2^n</math> pour tout <math>n\geq N</math> (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
:<math>VC(C)=\min_n\{n:S_C(n)<2^n\}</math> ou, de manière alternative, par : <math>VC_0(C)=\max_n\{n:S_C(n)=2^n\}</math>
On remarquera qu'on a : <math>VC(C)=VC_0(C)+1</math>.
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'', <math>S_C(n)=2^n</math>).
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 [[classe de Glivenko-Cantelli|Glivenko-Cantelli]] si et seulement si c'est une classe VC.
==Sources==
{{Traduction/Référence|en|Shattering|}}
* {{pdf}} [http://www.grappa.univ-lille3.fr/ftp/reports/courspartie1.ps.gz 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}} [http://www-2.cs.cmu.edu/~awm/tutorials/vcdim.html cours sur la dimension VC] de [[Andrew W. Moore|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 [[Manfred K. Warmuth|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é de Stanford''.
* {{en}} Steele, J.M. (1978), "Empirical discrepancies and subadditive processes"(Divergences empiriques et processus sous-additifs), ''Annals of Probability'', 6, 118--227.
{{Portail|mathématiques|informatique}}
[[Catégorie:Intelligence artificielle]]
[[de:Zerschmettern]]
[[en:Shattering]]