法諾不等式

法諾不等式（Fano's inequality）也稱為法諾引理（Fano lemma）是信息論中的一個定理，說明噪音信道中的平均信息損失和錯誤分類概率之間的關係。法諾不等式是羅伯特·法諾是1950年代於麻省理工學院教授博士討論班的時候推導的，後來放在1961年編寫的教科書中。

法諾不等式在信息論中，提供了解碼器錯誤概率的下界。在統計學中，提供了密度估計（英語：Density_estimation）時極小化極大風險（英語：minimax risks）的下界。

用符號 ${\displaystyle H(\cdot )}$表示熵， ${\displaystyle H(X|Y)}$ 表示隨機變量X與Y之間的條件熵，${\displaystyle {\tilde {X}}}$表示對於X的分類，e表示分類錯誤的事件（${\displaystyle e=\{X\neq {\tilde {X}}\}}$），法諾不等式是說

${\displaystyle H(X|Y)\leq H(e)+P(e)\log(|{\text{supp}}(X)|-1)}$

這裡 ${\displaystyle {\text{supp}}(X)}$ 是X可能取值（有限個）的集合。

參考資料

• P. Assouad, "Deux remarques sur l'estimation", Comptes Rendus de l'Académie 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 (PDF). 1991: 38–42 [2019-03-30]. ISBN 978-0-471-06259-2. （原始內容存檔 (PDF)於2020-11-12）.
• 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.
• Fano, Robert. Transmission of information: a statistical theory of communications. Cambridge, Mass: MIT Press. 1968. ISBN 978-0-262-56169-3. OCLC 804123877.
  • also: 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