Bretagnolle–Huber ojämlikhet

I informationsteorin begränsar Bretagnolle–Huber-olikheten det totala variationsavståndet mellan två sannolikhetsfördelningar $P$ och $Q$ av en konkav och begränsad funktion av Kullback-Leibler-divergensen $D_{\mathrm {KL} }(P\parallel Q)$ . Bindningen kan ses som ett alternativ till den välkända Pinskers ojämlikhet : när $D_{\mathrm {KL} }(P\parallel Q)$ är stor (större än 2 för instans.), Pinskers ojämlikhet är tom, medan Bretagnolle-Huber förblir begränsad och därmed icke-tom. Det används i statistik och maskininlärning för att bevisa informationsteoretiska nedre gränser baserat på hypotestestning

Formellt uttalande

Preliminära definitioner

Låt $P$ och $Q$ vara två sannolikhetsfördelningar på ett mätbart utrymme $({\mathcal {X}},{\mathcal {F}})$ . Kom ihåg att den totala variationen mellan $P$ och $Q$ definieras av

$d_{\mathrm {TV} }(P,Q)=\sup _{A\in {\mathcal {F}}}\{|P(A)-Q(A)|\}.$

Kullback -Leibler-divergensen definieras enligt följande:

$D_{\mathrm {KL} }(P\parallel Q)={\begin{cases}\int _{\mathcal {X}}\log {\bigl (}{\frac {dP}{dQ} }{\bigr )}\,dP&{\text{if }}P\ll Q,\\[1mm]+\infty &{\text{annars}}.\end{cases}}$

I ovanstående står notationen $P\ll Q$ för absolut kontinuitet av $P$ med avseende på $Q$ , och ${\frac { dP}{dQ}}$ står för Radon–Nikodym-derivatan av $P$ med avseende på $Q$ .

Allmänt uttalande

Ojämlikheten mellan Bretagnolle och Huber säger:

${\displaystyle d_{\mathrm$

Alternativ version

Följande version antyds direkt av bunden ovan men vissa författare föredrar att uttrycka det så här. Låt $A\in {\mathcal {F}}$ vara vilken händelse som helst. Sedan

$P(A)+Q({\bar {A}})\geq {\frac { 1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))$

där ${\bar {A}}=\Omega \smallsetminus A$ är komplementet till $A$ .

I själva verket, per definition av den totala variationen, för alla $A\in {\mathcal {F}}$ ,

${\begin{aligned}Q(A)-P(A)\leq d_{\mathrm {TV} }(P,Q)&\leq 1 -{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))\\&=Q(A)+Q({\bar {A}})- {\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))\end{aligned}}$

Om vi ​​arrangerar om får vi den påstådda nedre gränsen på $P(A)+Q({\bar {A}})$ .

Bevis

Vi bevisar huvudpåståendet efter idéerna i Tsybakovs bok (Lemma 2.6, sidan 89), som skiljer sig från originalbeviset (se C.Canonnes anteckning för en moderniserad omskrivning av deras argument).

Beviset är i två steg:

1. Bevisa med Cauchy–Schwarz att den totala variationen är relaterad till Bhattacharyya-koefficienten (höger sida av ojämlikheten):

$1-d_{\mathrm {TV} }(P,Q)^{2}\geq \left(\int {\sqrt {PQ}}\right)^{2}$

2. Bevisa genom en smart tillämpning av Jensens ojämlikhet att

$\left(\int {\sqrt {PQ}}\right)^{2}\geq \exp(-D_{ \mathrm {KL} }(P\parallel Q))$

• Steg 1:

Lägg först märke till att

${\ displaystyle d_{\mathrm {TV} }(P,Q)=1-\int \min(P,Q)=\int \max(P,Q)-1} För att se detta,$

beteckna ${\displaystyle A^{*}=\arg \max _{A\in \Omega }|P(A)-Q(A)|} och utan förlust av generalitet, antag$ att $P(A^{*})>Q(A^{*})$ så att $d_{ \mathrm {TV} }(P,Q)=P(A^{*})-Q(A^{*})$ . Sedan kan vi skriva om

${\displaystyle d_{\mathrm {TV} }(P,Q)=\ int _{A^{*}}\max(P,Q)-\int _{A^{*}}\min(P,Q)} Och sedan lägga till och ta$

