Как определяется энтропия дискретных случайных величин

Энтропия случайного источника

Рассмотрим схему [math]\mathcal_m[/math] c [math]m[/math] исходами и вероятностями [math]\[/math] и схему [math]\mathcal_k[/math] с [math]k[/math] исходами и вероятностями [math]\[/math] .

Образуем комбинированную схему c [math]m + k — 1[/math] исходами следующим образом:

Выбирается случайным образом один из исходов схемы [math]\mathcal_m[/math] , и если произошел [math]m[/math] -й исход, выбирается случайно один из исходов схемы [math]\mathcal_k[/math] , а остальные [math]m — 1[/math] исходов схемы [math]\mathcal_m[/math] считаются окончательными.

В этой комбинированной схеме [math]\mathcal[/math] мы получаем исходы [math]1, 2, \dots, m — 1, (m, 1), (m, 2), \dots, (m, k)[/math] с вероятностями [math]p_1, p_2, \dots, p_, p_mq_1, p_mq_2, \dots, p_mq_k[/math]

Легко видеть, что [math]H(\mathcal) = H(\mathcal_m) + p_mH(\mathcal_k)[/math] .

Потребуем выполнения этого свойства для любой меры неопределенности. [math]\lhd[/math]

Вычисление энтропии

Для доказательства формулы вычисления энтропии сначала докажем лемму.

[math]g(n) = H(\dfrac<1>, \dfrac<1>, \dots, \dfrac<1>) = -k \log_2 \dfrac<1> = k \log_2n[/math]

Будем рассматривать для [math]k=1[/math] (бит).

Рассмотрим функцию [math]g(mn)[/math] :

[math]g(mn)=g(m)+ \sum\limits_^ \dfrac g(n) = g(m)+g(n)[/math]

Пусть: [math]g(2)=1 \quad[/math] , тогда [math]g(2^t)=t[/math] и [math] \quad g(n^t)=t \cdot g(n)[/math]

Рассмотрим такое [math] i [/math] , что [math]2^i \leqslant n^t \lt 2^[/math]

Можно заметить, что если [math] i=[ \log_2 n^t ] [/math] , то неравенство останется верным.

По предыдущим рассуждениям получаем, что:

[math]g(2^i) \leqslant g(n^t) \lt g(2^)[/math] [math] i \leqslant t \cdot g(n) \lt i+1 \quad \quad [/math]

Делим неравенство на [math]t[/math] :

[math]H(p_1, p_2, \dots, p_n) = -k \sum\limits_^ p_i\log_2p_i = k \sum\limits_^ p_i\log_2\dfrac[/math]

Теперь рассмотрим функцию [math]H(\dfrac, \dfrac, \dots, \dfrac)[/math]

Приведем дроби внутри функции к одному знаменателю, получаем: [math] H(\dfrac, \dfrac, \dots, \dfrac) = H(\dfrac, \dfrac, \dots, \dfrac)[/math]

Далее по свойству энтропии и доказанной лемме:

Примеры

Энтропия честной монеты

Рассмотрим вероятностное пространство — честная монета. Найдем для нее энтропию:

[math]H(X) = -\sum\limits_^ p_i \log_2p_i = -\sum\limits_^ \cdot \log_2 \dfrac> = -\sum\limits_^ \cdot (-1)> = 1[/math]

Это означает что после броска честной монеты мы получим информацию в размере [math]1[/math] бит, уменьшив степень неопределенности вдвое.

Энтропия нечестной монеты

[math]H(X) = -\sum\limits_^ p_i \log_2p_i = -0.2\log_2(0.2)-0.8\log_2(0.8) \approx 0.722 \lt 1 [/math]

Ограниченность энтропии

[math]0 \leqslant H(p_1, p_2, \dots, p_n) \leqslant \log_2n [/math]

1) Докажем первую часть неравенства:

Так как [math] p_i\in[0,\;1][/math] , тогда [math]\log_2\dfrac \geqslant 0 [/math] . Таким образом [math] H(p_1, p_2, \dots, p_n) = \sum\limits_^ p_i\log_2 \dfrac \geqslant 0 [/math]

2) Докажем вторую часть неравенства:

