La desigualdad de Fano

En teoría de la información , la desigualdad de Fano (también conocida como el recíproco de Fano o el lema de Fano ) relaciona la información promedio perdida en un canal ruidoso con la probabilidad del error de categorización. Fue derivada por Robert Fano a principios de la década de 1950 mientras impartía un seminario de doctorado en teoría de la información en el MIT , y posteriormente recogida en su libro de texto de 1961.

Se utiliza para encontrar un límite inferior para la probabilidad de error de cualquier decodificador, así como los límites inferiores para los riesgos minimax en la estimación de densidad .

Sean las variables aleatorias discretas${\displaystyle X}$y${\displaystyle Y}$representar mensajes de entrada y salida con una probabilidad conjunta${\displaystyle P(x,y)}$. Dejar${\displaystyle e}$representan una ocurrencia de error; es decir, que${\displaystyle X\neq {\tilde {X}}}$, con${\displaystyle {\tilde {X}}=f(Y)}$siendo una versión aproximada de${\displaystyle X}$La desigualdad de Fano es

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

dónde${\displaystyle {\mathcal {X}}}$denota el apoyo de${\displaystyle X}$,${\displaystyle |{\mathcal {X}}|}$denota la cardinalidad de (número de elementos en)${\displaystyle {\mathcal {X}}}$,

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

es la entropía condicional ,

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

es la probabilidad del error de comunicación, y

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

es la entropía binaria correspondiente .

Defina una variable aleatoria indicadora${\displaystyle E}$, que indica el evento que nuestra estimación${\displaystyle {\tilde {X}}=f(Y)}$está equivocado,

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

Considerar${\displaystyle H(E,X|{\tilde {X}})}$Podemos usar la regla de la cadena para las entropías para expandir esto de dos maneras diferentes.

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

Igualar los dos

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

Ampliando el término más a la derecha,${\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}}}$

Desde${\displaystyle E=0}$medio${\displaystyle X={\tilde {X}}}$; recibiendo el valor de${\displaystyle {\tilde {X}}}$nos permite conocer el valor de${\displaystyle X}$con certeza. Esto hace que el término${\displaystyle H(X\mid E=0,{\tilde {X}})=0}$. Por otro lado,${\displaystyle E=1}$significa que${\displaystyle {\tilde {X}}\neq X}$, por lo tanto, dado el valor de${\displaystyle {\tilde {X}}}$, podemos acotar${\displaystyle X}$a uno de${\displaystyle |{\mathcal {X}}|-1}$diferentes valores, lo que nos permite establecer un límite superior para la entropía condicional.${\displaystyle H(X\mid E=1,{\tilde {X}})\leq \log(|{\mathcal {X}}|-1)}$. Por eso

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

El otro término,${\displaystyle H(E\mid {\tilde {X}})\leq H(E)}$, porque el condicionamiento reduce la entropía. Debido a la forma${\displaystyle E}$se define,${\displaystyle H(E)=H_{b}(e)}$, lo que significa que${\displaystyle H(E\mid {\tilde {X}})\leq H_{b}(e)}$. Reuniéndolo todo,

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

Porque${\displaystyle X\rightarrow Y\rightarrow {\tilde {X}}}$es una cadena de Markov , tenemos${\displaystyle I(X;{\tilde {X}})\leq I(X;Y)}$por la desigualdad del procesamiento de datos y, por lo tanto,${\displaystyle H(X\mid {\tilde {X}})\geq H(X\mid Y)}$, dándonos

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

La desigualdad de Fano puede interpretarse como una forma de dividir la incertidumbre de una distribución condicional en dos preguntas dado un predictor arbitrario. La primera pregunta, correspondiente al término${\displaystyle H_{b}(e)}$, se relaciona con la incertidumbre del predictor. Si la predicción es correcta, no queda más incertidumbre. Si la predicción es incorrecta, la incertidumbre de cualquier distribución discreta tiene un límite superior de la entropía de la distribución uniforme sobre todas las opciones excepto la predicción incorrecta. Esto tiene entropía${\displaystyle \log(|{\mathcal {X}}|-1)}$En los casos extremos, si el predictor siempre es correcto, el primer y el segundo término de la desigualdad son 0, y la existencia de un predictor perfecto implica${\displaystyle X}$está totalmente determinado por${\displaystyle Y}$, y entonces${\displaystyle H(X|Y)=0}$. Si el predictor siempre es incorrecto, entonces el primer término es 0 y ${\displaystyle H(X\mid Y)}$Solo se puede establecer un límite superior con una distribución uniforme sobre las opciones restantes.

Dejar${\displaystyle X}$sea ​​una variable aleatoria con densidad igual a una de${\displaystyle r+1}$posibles densidades${\displaystyle f_{1},\ldots ,f_{r+1}}$Además, la divergencia de Kullback-Leibler entre cualquier par de densidades no puede ser demasiado grande.

${\displaystyle D_{KL}(f_{i}\parallel f_{j})\leq \beta }$a pesar de${\displaystyle i\not =j.}$

Dejar${\displaystyle \psi (X)\in \{1,\ldots ,r+1\}}$ser una estimación del índice. Entonces

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

dónde${\displaystyle P_{i}}$es la probabilidad inducida por${\displaystyle f_{i}}$.

La siguiente generalización se debe a Ibragimov y Khasminskii (1979), Assouad y Birge (1983).

Sea F una clase de densidades con una subclase de r  +  1 densidades ƒ _θ tales que para cualquier θ  ≠ θ ′ 

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

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

En el peor de los casos, el valor esperado del error de estimación está acotado inferiormente.

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

donde ƒ _n es cualquier estimador de densidad basado en una muestra de tamaño n .

• P. Assouad, "Deux remarques sur l'estimation", Comptes Rendus de l'Académie des Sciences de Paris , vol. 296, págs.  1021-1024, 1983.
• L. Birge, "Estimación de una densidad bajo restricciones de orden: riesgo minimax no asintótico", Informe técnico, UER de Sciences Économiques, Université Paris X, Nanterre, Francia, 1983.
• T. Cover, J. Thomas (1991). Elementos de la teoría de la información . págs. 38–42 . ISBN  978-0-471-06259-2.
• L. Devroye, Curso de estimación de densidad . Avances en probabilidad y estadística, vol. 14. Boston, Birkhauser, 1987. ISBN 0-8176-3365-0, ISBN 3-7643-3365-0.
• Fano, Robert (1968). Transmisión de información: una teoría estadística de las comunicaciones . Cambridge, Mass: MIT Press. ISBN 978-0-262-56169-3OCLC 804123877​​ 
  • también: Cambridge, Massachusetts, MIT Press, 1961. ISBN 0-262-06001-9
• R. Fano, Desigualdad de Fano , Scholarpedia , 2008.
• IA Ibragimov, RZ Has′minskii, Estimación estadística, teoría asintótica . Aplicaciones de las matemáticas, vol. 16, Springer-Verlag, Nueva York, 1981. ISBN 0-387-90523-5