ファノの不等式

情報理論において、ファノの不等式（ファノの逆、ファノの補題とも呼ばれる）は、ノイズのある通信路で失われる平均情報量と分類誤りの確率を関連付ける。これは、1950年代初頭にロバート・ファノがMITで情報理論の博士課程セミナーを教えていた際に導出され、後に1961年の教科書に掲載された。

これは、任意のデコーダーのエラー確率の下限値と、密度推定におけるミニマックスリスクの下限値を見つけるために使用されます。

離散確率変数 とを、結合確率を持つ入力メッセージと出力メッセージとします。 をエラーの発生、つまり （ は の近似値）とします。ファノの不等式は ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle P(x,y)}$ ${\displaystyle e}$ ${\displaystyle X\neq {\tilde {X}}}$ ${\displaystyle {\tilde {X}}=f(Y)}$ ${\displaystyle X}$

${\displaystyle H(X\mid Y)\leq H_{b}(e)+P(e)\log(|{\mathcal {X}}|-1),}$

ここで はのサポートを表し、は （ の要素数）の基数を表し、 ${\displaystyle {\mathcal {X}}}$ ${\displaystyle X}$ ${\displaystyle |{\mathcal {X}}|}$ ${\displaystyle {\mathcal {X}}}$

${\displaystyle H(X\mid Y)=-\sum _{i,j}P(x_{i},y_{j})\log P(x_{i}\mid y_{j})}$

は条件付きエントロピーであり、

${\displaystyle P(e)=P(X\neq {\tilde {X}})}$

通信エラーの確率であり、

${\displaystyle H_{b}(e)=-P(e)\log P(e)-(1-P(e))\log(1-P(e))}$

は対応するバイナリエントロピーです。

証拠

推定値が誤っている という事象を示す指標確率変数を定義する。${\displaystyle E}$ ${\displaystyle {\tilde {X}}=f(Y)}$

${\displaystyle E:={\begin{cases}1~&{\text{ if }}~{\tilde {X}}\neq X~,\\0~&{\text{ if }}~{\tilde {X}}=X~.\end{cases}}}$

を考えてみましょう。エントロピーの連鎖律を用いて、これを2つの異なる方法で展開すること ができます。${\displaystyle H(E,X|{\tilde {X}})}$

${\displaystyle {\begin{aligned}H(E,X\mid {\tilde {X}})&=H(X\mid {\tilde {X}})+\underbrace {H(E\mid X,{\tilde {X}})} _{=0}\\&=H(E\mid {\tilde {X}})+H(X\mid E,{\tilde {X}})\end{aligned}}}$

両者を同等視する

${\displaystyle H(X\mid {\tilde {X}})=H(E\mid {\tilde {X}})+H(X\mid E,{\tilde {X}})}$

一番右の項を展開すると、${\displaystyle H(X\mid E,{\tilde {X}})}$

${\displaystyle {\begin{aligned}H(X\mid E,{\tilde {X}})&=\underbrace {H(X\mid E=0,{\tilde {X}})} _{=0}\cdot P(E=0)+H(X\mid E=1,{\tilde {X}})\cdot \underbrace {P(E=1)} _{=P(e)}\\&=H(X\mid E=1,{\tilde {X}})\cdot P(e)\end{aligned}}}$

は を意味するので、 の値が与えられれば の値が確実に分かります。そのため、 という項が成り立ちます。一方、 はを意味するので、 の値が与えられれば、異なる値のいずれかに絞り込むことができ、条件付きエントロピー の上限を定めることができます。したがって、 ${\displaystyle E=0}$ ${\displaystyle X={\tilde {X}}}$ ${\displaystyle {\tilde {X}}}$ ${\displaystyle X}$ ${\displaystyle H(X\mid E=0,{\tilde {X}})=0}$ ${\displaystyle E=1}$ ${\displaystyle {\tilde {X}}\neq X}$ ${\displaystyle {\tilde {X}}}$ ${\displaystyle X}$ ${\displaystyle |{\mathcal {X}}|-1}$ ${\displaystyle H(X\mid E=1,{\tilde {X}})\leq \log(|{\mathcal {X}}|-1)}$

${\displaystyle H(X\mid E,{\tilde {X}})\leq \log(|{\mathcal {X}}|-1)\cdot P(e).}$

もう一つの項は ​​です。これは、条件付けによってエントロピーが減少するからです。が定義されている方法により となり、 となります。これらをまとめると、 ${\displaystyle H(E\mid {\tilde {X}})\leq H(E)}$ ${\displaystyle E}$ ${\displaystyle H(E)=H_{b}(e)}$ ${\displaystyle H(E\mid {\tilde {X}})\leq H_{b}(e)}$