[math] f(x)=\log_2x [/math] — выпуклая вверх функция, [math] p_1,p_2,\ldots,p_n\gt 0[/math] и [math] \sum \limits_^ p_i = 1 [/math] , тогда для нее выполняется неравенство Йенсена: [math] \sum\limits_^ p_i f(\dfrac) \leqslant f(\sum\limits_^ (p_i \cdot\dfrac)) [/math]

Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.

Условная и взаимная энтропия

Определение:

Условная энтропия (англ. conditional entropy) — определяет количество остающейся энтропии (то есть, остающейся неопределенности) события [math]A[/math] после того, как становится известным результат события [math]B[/math] . Она называется энтропия [math]A[/math] при условии [math]B[/math] , и обозначается [math]H(A|B)[/math]

[math]H(A|B)= — \sum\limits_^p(b_i)\sum\limits_^ p(a_j|b_i)\log_2p(a_j|b_i) [/math]

Определение:

Взаимная энтропия (англ. joint entropy) — энтропия объединения двух событий [math]A[/math] и [math]B[/math] .

[math] H(A \cap B) = -\sum\limits_^ \sum\limits_^ p(a_j \cap b_i)\log_2p(a_j \cap b_i) [/math]

[math] H(A \cap B) = H(A|B)+H(B)=H(B|A)+H(A) [/math]

По формуле условной вероятности [math] p(a_j|b_i)=\dfrac [/math]

[math] H(A|B)=-\sum\limits_^p(b_i)\sum\limits_^ p(a_j|b_i)\log_2p(a_j|b_i) [/math] [math]= — \sum\limits_^p(b_i) \sum\limits_^ \dfrac\log_2 \dfrac = -\sum\limits_^ \sum\limits_^ p(a_j \cap b_i)\log_2 \dfrac = [/math] [math] = -\sum\limits_^ \sum\limits_^ p(a_j \cap b_i)\log_2p(a_j \cap b_i) + \sum\limits_^ \sum\limits_^ p(a_j \cap b_i)\log_2p(b_i) [/math] [math]= H(A \cap B) +\sum\limits_^ \sum\limits_^ p(a_j \cap b_i)\log_2p(b_i) = [/math]

[math] = H(A \cap B) +\sum\limits_^ \log_2p(b_i)\sum\limits_^ p(a_j \cap b_i) = H(A \cap B) +\sum\limits_^ \log_2p(b_i)p(b_i) = [/math] [math]H(A \cap B) — H(B) [/math]

Таким образом получаем, что: [math] H(A \cap B)= H(A|B)+H(B) [/math]

Аналогично: [math]H(B \cap A)= H(B|A)+H(A) [/math]

См. также

• Вероятностное пространство, элементарный исход, событие
• Условная вероятность
• Арифметическое кодирование

Источники информации

• И.В. Романовский «Дискретный анализ»
• Википедия — Информационная энтропия
• Wkipedia — Entropy(information_theory)

ML: Немного про энтропию

Энтропия — важная мера, характеризующая распределение вероятностей, имеет широкое применение в машинном обучении. Перед этим документом стоит просмотреть введение в теорию вероятностей.

Мера неопределённости

Рассмотрим дискретные случайные величины. Полезно иметь меру неопределённости их значений. Одной из мер, характеризующих такую неопределённость, является «типичное» отклонение от среднего значения: $\sigma=\sqrt$, где $D =\langle (X-X_)^2 \rangle$ — дисперсия. Такая неопределённость случайной величины $X$ зависит, как от распределения вероятностей $\$ , так и от её возможных значений: $\$. Это затрудняет сравнение степеней неопределённости двух величин существенно различной природы. Поэтому в ряде случаев удобно иметь меру неопределённости, которая зависит только от распределения вероятностей случайной величины.

Пусть для простоты есть два события $X$ и $Y$, имеющих вероятности $P_X$ и $P_Y$. Чем выше вероятность события, тем меньше его неопределённость (оно скорее всего произойдёт). Поэтому постулируем, что мера неопределённости, как функция вероятности, монотонно убывает: $L(P_X) \lt L(P_Y)$, если $P_X \gt P_Y$, а для достоверного события она равна нулю: $L(1)=0$.

