ファノの不等式

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

これは、任意の復号器の誤り確率の下限と、密度推定（英語版）におけるミニマックスリスクの下限を見つけるために使用される。

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

H ( X | Y ) ≤ H ( e ) + P ( e ) log ⁡ ( | X | − 1 ) , {\displaystyle H(X|Y)\leq H(e)+P(e)\log(|{\mathcal {X}}|-1),}

ここで、 X {\displaystyle {\mathcal {X}}} は X のsupportを表し、

H ( X | Y ) = − ∑ i , j P ( x i , y j ) log ⁡ P ( x i | y j ) {\displaystyle H\left(X|Y\right)=-\sum _{i,j}P(x_{i},y_{j})\log P\left(x_{i}|y_{j}\right)}

は条件付きエントロピー（英語版）、

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

は通信誤りの確率、

H ( e ) = − P ( e ) log ⁡ P ( e ) − ( 1 − P ( e ) ) log ⁡ ( 1 − P ( e ) ) {\displaystyle H(e)=-P(e)\log P(e)-(1-P(e))\log(1-P(e))}

対応する二値エントロピーである。

別の定式化

X を、 r + 1 {\displaystyle r+1} 個の確率密度 f 1 , … , f r + 1 {\displaystyle f_{1},\ldots ,f_{r+1}} の内の1つに等しい確率密度を持つ確率変数とする。さらに、密度の任意の対のカルバック・ライブラー情報量は大きすぎることはできない。

D K L ( f i ‖ f j ) ≤ β {\displaystyle D_{KL}(f_{i}\|f_{j})\leq \beta } （全ての i ≠ j {\displaystyle i\not =j} について）

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

sup i P i ( ψ ( X ) ≠ i ) ≥ 1 − β + log ⁡ 2 log ⁡ r {\displaystyle \sup _{i}P_{i}(\psi (X)\not =i)\geq 1-{\frac {\beta +\log 2}{\log r}}}

ここで、 P i {\displaystyle P_{i}} は f i {\displaystyle f_{i}} によって誘導される確率である。

一般化

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

F を、任意の θ ≠ θ′ に対して、 r + 1 個の密度 ƒθ のサブクラスを有する密度のクラスとする。

‖ f θ − f θ ′ ‖ L 1 ≥ α , {\displaystyle \|f_{\theta }-f_{\theta '}\|_{L_{1}}\geq \alpha ,}
D K L ( f θ ‖ f θ ′ ) ≤ β . {\displaystyle D_{KL}(f_{\theta }\|f_{\theta '})\leq \beta .}

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

sup f ∈ F E ‖ f n − f ‖ L 1 ≥ α 2 ( 1 − n β + log ⁡ 2 log ⁡ r ) {\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'Academie des Sciences de Paris, Vol. 296, pp. 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. 43.
  • L. Devroye, A Course in Density Estimation. Progress in probability and statistics, Vol 14. Boston, Birkhauser, 1987. ISBN 0-8176-3365-0, ISBN 3-7643-3365-0.
  • R. Fano, Transmission of information; a statistical theory of communications. Cambridge, Massachusetts, M.I.T. Press, 1961. ISBN 0-262-06001-9
  • R. Fano, 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. ISBN 0-387-90523-5