Энтропия в теории информации — мера неопределённости (средней «информации») случайной величины. Формально для дискретного распределения $P(X=x)=p(x)$ энтропия определяется как
$$H(X)=-\sum _{x}p(x)\log p(x),$$ где логарифм обычно берут по основанию $2$ (единицы — биты). Элементарная интерпретация: каждая реализация $x$ приносит «удивление» или самоинформацию $-\log p(x)$, и $H(X)$ — её математическое ожидание.
Связь с кодированием сообщений
- Самоинформация $-\log p(x)$ задаёт идеальную (необязательно целочисленную) длину кода для символа $x$. Средняя длина кода должна приблизительно равняться энтропии.
- Теорема источника (Шеннона): для независимых повторений источника средняя длина любого префиксного кода $L$ удовлетворяет
$$L\ge H(X),$$ и существует код с $L<H(X)+1$. То есть $H(X)$ — фундаментальный нижний предел сжатия на символ.
- Практические кодировщики: Huffman даёт оптимальный целочисленный префиксный код (минимизирует среднюю длину), арифметическое кодирование и range coding приближают предел $H(X)$ очень близко за счёт дробных длин в блоках.
Связь с вероятностной оценкой моделей
- Кросс-энтропия между истинным распределением $p$ и моделью $q$:
$$H(p,q)=-\sum _{x}p(x)\log q(x).$$ Минимизация кросс-энтропии эквивалентна максимизации правдоподобия и означает уменьшение ожидаемого количества бит, нужных при кодировании последовательностей, если использовать модель $q$.
- Разница между кросс-энтропией и энтропией — дивергенция Кульбака–Лейблера:
$$D_{KL}(p\Vert q)=\sum _{x}p(x)\log \frac{p(x)}{q(x)}=H(p,q)-H(p)\ge 0.$$ Это количество дополнительных бит в среднем, которые потребуются из-за использования неправильной модели $q$.
- Практически: при обучении probabilistic models (нейросети, language models) минимизация кросс-энтропии/логлоссов эквивалентна приближению к истинному распределению и снижению предполагаемой средней длины кодирования.
Практические задачи сжатия данных
- Энтропия даёт теоретическую границу сжатия: нельзя в среднем сжать данные ниже $H$ бит/символ без потерь (для независимых, стационарных источников).
- Реальные алгоритмы (Huffman, арифметика, LZ77/78, PPM) стараются приближаться к этой границе; универсальные алгоритмы (Lempel–Ziv) асимптотически достигают энтропии для широкого класса источников (стационарных эргодичных).
- Разность между средней длиной практического кода и энтропией называется избыточностью; она возникает из-за целочисленности кодовых слов, конечной длины блоков, неверной модели и служебной информации.
Пример вычисления энтропии
Пусть дискретная случайная величина принимает 4 символа с вероятностями
$$p(A)=0.5,p(B)=0.25,p(C)=0.125,p(D)=\mathrm{0.125.}$$ Энтропия:
$$H=-(0.5{\log }_{2}0.5+0.25{\log }_{2}0.25+0.125{\log }_{2}0.125+0.125{\log }_{2}0.125).$$ Поскольку ${\log }_{2}0.5=-1,{\log }_{2}0.25=-2,{\log }_{2}0.125=-3$, получаем
$$H=-(0.5(-1)+0.25(-2)+0.125(-3)+0.125(-3))=0.5+0.5+0.375+0.375=1.75\text{бит}.$$
Смысл результата: в среднем нужно как минимум $1.75$ бит для кодирования одного символа источника при известном распределении. Можно построить префиксный код с длинами $\{1,2,3,3\}$ (например, A:0, B:10, C:110, D:111), средняя длина которого равна
$$0.5\cdot 1+0.25\cdot 2+0.125\cdot 3+0.125\cdot 3=1.75,$$ то есть достигает энтропии (в этом примере целые длины совпадают с оптимумом). Если бы модель ошибалась (использовали $q$ вместо $p$), то средняя длина возросла бы на $D_{KL}(p\Vert q)$ бит/символ.
Короткие дополнительные замечания
- Энтропия ноль для детерминированного источника, максимальна при равномерном распределении: для $n$ символов максимум $={\log }_{2}n$.
- Для последовательностей действует правило цепочки: $H(X,Y)=H(X)+H(Y|X)$.
- Для непрерывных величин вводят дифференциальную энтропию, но она не является строгим эквивалентом дискретной по свойствам и интерпретации.
Если нужно, могу показать пример кода (Huffman или арифметика) для данного распределения или вычислить кросс-энтропию/ KL для заданной модели.