Постулируем также, что неопределённость совместной вероятности $P(X,Y)=P_X\cdot P_Y$ двух независимых событий равна сумме неопределённоcтей каждого события: $$ L\bigr(P_X\cdot P_Y\bigr) = L\bigr(P_X\bigr)+L\bigr(P_Y\bigr) $$ Эти требования с точностью до положительного множителя фиксируют функцию: $L(x)=-\log x$.
Энтропия распределения вероятностей $p_i$, по-определению, является средним значением $L(p_i)$.

Энтропия

Пусть $P=\$ — набор $n$ ненулевых вероятностей. Это могут быть вероятности появления символов в тексте или вероятности несовместных классов в модели классификации: $$ p_\alpha > 0,~~~~~~~~~~~\sum^n_ p_\alpha = 1. $$ Энтропия $H$ является мерой равномерности вероятностей (чем больше $H$, тем ближе $p_\alpha$ друг к другу): $$ H(P) = — \sum^n_ p_\alpha\,\log p_\alpha. $$

В качестве логарифма, обычно, выбирают натуральный логарифм $\ln$ или логарифм по основанию два: $\log_2$. Энтропия всегда положительна. Если все вероятности равны: $p_\alpha=1/n$, то энтропия достигает своего максимального значения $H_\max = \log n$. Если одна вероятность стремиться к 1, а остальные к 0, то энтропия стремиться к нулю. Например, для трёх вероятностей (c $\log=\ln$ и $\log_2$):

ln log2 H(0.33, 0.33, 0.33) = 1.10 | 1.58 | H(0.25, 0.25, 0.50) = 1.04 | 1.50 | n: 2 3 10 100 H(0.10, 0.20, 0.70) = 0.80 | 1.16 | ln n: 0.69 1.10 2.30 4.61 
Напомним, что $\ln p = \log_2 p \cdot \ln 2$. Поэтому энтропия с натуральным логарифмом всегда равна $0.69$ от энтропии с двоичным логарифмом.
Энтропия также характеризует степень "непредсказуемости" несовместных событий, вероятности которых равны $p_\alpha$. Eсли $n$ невелико и все вероятности малы, кроме одной, то почти всегда происходит соответствующее ей событие. Эта ситуация вполне предсказуема (энтропия мала). При равномерном же распределении вероятностей может произойти "что угодно" (энтропия максимальна).
☝ Доказательство основного свойства энтропии проводится при помощи поиска экстремума со связями (метод множителей Лагранжа). Условие нормировки (сумма $p_\alpha$ равна 1) умножаем на параметр $\lambda$ и добавляем к энтропии. Затем ищем экстремум по $p_1. p_n,\lambda$: $$ H = -\sum p_\alpha\,\ln p_\alpha + \lambda\,\bigr(\sum p_\alpha- 1\bigr), ~~~~~~~\frac<\partial H> <\partial p_\alpha>= -\ln p_\alpha - 1 +\lambda = 0~~~~~=>~~~~~p_\alpha=\mathrm. $$ Производная по $\lambda$ даёт условие нормировки и которого следует, что $p_\alpha=1/n$.
Код Хаффмана
Пусть есть строка символов, вероятности которых равны обратным степеням двойки. Закодируем каждый символ двоичным числом так, чтобы длина кода была тем больше, чем меньше вероятность символа. Тогда энтропия по логарифму с основанием $2$ равна средней длине в битах (на символ) кода строки символов.
Например, пусть вероятности символов $\$ равны $\$. Построим бинарное дерево, листьями которого являются символы. Спускаясь вниз от корня (равновероятно выбирая левую или правую ветки), мы будем попадать в эти символы с заданными вероятностями (см. рисунок). Тогда оптимальный код символа будет кодом пути к нему по дереву ($0$ - на левую ветку, $1$ - на правую):
 
