Pulvérisation

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

Le terme de pulvérisation a été introduit en 1975 par J. M. Steele dans sa thèse de doctorat, à l'université 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 empiriques ainsi qu'en théorie de l'apprentissage automatique statistique.

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

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

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 n coefficient de pulvérisation de C par

S C (n) = max x_{1}, x_{2}, \dots, x_{n} \in Ω card {{x_{1}, x_{2}, \dots, x_{n}} \cap s, s \in C}

où "card" signifie 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, 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, alors S_C(n) < 2 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

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

V**C(C) = min_n{n:S_C(n) < 2} ou, de manière alternative, par : V**C₀(C) = max_n{n:S_C(n) = 2}

On remarquera qu'on a : V**C(C) = V**C₀(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.