Le lemme de symétrisation (ou lemme de symétrisation de Vapnik-Tchervonenkis) est un résultat en théorie de probabilités proposée par Vladimir Vapnik et Alexeï Tchervonenkis. Au lieu de comparer la mesure empirique avec la mesure théorique (qui est souvent non connue) ce lemme permet de comparer cette mesure avec une copie indépendante d'elle-même.

Énoncé

modifier

Il existe différents énoncés de ce lemme : Pollard utilise la version de la symétrisation avec des processus stochastiques[1] mais il existe des versions faisant intervenir l'erreur de généralisation d'un échantillon[2]. Soit (Xt)t∈T,(Xt′)t∈T des processus stochastiques indépendants indexés par un ensemble T. Supposons qu'il existe des constantes α>0,β>0 tel que

∀t∈T,ℙ(|Xt′|≤α)≥β.

Alors,

∀t∈T,∀ε>0,ℙ(supt∈T|Xt|>ε)≤β−1ℙ(supt∈T|Xt−Xt′|>ε−α).

En particulier en posant

on obtient que

∀n≥8ε−2,ℙ(supt∈ℝ|Pn(t)−P(t)|>ε)≤2ℙ(supt∈ℝ|Pn(t)−Pn′(t)|>12ε).

Démonstration

modifier

On note τ=τ(ω) un élément de T pour lequel |Xτ|>ε (i.e. ω∈{supt∈T|Xt|>ε}). Puisqu'il dépend de X,τ est indépendant de X′ et donc conditionnellement à X il agit comme un élément de T fixé :

ℙ(|Xt′|≤α|X)≥β.

En intégrant :

βℙ(supt∈T|Xt|>ε)≤ℙ(|Xτ′|≤α)ℙ(|Xτ|>ε)≤ℙ(|Xτ′|≤α,|Xτ|>ε)≤ℙ(|Xτ−Xτ′|>ε−τ)≤ℙ(supt∈T|Xt−Xt′|>ε−α).

Références

modifier
  1. ↑ (en) David Pollard, Convergence of stochastic processes, Springer Series in Statistics, p. 14
  2. ↑ Massih-Reza Amini, Apprentissage machine de la théorie à la pratique, Eyrolles, p. 16-17