Кратко и по сути — про информационную энтропию Шеннона, её вычисление, смысл в битах и приложения в сжатии и ML.
Определение
- Для дискретной случайной величины $X$ с распределением $p(x_i)=\mathrm{Pr}(X=x_i)$ энтропия определяется как
$$H(X)=-\sum _{i}p(x_i){\log }_{2}p(x_i).$$ - Для последовательности символов вводят скорость (entropy rate): $H={\lim }_{n\to \infty }\frac{1}{n}H(X_1^n)$.
Интерпретация в битах
- Если логарифм по основанию 2, то единица измерения — бит. Энтропия $H(X)$ — среднее число бинарных (yes/no) вопросов, необходимых в оптимальной стратегии для идентификации исхода $X$.
- Границы: $0\le H(X)\le {\log }_{2}n$ (для $n$ возможных исходов). $H=0$ — полностью предсказуемо; $H={\log }_{2}n$ — равновероятно (максимальная неопределённость).
Простой числовой пример
- Для «смещённой монеты» с $p(\text{орёл})=0.7$ и $p(\text{решка})=0.3$:
$$H=-0.7{\log }_{2}0.7-0.3{\log }_{2}0.3\approx 0.881\text{бит}.$$
Связь с кодированием и сжатием
- Теорема источника (Shannon): средняя длина любого префиксного (без ambig.) кода $L$ удовлетворяет
$$H(X)\le L<H(X)+1$$ (для целочисленных дли кода; арифметическое кодирование может приближать $H(X)$ сколь угодно близко).
- Следствие: $H(X)$ — теоретический минимум среднего числа бит на символ для безусловно безошибочного сжатия при известных статистиках источника.
- Практика: Huffman даёт оптимальный целочисленный код, арифметическое/асимпт. коды — более плотное приближение; если модель неверна, средняя длина равна кросс-энтропии $H(P,Q)$ (см. ниже).
Кросс-энропия и дивергенция
- Кросс-энтропия и KL-дивергенция:
$$H(P,Q)=-\sum _{x}p(x){\log }_{2}q(x),D_{KL}(P\Vert Q)=\sum _{x}p(x){\log }_2\frac{p(x)}{q(x)}.$$ - $H(P,Q)=H(P)+D_{KL}(P\Vert Q)$. Используется как мера «потерь» при кодировании/моделировании с неверной моделью.
Применение в ML: информативность признаков и структуры моделей
- Информационный выигрыш для выбора разбиения (decision trees):
$$\text{IG}(Y;X)=H(Y)-H(Y\mid X)$$ (разница энтропий родителя и взвешенной суммы энтропий детей). Чем больше IG — тем более информативен признак относительно целевой метки.
- Взаимная информация для отбора признаков: $I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X)$. Показывает, сколько информации об одном даёт другой.
- Кросс-энтропия как функция потерь: в классификации модель минимизирует среднюю кросс-энтропию, что эквивалентно максимизации правдоподобия.
- Предупреждения: оценка энтропии и взаимной информации по конечной выборке имеет смещение; для непрерывных признаков стандартная «дифференциальная энтропия» не полностью аналогична дискретной и зависит от шкалы — часто требуется дискретизация или непараметрические оценители (k-NN, KDE).
Короткое резюме
- Энтропия Шеннона измеряет среднюю неопределённость/информацию одного символа в битах.
- Она даёт теоретический минимум бит для безошибочного сжатия и служит базой для алгоритмов (Huffman, арифметическое кодирование).
- В ML используется для оценки информативности признаков (information gain, mutual information) и в качестве критерия/функции потерь (кросс-энтропия), но требует аккуратной оценки на данных.