${\displaystyle H(X\mid {\tilde {X}})\leq H_{b}(e)+P(e)\log(|{\mathcal {X}}|-1)}$

はマルコフ連鎖なので、データ処理不等式によって、したがって、 ${\displaystyle X\rightarrow Y\rightarrow {\tilde {X}}}$ ${\displaystyle I(X;{\tilde {X}})\leq I(X;Y)}$ ${\displaystyle H(X\mid {\tilde {X}})\geq H(X\mid Y)}$

${\displaystyle H(X\mid Y)\leq H_{b}(e)+P(e)\log(|{\mathcal {X}}|-1)}$

直感

ファノの不等式は、任意の予測子を与えられた場合の条件付き分布の不確実性を 2 つの問題に分割する方法として解釈できます。 項 に対応する最初の問題は、予測子の不確実性に関するものです。予測が正しければ、それ以上不確実性は残りません。予測子が正しくない場合、任意の離散分布の不確実性には、誤った予測を除くすべての選択肢にわたる一様分布のエントロピーの上限があります。これはエントロピー を持ちます。極端な例を見ると、予測子が常に正しい場合、不等式の 1 番目と 2 番目の項は 0 であり、完全な予測子が存在するということは、 がによって完全に決定されることを意味するため となります。予測子が常に間違っている場合、最初の項は 0 であり、 残りの選択肢にわたる一様分布でのみ上限が制限されます。 ${\displaystyle H_{b}(e)}$ ${\displaystyle \log(|{\mathcal {X}}|-1)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H(X|Y)=0}$ ${\displaystyle H(X\mid Y)}$

代替処方

を、密度が可能な密度の1つに等しい確率変数とする。さらに、任意の密度のペア間のカルバック・ライブラー距離は、あまり大きくならない。 ${\displaystyle X}$ ${\displaystyle r+1}$ ${\displaystyle f_{1},\ldots ,f_{r+1}}$

${\displaystyle D_{KL}(f_{i}\parallel f_{j})\leq \beta }$ すべての人のために${\displaystyle i\not =j.}$

を指数の推定値とすると 、${\displaystyle \psi (X)\in \{1,\ldots ,r+1\}}$

${\displaystyle \sup _{i}P_{i}(\psi (X)\not =i)\geq 1-{\frac {\beta +\log 2}{\log r}}}$

ここで はによって誘導される確率です。 ${\displaystyle P_{i}}$ ${\displaystyle f_{i}}$

一般化

以下の一般化は、Ibragimov と Khasminskii (1979)、Assouad と Birge (1983) によるものです。

Fをr  + 1個の密度ƒθのサブクラスを持つ密度のクラスとし、任意_のθ ≠  θ  ′に対して

${\displaystyle \|f_{\theta }-f_{\theta '}\|_{L_{1}}\geq \alpha ,}$

${\displaystyle D_{KL}(f_{\theta }\parallel f_{\theta '})\leq \beta .}$

最悪の場合、推定誤差の 期待値は以下のように制限される。

${\displaystyle \sup _{f\in \mathbf {F} }E\|f_{n}-f\|_{L_{1}}\geq {\frac {\alpha }{2}}\left(1-{\frac {n\beta +\log 2}{\log r}}\right)}$

ここで、ƒ _nはサイズnのサンプルに基づく任意の密度推定値です。

参考文献

• P. Assouad、「Deux remarques sur l'estimation」、Comptes Rendus de l'Académie des Sciences de Paris、Vol. 296、1021–1024ページ、1983年。
• L. Birge、「注文制限の下での密度の推定: 非漸近的ミニマックス リスク」、技術レポート、UE​​R de Sciences Économiques、パリ第 10 大学、ナンテール、フランス、1983 年。
• T. Cover, J. Thomas (1991).情報理論の要素. pp.  38–42 . ISBN 978-0-471-06259-2。
• L. Devroye著『密度推定講座』確率統計学の進歩、第14巻。ボストン、バークハウザー、1987年。ISBN 0-8176-3365-0、ISBN 3-7643-3365-0。
• ファノ、ロバート（1968年）『情報の伝達：コミュニケーションの統計理論』ケンブリッジ、マサチューセッツ州：MIT出版。ISBN 978-0-262-56169-3. OCLC  804123877 .
  • 別名: マサチューセッツ州ケンブリッジ、MIT Press、1961 年。ISBN 0-262-06001-9
• R. Fano、「ファノ不等式」 Scholarpedia、2008年。
• IAイブラギモフ、RZハスミンスキー著『統計的推定、漸近理論』応用数学、第16巻、シュプリンガー・フェアラーク、ニューヨーク、1981年。ISBN 0-387-90523-5