WikiSort.ru - Не сортированное

Определение по Шеннону

Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

1. мера должна быть непрерывной; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
2. в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;
3. должна быть возможность сделать выбор (в нашем примере букв) в два шага, в которых значение функции конечного результата должно являться суммой функций промежуточных результатов.^{[прояснить]}

Поэтому функция энтропии ${\displaystyle H}$ должна удовлетворять условиям

1. ${\displaystyle H(p_{1},\;\ldots ,\;p_{n})}$ определена и непрерывна для всех ${\displaystyle p_{1},\;\ldots ,\;p_{n}}$ , где ${\displaystyle p_{i}\in [0,\;1]}$ для всех ${\displaystyle i=1,\;\ldots ,\;n}$ и ${\displaystyle p_{1}+\ldots +p_{n}=1}$ . (Нетрудно видеть, что эта функция зависит только от распределения вероятностей, но не от алфавита.)
2. Для целых положительных ${\displaystyle n}$ , должно выполняться следующее неравенство:

   ${\displaystyle H\underbrace {\left({\frac {1}{n}},\;\ldots ,\;{\frac {1}{n}}\right)} _{n}<H\underbrace {\left({\frac {1}{n+1}},\;\ldots ,\;{\frac {1}{n+1}}\right)} _{n+1}.}$

3. Для целых положительных ${\displaystyle b_{i}}$ , где ${\displaystyle b_{1}+\ldots +b_{k}=n}$ , должно выполняться равенство

   ${\displaystyle H\underbrace {\left({\frac {1}{n}},\;\ldots ,\;{\frac {1}{n}}\right)} _{n}=H\left({\frac {b_{1}}{n}},\;\ldots ,\;{\frac {b_{k}}{n}}\right)+\sum _{i=1}^{k}{\frac {b_{i}}{n}}H\underbrace {\left({\frac {1}{b_{i}}},\;\ldots ,\;{\frac {1}{b_{i}}}\right)} _{b_{i}}.}$

Шеннон показал,^[2] что единственная функция, удовлетворяющая этим требованиям, имеет вид

${\displaystyle -K\sum _{i=1}^{n}p(i)\log _{2}p(i),}$

где ${\displaystyle K}$  — положительная константа (и в действительности нужна только для выбора единицы измерения энтропии; изменение этой константы равносильно изменению основания логарифма).

Шеннон определил, что измерение энтропии (${\displaystyle H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}}$ ), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д. (см. цепи Маркова).

Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Определение с помощью собственной информации

Также можно определить энтропию случайной величины, введя предварительно понятия распределения случайной величины ${\displaystyle X}$ , имеющей конечное число значений:^[3]

