ピンスカーの不等式

情報理論において、ピンスカーの不等式は、発明者のマーク・セメノビッチ・ピンスカーにちなんで名付けられ、カルバック・ライブラー距離の観点から総変動距離（または統計距離）を制限する不等式である。この不等式は定数因子まで厳密である。^[1]

ピンスカーの不等式は、と が測定可能な空間上の2つの確率分布である場合、 ${\displaystyle P}$${\displaystyle Q}$ ${\displaystyle (X,\Sigma )}$

${\displaystyle \delta (P,Q)\leq {\sqrt {{\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)}},}$

どこ

${\displaystyle \delta (P,Q)=\sup {\bigl \{}|P(A)-Q(A)|\mid \quad A\in \Sigma {\text{ is a measurable event}}{\bigr \}}}$

ととの合計変動距離（または統計距離）です。 ${\displaystyle P}$${\displaystyle Q}$

${\displaystyle D_{\mathrm {KL} }(P\parallel Q)=\operatorname {E} _{P}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)=\int _{X}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)\,\mathrm {d} P}$

は、 NATSにおけるカルバック・ライブラー距離です。標本空間が有限集合である場合、カルバック・ライブラー距離は次のように表されます。 ${\displaystyle X}$

${\displaystyle D_{\mathrm {KL} }(P\parallel Q)=\sum _{i\in X}\left(\log {\frac {P(i)}{Q(i)}}\right)P(i)\!}$

符号付き測度の全変動ノルム に関して、ピンスカーの不等式は上記のものと2倍異なることに注意してください。 ${\displaystyle \|P-Q\|}$ ${\displaystyle P-Q}$

${\displaystyle \|P-Q\|\leq {\sqrt {2D_{\mathrm {KL} }(P\parallel Q)}}.}$

ピンスカー不等式の証明には、fダイバージェンスの分割不等式が使用されます。

ピンスカー不等式の表現は、KLダイバージェンスの定義でどのような対数の基底が使用されるかによって異なることに注意してください。 は(底 の対数)を使用して定義されますが、は通常(底 2 の対数) を使用して定義されます。次に、 ${\displaystyle D_{KL}}$${\displaystyle \ln }$${\displaystyle e}$${\displaystyle D}$${\displaystyle \log _{2}}$

${\displaystyle D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}.}$

上記のコメントを踏まえると、情報相違と変動距離を関連付けるいくつかの文献では、ピンスカーの不等式の別の記述があります。

${\displaystyle D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}\geq {\frac {1}{2\ln 2}}V^{2}(p,q),}$

つまり、

${\displaystyle {\sqrt {\frac {D_{KL}(P\parallel Q)}{2}}}\geq {\frac {V(p,q)}{2}},}$

その中で

${\displaystyle V(p,q)=\sum _{x\in {\mathcal {X}}}|p(x)-q(x)|}$

は同じアルファベット上の2つの確率密度関数と 間の（正規化されていない）変動距離である。^[2] ${\displaystyle p}$${\displaystyle q}$${\displaystyle {\mathcal {X}}}$

この形式のピンスカー不等式は、「発散における収束」が「変動距離における収束」よりも強い概念であることを示しています。

ジョン・ポラードによる簡単な証明は次のように示されます。 ${\displaystyle r(x)=P(x)/Q(x)-1\geq -1}$

${\displaystyle {\begin{aligned}D_{KL}(P\parallel Q)&=E_{Q}[(1+r(x))\log(1+r(x))-r(x)]\\&\geq {\frac {1}{2}}E_{Q}\left[{\frac {r(x)^{2}}{1+r(x)/3}}\right]\\&\geq {\frac {1}{2}}{\frac {E_{Q}[|r(x)|]^{2}}{E_{Q}[1+r(x)/3]}}&{\text{(from Titu's lemma)}}\\&={\frac {1}{2}}E_{Q}[|r(x)|]^{2}&{\text{(As }}E_{Q}[1+r(x)/3]=1{\text{ )}}\\&={\frac {1}{2}}V(p,q)^{2}.\end{aligned}}}$

ここで、ティトゥの補題はセドラキアンの不等式としても知られています。

ピンスカー不等式の下限値は、 となる分布に対しては空の値となることに注意してください。これは、総変動距離が最大でも となるためです。このような分布に対しては、 BretagnolleとHuber ^[3]による別の上限値を使用することができます（Tsybakov ^[4]も参照）。 ${\displaystyle D_{\mathrm {KL} }(P\parallel Q)>2}$${\displaystyle 1}$

${\displaystyle \delta (P,Q)\leq {\sqrt {1-e^{-D_{\mathrm {KL} }(P\parallel Q)}}}.}$

ピンスカーは最初により大きな定数を持つ不等式を証明した。上記の形式の不等式は、カルバック、チザール、ケンパーマンによって独立に証明された。^[5]

不等式の正確な逆は成り立ちません。つまり、任意の に対して、となる超関数が存在します。簡単な例として、およびとなる2点空間が挙げられます。^[6]${\displaystyle \varepsilon >0}$${\displaystyle P_{\varepsilon },Q}$${\displaystyle \delta (P_{\varepsilon },Q)\leq \varepsilon }$${\displaystyle D_{\mathrm {KL} }(P_{\varepsilon }\parallel Q)=\infty }$${\displaystyle \{0,1\}}$${\displaystyle Q(0)=0,Q(1)=1}$${\displaystyle P_{\varepsilon }(0)=\varepsilon ,P_{\varepsilon }(1)=1-\varepsilon }$

しかし、定数が に依存する有限空間では逆不等式が成り立つ。^[7]より具体的には、に絶対連続な任意の測度に対して、 の定義により、${\displaystyle X}$${\displaystyle Q}$${\displaystyle \alpha _{Q}:=\min _{x\in X:Q(x)>0}Q(x)}$${\displaystyle P}$${\displaystyle Q}$

${\displaystyle {\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.}$

その結果、 が完全な支持を持つ場合（つまり、すべての に対して）、 ${\displaystyle Q}$${\displaystyle Q(x)>0}$${\displaystyle x\in X}$

${\displaystyle \delta (P,Q)^{2}\leq {\frac {1}{2}}D(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.}$

• Thomas M. Cover と Joy A. Thomas:情報理論の要素、第 2 版、Willey-Interscience、2006 年
• ニコロ・チェサ＝ビアンキとガボール・ルゴシ：予測、学習、ゲー​​ム、ケンブリッジ大学出版局、2006年