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

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

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

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

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

где ${\mathcal {X}}$ означает поддержку $X$, $|{\mathcal {X}}|$ обозначает мощность (количество элементов в) ${\mathcal {X}}$,

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

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

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

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

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

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

Доказательство

Определить индикаторную случайную величину $E$, что указывает на то, что наша оценка ${\tilde {X}}=f(Y)$ находится в ошибке,

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

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

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

Приравнивание двух

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

Раскрывая правый самый член, $H(X|E,{\tilde {X}})$

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

С $E=0$ означает $X={\tilde {X}}$; придается значение ${\tilde {X}}$ позволяет нам узнать стоимость $X$ с уверенностью. Это делает термин $H(X|E=0,{\tilde {X}})=0$. С другой стороны, $E=1$ означает, что ${\tilde {X}}\neq X$, следовательно, учитывая значение ${\tilde {X}}$, мы можем сузить $X$ к одному из $|{\mathcal {X}}|-1$ разные значения, что позволяет нам определить верхнюю границу условной энтропии $H(X|E=1,{\tilde {X}})\leq \log(|{\mathcal {X}}|-1)$. Следовательно

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

Другой термин, $H(E|{\tilde {X}})\leq H(E)$, потому что кондиционирование уменьшает энтропию. Из-за способа $E$ определяется, $H(E)=H_{b}(e)$, это означает, что $H(E|{\tilde {X}})\leq H_{b}(e)$. Собрав все это вместе,

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

Потому что $X\rightarrow Y\rightarrow {\tilde {X}}$ является цепью Маркова, мы имеем $I(X;{\tilde {X}})\leq I(X;Y)$ неравенством обработки данных и, следовательно, $H(X|{\tilde {X}})\geq H(X|Y)$, давая нам

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

Интуиция

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

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

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

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

Позволять $\psi (X)\in \{1,\ldots ,r+1\}$ быть оценкой индекса. Затем

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

где $P_{i}$ вероятность , вызванная $f_{i}$

Обобщение

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

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

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

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

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

$\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.
• Л. Бирге, «Оценка плотности при ограничениях порядка: неасимптотический минимаксный риск», Технический отчет, EBU экономических наук, Университет Париж 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, Спрингер-Верлаг, Нью-Йорк, 1981 год. ISBN   0-387-90523-5