Desigualdad de Fano

Desigualdad aplicada a variables aleatorias

En teoría de la información , la desigualdad de Fano (también conocida como inverso de Fano y 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 sobre teoría de la información en el MIT y luego registrada en su libro de texto de 1961.

Se utiliza para encontrar un límite inferior en 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 y representen mensajes de entrada y salida con una probabilidad conjunta . Sea que represente una ocurrencia de error; es decir, que , con siendo una versión aproximada de . La desigualdad de Fano es ${\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|Y)\leq H_{b}(e)+P(e)\log(|{\mathcal {X}}|-1),}$

donde denota el soporte de , denota la cardinalidad de (número de elementos en) , ${\displaystyle {\mathcal {X}}}$ ${\displaystyle X}$ ${\displaystyle |{\mathcal {X}}|}$ ${\displaystyle {\mathcal {X}}}$

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

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 .

Prueba

Defina una variable aleatoria indicadora , que indique el evento de que nuestra estimación sea errónea. ${\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}}}$

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

${\displaystyle {\begin{aligned}H(E,X|{\tilde {X}})&=H(X|{\tilde {X}})+\underbrace {H(E|X,{\tilde {X}})} _{=0}\\&=H(E|{\tilde {X}})+H(X|E,{\tilde {X}})\end{aligned}}}$

Equiparando los dos

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

Ampliando el término más a la derecha, ${\displaystyle H(X|E,{\tilde {X}})}$

${\displaystyle {\begin{aligned}H(X|E,{\tilde {X}})&=\underbrace {H(X|E=0,{\tilde {X}})} _{=0}\cdot P(E=0)+H(X|E=1,{\tilde {X}})\cdot \underbrace {P(E=1)} _{=P(e)}\\&=H(X|E=1,{\tilde {X}})\cdot P(e)\end{aligned}}}$

Dado que significa ; al tener el valor de , podemos saber el valor de con certeza. Esto hace que el término . Por otro lado, significa que , por lo tanto, dado el valor de , podemos reducirlo a uno de diferentes valores, lo que nos permite limitar superiormente la entropía condicional . Por lo tanto ${\displaystyle E=0}$ ${\displaystyle X={\tilde {X}}}$ ${\displaystyle {\tilde {X}}}$ ${\displaystyle X}$ ${\displaystyle H(X|E=0,{\tilde {X}})=0}$ ${\displaystyle E=1}$ ${\displaystyle {\tilde {X}}\neq X}$ ${\displaystyle {\tilde {X}}}$ ${\displaystyle X}$ ${\displaystyle |{\mathcal {X}}|-1}$ ${\displaystyle H(X|E=1,{\tilde {X}})\leq \log(|{\mathcal {X}}|-1)}$

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

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

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

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

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

Intuición

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 , 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 además de la predicción incorrecta. Esto tiene entropía . Mirando los casos extremos, si el predictor siempre es correcto, el primer y segundo término de la desigualdad son 0, y la existencia de un predictor perfecto implica está totalmente determinada por , y por lo tanto . Si el predictor siempre es incorrecto, entonces el primer término es 0, y solo puede ser acotado superiormente con una distribución uniforme sobre las opciones restantes. ${\displaystyle H_{b}(e)}$ ${\displaystyle \log(|{\mathcal {X}}|-1)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H(X|Y)=0}$ ${\displaystyle H(X|Y)}$

Formulación alternativa

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

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

Sea una estimación del índice. Entonces ${\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}}}$

¿Dónde está la probabilidad inducida por ? ${\displaystyle P_{i}}$ ${\displaystyle f_{i}}$

Generalización

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 }\|f_{\theta '})\leq \beta .}$

Entonces, en el peor de los casos, el valor esperado del error de estimación está limitado desde abajo,

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

Referencias

• 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, Un curso sobre estimación de densidad . Progreso 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-3.OCLC 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