La preuve de la première inégalité se fait par une double induction sur la VC dimension d’une part et la taille de la base d’apprentissage m d’autre part selon le schéma suivant :
- cas de base pour m=0 et tout d_{VC}\geq 0 ;
- cas de base pour d_{VC}=0 et tout m\geq 1 ;
- induction du cas m, d_{VC} à partir de la validité pour m-1 points et toute VC-dimension < d_{VC}.
La seconde inégalité utilise simplement des calculs sur les coefficients du binôme.
Cas de base pour m=0 : sans aucun point, il n’y a aucune manière de les classer et on a \Pi_{\mathcal{F}}(0)=0, ce qui est bien inférieur à \sum_{k=0}^{d_{VC}} \begin{pmatrix}m\\k\end{pmatrix} pour toute d_{VC}.
Cas de base pour d_{VC}=0 : aucun point ne peut être pulvérisé par \mathcal{F} et la prédiciton f(\boldsymbol{x}) est donc constante pour tout f\in\mathcal{F} quel que soit \boldsymbol{x}\in\mathcal{X}. Donc, pour tout m, il n’y a qu’une seule classification possible et \Pi_{\mathcal{F}}(0)=1 qui est bien inférieur ou égal à la borne \sum_{k=0}^{0} \begin{pmatrix}m\\k\end{pmatrix} = \begin{pmatrix}m\\0\end{pmatrix}=1.
Induction : si le Lemme est valide pour m-1 points et toute VC-dimension < d_{VC}, alors pour tout F'\subset F\subset \mathcal{F},
\Pi_{F'}(m-1) \leq \Pi_{\mathcal{F}}(m-1) \leq \sum_{k=0}^{d_{VC}} \binom{m-1}{k}
et si d_{VC}(F\setminus F') \leq d_{VC} - 1,
\Pi_{F\setminus F'}(m-1) \leq \sum_{k=0}^{d_{VC}(F\setminus F')} \binom{m-1}{k} \leq \sum_{k=0}^{d_{VC} - 1} \binom{m-1}{k} = \sum_{k=1}^{d_{VC}} \binom{m-1}{k-1}
Dans ce cas,
\Pi_{F'}(m-1) + \Pi_{F\setminus F'}(m-1) \leq 1 + \sum_{k=1}^{d_{VC}} \binom{m-1}{k} + \binom{m-1}{k-1} = 1 + \sum_{k=1}^{d_{VC}} \binom{m}{k} = \sum_{k=0}^{d_{VC}} \binom{m}{k}
car \binom{m}{k} = \binom{m-1}{k} + \binom{m-1}{k-1} (cette identité caractérise le comptage du nombre de manières de choisir k éléments parmi m en deux étapes. Dans la prmeière étape, on laisse de côté le premier élément et on compte le nombre de manières de choisir k éléments parmi m-1. Dans la seconde étape, on choisit le premier élément et on compte le nombre de manières de choisir les k-1 restant parmi n-1. Le nombre total de choisir k éléments parmi m, \binom{m}{k} est la somme des deux comptes.)
Choisissons un ensemble de points S=\{\boldsymbol{x}_1,\dots,\boldsymbol{x}_m\} tel que les \Pi_{\mathcal{F}}(m) classifications de ces points soient toutes obtenues avec des classifieurs f\in\mathcal{F} différents (cela implique aussi que S est choisi de telle sorte qu’un nombre maximal de classifications différentes soient obtenues). Notons F\subset\mathcal{F} l’ensemble de ces classifieurs. Définissons S'=S\setminus \{\boldsymbol{x}_1\} et F'\subset F le plus petit sous-ensemble de F qui peut classer S' du plus grand nombre de manières possibles (ainsi, F' ne peut pas contenir deux classifieurs qui produisent la même classification de S').
Pour chaque classification de S', deux classifieurs de F produisent cette classification et diffèrent sur \boldsymbol{x}_1, sachant que l’un est dans F' et l’autre dans F\setminus F'. Considérons la partition de F : F=F'\cup(F\setminus F') avec la relation |F| = |F'| + |F\setminus F'|.
Puisque F a été construit avec une seule fonction pour chaque classification de S, |F|= \Pi_{\mathcal{F}}(m) et |F'| et |F\setminus F'| représentent aussi le nombre de classifications de S' produites par F' et F\setminus F'. Ainsi :
|F'| \leq \Pi_{F'}(m-1) \qquad \text{et}\qquad |F\setminus F'| \leq \Pi_{F\setminus F'}(m-1)
Nous allons maintenant nous intéresser à la VC dimension de ces ensembles. Puisque F'\subset F\subset \mathcal{F}, alors leur VC-dimension respecte
d_{VC}(F') \leq d_{VC}(F) \leq d_{VC}(\mathcal{F})
S’il existe un ensemble de points T\subset S' pulvérisé par F\setminus F', alors F' pulvérise aussi T car F' a été choisi pour produire la plus grand nombre de classifications de S' et donc aussi de ses sous-ensembles.
Ainsi, pour chaque classification de T, il existe f\in F\setminus F' et f'\in F' qui produisent cette classification. Mais puisque F ne contient qu’une fonction pour chaque classification de S, cela implique que f et f' doivent être en désaccord sur S\setminus T. Et puisque F' produit le plus grand nombre de classifications de S', quelle que soit la classification de S' donnée par f, il existe un f'\in F' qui la produit aussi. Le désaccord entre f et f' doit donc être observé sur S\setminus S' = \{\boldsymbol{x}_1\} et f(\boldsymbol{x}_1)\neq f'(\boldsymbol{x}_1). Puisque toutes les paires f et f' construites ainsi appartiennet à F, l’ensemble de points T\cup\{\boldsymbol{x}_1\} est donc pulvérisé par F (car toutes les classifications de \boldsymbol{x}_1 sont possibles en plus de celles de T).
D’un autre côté, F\setminus F' ne peut pas pulvériser T\cup\{\boldsymbol{x}_1\} et donc d_{VC}(F\setminus F')\leq d_{VC}(F) - 1 \leq d_{VC}(\mathcal{F}) - 1.
Au final,
\Pi_{\mathcal{F}}(m) = |F| = |F'| + |F\setminus F'| \leq \Pi_{F'}(m-1) + \Pi_{F\setminus F'}(m-1) \leq \sum_{k=0}^{d_{VC}} \binom{m}{k}
Borne polynomiale : pour obtenir la dernière borne polynomiale, nous utilisons, pour m>d_{VC},
\sum_{k=0}^{d_{VC}} \binom{m}{k} \leq \left( \frac{em}{d_{VC}} \right)^{d_{VC}}
que l’on peut prouver ainsi.
Pour d<n, n/d>1 et pour k\leq d, (n/d)^{d-k} \geq 1. Ainsi, \begin{align*}
\sum_{k=0}^{d_{VC}} \binom{m}{k} &\leq \sum_{k=0}^{d_{VC}} \binom{m}{k} \left(\frac{m}{d_{VC}}\right)^{d_{VC}-k} \\
&=\left(\frac{m}{d_{VC}}\right)^{d_{VC}} \sum_{k=0}^{d_{VC}} \binom{m}{k} \left(\frac{d_{VC}}{m}\right)^{k}\\
&\leq \left(\frac{m}{d_{VC}}\right)^{d_{VC}} \sum_{k=0}^{m} \binom{m}{k} \left(\frac{d_{VC}}{m}\right)^{k}\\
&= \left(\frac{m}{d_{VC}}\right)^{d_{VC}} \left(1 + \frac{d_{VC}}{m}\right)^{m}\\
&\leq \left(\frac{m}{d_{VC}}\right)^{d_{VC}} \left(e^{d_{VC}/m}\right)^{m}\\
&= \left(\frac{m}{d_{VC}}\right)^{d_{VC}} e^{d_{VC}}\\
&= \left(\frac{m}{e d_{VC}}\right)^{d_{VC}}
\end{align*}
