ファノの不等式のソースを表示

[[情報理論]]において、'''ファノの不等式'''（ファノのふとうしき、{{lang-en|Fano's inequality}}）は、雑音の多い通信路で失われた情報の平均を分類誤りの確率と関連付ける[[不等式]]である。1950年代初めに[[ロベルト・ファノ]]によって[[MIT]]での情報理論の[[Ph.D]]セミナーで導かれ、その後の彼の1961年の教科書にも記載されている。ファノの逆定理(Fano converse)またはファノの補題(Fano lemma)とも呼ばれる。

これは、任意の復号器の誤り確率の下限と、{{仮リンク|密度推定|en|density estimation}}におけるミニマックスリスクの下限を見つけるために使用される。

[[確率変数]] ''X'' と ''Y'' を、[[同時分布]] <math>P(x,y)</math> による入力・出力メッセージとする。''e'' を誤りの発生、すなわち、<math>\tilde{X}=f(Y)</math> を出力メッセージ ''Y'' から推定した入力メッセージ ''X'' としたとき、 <math>X\neq \tilde{X}</math> となることであるとする。すると、ファノの不等式は以下のように表される。

:<math>H(X|Y)\leq H(e)+P(e)\log(|\mathcal{X}|-1),</math>

ここで、<math>\mathcal{X}</math> は ''X'' のsupportを表し、

:<math>H\left(X|Y\right)=-\sum_{i,j} P(x_i,y_j)\log P\left(x_i|y_j\right)</math>

は{{仮リンク|条件付きエントロピー|en|conditional entropy}}、

:<math>P(e)=P(X\neq  \tilde{X})</math>

は通信誤りの確率、

:<math>H(e)=-P(e)\log P(e)-(1-P(e))\log(1-P(e))</math>

対応する[[二値エントロピー関数|二値エントロピー]]である。

==別の定式化==
''X'' を、 <math>r+1</math> 個の[[確率密度関数|確率密度]] <math>f_1,\ldots,f_{r+1}</math> の内の1つに等しい確率密度を持つ[[確率変数]]とする。さらに、密度の任意の対の[[カルバック・ライブラー情報量]]は大きすぎることはできない。

:<math> D_{KL}(f_i\|f_j)\leq \beta</math> （全ての <math>i\not = j</math> について）

<math>\psi(X)\in\{1,\ldots, r+1\}</math> をインデックスの推定とする。すると、ファノの不等式は以下のように表される。

:<math>\sup_i P_i(\psi(X)\not = i) \geq 1-\frac{\beta+\log 2}{\log r}</math>

ここで、<math>P_i</math> は <math>f_i</math> によって誘導される[[確率]]である。

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

'''F''' を、任意の ''&theta;''&nbsp;≠&nbsp;''&theta;''<nowiki>&prime;</nowiki> に対して、 ''r''&nbsp;+&nbsp;1 個の密度 ''&fnof;''<sub>''&theta;''</sub> のサブクラスを有する密度の[[クラス (集合論)|クラス]]とする。 

:<math>\|f_{\theta}-f_{\theta'}\|_{L_1}\geq \alpha,</math>
:<math>D_{KL}(f_\theta\|f_{\theta'})\leq \beta.</math>

最悪の場合、推定誤りの[[期待値]]は下から拘束され、 

:<math>\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)</math>

となる。ここで、''&fnof;''<sub>''n''</sub> は、サイズ ''n'' の[[標本 (統計学)|標本]]に基づく任意の{{仮リンク|密度推定|en|density estimation|label=密度推定器}}である。 

==脚注==
* P. Assouad, "Deux remarques sur l'estimation", ''Comptes Rendus de L'Academie des Sciences de Paris'', Vol. 296, pp.&nbsp;1021–1024, 1983.
* L. Birge, "Estimating a density under order restrictions: nonasymptotic minimax risk", Technical report, UER de Sciences Économiques, Universite Paris X, Nanterre, France, 1983.
* T. Cover, J. Thomas, ''Elements of Information Theory''. pp.&nbsp;43.
* L. Devroye, ''A Course in Density Estimation''. Progress in probability and statistics, Vol 14. Boston, Birkhauser, 1987. {{ISBN2|0-8176-3365-0}}, {{ISBN2|3-7643-3365-0}}.
* R. Fano, ''Transmission of information; a statistical theory of communications.'' Cambridge, Massachusetts, M.I.T. Press, 1961. {{ISBN2|0-262-06001-9}}
* R. Fano, ''[http://www.scholarpedia.org/article/Fano_inequality Fano inequality]'' [[Scholarpedia]], 2008.
* I. A. Ibragimov, R. Z. Has′minskii, ''Statistical estimation, asymptotic theory''. Applications of Mathematics, vol. 16, Springer-Verlag, New York, 1981. {{ISBN2|0-387-90523-5}}

{{デフォルトソート:ふあののふとうしき}}
[[Category:情報理論]]
[[Category:不等式]]
[[Category:数学に関する記事]]