bort $\int _{\bar {A^{*}}}\max(P,Q){\text{ eller }}\int _{\bar {A ^{*}}}\min(P,Q)$ vi får båda identiteterna.

Då

${\begin{aligned}1-d_{\mathrm {TV} }(P,Q) ^{2}&=(1-d_{\mathrm {TV} }(P,Q))(1+d_{\mathrm {TV} }(P,Q))\\&=\int \min(P ,Q)\int \max(P,Q)\\&\geq \left(\int {\sqrt {\min(P,Q)\max(P,Q)}}\höger)^{2}\ \&=\left(\int {\sqrt {PQ}}\right)^{2}\end{aligned}}$

eftersom $PQ=\min(P,Q)\max(P,Q).$

• Steg 2:

Vi skriver $(\cdot )^{ 2}=\exp(2\log(\cdot ))$ och tillämpa Jensens olikhet :

${\displaystyle {\begin{aligned}\left(\int {\sqrt {PQ}}\right)^{2}&=\exp \left(2\log \left(\int {\ sqrt {PQ}}\right)\right)\\&=\exp \left(2\log \left(\int P{\sqrt {\frac {Q}{P}}}\right)\right)\ \&=\exp \left(2\log \left(\operatörsnamn {E} _{P}\left[\left({\sqrt {\frac {P}{Q}}}\right)^{-1 }\,\right]\right)\right)\\&\geq \exp \left(\operatörsnamn {E} _{P}\left[-\log \left({\frac {P}{Q}} \right)\right]\right)=\exp(-D_{KL}(P,Q))\end{aligned}}} Att kombinera$

resultaten av steg 1 och 2 leder till den anspråkade gränsen för den totala varianten.

Exempel på applikationer

Exempel på komplexitet för partiska myntkast

Frågan är hur många myntkast behöver jag för att skilja ett rättvist mynt från ett partiskt?

Antag att du har 2 mynt, ett rättvist mynt ( Bernoulli fördelat med medelvärde $p_{1}=1/2$ ) och ett $\varepsilon$ -förspänt mynt ( $p_{2}=1/2+\varepsilon$ ). Sedan, för att identifiera det partiska myntet med sannolikhet minst $1-\delta$ (för vissa $\delta >0$ ), åtminstone

$n\geq {\frac {1}{2\varepsilon ^{2}}}\log \left({\frac {1}{2\delta }}\right).$

För att erhålla denna nedre gräns kräver vi att det totala variationsavståndet mellan två sekvenser av $n$ sampel är minst $1-2\delta$ . Detta beror på att den totala variationen övre gränsen för sannolikheten för att under- eller överskatta myntens medel. Beteckna $P_{1}^{n}$ och $P_{2}^{n}$ de respektive gemensamma fördelningarna av de $n$ myntkasten för varje mynt, sedan

Vi har

${\begin{aligned}(1-2\delta )^{2}&\leq d_{\ mathrm {TV} }\left(P_{1}^{n},P_{2}^{n}\right)^{2}\\[4pt]&\leq 1-e^{-D_{\mathrm {KL} }(P_{1}^{n}\parallel P_{2}^{n})}\\[4pt]&=1-e^{-nD_{\mathrm {KL} }(P_{1 }\parallel P_{2})}\\[4pt]&=1-e^{-n{\frac {\log(1/(1-4\varepsilon ^{2}))}{2}}} \end{aligned}}$

Resultatet erhålls genom att ordna om termerna.

Informationsteoretisk nedre gräns för k -armade banditspel

I flerarmad bandit kan en nedre gräns för minimax-ångret för någon banditalgoritm bevisas med Bretagnolle-Huber och dess konsekvens på hypotestestning (se kapitel 15 i Bandit Algorithms ).

Historia

Resultatet bevisades första gången 1979 av Jean Bretagnolle och Catherine Huber, och publicerades i handlingarna av Strasbourg Probability Seminar. Alexandre Tsybakovs bok innehåller en tidig återpublicering av ojämlikheten och dess tillskrivning till Bretagnolle och Huber, som presenteras som en tidig och mindre allmän version av Assouads lemma (se not 2.8). En ständig förbättring av Bretagnolle–Huber bevisades 2014 som en konsekvens av en förlängning av Fanos Inequality .

Se även

• Total variation för en lista med övre gränser