Энтропия и информация

Определим более строго понятия энтропии и информации.

Шеннон определяет информационную энтропию как математическое ожидание количества информации в случайном событии \(x \in X\), где \(X = {(x_i, P(x_i))}\) – дискретный ансамбль: \[H(X) = \mathrm E[I(X)]\]

Функция информации \(I(p)\), имеющая аргументом вероятность события, должна удовлетворять следующим фундаментальным свойствам:

1. \(I(p)\) монотонно убывает с \(p\)
2. \(I(p) \ge 0\)
3. \(I(1) = 0\)
4. \(I(p_1 p_2) = I(p_1) + I(p_2)\), если \(p_1\) и \(p_2\) независимы.

Интуитивно, эти свойства объясняются из содержательного подхода к информации, рассмотренного в лекции 1.

Шеннон показал, что это должна быть логарифмическая функция: \[I(p) = - log(p)\]

Действительно, пусть \(I(p)\) – дважды непрерывно дифференцируемая функция. Из свойства (4), \[I(p_1 p_2) = I(p_1) + I(p_2).\] Дифференцируя обе части уравнения по \(p_1\), \[p_2\fd{I(p_1 p_2)}{p_1 p_2} = \fd{I(p_1)}{p_1}\] Дифференцируя обе части уравнения по \(p_2\), \[\fd{I(p_1 p_2)}{p_1 p_2} + p_1 p_2 \frac{\d^2 I(p_1 p_2)}{\d (p_1 p_2)^2} = 0\] Заменяя \(u = p_1 p_2\) \[\fd{I(u)}{u} + u \frac{\d^2 I(u)}{\d u^2} = 0\]

Это линейное однородное ОДУ второй степени. Произведём замену \(f(u) = u I'(u)\), тогда \(f'(u) = I'(u) + u I''(u)\), то есть уравнение сводится к решению \[f'(u) = 0\] \[f(u) = c_1\] \[u \fd{I}{u} = c_1\] \[ \int \d{I(u)} = c_1 \int \frac{\d u}{u}\] \[ I(u) = c_1 \ln(u) + c_2\]

Свойство (3) даёт граничное условие для определения \(c_2\): \[ c_1 \ln(1) = - c_2 \] \[ c_2 = 0 \]

Из свойства (2) следует, что \(c_1 \le 0\). Тогда,

\[I(p) = - K \ln(p),\]

где \(K\) – положительная константа, которая определяет единицы измерения.

Шеннон положил \(K=\log_2(e)\), так, что окончательно имеем

\[I(p) = - \log_2(e)\ln(p) = - \log_2(p).\]

Собственно основание логарифма определяет единицы измерения. Для двоичных логарифмов, единицы измерения называются биты (или шенноны, в честь Шеннона). Для десятичных – хартли (в честь Хартли). Для натуральных – наты. Для большинства теоретико-информационных выкладок основание логарифма значения не имеет, поэтому во многих случаях оно может быть не указано.

\[1 \unit{бит} = \frac{1}{\log_2 10} \unit{хартли} = \frac{1}{\log_2 e} \unit{нат}\] \[1 \unit{бит} = \log_{10} 2 \unit{хартли} = \ln 2 \unit{нат}\] \[1 \unit{хартли} \approx 3.32 \unit{бит}\] \[1 \unit{нат} \approx 1.44 \unit{бит}\]

Такое определение \(I(x)\), как несложно заметить, действительно удовлетворяет свойству (1) – отрицательный логарифм действительно монотонно убывающая функция.

Математическое ожидание количества информации для ансамбля случайных событий \(X=\{x, P(x)\}\) можно вычислить как среднюю величину при бесконечном числе опытов \[\begin{align} \mathrm E[I(x)] & = \lim_{N\to \infty}\frac{1}{N}\sum_{x\in X} n(x) I(P(x)) \\ & = \sum_{x\in X} \lim_{N\to \infty}\frac{n(x)}{N} I(P(x)) \\ & = \sum_{x\in X} P(x) I(P(x)) \\ & = - \sum_{x\in X} P(x) log(P(x)) \end{align}\]

