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

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

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

Пусть случайные величины и представляют входные и выходные сообщения с совместной вероятностью . Позвольте представить возникновение ошибки; то есть, с приблизительной версией . Неравенство Фано${\ displaystyle X}$${\ displaystyle Y}$ ${\ Displaystyle Р (х, у)}$${\ displaystyle e}$${\ displaystyle X \ neq {\ tilde {X}}}$${\ Displaystyle {\ тильда {X}} = е (Y)}$${\ displaystyle X}$

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

где обозначает носитель ,${\displaystyle {\mathcal {X}}}$${\displaystyle 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{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}}}$

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

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

Расширяя самый правый термин, ${\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}}}$

Так как означает ; получение значения позволяет нам с уверенностью узнать значение . Это делает термин . С другой стороны, это означает, что , таким образом, учитывая значение , мы можем сузиться до одного из различных значений, что позволяет нам ограничить верхнюю границу условной энтропии . Следовательно${\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)}$

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

Альтернативная формулировка

Пусть - случайная величина с плотностью, равной одной из возможных плотностей . Кроме того, расхождение Кульбака – Лейблера между любой парой плотностей не может быть слишком большим,${\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 .

использованная литература

• П. Ассуад, "Deux remarques sur l'estimation", Comptes Rendus de l'Académie des Sciences de Paris , Vol. 296. С. 1021–1024, 1983.
• Л. Бирж, "Оценка плотности при ограничениях порядка: неасимптотический минимаксный риск", Технический отчет, UER de Sciences Économiques, Universite Paris X, Нантер, Франция, 1983.
• Т. Кавер, Дж. Томас (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