Desigualdad de Bretagnolle-Huber - Enciclopedia
En la teoría de la información, la desigualdad de Bretagnolle-Huber limita la distancia de variación total entre dos distribuciones de probabilidad
P
{\displaystyle P}
y
Q
{\displaystyle Q}
mediante una función cóncava y acotada de la divergencia de Kullback-Leibler
D
K
L
(
P
∥
Q
)
{\displaystyle D_{\mathrm {KL} }(P\parallel Q)}
. La frontera puede considerarse como una alternativa a la conocida desigualdad de Pinsker: cuando
D
K
L
(
P
∥
Q
)
{\displaystyle D_{\mathrm {KL} }(P\parallel Q)}
es grande (por ejemplo, mayor que 2), la desigualdad de Pinsker está vacía, mientras que Bretagnolle-Huber sigue acotada y, por lo tanto, no vacía. Se utiliza en estadística y aprendizaje automático para probar límites inferiores de información teórica que dependen de las pruebas de hipótesis. (La desigualdad de Bretagnolle-Huber-Carol es una variación de la desigualdad de concentración para variables aleatorias multinomiales que limita la distancia de variación total.)
Declaración formal
= Definiciones preliminares =
Sean
P
{\displaystyle P}
y
Q
{\displaystyle Q}
dos distribuciones de probabilidad en un espacio medible
(
X
,
F
)
{\displaystyle ({\mathcal {X}},{\mathcal {F}})}
.
Recuerde que la variación total entre
P
{\displaystyle P}
y
Q
{\displaystyle Q}
se define como
d
T
V
(
P
,
Q
)
=
sup
A
∈
F
{
|
P
(
A
)
−
Q
(
A
)
|
}
.
{\displaystyle d_{\mathrm {TV} }(P,Q)=\sup _{A\in {\mathcal {F}}}\{|P(A)-Q(A)|\}.}
La divergencia de Kullback-Leibler se define como sigue:
D
K
L
(
P
∥
Q
)
=
{
∫
X
log
(
d
P
d
Q
)
d
P
if
P
≪
Q
,
+
∞
otherwise
.
{\displaystyle 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{otherwise}}.\end{cases}}}
En el caso anterior, la notación
P
≪
Q
{\displaystyle P\ll Q}
significa la absoluta continuidad de
P
{\displaystyle P}
con respecto a
Q
{\displaystyle Q}
, y
d
P
d
Q
{\displaystyle {\frac {dP}{dQ}}}
representa la derivada de Radon-Nikodym de
P
{\displaystyle P}
con respecto a
Q
{\displaystyle Q}
.
= Declaración general =
La desigualdad de Bretagnolle-Huber dice:
d
T
V
(
P
,
Q
)
≤
1
−
exp
(
−
D
K
L
(
P
∥
Q
)
)
≤
1
−
1
2
exp
(
−
D
K
L
(
P
∥
Q
)
)
{\displaystyle d_{\mathrm {TV} }(P,Q)\leq {\sqrt {1-\exp(-D_{\mathrm {KL} }(P\parallel Q))}}\leq 1-{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))}
Versión alternativa
La siguiente versión se implica directamente por la frontera anterior, pero algunos autores prefieren expresarla de esta manera.
Sea
A
∈
F
{\displaystyle A\in {\mathcal {F}}}
cualquier evento. Entonces
P
(
A
)
+
Q
(
A
¯
)
≥
1
2
exp
(
−
D
K
L
(
P
∥
Q
)
)
{\displaystyle P(A)+Q({\bar {A}})\geq {\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))}
donde
A
¯
=
Ω
∖
A
{\displaystyle {\bar {A}}=\Omega \smallsetminus A}
es el complemento de
A
{\displaystyle A}
.
De hecho, por definición de la variación total, para cualquier
A
∈
F
{\displaystyle A\in {\mathcal {F}}}
,
Q
(
A
)
−
P
(
A
)
≤
d
T
V
(
P
,
Q
)
≤
1
−
1
2
exp
(
−
D
K
L
(
P
∥
Q
)
)
=
Q
(
A
)
+
Q
(
A
¯
)
−
1
2
exp
(
−
D
K
L
(
P
∥
Q
)
)
{\displaystyle {\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}}}
Reordenando, obtenemos la frontera inferior reclamada sobre
P
(
A
)
+
Q
(
A
¯
)
{\displaystyle P(A)+Q({\bar {A}})}
.
Prueba
Demostramos la declaración principal siguiendo las ideas en el libro de Tsybakov (Lema 2.6, página 89), que difieren de la prueba original (ver la nota de C.Canonne para una transcripción modernizada de su argumento).
La prueba se realiza en dos pasos:
1. Demostrar usando el teorema de Cauchy-Schwarz que la variación total está relacionada con el coeficiente de Bhattacharyya (lado derecho de la desigualdad):
1
−
d
T
V
(
P
,
Q
)
2
≥
(
∫
P
Q
)
2
{\displaystyle 1-d_{\mathrm {TV} }(P,Q)^{2}\geq \left(\int {\sqrt {PQ}}\right)^{2}}
2. Demostrar mediante una aplicación inteligente del teorema de Jensen que
(
∫
P
Q
)
2
≥
exp
(
−
D
K
L
(
P
∥
Q
)
)
{\displaystyle \left(\int {\sqrt {PQ}}\right)^{2}\geq \exp(-D_{\mathrm {KL} }(P\parallel Q))}
Paso 1:
Primero, notamos que
d
T
V
(
P
,
Q
)
=
1
−
∫
min
(
P
,
Q
)
=
∫
max
(
P
,
Q
)
−
1
{\displaystyle d_{\mathrm {TV} }(P,Q)=1-\int \min(P,Q)=\int \max(P,Q)-1}
Para ver esto, denota
A
∗
=
arg
max
A
∈
Ω
|
P
(
A
)
−
Q
(
A
)
|
{\displaystyle A^{*}=\arg \max _{A\in \Omega }|P(A)-Q(A)|}
y sin pérdida de generalidad, supongamos que
P
(
A
∗
)
>
Q
(
A
∗
)
{\displaystyle P(A^{*})>Q(A^{*})}
tal que
d
T
V
(
P
,
Q
)
=
P
(
A
∗
)
−
Q
(
A
∗
)
{\displaystyle d_{\mathrm {TV} }(P,Q)=P(A^{*})-Q(A^{*})}
. Luego podemos escribir
d
T
V
(
P
,
Q
)
=
∫
A
∗
max
(
P
,
Q
)
−
∫
A
∗
min
(
P
,
Q
)
{\displaystyle d_{\mathrm {TV} }(P,Q)=\int _{A^{*}}\max(P,Q)-\int _{A^{*}}\min(P,Q)}
Y luego sumando y restando
∫
A
∗
¯
max
(
P
,
Q
)
o
∫
A
∗
¯
min
(
P
,
Q