${\displaystyle P_{X}(x_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots ,\;n}$

${\displaystyle \sum _{i=1}^{n}p_{i}=1}$

и собственной информации:

${\displaystyle I(X)=-\log P_{X}(X).}$

Тогда энтропия определяется как:

${\displaystyle H(X)=E(I(X))=-\sum _{i=1}^{n}p(i)\log p(i).}$

Единицы измерения информационной энтропии

От основания логарифма зависит единица измерения количества информации и энтропии: бит, нат, трит или хартли.

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

1. Неотрицательность: ${\displaystyle H(X)\geqslant 0}$ .
2. Ограниченность: ${\displaystyle H(X)=-E(\log _{2}p_{i})=\sum _{i=1}^{n}p_{i}\log _{2}{\frac {1}{p_{i}}}=\sum _{i=1}^{n}p_{i}f(g_{i})\leqslant f\left(\sum _{i=1}^{n}p_{i}g_{i}\right)=\log _{2}n}$ , что вытекает из неравенства Йенсена для вогнутой функции ${\displaystyle f(g_{i})=\log _{2}g_{i}}$ и ${\displaystyle g_{i}={\frac {1}{p_{i}}}}$ . Если все ${\displaystyle n}$ элементов из ${\displaystyle X}$ равновероятны, ${\displaystyle H(X)=\log _{2}n}$ .
3. Если ${\displaystyle X,\;Y}$ независимы, то ${\displaystyle H(X\cdot Y)=H(X)+H(Y)}$ .
4. Энтропия — выпуклая вверх функция распределения вероятностей элементов.
5. Если ${\displaystyle X,\;Y}$ имеют одинаковое распределение вероятностей элементов, то ${\displaystyle H(X)=H(Y)}$ .

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

Алфавит может иметь вероятностное распределение далекое от равномерного. Если исходный алфавит содержит ${\displaystyle n}$ символов, тогда его можно сравнить с «оптимизированным алфавитом», вероятностное распределение которого равномерное. Соотношение энтропии исходного и оптимизированного алфавита — это эффективность исходного алфавита, которая может быть выражена в процентах. Эффективность исходного алфавита с ${\displaystyle n}$ символами может быть также определена как его ${\displaystyle n}$ -арная энтропия.

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически — типичного набора или, на практике, — кодирования Хаффмана, кодирования Лемпеля — Зива — Велча или арифметического кодирования.

b-арная энтропия

В общем случае b-арная энтропия (где b равно 2, 3, …) источника ${\displaystyle {\mathcal {S}}=(S,\;P)}$ с исходным алфавитом ${\displaystyle S=\{a_{1},\;\ldots ,\;a_{n}\}}$ и дискретным распределением вероятности ${\displaystyle P=\{p_{1},\;\ldots ,\;p_{n}\},}$ где ${\displaystyle p_{i}}$ является вероятностью ${\displaystyle a_{i}}$ (${\displaystyle p_{i}=p(a_{i})}$ ), определяется формулой:

${\displaystyle H_{b}({\mathcal {S}})=-\sum _{i=1}^{n}p_{i}\log _{b}p_{i}.}$

В частности, при ${\displaystyle b=2}$ , мы получаем обычную двоичную энтропию, измеряемую в битах. При ${\displaystyle b=3}$ , мы получаем тринарную энтропию, измеряемую в тритах (один трит имеет источник информации с тремя равновероятными состояниями). При ${\displaystyle b=e}$ , мы получаем информацию измеряемую в натах.

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

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

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

${\displaystyle H_{1}({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\log _{2}p_{i}(j),}$

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

Например, для русского языка без буквы «ё» ${\displaystyle H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01}$ ^[4].

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы. Для описания потерь со стороны источника (то есть известен посланный сигнал) рассматривают условную вероятность ${\displaystyle p(b_{j}\mid a_{i})}$ получения приёмником символа ${\displaystyle b_{j}}$ при условии, что был отправлен символ ${\displaystyle a_{i}}$ . При этом канальная матрица имеет следующий вид:

	${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	…	${\displaystyle b_{j}}$	…	${\displaystyle b_{m}}$
${\displaystyle a_{1}}$	${\displaystyle p(b_{1}\mid a_{1})}$	${\displaystyle p(b_{2}\mid a_{1})}$	…	${\displaystyle p(b_{j}\mid a_{1})}$	…	${\displaystyle p(b_{m}\mid a_{1})}$
${\displaystyle a_{2}}$	${\displaystyle p(b_{1}\mid a_{2})}$	${\displaystyle p(b_{2}\mid a_{2})}$	…	${\displaystyle p(b_{j}\mid a_{2})}$	…	${\displaystyle p(b_{m}\mid a_{2})}$
…	…	…	…	…	…	…
${\displaystyle a_{i}}$	${\displaystyle p(b_{1}\mid a_{i})}$	${\displaystyle p(b_{2}\mid a_{i})}$	…	${\displaystyle p(b_{j}\mid a_{i})}$	…	${\displaystyle p(b_{m}\mid a_{i})}$
…	…	…	…	…	…	…
${\displaystyle a_{m}}$	${\displaystyle p(b_{1}\mid a_{m})}$	${\displaystyle p(b_{2}\mid a_{m})}$	…	${\displaystyle p(b_{j}\mid a_{m})}$	…	${\displaystyle p(b_{m}\mid a_{m})}$

Очевидно, вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый сигнал ${\displaystyle a_{i}}$ , описываются через частную условную энтропию:

${\displaystyle H(B\mid a_{i})=-\sum _{j=1}^{m}p(b_{j}\mid a_{i})\log _{2}p(b_{j}\mid a_{i}).}$

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

${\displaystyle H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i}).}$

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

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

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

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий ${\displaystyle p(a_{i}b_{j})}$ , и для полного описания характеристик канала требуется только одна матрица:

${\displaystyle p(a_{1}b_{1})}$	${\displaystyle p(a_{1}b_{2})}$	…	${\displaystyle p(a_{1}b_{j})}$	…	${\displaystyle p(a_{1}b_{m})}$
${\displaystyle p(a_{2}b_{1})}$	${\displaystyle p(a_{2}b_{2})}$	…	${\displaystyle p(a_{2}b_{j})}$	…	${\displaystyle p(a_{2}b_{m})}$
…	…	…	…	…	…
${\displaystyle p(a_{i}b_{1})}$	${\displaystyle p(a_{i}b_{2})}$	…	${\displaystyle p(a_{i}b_{j})}$	…	${\displaystyle p(a_{i}b_{m})}$
…	…	…	…	…	…
${\displaystyle p(a_{m}b_{1})}$	${\displaystyle p(a_{m}b_{2})}$	…	${\displaystyle p(a_{m}b_{j})}$	…	${\displaystyle p(a_{m}b_{m})}$

Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером ${\displaystyle j}$ даёт ${\displaystyle p(b_{j})}$ , сумма строки с номером ${\displaystyle i}$ есть ${\displaystyle p(a_{i})}$ , а сумма всех элементов матрицы равна 1. Совместная вероятность ${\displaystyle p(a_{i}b_{j})}$ событий ${\displaystyle a_{i}}$ и ${\displaystyle b_{j}}$ вычисляется как произведение исходной и условной вероятности:

${\displaystyle p(a_{i}b_{j})=p(a_{i})p(b_{j}\mid a_{i})=p(b_{j})p(a_{i}\mid b_{j}).}$

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

${\displaystyle H(A)=-\sum _{i}\left(\sum _{j}p(a_{i}b_{j})\log \sum _{j}p(a_{i}b_{j})\right),}$

${\displaystyle H(B)=-\sum _{j}\left(\sum _{i}p(a_{i}b_{j})\log \sum _{i}p(a_{i}b_{j})\right).}$

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

${\displaystyle H(AB)=-\sum _{i}\sum _{j}p(a_{i}b_{j})\log p(a_{i}b_{j}).}$

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

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

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