Информатика / Кодирование информации

Неравенство Фано: связь ошибки и условной энтропии

Неравенство Фано сверху оценивает условную энтропию дискретного X через вероятность ошибки декодера X-hat=g(Y). Оно формализует: если X почти удаётся восстановить из наблюдения Y, неопределённость H(X|Y) не может быть большой.

Опубликовано: 3 ноября 2026 г.Обновлено: 3 ноября 2026 г.

Формула

H(X|Y)\le h_2(P_e)+P_e\log_2(|\mathcal X|-1)

Схема Граница Фано для четырёх классов

Кривая ограничивает условную энтропию; равенство для произвольного классификатора не обещается.

Обозначения

X, Y: дискретный исходный символ и наблюдение, безразмерные случайные величины
$X-hat=g(Y), P_e$: декодер и вероятность его ошибки, P_e безразмерна, 0≤P_e≤1
$h_2, |X|$: двоичная энтропия и мощность конечного алфавита X, h_2 измеряется в битах при log_2

Условия применения

Пусть X имеет конечный алфавит размера M=|X|≥2, Y — наблюдение, а X-hat=g(Y) — явно выбранный декодер. Тогда для P_e=P[X-hat≠X] верно H(X|Y)≤h_2(P_e)+P_e log_2(M−1). Логарифмы берут по основанию 2, поэтому результат измеряется в битах. Для непрерывного X или иной меры ошибки нужна другая версия неравенства.

Ограничения

Это верхняя оценка условной энтропии, а не формула для P_e и не равенство в общем случае. Она зависит от выбранного декодера: замена g меняет P_e. При M=2 добавка log_2(M−1) равна нулю; при больших алфавитах граница может быть неточной. Нельзя механически переносить дискретную запись на непрерывные параметры.

Подробное объяснение

Если декодер ошибся, после Y остаётся вопрос, какой из остальных M−1 символов был истинным. Если он не ошибся, X определён. Разделение этих двух событий даёт двоичную энтропию самого индикатора ошибки и добавку P_e log_2(M−1).

При M=2 неверная альтернатива ровно одна, поэтому log_2(1)=0. Это не означает, что неопределённость исчезла: её учитывает h_2(P_e). При четырёх классах ошибка оставляет до трёх альтернатив, и появляется добавка P_e log_2(3).

Направление неравенства принципиально. Небольшая вероятность ошибки ограничивает H(X|Y) сверху, а для нижних границ ошибки неравенство обычно преобразуют вместе с другими известными величинами, например взаимной информацией.

Формула не требует равновероятных классов, но требует конечного алфавита и указанного декодера. В прикладной задаче сначала надо определить, что считается ошибкой, а затем уже подставлять P_e. Выбор единицы логарифма нельзя менять внутри вычисления: при натуральном логарифме ответ был бы в натах, а не в битах.

Как пользоваться формулой

Задайте конечный алфавит X и наблюдение Y, указав его размер M≥2 и основание логарифма для энтропии.
Выберите декодер X-hat=g(Y), определите событие X-hat≠X и фиксируйте правило выбора при равенстве оценок.
Найдите или оцените P_e для именно этого декодера, не подменяя её ошибкой другого классификатора.
Вычислите h_2(P_e) и P_e log_2(M−1) в одной системе логарифмов и сложите оба слагаемых.
Запишите полученную верхнюю границу H(X|Y) в битах, не превращая её в равенство.

Историческая справка

Роберт Фано развивал связь между вероятностью ошибки и информацией в работах по передаче сообщений середины XX века. Неравенство вошло в стандартный аппарат теории информации, потому что связывает задачу восстановления с условной энтропией без задания конкретного канала. Позднее оно стало обычным инструментом нижних границ в статистике, распознавании и кодировании. Исторический контекст здесь — шенноновская программа перевести надёжность передачи в измеримые информационные величины. Неравенство удобно тем, что отделяет неопределённость самого события ошибки от числа возможных неверных символов. В дальнейшем оно стало использоваться не только для каналов связи: через связь H(X|Y)=H(X)−I(X;Y) оно позволяет доказывать, что ограниченный объём наблюдений не может обеспечить произвольно точное восстановление скрытого дискретного параметра.

Историческая линия формулы

Неравенство названо по Роберту Фано; его монография «Transmission of Information» (1961) — один из классических источников этой традиции. Атрибуция не означает, что вся современная теория границ классификации принадлежит одному автору.

Пример

Для четырёх равновероятных классов и ошибки P_e=0,1: h₂(0,1)≈0,468996, добавка 0,1log₂3≈0,158496, итого H(X|Y)≤0,627492 бита. При P_e=0,1 двоичная часть равна 0,468996. Для четырёх классов остаётся три неверные альтернативы, поэтому добавка 0,1log₂3≈0,158496; сумма 0,627492. Для двух классов log₂(2−1)=0, а не один, что служит точной проверкой формулы. Неравенство Фано использует вероятность ошибки P_e декодера, чтобы сверху ограничить неопределённость H(X|Y). Чем надёжнее восстановление X по Y, тем меньше допустимая условная энтропия.

Частая ошибка

Не подставляйте M вместо M−1. Не оставляйте log_2 2 в двоичном случае: здесь стоит log_2 1=0. Не называйте границу двусторонней оценкой ошибки. Не используйте запись без заданных алфавита, декодера и P_e. Не смешивайте биты с натами при выборе основания логарифма.

Практика

Задачи с решением

Двоичный частный случай Фано

Условие. Упростите границу Фано для |X|=2.

Решение. log₂(|X|−1)=log₂1=0, поэтому остаётся H(X|Y)≤h₂(P_e).

Ответ. Граница равна h₂(P_e).

Нулевая ошибка и условная энтропия

Условие. Проверьте P_e=0 при |X|=4.

Решение. h₂(0)=0 и 0·log₂3=0; правая часть равна нулю.

Ответ. H(X|Y)≤0.

Дополнительные источники

https://ocw.mit.edu/courses/6-441-information-theory-spring-2016/5d8f16adc3385c9ff2975b121bd620e4_MIT6_441S16_course_notes.pdf
https://ocw.mit.edu/courses/6-050j-information-and-entropy-spring-2008/80c7258fd6bc5780797975eabb6fd747_MIT6_050JS08_textbook.pdf
https://mitpress.mit.edu/9780262561693/transmission-of-information/

Связанные формулы

Информатика

Функция скорость—искажение для гауссовского источника

$R(D)=\max\left\{0,\frac12\log_2\frac{\sigma^2}{D}\right\},\quad D>0$

Для независимого гауссовского источника с дисперсией sigma² и средней квадратичной ошибкой D функция скорость—искажение задаёт минимальную асимптотическую скорость кодирования: R(D)=max{0, 1/2 log_2(sigma²/D)} бит на отсчёт.

Информатика

Энтропия Шеннона: средняя информация дискретного источника

$H(X)=-\sum_{i=1}^{m}p_i\log_2p_i$

Энтропия Шеннона измеряет среднюю неопределённость исхода по его вероятностям. При двоичном логарифме результат выражают в битах на символ; редкие и частые символы вносят разный вклад.

Информатика

Информационный объем сообщения по мощности алфавита

$I=K\cdot \lceil\log_2 q\rceil$

Информационный объем сообщения по мощности алфавита: формула I=K\cdot \lceil\log_2 q\rceil помогает величины I, K, q заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.