Неравенство фаноса - Википедия - Fanos inequality

В теория информации, Неравенство Фано (также известный как Фано-конверс и Лемма Фано) связывает среднее значение информации, потерянной в канале с шумом, с вероятностью ошибки категоризации. Это было получено Роберт Фано в начале 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 (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} верно)}

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

{ Displaystyle Р (е) = Р (Икс neq { тильда {X}})}

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

{ Displaystyle Н (е) = - P (e) журнал P (e) - (1-P (e)) log (1-P (e))}

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

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

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

{ Displaystyle D_ {KL} (е_ {я} | е_ {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 быть классом плотностей с подклассом р + 1 плотности ƒ_θ такой, что для любого θ ≠ θ′

{ Displaystyle | е _ { theta} -f _ { theta '} | _ {L_ {1}} geq alpha,}

{ displaystyle D_ {KL} (f _ { theta} | f _ { theta '}) leq beta.}

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

{ displaystyle sup _ {е in mathbf {F}} E | f_ {n} -f | _ {L_ {1}} geq { frac { alpha} {2}} left ( 1 - { frac {n beta + log 2} { log r}} right)}

куда ƒ_п есть ли оценщик плотности на основе образец размера п.

Неравенство фаноса - Википедия - Fanos inequality

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

Обобщение

Рекомендации