Неравенство Фано

В теории информации неравенство Фано (также известное как обратное уравнение Фано и лемма Фано ) связывает среднюю потерю информации в шумном канале с вероятностью ошибки категоризации. Оно было выведено Робертом Фано в начале 1950-х годов во время преподавания на семинаре по теории информации в Массачусетском технологическом институте и позднее записано в его учебнике 1961 года.

Он используется для нахождения нижней границы вероятности ошибки любого декодера, а также нижних границ минимаксных рисков при оценке плотности .

Пусть дискретные случайные величины и представляют входные и выходные сообщения с совместной вероятностью . Пусть представляют возникновение ошибки; т.е., что , причем является приближенной версией . Неравенство Фано имеет вид${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle P(x,y)}$${\displaystyle е}$${\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),}$

где обозначает поддержку , обозначает мощность (количество элементов в) ,${\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)}$

- условная энтропия ,

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

вероятность ошибки связи, и

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

— соответствующая бинарная энтропия .

Определим индикаторную случайную величину , которая указывает на событие, когда наша оценка ошибочна,${\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}}}$

Рассмотрим . Мы можем использовать цепное правило для энтропий, чтобы расширить это двумя разными способами${\displaystyle H(E,X|{\tilde {X}})}$

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

Приравнивая эти два

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

Расширяя самый правый термин,${\displaystyle H(X|E,{\tilde {X}})}$

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

Так как означает ; , имея значение , мы можем точно знать значение . Это делает термин . С другой стороны, означает, что , следовательно, имея значение , мы можем сузить круг до одного из различных значений, что позволяет нам ограничить сверху условную энтропию . Следовательно${\displaystyle E=0}$${\displaystyle X={\тильда {X}}}$${\displaystyle {\тильда {X}}}$${\displaystyle X}$${\displaystyle H(X|E=0,{\tilde {X}})=0}$${\displaystyle E=1}$${\displaystyle {\tilde {X}}\neq X}$${\displaystyle {\тильда {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)}$

Другой термин, , потому что обусловливание уменьшает энтропию. Из-за способа определяется, , что означает, что . Собирая все вместе,${\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)}$

Поскольку — цепь Маркова, то по неравенству обработки данных имеем , и, следовательно , , что дает нам${\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)}$

Неравенство Фано можно интерпретировать как способ разделения неопределенности условного распределения на два вопроса при наличии произвольного предиктора. Первый вопрос, соответствующий термину , относится к неопределенности предиктора. Если прогноз верен, то неопределенности больше не остается. Если прогноз неверен, то неопределенность любого дискретного распределения имеет верхнюю границу энтропии равномерного распределения по всем выборам, кроме неверного прогноза. Это имеет энтропию . Рассматривая крайние случаи, если предиктор всегда верен, первый и второй члены неравенства равны 0, и существование идеального предиктора подразумевает, что полностью определяется , и поэтому . Если предиктор всегда неверен, то первый член равен 0 и может быть ограничен сверху только равномерным распределением по оставшимся выборам.${\displaystyle H_{b}(e)}$${\displaystyle \log(|{\mathcal {X}}|-1)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle H(X|Y)=0}$${\displaystyle H(X|Y)}$

Пусть будет случайной величиной с плотностью, равной одной из возможных плотностей . Более того, расхождение Кульбака–Лейблера между любой парой плотностей не может быть слишком большим,${\displaystyle X}$${\displaystyle r+1}$${\displaystyle f_{1},\ldots ,f_{r+1}}$

${\displaystyle D_{KL}(f_{i}\|f_{j})\leq \beta }$для всех${\displaystyle i\not =j.}$

Пусть будет оценкой индекса. Тогда${\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}}}$

где — вероятность, индуцированная .${\displaystyle P_{i}}$${\displaystyle f_{i}}$

Следующее обобщение принадлежит Ибрагимову и Хасминскому (1979), Ассуаду и Бирге (1983).

Пусть F — класс плотностей с подклассом из r  + 1 плотностей ƒ _θ, таких что для любого θ  ≠  θ ′

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

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

Тогда в худшем случае ожидаемое значение погрешности оценки ограничено снизу,

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

• П. Ассуад, «Два замечания по оценке», Comptes Rendus de l'Académie des Sciences de Paris , Vol. 296, стр. 1021–1024, 1983.
• Л. Бирге, «Оценка плотности при ограничениях порядка: неасимптотический минимаксный риск», Технический отчет, UER de Sciences Économiques, Universite Paris X, Нантер, Франция, 1983.
• T. Cover, J. Thomas (1991). Элементы теории информации. стр. 38–42. ISBN 978-0-471-06259-2.
• Л. Деврой, Курс оценки плотности . Прогресс в теории вероятности и статистики, т. 14. Бостон, Биркхаузер, 1987. ISBN 0-8176-3365-0 , ISBN 3-7643-3365-0 .  
• Фано, Роберт (1968). Передача информации: статистическая теория коммуникаций. Кембридж, Массачусетс: MIT Press. ISBN 978-0-262-56169-3. OCLC  804123877.
  • также: Кембридж, Массачусетс, MIT Press, 1961. ISBN 0-262-06001-9. 
• Р. Фано, Неравенство Фано Scholarpedia , 2008.
• И. А. Ибрагимов, Р. З. Хасьминский, Статистическое оценивание, асимптотическая теория . Приложения математики, т. 16, Springer-Verlag, Нью-Йорк, 1981. ISBN 0-387-90523-5