Pulvérisation
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Le terme de pulvérisation a été introduit en 1975 par J. M. Steele dans sa thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à l'égard du sujet ou du thème qu'il évoque.) de doctorat (Le doctorat (du latin doctorem, de doctum, supin de docere, enseigner) est généralement le grade universitaire le plus élevé. Le titulaire de ce grade est le docteur. Selon les...), à l'université Stanford (La Leland Stanford Junior University, plus connue sous le nom d'université Stanford, est l'une des plus prestigieuses universités américaines. Située au cœur de la Silicon Valley, séparée de Palo...).

Le concept de pulvérisation d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble),...) de points joue (La joue est la partie du visage qui recouvre la cavité buccale, fermée par les mâchoires. On appelle aussi joue le muscle qui sert principalement à ouvrir et fermer la...) 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 (L’apprentissage est l'acquisition de savoir-faire, c'est-à-dire le processus d’acquisition de pratiques, de connaissances, compétences,...) automatique (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques. Elle a pour fondements...) statistique (Une statistique est, au premier abord, un nombre calculé à propos d'un échantillon. D'une façon générale, c'est le résultat de l'application d'une méthode statistique à un...).

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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du...) 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 (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) du cercle (Un cercle est une courbe plane fermée constituée des points situés à égale distance d'un point nommé centre. La valeur de cette...) unité.

classe de Vapnik-Chervonenkis

La dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien...) VC d'une classe C est définie par

VC(C) = minn{n:SC(n) < 2n} ou, de manière alternative, par : VC0(C) = maxn{n:SC(n) = 2n}

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

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.

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  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" signifie cardinal, c'est-à-dire, le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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. SC(n) = 2n, si et seulement s'il existe un ensemble de cardinal n pulvérisé par C.
3. S'il existe N > 1 tel que SC(N) < 2N, alors SC(n) < 2n 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).
Page générée en 0.123 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique