Введение

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

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

– вероятность ошибки передачи, а

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

Интуиция

Неравенство Фано можно интерпретировать как способ разделения неопределенности условного распределения на два вопроса, задаваемых произвольным предиктором. Первый вопрос, соответствующий члену , относится к неопределенности, связанной с самим предиктором. Если предсказание верно, то дальнейшая неопределенность отсутствует. Если предсказание неверно, то неопределенность любого дискретного распределения ограничена сверху энтропией равномерного распределения по всем возможным вариантам, исключая неверное предсказание. Эта энтропия равна… Рассматривая крайние случаи, если предиктор всегда верен, то первый и второй члены неравенства равны 0, и существование идеального предиктора означает, что полностью определяется , а следовательно, и . Если же предиктор всегда ошибается, то первый член равен 0, и можно ограничить только сверху, используя равномерное распределение по оставшимся вариантам.