ブレタノレ-フーバー不等式 - 百科事典

情報理論において、Bretagnolle-Huber 不等式は、二つの確率分布の間の総変化距離をKullback-Leibler 拡散の凸で制限された関数で制限します。

正式な記述

= 初期定義 =
次の二つの確率分布

P
{\displaystyle P}

と

Q
{\displaystyle Q}

が測度空間

(
X,
F
)
{\displaystyle ({\mathcal {X}},{\mathcal {F}})}

上にあると仮定します。

次の通り、PとQの間の総変化距離は次のように定義されます。

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)|\}.}


次の通り、Kullback-Leibler 拡散は次のように定義されます。

D
K
L
(
P
∥
Q
)
=
{
∫
X
log
⁡
(
d
P
d
Q
)
d
P
& {\text{if }}P\ll Q,\\
+
∞
& {\text{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}}}


上記の

P
≪
Q
{\displaystyle P\ll Q}

は、PがQに関する絶対連続であることを示し、

d
P
d
Q
{\displaystyle {\frac {dP}{dQ}}}

は、PがQに関するRadon-Nikodym 微分を示します。

= 一般的な記述 =
Bretagnolle-Huber 不等式は次のように言います。

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))}


代数的バージョン
上記の制限に直接含まれる以下のバージョンが、一部の著者によって好まれます。

次の通り、任意のイベント

A
∈
F
{\displaystyle A\in {\mathcal {F}}}

について

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))}


ここで、

A
¯
=
Ω
∖
A
{\displaystyle {\bar {A}}=\Omega \smallsetminus A}

は、Aの補集合です。

実際、総変化の定義により、任意の

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
)
)
{\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}}}


このように整理すると、次の通り

P
(
A
)
+
Q
(
A
¯
)
{\displaystyle P(A)+Q({\bar {A}})}

上の主張される下限が得られます。

証明
Tsybakovの本（レーマ2.6、89ページ）のアイデアに従って主張を証明します。これは元の証明（C.Canonneのノートを参照して、その議論の現代化された再録を）と異なります。

証明は2つのステップで行われます。

1. Cauchy-Schwarzを使って、総変化距離がBhattacharyya係数（不等式の右側）に関連していることを証明します。

1
−
d
T
V
(
P,
Q
)
≤
(
∫
P
Q
)
2
{\displaystyle 1-d_{\mathrm {TV} }(P,Q)^{2}\geq \left(\int {\sqrt {PQ}}\right)^{2}}


2. Jensenの不等式を使って以下を証明します。

(
∫
P
Q
)
2
≥
exp
(
−
D
K
L
(
P
∥
Q
)
)
{\displaystyle \left(\int {\sqrt {PQ}}\right)^{2}\geq \exp(-D_{\mathrm {KL} }(P\parallel Q))}


ステップ1：
まず以下を注意します。

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}


このように見ると、以下を示します。

1
−
d
T
V
(
P,
Q
)
≤
(
∫
min
(
P,
Q
)
∫
max
(
P,
Q
)
{\displaystyle 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)}


そして、以下を加えたり取り除いたりします。

∫
A
∗
¯
max
(
P,
Q
)
{\displaystyle \int _{\bar {A^{*}}}\max(P,Q){\text{ or }}\int _{\bar {A^{*}}}\min(P,Q)}

これにより、両方の恒等式が得られます。

次に、以下を示します。

1
−
d
T
V
(
P,
Q
)
≤
(
∫
min
(
P,
Q
)
∫
max
(
P,
Q
)
≥
(
∫
min
(
P,
Q
)
max
(
P,
Q
)
)
2
{\displaystyle {\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)}}\right)^{2}\\&=\left(\int {\sqrt {PQ}}\right)^{2}\end{aligned}}}


これは以下の通りです。

P
Q
=
min
(
P,
Q
)
max
(
P,
Q
)
{\displaystyle PQ=\min(P,Q)\max(P,Q).}


ステップ2：
以下を書きます。

(
⋅
)
2
=
exp
(
2
log
(
⋅
)
)
{\displaystyle (\cdot )^{2}=\exp(2\log(\cdot ))}

そして、Jensenの不等式を適用します。

(
∫
P
Q
)
2
=
exp
(
2
log
(
∫
P
Q
)
)
≥
exp
(
∫
P
Q
−
log
(
∫
P
Q
)
)
=exp
(
−
D
K
L
(
P,
Q
)
)
{\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(\operatorname {E} _{P}\left[\left({\sqrt {\frac {P}{Q}}}\right)^{-1}\,\right]\right)\right)\\&\geq \exp \left(\operatorname {E} _{P}\left[-\log \left({\frac {P}{Q}}\right)\right]\right)=\exp(-D_{KL}(P,Q))\end{aligned}}}


ステップ1とステップ2の結果を組み合わせると、主張される総変化距離の制限が得られます。

应用例

= 偏りのあるコイン投げのサンプル複雑さ =
ソース：
質問は次の通りです。公正なコインと偏ったコインを区別するためにどれだけのコイン投げが必要ですか？次のように仮定します。2つのコインがあります。公正なコイン（Bernoulli分布で平均

p
1
=
1
/
2
{\displaystyle p_{1}=1/2}

）と

ε
{\displaystyle \varepsilon }

-偏りのコイン（

p
2
=
1
/
2
+
ε
{\displaystyle p_{2}=1/2+\varepsilon }

）です。このようにして、少なくとも

1
−
δ
{\displaystyle 1-\delta }

-確率で偏ったコインを識別するために、以下のようになります。

n
≥
1
2
ε
2
log
⁡
(
1
/
2
δ