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é

On dit qu'une classe ${\mathcal {C}}$ d'un ensemble ${\mathcal {X}}$ prélève un sous-ensemble $S$ de $\{x_{1},\dots ,x_{n}\}$ s'il existe un élément $C\in {\mathcal {C}}$ 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 ${\mathcal {C}}$ n'arrive pas à pulvériser tout ensemble $\{x_{1},\dots ,x_{n}\}$ de taille $n$. On note $\Delta ({\mathcal {C}};n)$ le nombre maximum de sous-ensemble prélevées de taille $n$, i.e.

$\Delta ({\mathcal {C}};n)=\max _{x_{1},\dots ,x_{n}\in {\mathcal {X}}}\mathrm {card} \{C\cap \{x_{1},\dots ,x_{n}\}:C\in {\mathcal {C}}\}.$

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

$\forall n<{\mathcal {V}},\quad \Delta ({\mathcal {C}};n)\leq \sum _{i=0}^{\mathcal {V}}{\binom {n}{i}}\quad {\textrm {et}}\quad \forall n\geq {\mathcal {V}},\quad \Delta ({\mathcal {C}};n)\leq \left({\frac {en}{\mathcal {V}}}\right)^{\mathcal {V}}=O(n^{\mathcal {V}}).$

Preuve

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

Initialisation : Si $n=0,\{{\mathcal {C}}\cap \emptyset :C\in {\mathcal {C}}\}=\{\emptyset \}$ donc $\Delta ({\mathcal {C}},0)=1=\sum _{i=0}^{\mathcal {V}}{\binom {0}{i}}$.

Si ${\mathcal {V}}=1,{\mathcal {C}}$ n'arrive à pulvériser aucun point.

Hérédité : Supposons que la propriété soit vérifiée pour tout $n'+{\mathcal {V}}'<n+{\mathcal {V}}$. Soit ${\mathcal {C}}$ une classe VC (de sous-ensemble d'un ensemble ${\mathcal {X}}$) de dimension ${\mathcal {V}}$ et $S$ un ensemble de $n$ points de ${\mathcal {X}}$. On se fixe un élément $s\in S$ et on découpe ${\mathcal {C}}$ par ${\mathcal {C}}={\mathcal {C}}_{1}\cup {\mathcal {C}}_{2}$ avec

${\begin{array}{rl}{\mathcal {C}}_{1}&=\{C\in {\mathcal {C}}:s\not \in C\}\cup \{C\cup \{s\}\in {\mathcal {C}}:C\not \in {\mathcal {C}}\}\\{\mathcal {C}}_{2}&=\{C\cup \{s\}\in {\mathcal {C}}:C\in {\mathcal {C}}\}.\end{array}}$

On a que $\Delta ({\mathcal {C}};S)=\Delta (C_{1};S)+\Delta (C_{2};S)$ et par construction $\Delta ({\mathcal {C}}_{1};S)=\Delta ({\mathcal {C}};S\setminus \{s\})$. En notant ${\mathcal {C}}'$ les $C$ qui constituent ${\mathcal {C}}_{2}$, i.e.

${\mathcal {C}}'=\left\{C\in {\mathcal {C}}:s\not \in C,C\cup \{s\}\in {\mathcal {C}}\right\}.$

on a que $\Delta ({\mathcal {C}}_{2};S)=\Delta ({\mathcal {C}}';S\setminus \{s\})$.

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

$\Delta ({\mathcal {C}};S)=\Delta ({\mathcal {C}};S\setminus \{s\})+\Delta ({\mathcal {C}}';S\setminus \{s\})\leq \sum _{i=0}^{\mathcal {V}}{\binom {n-1}{i}}+\sum _{i=0}^{{\mathcal {V}}-1}{\binom {n-1}{i}}=\sum _{i=0}^{\mathcal {V}}{\binom {n}{i}}$

Si $n\geq {\mathcal {V}}$, alors en utilisant le résultat précédent et l'inégalité $1+x\leq e^{x}$,

${\begin{aligned}\left({\frac {\mathcal {V}}{n}}\right)^{\mathcal {V}}\leq 1\quad &\Rightarrow \quad \left({\frac {\mathcal {V}}{n}}\right)^{\mathcal {V}}\Delta ({\mathcal {C}},n)\leq \left({\frac {\mathcal {V}}{n}}\right)^{\mathcal {V}}\sum _{i=0}^{\mathcal {V}}{\binom {n}{i}}\leq \sum _{i=0}^{\mathcal {V}}{\binom {n}{i}}\left({\frac {\mathcal {V}}{n}}\right)^{i}\leq \left(1+{\frac {\mathcal {V}}{n}}\right)^{n}\\&\Rightarrow \quad \Delta (C,n)\leq \left({\frac {n}{\mathcal {V}}}\right)^{\mathcal {V}}\left(1+{\frac {\mathcal {V}}{n}}\right)^{n}\leq \left({\frac {en}{\mathcal {V}}}\right)^{\mathcal {V}}\end{aligned}}$