Shannon-энтропия — мера неопределённости распределения случайной величины X. Формально:
$$H(X)=-\sum _{x}p(x){\log }_{2}p(x),$$ где логарифм по базе 2 даёт единицы в битах. Интерпретация: среднее количество “бит сюрприза” при наблюдении значения X или нижняя граница для ожидаемой длины без­потерьного кода (теорема кодирования Шеннона).
Взаимная информация — мера зависимости между двумя случайными величинами X и Y; показывает, насколько знание Y уменьшает неопределённость X:
$$I(X;Y)=\sum _{x,y}p(x,y){\log }_2\frac{p(x,y)}{p(x)p(y)}.$$ Эквивалентные выражения:
$$I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X),$$ интерпретация: количество бит неопределённости X, устранённое знанием Y.
Применения:
- Сжатие: энтропия даёт нижнюю границу средней длины кода. Практические алгоритмы (Huffman, арифметическое кодирование) приближают среднюю длину к $H(X)$. Теорема: при блочном кодировании можно приблизить среднюю длину к $H(X)$ сколь угодно близко.
- Отбор признаков: взаимная информация $I(\text{признак};\text{метка})$ используется для оценки информативности признака относительно целевой переменной — признаки с большим $I$ обычно полезнее; популярные методы: отбор по взаимной информации, mRMR (максимизировать релевантность, минимизировать избыточность).
Вычисление энтропии для распределения $\{0.5,0.3,0.2\}$ (в битах):
$$H=-(0.5{\log }_{2}0.5+0.3{\log }_{2}0.3+0.2{\log }_{2}0.2)=0.5+0.3\cdot 1.7369656+0.2\cdot 2.3219281\approx 1.485\text{бит}.$$ Интерпретация результата: в среднем для кодирования одного значения этого распределения без потерь требуется примерно $1.485$ бита информации. Это минимально достижимая средняя длина кода при оптимальном (приближающем) сжатии; максимум для трёх равновероятных исходов был бы ${\log }_{2}3\approx 1.585$ бит, значит распределение немного менее неопределённо, чем равномерное.