32

32. Свойства энтропии. Энтропия и информация.

Энтропи́я (информационная) — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n-ого порядка, см. ниже) встречаются очень редко, то неопределённость ещё более уменьшается.

Информационная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n) рассчитывается по формуле:

$H(x)=-\sum_{i=1}^np(i)\log_2 p(i).$

Эта величина также называется средней энтропией сообщения. Величина $\log_2\frac{1}{p(i)}$ называется частной энтропией, характеризующей только i-e состояние.

Таким образом, энтропия события x является суммой с противоположным знаком всех произведений относительных частот появления события i, умноженных на их же двоичные логарифмы (основание 2 выбрано только для удобства работы с информацией, представленной в двоичной форме).

Математические свойства:

Неотрицательность: $H(X)\geqslant 0$ .

Ограниченность: $H(X)\leqslant\log|X|$ . Равенство, если все элементы из X равновероятны.

Если $X,\;Y$ независимы, то H(XY) = H(X) + H(Y).

Энтропия — выпуклая вверх функция распределения вероятностей элементов.

Если $X,\;Y$ имеют одинаковое распределение вероятностей элементов, то H(X) = H(Y).

Эффективность

Исходный алфавит, встречающийся на практике, имеет вероятностное распределение, которое далеко от оптимального. Если исходный алфавит имел n символов, тогда он может быть сравнён с «оптимизированным алфавитом», вероятностное распределение которого однородно. Соотношение энтропии исходного и оптимизированного алфавита — это эффективность исходного алфавита, которая может быть выражена в процентах. Из этого следует, что эффективность исходного алфавита с n символами может быть определена просто как равная его n-арной энтропии.

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний):

$H_1(\mathcal{S})=-\sum_i p_i\sum_j p_i (j)\log_2 p_i(j),$

где i — это состояние, зависящее от предшествующего символа, и pi(j) — это вероятность j, при условии, что i был предыдущим символом.

Так, для русского языка без буквы «ё» $H_0=5,\;H_1=4{,}358,\;H_2=3{,}52,\;H_3=3{,}01$

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы. Так, для описания потерь со стороны источника (то есть известен посланный сигнал), рассматривают условную вероятность $p(b_j\mid a_i)$ получения приёмником символа bj при условии, что был отправлен символ ai. При этом канальная матрица имеет следующий вид:

	b1	b2	…	bj	…	bm
a1	$p(b_1\mid a_1)$	$p(b_2\mid a_1)$	…	$p(b_j\mid a_1)$	…	$p(b_m\mid a_1)$
a2	$p(b_1\mid a_2)$	$p(b_2\mid a_2)$	…	$p(b_j\mid a_2)$	…	$p(b_m\mid a_2)$
…	…	…	…	…	…	…
ai	$p(b_1\mid a_i)$	$p(b_2\mid a_i)$	…	$p(b_j\mid a_i)$	…	$p(b_m\mid a_i)$
…	…	…	…	…	…	…
am	$p(b_1\mid a_m)$	$p(b_2\mid a_m)$	…	$p(b_j\mid a_m)$	…	$p(b_m\mid a_m)$

Очевидно, вероятности, расположенные по диагонали описывают вероятность правильного приёма, а сумма всех элементов столбца даст вероятность появления соответствующего символа на стороне приёмника — p(bj). Потери, приходящиеся на передаваемый сигнал ai, описываются через частную условную энтропию:

$H(B\mid a_i)=-\sum_{j=1}^m p(b_j\mid a_i)\log_2 p(b_j\mid a_i).$

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

$H(B\mid A)=\sum_i p(a_i)H(B\mid a_i).$

$H(B\mid A)$ означает энтропию со стороны источника, аналогично рассматривается $H(A\mid B)$ — энтропия со стороны приёмника: вместо $p(b_j\mid a_i)$ всюду указывается $p(a_i\mid b_j)$ (суммируя элементы строки можно получить p(ai), а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия

Взаимная энтропия, или энтропия объединения, предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H(AB), где A, как всегда, характеризует передатчик, а B — приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий p(aibj), и для полного описания характеристик канала требуется только одна матрица:

p(a1b1)	p(a1b2)	…	p(a1bj)	…	p(a1bm)
p(a2b1)	p(a2b2)	…	p(a2bj)	…	p(a2bm)
…	…	…	…	…	…
p(aib1)	p(aib2)	…	p(aibj)	…	p(aibm)
…	…	…	…	…	…
p(amb1)	p(amb2)	…	p(ambj)	…	p(ambm)

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j даст p(bj), сумма строки с номером i есть p(ai), а сумма всех элементов матрицы равна 1. Совместная вероятность p(aibj) событий ai и bjвычисляется как произведение исходной и условной вероятности,

$p(a_ib_j)=p(a_i)p(b_j\mid a_i)=p(b_j)p(a_i\mid b_j).$

Условные вероятности производятся по формуле Байеса. Таким образом имеются все данные для вычисления энтропий источника и приёмника:

$H(A)=-\sum_i\left(\sum_j p(a_i b_j)\log\sum_j p(a_i b_j)\right),$

$H(B)=-\sum_j\left(\sum_i p(a_i b_j)\log\sum_i p(a_i b_j)\right).$

Взаимная энтропия вычисляется последовательным суммированием по строкам (или по столбцам) всех вероятностей матрицы, умноженных на их логарифм:

H(AB) = −	∑	∑	p(aibj)logp(aibj).
	i	j

Единица измерения — бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов — отправленного и полученного. Путём несложных преобразований также получаем

$H(AB)=H(A)+H(B\mid A)=H(B)+H(A\mid B).$

Взаимная энтропия обладает свойством информационной полноты — из неё можно получить все рассматриваемые величины.