Если $p_b = 1/2^b$, то $b = -\log_2 p_b$ равно числу бит (шагов от корня к листу). Соответственно, средняя длина на символ $b\,p_b$ равна энтропии текста.
Такой код является префиксным кодом Хаффмана и не требует разделительного символа (бинарная последовательность однозначно декодируется). Когда вероятности не являются обратными степенями двойки, также можно построить бинарное дерево, следуя следующему алгоритму.
Сначала из списка символов выбирают два символа с самыми малыми вероятностями и объединяют их в бинарную ветку (выше это были бы d,e). Затем эти символы из списка удаляют, а вместо них в список помещают корень их ветки (как фиктивный символ) с их суммарной вероятностью. 
Процедура повторяется, пока в списке не останется единственный узел (корень бинарного дерева).
Средняя длина кода Хаффмана на символ больше или равна энтропии $H$ распределения вероятностей символов и меньше, чем $H_<\max>=\log_2 n$. Длина кода каждого символа обычно (но не всегда) равна целой части $-\log_2 p_\alpha$.
Кросс-энтропия
Рассмотрим два набора вероятностей $P=\$ и $Q=\$. Степень различности этих распределений характеризует кросс-энтропия: $$ H(P,Q) = -\sum^n_ p_\alpha\,\ln q_\alpha. $$
Она достигает минимума, когда распределения совпадают $p_\alpha=q_\alpha$ (это доказывается также, как и для энтропии). На Python кросс-энтропию легко вычислить при помощи библиотеки numpy:
import numpy as np p = np.array([0.1, 0.2, 0.7]) q = np.array([0.7, 0.1, 0.2]) H = - p @ np.log(q)
Приведём примеры кросс-энтропии:
Q H(P,Q) [0.33, 0.33, 0.33] 1.10 [0.25, 0.25, 0.50] 0.90 P = [0.10, 0.20, 0.70] [0.10, 0.20, 0.70] 0.80 [0.10, 0.10, 0.80] 0.85 [0.70, 0.10, 0.20] 1.62
Заметим, что для любых $P,Q$ справедливо неравенство $H(P) \le H(P,Q)$.
Кросс-энтропия непосредственно связана с расстоянием Кульбака — Лейблера: $$ D_(P,Q) = \sum^n_ p_\alpha \ln \frac = H(P,Q)-H(P). $$ Это расстояние всегда неотрицательно и равно нулю, когда распределения вероятностей $P$ и $Q$ совпадают. 
В отличии от обычных метрик, это расстояние несимметрично: $D_(P,Q)\neq D_(Q,P)$.
Условная энтропия
Пусть есть словарь $\mathcal=\. w^<(\text)>\>$, состоящий из $\text=|\mathcal|$ слов (или символов). Последовательность $\mathcal= w_1\,w_2. \,w_N$, где $w_i\in \mathcal$ образует текст длиной $N=\mathrm(\mathcal)$. .
Пусть для каждого слова известны $\text$ вероятностей $P(w_i)$ и $\text^2$ условных вероятностей $P(w_i\to w_j)$. Тогда можно определить условную энтропию: $$ H_1 = - \sum_i P\bigr(w^\bigr)~~\sum_j P\bigr(w^\to w^\bigr)\,\log P\bigr(w^\to w^\bigr). $$ Аналогично, при помощи $P(w^,w^)$ и $P(w^,w^ \to w^)$, можно определить условную энтропию второго порядка $H_2$ и т.д.
Перплексия
Вероятностная языковая модель для данного слова $w$, по его контексту $\ <\mathcal- w\>$ (текст $\mathcal$ без слова $w$) или по предшествующим к $w$ словам предсказывает вероятность этого слова: $P(w|\mathcal - w)$. Одной из метрик качества различных моделей является перплексия. Чем меньше перплексия, тем лучше модель.
Перплексией (perplexity) текста $\mathcal$ длиной $N=\mathrm(\mathcal)$ называют: $$ \mathcal = \exp\Bigr( -\frac\,\sum^_ \ln P(w_i|\mathcal-w_i) \Bigr). $$
Если вероятности $P(w_i|\mathcal-w_i)$ оцениваются по предшествующей слову $w_i$ истории $P(w_i|w_1. w_)$ то, по цепному правилу имеем (сумма логарифмов равна логарифму произведения): $\mathcal=\exp(-\ln P(w_1. w_n)/N)$, или: $$ \mathcal = P(w_1. w_N)^ \equiv \sqrt[N]>. $$ Чем выше совместная вероятность последовательности слов, тем меньше перплексия. Важно помнить, что языковая модель должна возвращать "честную", нормированную на единицу вероятность слова $P(w_i|\mathcal-w_i)$. 
Т.е. сумма таких вероятностей по всем словам словаря должна равняться единице. Если это не так, то перплексия может оказаться неоправданно заниженной (например, когда для любого слова словаря модель возвращает 1).
Простейшая языковая модель, независимо от контекста, предсказывает безусловную вероятность слова: $P(w|\mathcal - w) = P(w)$. В этом случае в сумме будет $N^ = P(w^)\cdot N$ раз встречаться слово $w^$ и перплексия равна экспоненте от энропии вероятностей слов словаря: $$ \mathcal_ = \exp\Bigr( -\sum^_ P\bigr(w^\bigr)\,\ln P\bigr(w^\bigr) \Bigr) ~=~ e^, $$ где $\mathcal=\. w^\>$ - словарь из $n$ слов. Когда в модели все вероятности равны $P(w)=1/n$, перплексия равна мощности словаря (количеству различных слов): $\mathcal_0 = n$. Минимальное значение перплексии равно 1. Перплексия, в отличии от энтропии, не зависит от основания логарифма (можно заменить $\ln\mapsto \log_2$ и $e\mapsto 2$).
Перплексию иногда интерпретируют как степень ветвления текста (branching factor) (сколько возможно веток для очередного слова, взвешенных на вероятности этих веток).
Энтропия словаря зависит от его размера. Ниже приведены значения энтропии (натуральный логарифм), вероятности которой вычислены на одном и том-же английском тексте при различных размерах словаря n (не попавшие в словарь слова заменяются на токен UNK):
n: 100 1000 5000 10000 36500 H: 2.913 4.811 5.841 6.080 6.247 P = exp H: 18 123 344 437 516
Поэтому, указание перплексии языковой модели, вообще говоря, необходимо сопровождать размером словаря которым оперирует модель.
Обычно языковую модель строят на одном множестве документов, а перплексию измеряют на другом. Чтобы не было тематического или стилевого перекоса, каждый документ разбивается на тренировочную и тестовую части (hold-out perplexity). Если в качестве ошибки модели используют кросс-энтропию CE в расчёте на слово, то перплексия равна $\mathcal=\exp\text$.
Существует 1B Word Benchmark data set длиной около 829'250'940 английских слов со словарём 793'471 слов (в архиве 11 GB). На этом датасете часто сравнивают различные языковые модели (см. тут и тут). Так 5-граммные модели с интерполяцией дают значение $\mathcal=67$ (1.76B параметров), LSTM + CNN INPUTS (см. этот документ) $\mathcal=30$ (1.04B параметров), а ансамбль моделей достигает значения $\mathcal=23.7$ (2016).
Дифференциальная энтропия
Для непрерывных случайных величин энтропия их плотности вероятности $p(x)$ определяется аналогичным образом: $$ H[X] = -\int\limits_X p(x)\,\ln p(x)\,dx = - \langle \ln p(x) \rangle $$ и называется дифференциальной энтропией. Рассмотрим в качестве примера нормальное (гауссово) распределение со средним $\mu$ и дисперсией $D$: $$ p(x) = \frac<\sqrt<2\pi D>>\, e^<-\frac<(x-\mu)^2>>. $$ Дифференциальная энтропия этого распределения равна: $$ H[X] ~=~ \ln\sqrt <2\pi D>+ \frac<\langle(x-\mu)^2\rangle> ~=~ \frac\ln (2\pi\,D\,e). $$ Обратим внимание, что в отличии от энтропии для дискретных случайных чисел, дифференциальная энтропия может быть отрицательной (выше при $D \lt 1/2\pi e$). Связано это с тем, что значения плотности вероятности (в отличии от вероятностей) могут быть больше единицы.
Можно показать, что нормальное распределение имеет наибольшую дифференциальную энтропию среди всех распределений с такой же дисперсией (доказывается это при помощи лагранжевого метода с двумя связями - на нормировку распределения и равенство его дисперсии $D$). Поэтому, для любой случайной величины $$ \langle(x-x_)^2\rangle \ge \frac><2\pi e>. $$
Энтропия непрерывной случайной величины
При попытке оценить неопределенность непрерывной случайной величины (с непрерывным множеством возможных состояний) – появляются особенности.

