Hoeffding (inégalité de)

Lancez 100 fois une pièce équilibrée. Obtenir exactement 50 faces n'est pas garanti, mais un résultat très éloigné de 50 devient vite peu probable. L'inégalité de Hoeffding traduit cette idée en une limite chiffrée, sans connaître tous les détails de la loi des résultats.

Elle exploite deux informations : les essais sont indépendants et chaque résultat reste entre deux bornes connues. Plus le nombre d'essais augmente, plus sa borne décroît rapidement pour un écart fixé.

L'inégalité de Hoeffding est une inégalité de concentration pour une somme, ou une moyenne, de variables aléatoires indépendantes et bornées. Elle majore la probabilité que leur valeur observée s'écarte de leur espérance, sans exiger qu'elles aient toutes la même loi.

Pour chaque indice i allant de 1 à n, la variable X_i doit rester entre deux nombres connus a_i et b_i. On note S_n leur somme et E[S_n] son espérance. Pour tout écart positif u, la forme bilatérale s'écrit :

Pour la moyenne, l'écart u vaut nt si t désigne l'écart moyen recherché. Le membre de droite devient alors $2\exp (-\frac{2n^2{t}^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2})2\backslash exp\backslash left(-\backslash frac\{2n^2t^2\}\{\backslash sum\_\{i=1\}^\{n\}(b\_i-a\_i)^2\}\backslash right)$. Si toutes les variables appartiennent au même intervalle [a, b], cette borne se simplifie en $2\exp (-\frac{2n{t}^2}{(b-a{)}^2})2\backslash exp\backslash left(-\backslash frac\{2nt^2\}\{(b-a)^2\}\backslash right)$.

Si X₁, …, X_n sont indépendantes et si chaque X_i reste presque sûrement dans l'intervalle [a_i, b_i], alors, pour tout nombre positif t, leur moyenne $\bar{X}=\frac{1}{n}{\sum }_{i=1}^n{X}_i\backslash overline\; X=\backslash frac\{1\}\{n\}\backslash sum\_\{i=1\}^\{n\}X\_i$ vérifie :

À nombre d'observations et intervalles fixés, la borne diminue quand l'écart t augmente. Lorsque toutes les variables sont bornées dans un même intervalle, elle diminue aussi quand le nombre d'observations augmente ; dans le cas général, cette dépendance est gouvernée par le rapport entre n² et la somme des largeurs d'intervalle au carré.

L'inégalité s'applique à une somme finie de variables réelles. Première condition vérifiable : les variables sont indépendantes. Deuxième condition : pour chacune, des bornes finies a_i et b_i sont valables presque sûrement. Les variables peuvent toutefois avoir des lois et des intervalles différents. Il faut enfin choisir un écart positif et connaître, ou pouvoir exprimer, l'espérance de la somme ou de la moyenne.

Des lancers successifs influencés par les résultats précédents ne satisfont pas l'indépendance : la formule précédente n'est alors pas justifiée. Une inégalité adaptée aux martingales peut convenir. Si les valeurs ne sont pas bornées, une autre hypothèse de queue est nécessaire : une hypothèse sous-gaussienne donne par exemple une borne exponentielle analogue, tandis qu'une variance finie permet d'appliquer Tchebychev. Une borne de type Bernstein ne convient que si ses propres hypothèses de contrôle des amplitudes, des moments ou de la fonction génératrice sont vérifiées.

Une pièce équilibrée est lancée 100 fois, indépendamment. Pour le lancer numéro i, X_i vaut 1 si face apparaît et 0 sinon. Chaque variable appartient donc à [0, 1], et la proportion moyenne attendue de faces vaut 0,50. On cherche la probabilité que la proportion observée s'écarte d'au moins 0,15 de cette valeur.

1. Le nombre d'essais est n = 100 et chaque largeur b_i − a_i vaut 1.
2. La somme des carrés des largeurs vaut donc 100.
3. L'écart choisi est t = 0,15, soit 15 points de proportion.
4. La borne de Hoeffding vaut $2\exp (-\frac{2\times {100}^2\times {\mathrm{0,15}}^2}{100})=2e^{-\mathrm{4,5}}\approx \mathrm{0,0222}2\backslash exp\backslash left(-\backslash frac\{2\backslash times100^2\backslash times0\{,\}15^2\}\{100\}\backslash right)=2e^\{-4\{,\}5\}\backslash approx0\{,\}0222$.

La probabilité d'obtenir au plus 35 faces ou au moins 65 faces est donc majorée par environ 2,22 %. Pour contrôler le calcul, la forme simplifiée donne le même exposant : −2 × 100 × 0,15² = −4,5. La figure matérialise les deux zones d'écart concernées autour des 50 faces attendues.

Dans un sondage fondé sur des réponses indépendantes valant 0 ou 1, Hoeffding fournit une marge probabiliste qui ne dépend pas de la proportion inconnue. Si une estimation fiable de la variance est disponible, une borne de Bernstein peut être plus serrée.

En apprentissage automatique, une perte bornée calculée sur des exemples indépendants peut relier performance empirique et performance moyenne. Le geste consiste à fixer un risque maximal, puis à résoudre la borne pour l'écart ou la taille d'échantillon recherchée.

Lors d'essais répétés dont chaque score reste dans un intervalle connu, la borne donne un contrôle rapide sans modéliser toute la distribution. Si les observations sont dépendantes ou non bornées, il faut choisir un outil conforme à cette structure plutôt que réutiliser automatiquement Hoeffding.

Avec l'inégalité de Tchebychev. Tchebychev utilise une variance finie et produit une décroissance en inverse du carré de l'écart. Hoeffding utilise indépendance et bornes presque sûres, puis donne une décroissance exponentielle. Pour des variables indépendantes dans [0, 1] sans variance calculée, Hoeffding est directement applicable.

Avec l'inégalité de Bernstein. Bernstein fait intervenir une information de variance en plus d'un contrôle des amplitudes. Le gain éventuel par rapport à Hoeffding dépend conjointement de la variance, de l'amplitude maximale et de l'écart considéré ; si seule l'étendue de chaque variable est connue, Hoeffding reste le choix immédiat.

Une borne supérieure n'est pas la probabilité exacte. Dans l'exemple, 2,22 % est un plafond garanti, pas la fréquence exacte des résultats hors de [35, 65]. Pour une probabilité exacte, il faut utiliser la loi binomiale de la somme.

Le membre de droite peut dépasser 1. Une probabilité ne dépasse jamais 1, mais la formule bilatérale tend vers 2 lorsque t tend vers 0. Dans ce cas, on retient le minimum entre 1 et la borne exponentielle ; la garantie est valide mais peu informative.

Des bornes exagérément larges affaiblissent le résultat. Déclarer [−100, 100] pour une variable qui reste en pratique près de zéro gonfle le dénominateur et peut rendre le plafond inutilisable. Il faut employer les bornes presque sûres les plus précises que les données permettent de justifier.

L'indépendance ne se devine pas sur une série. Des mesures successives peuvent partager une cause ou dépendre du passé sans que le tableau de valeurs le montre. Il faut justifier le mécanisme d'échantillonnage ; sinon, une borne conçue pour la dépendance est requise.

La fiche variable aléatoire précise l'objet auquel les bornes et l'espérance de Hoeffding s'appliquent.

L'article Apprentissage automatique et réseaux de neurones situe le domaine où les bornes de généralisation contrôlent l'écart entre échantillon et population.