Lemme de Sauer

Le lemme de Sauer ou lemme de Sauer-Shelah est un résultat issu de la théorie des probabilités et en particulier de la théorie de Vapnik-Chervonenkis. Il précise le nombre maximal d'échantillons de taille $n$ qu'une classe VC de dimension finie peut pulvériser. Ce résultat a été montré en 1972 par les mathématiciens Norbert Sauer et Saharon Shelah.

Énoncé

Modèle:Article détaillé On dit qu'une classe $𝒞$ d'un ensemble $𝒳$ prélève un sous-ensemble $S$ de $\{x_1,\dots ,x_n\}$ s'il existe un élément $C\in 𝒞$ vérifiant $C\cap \{x_1,\dots ,x_n\}=S$. On dit que cette classe pulvérise $\{x_1,\dots ,x_n\}$ s'il prélève tout sous-ensemble $S$ de $\{x_1,\dots ,x_n\}$. Enfin cette classe est appelée classe VC de dimension n si $𝒞$ n'arrive pas à pulvériser tout ensemble $\{x_1,\dots ,x_n\}$ de taille $n$. On note $\mathrm{\Delta }(𝒞;n)$ le nombre maximum de sous-ensemble prélevées de taille $n$, i.e.

$\mathrm{\Delta }(𝒞;n)=\underset{x_1,\dots ,x_n\in 𝒳}{\max }\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\{C\cap \{x_1,\dots ,x_n\}:C\in 𝒞\}.$

Le lemme de Sauer donne une borne majorante de $\mathrm{\Delta }(𝒞;n)$ si $𝒞$ est une classe VC. Formellement si $𝒞$ est une classe VC de dimension $𝒱$ alors

$\mathrm{\forall }n<𝒱,\mathrm{\Delta }(𝒞;n)\le \sum _{i=0}^{𝒱}(\genfrac{}{}{0ex}{}{n}{i})\text{et}\mathrm{\forall }n\ge 𝒱,\mathrm{\Delta }(𝒞;n)\le {\left(\frac{en}{𝒱}\right)}^{𝒱}=O(n^{𝒱}).$

Preuve

Une manière classique de démontrer ce résultat est de le faire par récurrenceModèle:,. On raisonne par récurrence sur des classes de dimension VC $n+𝒱\in \mathbb{N}$.

Initialisation : Si $n=0,\{𝒞\cap \mathrm{\varnothing }:C\in 𝒞\}=\{\mathrm{\varnothing }\}$ donc $\mathrm{\Delta }(𝒞,0)=1=\sum _{i=0}^{𝒱}(\genfrac{}{}{0ex}{}{0}{i})$.

Si $𝒱=1,𝒞$ n'arrive à pulvériser aucun point.

Hérédité : Supposons que la propriété soit vérifiée pour tout $n^{\prime }+{𝒱}^{\prime }<n+𝒱$. Soit $𝒞$ une classe VC (de sous-ensemble d'un ensemble $𝒳$) de dimension $𝒱$ et $S$ un ensemble de $n$ points de $𝒳$. On se fixe un élément $s\in S$ et on découpe $𝒞$ par $𝒞={𝒞}_1\cup {𝒞}_2$ avec

$\begin{array}{cc}{𝒞}_1& =\{C\in 𝒞:s\in ̸C\}\cup \{C\cup \{s\}\in 𝒞:C\in ̸𝒞\}\\ {𝒞}_2& =\{C\cup \{s\}\in 𝒞:C\in 𝒞\}.\end{array}$

On a que

$\mathrm{\Delta }(𝒞;S)=\mathrm{\Delta }(C_1;S)+\mathrm{\Delta }(C_2;S)$

et par construction

$\mathrm{\Delta }({𝒞}_1;S)=\mathrm{\Delta }(𝒞;S\setminus \{s\})$

. En notant

${𝒞}^{\prime }$

les

$C$

qui constituent

${𝒞}_2$

, i.e.

${𝒞}^{\prime }=\{C\in 𝒞:s\in ̸C,C\cup \{s\}\in 𝒞\}.$

on a que

$\mathrm{\Delta }({𝒞}_2;S)=\mathrm{\Delta }({𝒞}^{\prime };S\setminus \{s\})$

.

Par construction, si ${𝒞}^{\prime }$ pulvérise un échantillon, $𝒞$ pulvérise également cet échantillon et ce même si on lui rajoute $\{s\}$ d'où $\mathrm{V}\mathrm{C}\mathrm{D}({𝒞}^{\prime })+1\le \mathrm{V}\mathrm{C}\mathrm{D}(𝒞)\iff \mathrm{V}\mathrm{C}\mathrm{D}({𝒞}^{\prime })\le 𝒱-1$. Ainsi par hypothèse de récurrence,

$\mathrm{\Delta }(𝒞;S)=\mathrm{\Delta }(𝒞;S\setminus \{s\})+\mathrm{\Delta }({𝒞}^{\prime };S\setminus \{s\})\le \sum _{i=0}^{𝒱}(\genfrac{}{}{0ex}{}{n-1}{i})+\sum _{i=0}^{𝒱-1}(\genfrac{}{}{0ex}{}{n-1}{i})=\sum _{i=0}^{𝒱}(\genfrac{}{}{0ex}{}{n}{i})$

Si $n\ge 𝒱$, alors en utilisant le résultat précédent et l'inégalité $1+x\le e^x$,

$\begin{array}{cc}{\left(\frac{𝒱}{n}\right)}^{𝒱}\le 1& \Rightarrow {\left(\frac{𝒱}{n}\right)}^{𝒱}\mathrm{\Delta }(𝒞,n)\le {\left(\frac{𝒱}{n}\right)}^{𝒱}\sum _{i=0}^{𝒱}(\genfrac{}{}{0ex}{}{n}{i})\le \sum _{i=0}^{𝒱}(\genfrac{}{}{0ex}{}{n}{i}){\left(\frac{𝒱}{n}\right)}^i\le {(1+\frac{𝒱}{n})}^n\\ & \Rightarrow \mathrm{\Delta }(C,n)\le {\left(\frac{n}{𝒱}\right)}^{𝒱}{(1+\frac{𝒱}{n})}^n\le {\left(\frac{en}{𝒱}\right)}^{𝒱}\end{array}$