«Непрерывность» имеет смысл только для количеств, то есть объект с непрерывным множеством возможных состояний – это количественная случайная величина.
Распределение вероятности по состояниям характеризуется в этом случае плотностью вероятности p(x). Плотность вероятности величина размерная. Размерность обратная размерности случайной величины X, так как вероятность p(x)·dx безразмерна.

Переход к безразмерной случайной величине X, проведем путем деления размерной случайной величины X* на единицу ее измерения X0. Тогда и плотность вероятности будет безразмерной. Разобьем всю область (–; +) возможных значений случайной величины X на интервалы, разделенные отстоящими на равных расстояниях Δx друг от друга интервалами (x-1; x0;. xk;. ).
Всякий раз, когда реализуется значение x О (xk; xk + Δx) будем считать, что реализовалось значение xk величины X.
Таким образом перешли к дискретной случайной величине, которая характеризуется распределением вероятностей. Вероятность наступления какого-либо состояния равна
Очевидно, что при Δx ® 0 квантованная величина Xд будет все более и более полно отражать все свойства непрерывной величины X. С другой стороны, к величине Xд (дискретной) можно применить понятие энтропии
Устремим Δx ® 0. При достаточно малых Δx примем . Поэтому
Таким образом предел энтропии H(Xд) за счет второго члена (–log Δx) стремится к бесконечности при Δx ® 0. Убедившись в том, что непрерывные случайные величины не допускают введения конечной абсолютной меры неопределенности, введем относительную меру. В качестве стандарта для сравнения можно брать неопределенность какого-либо простого распределения, например – равномерного в интервале шириной e. Разделим интервал e также на участки Δx и подсчитаем
Будем характеризовать неопределенность непрерывной случайной величины X числом, к которому стремится разность энтропий квантованных величин Xд (случайной величины X любого распределения) и Xд;равн(случайной величины, распределенной по равномерному закону на интервале e):
Эта разность конечна.
Если взять за стандарт неопределенность случайной величины, равномерно распределенной в единичном интервале, то есть принять (e = 1), то
Число He=1(X) обычно и называют относительной энтропией непрерывной случайной величины. http://peredacha-informacii.ru/ По численному значению относительной энтропии различные источники сообщения можно сравнить между собой.
Относительная энтропия характеризуется теми же свойствами, что и энтропия дискретного источника:
1. Не зависит от конкретного содержания случайной величины.
2. Энтропия объединения двух независимых источников выражается формулой:
3. Энтропия объединения двух статистически зависимых источников:
5. Всякое сглаживание функций распределения p(X) ведет к росту He(X).
Исключение составляет лишь то, что He(X) может принимать отрицательные значения, так как He(X) – это разность энтропий, а случайная величина X может быть распределена на небольшом интервале меньшем, чем (e = 1).
Подсчитайте относительную энтропию непрерывного источника, имеющего следующий закон распределения плотности вероятности случайной величины X:
Энтропия дискретной случайной величины представляет собой:

