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 qu'une classe VC de dimension finie peut pulvériser. Ce résultat a été montré en 1972 par les mathématiciens Norbert Sauer[1] et Saharon Shelah[2].

Énoncé

On dit qu'une classe d'un ensemble prélève un sous-ensemble de s'il existe un élément vérifiant . On dit que cette classe pulvérise s'il prélève tout sous-ensemble de . Enfin cette classe est appelée classe VC de dimension n si n'arrive pas à pulvériser tout ensemble de taille . On note le nombre maximum de sous-ensemble prélevées de taille , i.e.

Le lemme de Sauer donne une borne majorante de si est une classe VC. Formellement si est une classe VC de dimension alors

Preuve

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 .

Initialisation : Si donc .

Si n'arrive à pulvériser aucun point.

Hérédité : Supposons que la propriété soit vérifiée pour tout . Soit une classe VC (de sous-ensemble d'un ensemble ) de dimension et un ensemble de points de . On se fixe un élément et on découpe par avec

On a que et par construction . En notant les qui constituent , i.e.

on a que .

Par construction, si pulvérise un échantillon, pulvérise également cet échantillon et ce même si on lui rajoute d'où . Ainsi par hypothèse de récurrence,

Si , alors en utilisant le résultat précédent et l'inégalité ,

Références

  1. (en) N. Sauer, « On the density of families of sets », Journal of Combinatorial Theory, a, vol. 13, , p. 145-147 (lire en ligne)
  2. (en) S. Shelah, « A combinatorial problem; stability and order for models and theories in infinitary languages », Pacific Journal of Mathematics, vol. 41, , p. 247-261 (lire en ligne)
  3. (en) Aad W. Van der Vaart et Jon A. Wellner, Weak convergence and empirical processes, Springer
  4. Massih-Reza Amini, Apprentissage machine de la théorie à la pratique, Eyrolles
  • Portail des mathématiques
  • Portail des probabilités et de la statistique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.