В результате, ожидаемо, получается формула Шеннона для информационной энтропии.

Информационная энтропия характеризует “неупорядоченность”, то есть степень нашего незнания, о предмете в среднем, в то время как количество информации характеризует насколько в результате опыта уменьшилась неопределённость. Количественно, однако, энтропия – это количество информации, которое в среднем будет получено на одно событие.

Собственная информация

Собственная информация, так же называемая собственным информационным содержанием, или “неожиданностью”, \(I(x)\) случайного события \(x\), выбираемого из дискретного ансамбля \(X = \{x_i, P(x_i)\}\) определяется как \[I(x) = -\log{P(x)},\] и отражает количество информации, получаемое при измерении значения \(x\).

Информационная энтропия может быть определена через собственную информацию как \[H(X) = \sum_{x_i\in X} P(x_i) I(x_i)\]

Собственная информация удовлетворяет фундаментальным свойствам функции информации.

Собственная информация характеризует степень неожиданности конкретного события.

Совместная энтропия

До сих пор мы говорили об индивидуальных событиях. Рассмотрим теперь ансамбли событий \(X\) и \(Y\). Какова будет информационная энтропия совместного возникновения событий из \(X\) и \(Y\)?

Логично предположить, что совместная энтропия \(H(XY)\) будет определяться аналогично энтропии единичного случайного события, но вместо вероятности одного события будет фигурировать совместная вероятность двух событий \(P(x y)\):

\[H(XY) = - \sum_{x \in X}\sum_{y \in Y} P(x y) \log P(x y)\]

Это определение легко обобщается на случай совместной энтропии более, чем двух событий:

\[H(X_1, \ldots, X_n) = - \sum_{x_1\in X_1} \ldots \sum_{x_n \in X_n} P(x_1 \ldots x_n) \log P(x_1 \ldots x_n)\]

Совместная энтропия отражает незнание о совокупности случайных событий.

Свойства совместной энтропии

• Неотрицательность

  \[H(X_1 \ldots X_n) \ge 0\]

• Не меньше индивидуальных энтропий

  \[H(X_1 \ldots X_n) \ge \underset{1\le i\le n}\max\{H(X_i)\}\]

• Не больше суммы индивидуальных энтропий

  \[H(X_1 \ldots X_n) \le \sum_{i=1}^n\max\{H(X_i)\}\]

• Симметрия к перестановкам

  \[H(X_1 X_2 \ldots X_n) = H(X_2 X_1 \ldots X_n)\]