Дискретная случайная величина X может принимать три различных значения. Если считать сложность построения кода пропорциональной количеству различных значений кодируемой дискретной случайной величины, то блочный код для X по сравнению с неблочным сложнее строить в:
Вычислить длины кодов Хаффмена и арифметического для сообщения AAB, полученного от дискретной случайной величины X со следующим распределением вероятностей P(X=A)=1/3 , P(X=B)=2/3 :
 Найти энтропию дискретной случайной величины X :
Про дискретную случайную величину X известно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений X , результат которых - "ТЕОРИЯИНФОРМАЦИИ". Составить на основании этого результата приблизительный закон распределения вероятностей этой дискретной случайной величины и оценить минимальную среднюю длину кодов для X :
Составить арифметический код для сообщения BAABC, полученного от дискретной случайной величины X со следующим распределением вероятностей P(X=A)=1/4 , P(X=B)=1/2 , P(X=C)=1/4 :
Составить арифметический код для сообщения BAABC, полученного от дискретной случайной величины X со следующим распределением вероятностей P(X=A)=1/3 , P(X=B)=7/15 , P(X=C)=1/5 :
Значения дискретной случайной величины X1 и X2 определяются подбрасыванием двух идеальных монет, а дискретная случайная величина Y равна сумме количества "гербов", выпавших при подбрасывании этих монет. В Y содержится:
 Найти среднюю длину code1 для дискретной случайной величины X :


Похожие публикации:

Как вытащить карту из 2гис
Как выучить технический английский самостоятельно
Как создать в ворде шаблон для заполнения
Что такое презентация и как ее делать