ファノの不平等

情報理論において、ファノの不等式（ファノの逆、ファノの補題とも呼ばれる）は、ノイズのある通信経路で失われる平均情報量と分類エラーの確率との関係を表す。これは、ロバート・ファノが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}}}$

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

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

2つを等しくする

${\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}$の1つに${\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 つの質問に分割する方法として解釈できます。最初の質問は、次の項に対応します。${\displaystyle H_{b}(e)}$は、予測者の不確実性に関係します。予測が正しければ、不確実性は残りません。予測が間違っている場合、任意の離散分布の不確実性は、間違った予測を除くすべての選択肢にわたる一様分布のエントロピーの上限を持ちます。これはエントロピーを持ちます。${\displaystyle \log(|{\mathcal {X}}|-1)}$極端なケースを見ると、予測器が常に正しい場合、不等式の第 1 項と第 2 項は 0 となり、完全な予測器の存在は、${\displaystyle X}$完全に決定されます${\displaystyle Y}$、 など${\displaystyle H(X|Y)=0}$予測が常に間違っている場合、最初の項は 0 となり、 ${\displaystyle H(X\mid Y)}$残りの選択肢全体にわたって一様分布を用いることでのみ、上限値を定めることができる。

させて${\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}}$。

以下の一般化は、イブラギモフとハスミンスキー（1979）、アソアドとビルゲ（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) 『情報理論の基礎』38-42頁。ISBN  978-0-471-06259-2。
• L. デヴロイ著『密度推定入門』 、確率統計学の進歩、第14巻、ボストン、バークハウザー、1987年。ISBN 0-8176-3365-0ISBN​ 3-7643-3365-0。
• ファノ、ロバート（1968）。情報伝達：通信の統計理論。マサチューセッツ州ケンブリッジ：MIT Press。ISBN 978-0-262-56169-3. OCLC 804123877 . 
  • 別名: マサチューセッツ州ケンブリッジ、MIT Press、1961 年。ISBN 0-262-06001-9
• R. Fano、「ファノ不等式」、Scholarpedia、2008年。
• I.A. イブラギモフ、R.Z. ハスミンスキー、「統計的推定、漸近理論」。数学の応用、第16巻、シュプリンガー・フェルラーク、ニューヨーク、1981年。ISBN 0-387-90523-5