Inégalité de Bretagnolle – Huber
En théorie de l'information, l' inégalité de Bretagnolle – Huber limite la distance de variation totale entre deux distributions de probabilité et par une fonction concave et bornée de la divergence Kullback – Leibler . La borne peut être considérée comme une alternative à la célèbre inégalité de Pinsker : lorsque est grand (supérieur à 2 par exemple), l'inégalité de Pinsker n'est pas informative car la borne tend vers l'infini, tandis que Bretagnolle – Huber reste bornée. Elle est utilisée en statistiques et en apprentissage automatique pour prouver les limites inférieures de la théorie de l'information en s'appuyant sur des tests d'hypothèses[1] (l'inégalité de Bretagnolle – Huber – Carol est une variation de l'inégalité de concentration pour les variables aléatoires multinomiales qui délimite la distance de variation totale).
Enoncé
modifierDéfinitions préliminaires
modifierSoient et deux distributions de probabilité sur un espace mesurable . Rappelons que la variation totale entre et est défini par
La divergence Kullback-Leibler est définie comme suit :
Dans ce qui précède, la notation signifie que P est absolument continue par rapport a Q, et représente le dérivée de Radon – Nikodym de par rapport à .
Enoncé général
modifierL'inégalité de Bretagnolle-Huber s'énonce comme suit: Pour deux distributions de probabilités P et Q telles que ,
Version alternative
modifierLa version suivante est directement impliquée par la limite ci-dessus mais certains auteurs[1] préfèrent l'énoncer de cette façon. Soit un événement. Alors,
où est le complément de .
En effet, par définition de la variation totale, pour tout ,
En réorganisant, nous obtenons la borne inférieure revendiquée sur .
Preuve
modifierNous prouvons l'énoncé principal suivant les idées du livre de Tsybakov (Lemme 2.6, page 89)[2], qui diffèrent de la preuve originale (voir la note de C.Canonne[3] pour une retranscription modernisée de leur argument).
La preuve se déroule en deux étapes :
1. Prouver à l'aide de Cauchy – Schwarz que la variation totale est liée au coefficient Bhattacharyya (partie droite de l'inégalité) :
2. Prouver par une application appropriée de l'inégalité de Jensen que
- Étape 1:
- Remarquez d'abord que
- Pour voir cela, notez et sans perte de généralité, supposons que tel que . Ensuite, nous pouvons réécrire
- Et puis ajouter et supprimer nous obtenons les deux identités.
- Alors
- parce que
- Étape 2:
- Nous écrivons et appliquer l'inégalité de Jensen :
- La combinaison des résultats des étapes 1 et 2 conduit à la limite revendiquée sur la variation totale.
Exemples d'applications
modifierExemple de complexité de lancers de pièces biaisés
modifierLa question[3] est de savoir combien de tirages à pile ou face ai-je besoin pour distinguer une pièce équilibrée d’une pièce biaisée ?
Supposons que vous ayez 2 pièces, une pièce équilibrée (Bernoulli distribué avec une moyenne ) et un pièce -biaisée ( ). Ensuite, afin d'identifier la pièce biaisée avec une probabilité d'au moins (pour certains ), on doit tirer la pièce $n$ fois avec
Afin d’obtenir cette borne inférieure nous imposons que la distance totale de variation entre deux séquences de échantillons soit au moins . En effet, la variation totale limite la probabilité de sous-estimer ou de surestimer les moyennes des pièces. Dénotons et les distributions conjointes respectives des des tirages au sort pour chaque pièce. Alors nous avons,
Le résultat est obtenu en réorganisant les termes.
Borne inférieure théorique pour les jeux de bandits manchots à k bras
modifierDans le problème du bandit manchot, une limite inférieure du regret minimax de tout algorithme de bandit peut être prouvée en utilisant Bretagnolle – Huber et ses conséquences sur les tests d'hypothèses (voir le chapitre 15 de Bandit Algorithms[1] ).
Histoire
modifierLe résultat a été prouvé pour la première fois en 1979 par Jean Bretagnolle et Catherine Huber, et publié dans les actes du Séminaire de Probabilités de Strasbourg[4]. Le livre d'Alexandre Tsybakov[2] présente une première réédition de l'inégalité et de son attribution à Bretagnolle et Huber. Celle-ci est présentée comme une version ancienne et moins générale du lemme d'Assouad (voir notes 2.8). Une amélioration constante par rapport à Bretagnolle – Huber a été prouvée en 2014 grâce à une extension de l'inégalité de Fano[5].
Voir également
modifier- Variation totale pour une liste de bornes supérieures
- Inégalité de Bretagnolle – Huber – Carol dans la page Inégalité de concentration
Références
modifier- Tor Lattimore et Csaba Szepesvari, Bandit Algorithms, Cambridge University Press, (lire en ligne)
- Alexandre B. Tsybakov, Introduction to nonparametric estimation, Springer, coll. « Springer Series in Statistics », (ISBN 978-1-4419-2709-5, OCLC 757859245, DOI 10.1007/b13794, S2CID 42933599, lire en ligne)
- (en) Canonne, Clément L., « A short note on an inequality between KL and TV », sur arXiv.org, (consulté le ).
- Jean Bretagnolle et Catherine Huber-Carol, « Estimation des densités : Risque minimax », Lecture notes in Mathematics, séminaire de Probabilités XII, vol. vol. 649, , pp. 342–363 (DOI doi:10.1007/bfb0064610, lire en ligne [PDF])
- Gerchinovitz, Ménard et Stoltz, « Fano's Inequality for Random Variables », Statistical Science, vol. 35, no 2, (ISSN 0883-4237, DOI 10.1214/19-sts716, arXiv 1702.05985, S2CID 15808752, lire en ligne)