• Для независимых событий, \(P(xy) = P(x)P(y),\) и тогда \[\begin{align} H(XY) = & - \sum_{x \in X}\sum_{y \in Y} P(x) P(y) \log P(x) - \sum_{x \in X}\sum_{y \in Y} P(x) P(y) \log P(y \\ = & - \sum_{x \in X}P(x) \log P(x) \sum_{y \in Y} P(y) - \sum_{y \in Y} P(y) \log P(y) \sum_{x \in X} P(x) \\ \overset{\begin{matrix} \sum_{x \in X} P(x)=1 \\ \sum_{y \in Y} P(y)=1 \end{matrix}}= & - \sum_{x \in X}P(x) \log P(x) - \sum_{y \in Y} P(y) \log P(y) \\ = & H(X) + H(Y) \end{align}\]

  Аналогично для более двух событий (тривиально доказывается по индукции).

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

До сих пор полагалось, что случайные события независимы, то есть каждое новое событие элемента никак не связано с предыдущими.

Рассмотрим теперь ансамбли событий \(X\) и \(Y\), которые кроме собственных вероятностей характеризуются так же условными \(P(y | x)\), отражающими взаимосвязь событий.

Общая энтропия зависимых ансамблей \[\begin{align} H(XY) = & - \sum_{x\in X} \sum_{y\in Y} P(xy) \log P(xy) \\ \overset{P(xy) = P(x)P(y|x)}= & - \sum_{x\in X} \sum_{y\in Y} P(x) P(y|x) \log (P(x) P(y | x))\\ = & - \sum_{x\in X} P(x) \log (P(x)) \sum_{y\in Y} P(y | x) - \sum_{x\in X} P(x) \sum_{y\in Y} P(y|x) \log (P(y|x)) \\ \overset{\sum_{y\in Y} P(y_j | x_i) = 1}= & - \sum_{x\in X} P(x) \log (P(x)) - \sum_{x\in X} P(x) \sum_{y\in Y} P(y | x) \log (P(y|x)) \\ & = H(X) + H(Y|X) \\ \end{align}\]

Здесь \(H(Y|X)\) называется условной энтропией \(Y\) при условии \(X\): \[H(Y|X) = - \sum_{x\in X} P(x) \sum_{y\in Y} P(y | x) \log (P(y|x))\]

Она определяется через совместную энтропию как \[H(Y|X) = H(XY) - H(X).\]

Выделяют так же частную условную энтропию \(H(Y|x),\) \[H(Y|x) = - \sum_{y\in Y} P(y | x) \log (P(y|x))\]

Тогда полная условная энтропия может быть выражена через частную: \[H(Y|X) = \sum_{x\in X} P(x) H(Y|x)\]

Условная энтропия \(H(Y|X)\) отражает количество информации, содержащееся (в среднем) в событии \(y \in Y\), при условии, что событие \(x \in X\) уже произошло. Поэтому её так же иногда называют условной информацией и обозначают \(I(Y|X)\).

Свойства условной энтропии

• \(H(Y|X)=0\) тогда и только тогда, когда исход \(X\) полностью предопределяет исход \(Y\).

• Правило цепочки

  \[H(X Y) = H(Y | X) + H(X) = H(X|Y)+H(Y)\]

  \[H(X_1\ldots X_n) = \sum_{i=1}^n H(X_i | X_1\ldots X_{i-1})\]

• Правило Байеса

  \[H(Y|X) = H(X|Y) - H(X) + H(Y)\]

  Доказательство: \[H(XY) = H(Y|X) + H(X),\] \[H(YX) = H(X|Y) + H(Y),\] \[H(XY)=H(YX),\] \[H(Y|X) + H(X) = H(X|Y) + H(Y)\]

• Не превосходит безусловной энтропии

  \[H(Y|X) \le H(Y)\]

• Для независимых \(X\) и \(Y\), \(P(y|x) = P(y)\) и тогда \[H(Y|X) = - \sum_{y\in Y} P(y) \log (P(y)) = H(Y)\]

  Эквивалентно через совместную энтропию, если \(X\) и \(Y\) независимы, \[H(Y|X) = H(XY) - H(X) = H(X) + H(Y) - H(X) = H(Y)\]

Относительная энтропия

Относительная энтропия, или расстояние Кульбака-Лейблера (введённая в 1951 г. Соломоном Кульбаком и Ричардом Лейблером) – это мера информационного отличия одного распределения от другого. Для дискретных вероятностей \(P\) и \(Q\) определяется как \[D_{KL}(P||Q) = \sum_{x\in X} P(x) \log\left(\frac{P(x)}{Q(x)}\right)\]

В теории кодирования, \(D_{KL}(P||Q)\) показывает ожидаемое число дополнительных бит, необходимых для кодирования значений, распределённых как \(P\) используя код, оптимизированный для распределения \(Q\).

Относительная энтропия неотрицательна. Этот результат известен как неравенство Гиббса.

Взаимная информация

Рассмотрим вновь ансамбли событий \(X\) и \(Y\), которые кроме собственных вероятностей характеризуются так же условными \(P(x | y)\), отражающими взаимосвязь событий.

Формально, взаимная информация \(I(X;Y)\) определяется как \[\begin{align} I(X;Y) & = \sum_{x\in X}\sum_{y\in Y} P(xy) \log\frac{P(xy)}{P(x)P(y)} \\& = \sum_{y\in Y} P(y) \sum_{x\in X}P(x|y) \log\frac{P(x|y)}{P(x)} \\& = \sum_{x\in X}P(x) \sum_{y\in Y} P(y|x) \log\frac{P(y|x)}{P(y)} \end{align}\]

Взаимная информация отражает количество информации, которое теряется в результате связи \(Y\) и \(X\), по сравнению с независимыми ансамблями: \[\begin{align} I(X;Y) & = H(X) + H(Y) - H(XY) \\& = H(X) - H(X|Y) \\& = H(Y) - H(Y|X) \end{align}\]

Иначе говоря, \(I(X;Y)\) характеризует степень взаимосвязи \(X\) и \(Y\), она максимальна при полной взаимосвязи и равна нулю при отсутствии таковой.

Выделяют так же взаимную информацию событий \[\begin{align} I(x;y) & = \log \frac{P(xy)}{P(x)P(y)} \\ & = \log \frac{P(x|y)}{P(x)} \\ & = \log \frac{P(y|x)}{P(y)} \end{align}\]

И взаимную информацию ансамбля и события \[I(X;y) = \mathrm E_x[I(x;y)] = \sum_{x\in X} P(x|y) I(x;y)\]

Взаимная информация ансамблей тогда: \[I(X;Y) = \mathrm E[I(X;y)] = \sum_{y\in Y} P(y) I(X;y)\]

Свойства взаимной информации

• Неотрицательность

  Поскольку \(H(XY) \le H(X)+H(Y)\), \[I(X;Y)\ge 0\]

• Симметрия

  \[I(X;Y) = I(Y;X)\]

• Не превосходит энтропию аргументов

  Поскольку \(H(XY) \ge \max[H(X), H(Y)]\) \[I(X;Y) \le \min[H(X), H(Y)]\]

• Взаимная информация ансамбля с самим собой даёт информационную энтропию ансамбля \[I(X;X) = H(X)\]
• Если ансамбли полностью зависимы, \(H(X) = H(Y)\), \(H(Y|X)=H(X|Y)=0\), то \[I(X;Y) = H(X) = H(Y)\]
• Если ансамбли полностью независимы, \(H(XY)= H(X)+H(Y)\), \[I(X;Y) = 0\]

Информационная энтропия в теории связи

Различные определения энтропии и информации приобретают специфический смысл в приложении к теории связи. В частности, в случаях, когда речь идёт о двух случайных величинах, в теории связи эти две величины, как правило, сообщение и сигнал. Рассмотрим подробнее.

Совместная энтропия системы связи \[H(MR) = H(M|R)+H(R) = H(R|M)+H(M).\]

Здесь \(H(M)\) – априорная энтропия источника информации, \(H(R)\) – энтропия приёмника, \(H(R|M)\) – энтропия канала, \(H(M|R)\) – апостериорная энтропия источника.

Взаимная информация приёмника и источника \[\begin{align} I(MR) & = H(M) + H(R) - H(MR) \\ & = H(M) - H(M|R) \\ & = H(R) - H(R|M). \end{align}\]

В случае идеального канала передачи, R полностью определяется M, \(H(R|M) = 0\), и тогда \[H(MR) = H(M) = H(R),\] \[I(MR) = H(R) = H(M).\]

В случае 100% потерь в канале передачи, R и M независимы, \(H(R|M) = H(R)\), и тогда \[H(MR) = H(M) + H(R),\] \[I(MR) = 0.\]

Совместная энтропия \(H(MR) = H(R|M) + H(M)\) отражает суммарную энтропию источника и канала.

\(I(MR) = H(M) - H(M|R) = H(R) - H(R|M)\) отражает количество информации, получаемое в результате передачи сообщения через канал.

Условная энтропия \(H(M|R) = H(M) - I(MR)\) соответствует потерям информации в канале.

Условная энтропия \(H(R|M) = H(R) - I(MR)\) соответствует энтропии, вносимой шумом в канале.

Энтропия непрерывных источников

До сих пор, мы обсуждали энтропию переменных, приобретающих дискретные значения.

Для перехода к непрерывным величинам, определение строится по аналогии:

\[ h[x] = E[-\ln(\rho(x))] = - \int_\mathbb X \rho(x) \ln(\rho(x)) \d x,\] где \(\rho(x)\) – плотность вероятности непрерывной случайной переменной x.

Эта формула называется формулой непрерывной энтропии, или дифференциальной энтропии.

Несмотря на то, что она строится по аналогии с дискретным случаем, их нельзя считать полностью аналогичными: дифференциальная энтропия не является предельным случаем дискретной. Покажем это.

Смоделируем дискретную переменную в терминах непрерывной. Для этого, разделим область определения функции на интервалы ширины \(\Delta\). Тогда, по первой теореме о среднем, для любой функции \(f(x)\), \[f(x)\Delta = \int_{i\Delta}^{(i+1)\Delta}f(x) \d x,\] тогда \[\int_\mathbb X f(x) \d x = \sum_{i\in \mathcal I_x} f(x_i)\Delta\]

Рассмотрим дифференциальную энтропию: \[h[x] = -\int_\mathbb X \rho(x) \ln(\rho(x)) \d x = -\sum_{i\in \mathcal I_x} \rho(x_i) \ln(\rho(x_i))\Delta\]

В то же время, для дискретной энтропии \[H[x] = -\sum_{i\in \mathcal I_x} \rho(x_i)\Delta \ln(\rho(x_i)\Delta)\]

Разница между этими выражениями \[H[x] - h[x] = -\sum_{i\in \mathcal I_x} \rho(x_i)\Delta (\ln(\rho(x_i)\Delta) - \ln(\rho(x_i))) = -\ln(\Delta)\sum_{i\in \mathcal I_x} \rho(x_i)\Delta \]

При \(\Delta\to0,\) \[\lim_{\Delta\to0}\sum_{i\in \mathcal I_x} \rho(x_i)\Delta = \int_\mathbb X \rho(x) \d x = 1,\] тогда \[\lim_{\Delta\to0}(H[x]-h[x]) = - \lim_{\Delta\to0}\ln\Delta = \infty,\]

В общем случае, оказывается, дифференциальная энтропия, определённая в такой форме, не является хорошей мерой информационного содержания. Эта величина может становиться отрицательной, не инвариантна к замене переменных, и наконец при размерной переменной \(x\) просто размерно некорректна. Более корретное построение предложено физиком Эдвином Томпсоном Джейнсом в 1968 г.

Рассмотрим дискретное распределение переменной \(x\), имеющем \(N\) точек \(\{x_i\}\), причём распределение этих точек при \(N\to\infty\) описывается функцией плотности вероятности \(m(x)\), такой, что \[\lim_{N\to\infty} \frac{1}{N} \mathcal N(a,b) = \int_a^b m(x) \d x,\] где \(\mathcal N(a,b)\) – количество точек в интервале \([a, b)\). Тогда, для любых двух соседних точек \(x_i\) и \(x_{i+1}\), \[\lim_{N\to\infty} \frac{1}{N} \mathcal N(x_i,x_{i+1}) = \int_{x_i}^{x_{i+1}} m(x) \d x,\] где \(\mathcal N(x_i,x_{i+1}) = 1\), и по первой теореме о среднем, \[\lim_{N\to\infty} \frac{1}{N} = m(x_i) (x_{i+1}-x_i) ,\] \[(x_{i+1}-x_i) = \lim_{N\to\infty} \frac{1}{N m(x_i)},\] и тогда, учитывая формулу дискретной энтропии, \[H_N[x] = - \sum_{i=1}^N P(x_i) \log(P(x_i)),\] получаем \[\begin{align} \lim_{N\to\infty} H_N[x] & = - \lim_{N\to\infty}\sum_{i=1}^N \rho(x_i)(x_{i+1}-x_i) \log(\rho(x_i)(x_{i+1}-x_i))\\ & = - \lim_{N\to\infty} \int_\mathbf X \rho(x) \log\left(\frac{\rho(x)}{N m(x)}\right) \d x\\ & = - \int_\mathbf X \rho(x) \log\left(\frac{\rho(x)}{m(x)}\right) \d x + \lim_{N\to\infty}\log N\\ \end{align}\]

Член \(\lim_{N\to\infty}\log N\) стремится к бесконечности, но это не удивительно: при переходе к непрерывному распределению, алфавит случайной величины имеет бесконечную мощность, и, следовательно, энтропия любого символа бесконечна. Этот член однако постоянный. Первый же член суммы конечен, что позволяет осмысленно анализировать непрерывные распределения.

По сути, \(m(x)\) по определению является функцией равномерного распределения (точек, не вероятности!). Сам первый член можно интерпретировать как количество информации, получаемое от знания, что величина \(x\) распределена в соответствии с \(\rho(x)\), а не равномерно (т.е. с плотностью \(m(x)\)). Вообще, этот член соответствует расстоянию Кульбака-Лейблера (взятому со знаком “минус”). Собственно, поскольку бесконечный член не несёт смысловой нагрузки, часто под непрерывной энтропией понимают просто этот член: \[ H[x] = - \int_\mathbf X \rho(x) \log\left(\frac{\rho(x)}{m(x)}\right) \d x.\]

Отметим, что расстояние Кульбака-Лейблера неотрицательно, соответственно \(H[x]\le 0\).

Максимальная энтропия непрерывного процесса

Одним из вопросов, на который призвана ответить теория информации, является вопрос оптимизации связи. Формально, при прочих равных, как достичь максимальной энтропии сингала?

Рассмотрим относительную энтропию двух функций плотности вероятности \(f\) и \(g\) с одинаковой дисперсией:

\[D_{KL}(f || g) = \int_{-\infty}^{\infty} f(x) \log\left(\frac{f(x)}{g(x)}\right) \d x= - h(f) - \int_{-\infty}^{\infty}f(x)\log(g(x))\d x \]

Из неравенства Гиббса, \(D_{KL}(f || g)\ge 0\).

Пусть \(g(x)\) – нормальное (Гауссово) распределение. Тогда,

\[\begin{align} \int_{-\infty}^{\infty}f(x)\log(g(x))\d x & = \int_{-\infty}^{\infty}f(x)\log\left(\frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)\right)\d x \\ & = \int_{-\infty}^{\infty}f(x)\log\left(\frac{1}{\sqrt{2\pi\sigma^2}}\right) \\ & +\int_{-\infty}^{\infty}f(x)\log\left(\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)\right)\d x \\ & = -\log\left(\sqrt{2\pi\sigma^2}\right) \int_{-\infty}^{\infty}f(x)\d x - \log(e)\int_{-\infty}^{\infty}f(x)\frac{(x-\mu)^2}{2\sigma^2}\d x \\ & = -\log\left(\sqrt{2\pi\sigma^2}\right) - \log(e)\frac{\sigma^2}{2\sigma^2} \\ & = -\frac{1}{2}\log(2\pi\sigma^2 e) \end{align}\]

С другой стороны, \[\begin{align} & h(g) = -\int_{-\infty}^{\infty}g(x)\log(g(x))\d x \\ & =-\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)\log\left(\frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)\right)\d x \\ & =\frac{\log(\sqrt{2\pi\sigma^2})}{\sqrt{2\pi\sigma^2}}\int_{-\infty}^{\infty}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right) \d x\\ & +\frac{\log(e)}{\sqrt{2\pi\sigma^2}}\int_{-\infty}^{\infty}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)\frac{(x-\mu)^2}{2\sigma^2}\d x \\ & =\log(\sqrt{2\pi\sigma^2}) +\log(e)\frac{\sigma^2}{2\sigma^2} \\ & =\frac{1}{2}\log(2\pi\sigma^2 e) \end{align}\]

Таким образом, \[h(g)-h(f) \ge 0,\] то есть, энтропия максимальна, если случайная величина распределена в соответствии с распределением Гаусса.