Lemme de Sauer

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

${\displaystyle \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 ${\displaystyle \Delta ({\mathcal {C}};n)}$ si ${\displaystyle {\mathcal {C}}}$ est une classe VC. Formellement si ${\displaystyle {\mathcal {C}}}$ est une classe VC de dimension ${\displaystyle {\mathcal {V}}}$ alors

${\displaystyle \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}}).}$

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

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

Si ${\displaystyle {\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 ${\displaystyle n'+{\mathcal {V}}'<n+{\mathcal {V}}}$. Soit ${\displaystyle {\mathcal {C}}}$ une classe VC (de sous-ensemble d'un ensemble ${\displaystyle {\mathcal {X}}}$) de dimension ${\displaystyle {\mathcal {V}}}$ et ${\displaystyle S}$ un ensemble de ${\displaystyle n}$ points de ${\displaystyle {\mathcal {X}}}$. On se fixe un élément ${\displaystyle s\in S}$ et on découpe ${\displaystyle {\mathcal {C}}}$ par ${\displaystyle {\mathcal {C}}={\mathcal {C}}_{1}\cup {\mathcal {C}}_{2}}$ avec

${\displaystyle {\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 ${\displaystyle \Delta ({\mathcal {C}};S)=\Delta (C_{1};S)+\Delta (C_{2};S)}$ et par construction ${\displaystyle \Delta ({\mathcal {C}}_{1};S)=\Delta ({\mathcal {C}};S\setminus \{s\})}$. En notant ${\displaystyle {\mathcal {C}}'}$ les ${\displaystyle C}$ qui constituent ${\displaystyle {\mathcal {C}}_{2}}$, i.e.

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

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

Par construction, si ${\displaystyle {\mathcal {C}}'}$ pulvérise un échantillon, ${\displaystyle {\mathcal {C}}}$ pulvérise également cet échantillon et ce même si on lui rajoute ${\displaystyle \{s\}}$ d'où ${\displaystyle \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,

${\displaystyle \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 ${\displaystyle n\geq {\mathcal {V}}}$, alors en utilisant le résultat précédent et l'inégalité ${\displaystyle 1+x\leq e^{x}}$,

${\displaystyle {\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}}}$