Как найти энтропию алфавита - Сайт, где вы сможете решить свои вопросы

Теория информации

Энтропия Дифференциальная энтропия Условная энтропия Совместная энтропия Взаимная информация Условная взаимная информация Относительная энтропия Энтропийная скорость
Свойство асимптотической равнораспределенности Теория частотных искажений
Теорема Шеннона об источнике шифрования Пропускная способность Теоремы Шеннона для канала с шумами Теорема Шеннона — Хартли

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

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

Формальные определения[править | править код]

Информационная двоичная энтропия, при отсутствии информационных потерь, рассчитывается по формуле Хартли:

${displaystyle I=log _{2}N}$ ,

где — мощность алфавита, — количество информации в каждом символе сообщения. Для случайной величины , принимающей независимых случайных значений $x_{i}$ с вероятностями $p_{i}$ (), формула Хартли переходит в формулу Шеннона:

${displaystyle H(x)=-sum _{i=1}^{n}p_{i}log _{2}p_{i}.}$

Здесь ${displaystyle (-log_{2}p_{i})}$ означает измеряемое в битах количество информации, содержащейся в том событии, что случайная величина приняла значение $x_{i}$ (для предложений на русском языке – количество информации, содержащейся в конкретной букве, имеющей номер в русском алфавите, ),

а H(x) означает количество информации, которое в среднем приходится на одно событие (для предложений на русском языке – количество информации, которое в среднем содержится в одной букве).

Эта величина также называется средней энтропией сообщения и означает измеряемое в битах среднее количество информации на символ передаваемого сообщения. Величина ${displaystyle H_{i}=-log _{2}{p_{i}}}$ называется частной энтропией, характеризующей только -e состояние.

Таким образом, энтропия системы является суммой с противоположным знаком всех относительных частотностей появления состояния (события) с номером , умноженных на их же двоичные логарифмы^[1]. Это определение для дискретных случайных событий можно формально расширить для непрерывных распределений, заданных плотностью распределения вероятностей, однако полученный функционал будет обладать несколько иными свойствами (см. дифференциальная энтропия).

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

Определение по Шеннону[править | править код]

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

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

Поэтому функция энтропии должна удовлетворять условиям

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

$Hunderbrace {left({frac {1}{n}},;ldots ,;{frac {1}{n}}right)}_{n}<Hunderbrace {left({frac {1}{n+1}},;ldots ,;{frac {1}{n+1}}right)}_{{n+1}}.$
Для целых положительных $b_{i}$ , где $b_{1}+ldots +b_{k}=n$ , должно выполняться равенство

$Hunderbrace {left({frac {1}{n}},;ldots ,;{frac {1}{n}}right)}_{n}=Hleft({frac {b_{1}}{n}},;ldots ,;{frac {b_{k}}{n}}right)+sum _{{i=1}}^{k}{frac {b_{i}}{n}}Hunderbrace {left({frac {1}{b_{i}}},;ldots ,;{frac {1}{b_{i}}}right)}_{{b_{i}}}.$

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

$-Ksum _{{i=1}}^{n}p(i)log _{2}p(i),$

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

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

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

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

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

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

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

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

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

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

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

Единицы измерения информационной энтропии[править | править код]

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

Свойства[править | править код]

Энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию:

$-2left({frac {1}{2}}log _{2}{frac {1}{2}}right)=-log _{2}{frac {1}{2}}=log _{2}2=1$

бит на одно кидание (при условии его независимости), а количество возможных состояний равно: $2^{1}=2$

возможных состояния (значения) («орёл» и «решка»).

У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: $-sum _{{i=1}}^{infty }log _{2}1=0$ , а количество возможных состояний равно: $2^{0}=1$ возможное состояние (значение) («А») и от основания логарифма не зависит.
Это тоже информация, которую тоже надо учитывать. Примером запоминающих устройств, в которых используются разряды с энтропией, равной нулю, но с количеством информации, равным одному возможному состоянию, то есть не равным нулю, являются разряды данных записанных в ПЗУ, в которых каждый разряд имеет только одно возможное состояние.

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

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

Математические свойства[править | править код]

Неотрицательность: .
Ограниченность: ${displaystyle H(X)=-mathop {mathbb {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 fleft(sum _{i=1}^{n}p_{i}g_{i}right)=log _{2}n}$ , что вытекает из неравенства Йенсена для вогнутой функции $f(g_{i})=log _{2}g_{i}$ и $g_{i}={frac {1}{p_{i}}}$ . Если все элементов из равновероятны, $H(X)=log _{2}n$ .
Если независимы, то .
Энтропия — выпуклая вверх функция распределения вероятностей элементов.
Если имеют одинаковое распределение вероятностей элементов, то .

Эффективность[править | править код]

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

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

Вариации и обобщения[править | править код]

b-арная энтропия[править | править код]

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

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

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

Условная энтропия[править | править код]

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

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

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

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

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

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

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

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

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

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

$H(Bmid A)=sum _{i}p(a_{i})H(Bmid a_{i}).$

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

Взаимная энтропия[править | править код]

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

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

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

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

$p(a_{i}b_{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)=-sum _{i}sum _{j}p(a_{i}b_{j})log p(a_{i}b_{j}).$

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

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

История[править | править код]

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

Понятие энтропии как меры случайности введено Шенноном в его статье «Математическая теория связи» (англ. A Mathematical Theory of Communication), опубликованной в двух частях в Bell System Technical Journal в 1948 году.

Примечания[править | править код]

↑ Данное представление удобно для работы с информацией, представленной в двоичной форме; в общем случае основание логарифма может быть другим.
↑ Shannon, Claude E. A Mathematical Theory of Communication (неопр.) // Bell System Technical Journal (англ.) (рус.. — 1948. — July (т. 27, № 3). — С. 419. — doi:10.1002/j.1538-7305.1948.tb01338.x. Архивировано 1 августа 2016 года.
↑ Габидулин Э. М., Пилипчук Н. И. Лекции по теории информации — МФТИ, 2007. — С. 16. — 214 с. — ISBN 978-5-7417-0197-3
↑ Лебедев Д. С., Гармаш В. А. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958. — № 1. — С. 68—69.

См. также[править | править код]

Дифференциальная энтропия (энтропия для непрерывного распределения)
Взаимная информация
Энтропийное кодирование
Цепь Маркова
Расстояние Кульбака — Лейблера

Ссылки[править | править код]

Shannon Claude E. A Mathematical Theory of Communication Архивная копия от 31 января 1998 на Wayback Machine (англ.)
Коротаев С. М. Энтропия и информация — универсальные естественнонаучные понятия.

Литература[править | править код]

Шеннон К. Работы по теории информации и кибернетике. — М.: Изд. иностр. лит., 2002.
Волькенштейн М. В. Энтропия и информация. — М.: Наука, 2006.
Цымбал В. П. Теория информации и кодирование. — К.: Вища Школа, 2003.
Martin, Nathaniel F.G. & England, James W. Mathematical Theory of Entropy. — Cambridge University Press, 2011. — ISBN 978-0-521-17738-2.
Шамбадаль П. Развитие и приложение понятия энтропии. — М.: Наука, 1967. — 280 с.
Мартин Н., Ингленд Дж. Математическая теория энтропии. — М.: Мир, 1988. — 350 с.
Хинчин А. Я. Понятие энтропии в теории вероятностей // Успехи математических наук. — Российская академия наук, 1953. — Т. 8, вып. 3(55). — С. 3—20.
Брюллюэн Л. Наука и теория информации. — М., 1960.
Винер Н. Кибернетика и общество. — М., 1958.
Винер Н. Кибернетика или управление и связь в животном и машине. — М., 1968.
Петрушенко Л. А. Самодвижение материи в свете кибернетики. — М., 1974.
Эшби У. Р. Введение в кибернетику. — М., 1965.
Яглом А. М., Яглом И. М. Вероятность и информация. — М., 1973.
Волькенштейн М. В. Энтропия и информация. — М.: Наука, 1986. — 192 с.
Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. — М.: ФМОП, МЦНМО, 2012. — 238 с. — ISBN 978-5-94057-920-5.

Источник

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

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

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

Формальные определения

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

${displaystyle H(x)=-sum _{i=1}^{n}p(i)log _{2}p(i)}$

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

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

Шеннон вывел это определение энтропии из следующих предположений:

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

Шеннон показал, что любое определение энтропии, удовлетворяющее этим предположениям, должно быть в форме:

${displaystyle -Ksum _{i=1}^{n}p(i)log _{2}p(i)}$

где K — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии (H = − p₁ log₂ p₁ − … − p_n log₂ p_n), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надежной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидания «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д. См. Цепи Маркова.

В общем случае b-арная энтропия (где b равно 2,3,… ) источника = (S,P) с исходным алфавитом S = {a₁, …, a_n} и дискретным распределением вероятности P = {p₁, …, p_n} где p_i является вероятностью a_i (p_i = p(a_i)) определяется формулой:

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle displaystyle H(B|A)=sum _{i}p(a_{i})H(B|a_{i})}$

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

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

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

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

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

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

${displaystyle displaystyle p(a_{i}b_{j})=p(a_{i})p(b_{j}|a_{i})=p(b_{j})p(a_{i}|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 displaystyle H(AB)=-sum _{i}sum _{j}p(a_{i}b_{j})log p(a_{i}b_{j})}$

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

{displaystyle displaystyle H(AB)=H(A)+H(B|A)=H(B)+H(A|B).}

Свойства

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию ${displaystyle -2(0,5log _{2}0,5)=1}$ бита на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: ${displaystyle -sum _{i=1}^{infty }log _{2}1=0}$ . Так, к примеру, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

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

Альтернативное определение

Другим способом определения функции энтропии H является доказательство, что H однозначно определена (как указано ранее), если и только если H удовлетворяет пунктам 1)—3):

1) H(p₁, …, p_n) определена и непрерывна для всех p₁, …, p_n, где p_i [0,1] для всех i = 1, …, n и p₁ + … + p_n = 1. (Заметьте, что эта функция зависит только от распределения вероятностей, а не от алфавита.)

2) Для целых положительных n, должно выполняться следующее неравенство:

${displaystyle Hunderbrace {left({frac {1}{n}},ldots ,{frac {1}{n}}right)} _{n mathrm {arguments} }<Hunderbrace {left({frac {1}{n+1}},ldots ,{frac {1}{n+1}}right).} _{n+1 mathrm {arguments} }}$

3) Для целых положительных b_i, где b₁ + … + b_n = n, должно выполняться равенство:

${displaystyle Hleft({frac {1}{n}},ldots ,{frac {1}{n}}right)=Hleft({frac {b_{1}}{n}},ldots ,{frac {b_{k}}{n}}right)+sum _{i=1}^{k}{frac {b_{i}}{n}}Hleft({frac {1}{b_{i}}},ldots ,{frac {1}{b_{i}}}right).}$

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

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

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

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

История

В 1948 году, исследуя проблему рациональной передачи информации через зашумленный коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки двух основных направлений: теории информации, которая использует понятие вероятности и эргодическую теорию для изучения статистических характеристик данных и коммуникационных систем, и теории кодирования, в которой используются главным образом алгебраические и геометрические инструменты для разработки эффективных шифров.

Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.

Литература

↑ Д.С. Лебедев, В.А. Гармаш. О возможности увеличения скорости передачи телеграфных сообщений. — М.:Электросвязь, 1958, №1. с.68-69

2.Цымбал В.П. Теория информации и кодирование. — К.:Выща Школа, 1977. — 288 с.

См. также

Энтропийное кодирование
Цепь Маркова
Для понимания информационной энтропии можно прибегнуть к примеру из области термодинамической энтропии получившему широко известное название Демона Максвелла.

Внешние ссылки

http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html
С.М. Коротаев. Энтропия и информация — Универсальные естественнонаучные понятия

Эта статья содержит материал из статьи Информационная энтропия русской Википедии.

Источник

Источник: Nuances of Programming

Индонезийские пещеры острова Борнео дают представление о самой примитивной зарегистрированной форме коммуникации. Около 40000 лет назад, ещё до развития письменного языка, физические иллюстрации на стенах пещеры были наиболее систематическим зарегистрированным способом общения. С течением времени методология записи эволюционировала от наскальных рисунков до сложных алфавитов, предлагая полноценное выражение с помощью сложной структуры называемой язык. В английском языке идеи, столь же чёткие, как “дерево”, и столь же неоднозначные, как “любовь”, выражаются с помощью 26 букв, не имея никакой внутренней ценности кроме той, которую в них вкладывает общество.

Информация в контексте недавно развившейся области определяется как разрешение неопределённости (или неожиданности). Рассмотрим сообщение о существовании дерева. Например, на фиксированном изображении форма, цвет и даже относительный размер соседних деревьев прекрасно видны, но является ли эта информация предельно точной? Относительно. Несоответствие проявляется только при сравнении с дополнительной информацией, предоставленной письменным языком. С неограниченным запасом слов язык предлагает намного более глубокую описательную информацию, которую невозможно увидеть на изображении, например, где дерево было выращено, кем и в какой почве. Различные методы коммуникации подразумевают различия в сообщаемой неопределённости.

Отец теории информации, математик Массачусетского технологического института Клод Шеннон, блистательно представил логический математический способ измерения этого различия в зарегистрированных методах коммуникации: он определил её как энтропию. Энтропия дополняет математический набор инструментов для измерения взаимосвязи между принципами неупорядоченности и неопределённости. Высокий уровень энтропии указывает на высокий уровень неопределённости информации. Или, на практике, на более высокое число возможных выводов функции. Прежде чем перейти к современной формуле измерения информации, вернёмся назад в 1920–е, когда Ральф Хартли вывел первую формулу на основе работ Генри Найквиста.

Ранняя энтропия — мера неопределённости

Информация определяется как разрешение неопределённости: если для определения значения не требуется никаких вопросов, то предоставляемой информации не существует. Энтропия напрямую соотносится с информацией системы. Чем выше энтропия, тем больше неопределённости связано с определением символа (числа, буквы и т.д.). Энтропия, или неопределённость, математически максимальна, когда символ может в равной степени иметь множество значений (равномерное распределение). Простейшая единица энтропии — символ, в равной степени способный принимать одно из двух значений. Бросок монеты, например, имеет двоичное свойство — либо орёл, либо решка.

На графике по оси y, H(x), отображается энтропия для символа с двумя возможностями (двоичная). Заметьте, что энтропия, или неопределённость, максимальна (равна 1) в середине графика. Объяснение интуитивно понятно: когда мы бросаем монетку, неопределённость исхода максимальна, когда монета находится в воздухе. Соответственно энтропия минимальна (равна 0) на противоположных концах оси x, когда мы точно знаем значение двоичного символа. Имея это в виду, можно смело утверждать, что подбрасывание монетки, вопросы типа “да/нет”, логические значения и двоичные числа (0 или 1) математически эквивалентны — на графике все они представлены в терминах теории информации.

Символ с двоичным свойством, называющийся “бит”, является базовой единицей энтропии, используемой во всей теории информации.

Хронологически термин “бит” не был общепринятым до довольно позднего времени, однако мы используем его сейчас для простоты понимания, поскольку приближаемся к современной теории информации. Забавный факт: слово “бит” образовано от слов binary digit — двоичное число.

Резонно предположить, что предполагаемое сообщение с решением за один шаг (один бит, бросок монеты, ответ на вопрос типа “да/нет”, логическое значение неопределённости) имеет меньшее значение энтропии, чем решения в два или более шагов. Например, рассмотрим бросок монеты. При попытке определить, выпадет орёл или решка, для разгадки значения “выпал орёл?” достаточно одного бита. В любом случае мы уверены в том, что значение будет получено с первой попытки. Энтропия этой задачи равна единице, поскольку ответ определяется за один шаг:

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

Что, если отправить сообщение из трёх символов (все биты)?

Продолжая пример выше, скажем, мы хотим отправить трёхсимвольное сообщение из трёх бросков монет. Общее число возможных сообщений теперь равно восьми (2³), но энтропия этого сообщения равна трём. Помним, что энтропия — это не количество возможных сообщений, а минимальное число вопросов, необходимых для определения сообщения.

Что, если отправить сообщение с единственным не двоичным символом?

Теперь, допустим, мы хотим отправить один символ, что означает, что символ может быть любой из двадцати шести букв (1/26). Каково будет значение энтропии на этот раз? То есть, на сколько вопросов типа “да/нет” мы должны ответить, чтобы определить, например, букву J?

Проще всего запрашивать в алфавитном порядке “является ли X предполагаемой буквой?”. Например, “нам нужна А буква? Как насчёт B? Или C?…”. С помощью этого метода для определения одного символа в среднем нам понадобится 13 вопросов типа “да/нет” (или 13 бит энтропии). Однако здесь есть большая оговорка: для измерения информации необходим наиболее эффективный способ присвоения значения символам. В отличие от индивидуального поиска по порядку, мы заимствуем концепцию алгоритма двоичного поиска. При повторном поиске буквы Jспрашиваем, находится ли искомая буква в первой половине алфавита? Да. Далее делим оставшийся массив пополам и спрашиваем, попадает ли искомый символ в первые 6 букв (A-F)? Нет. И так далее, пока не найдём искомый символ — J. Заметьте, что подобный способ поиска значения гораздо более эффективен. В отличие от среднего значения из 13 вопросов “да/нет”, со вторым методом нам никогда не понадобится более 5 вопросов (иногда только 4).

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

Формула выше даёт приблизительное количество энтропии (4,7 бит), связанное с отправкой одного случайного символа алфавита. Как заключил Ральф Хартли в своей выдающейся статье “Передача информации”:

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

Его раннее определение информации немного отличалось в нотации. Он определил H (информацию) как H = n log (s), где H — это информация, n — количество символов (букв, чисел и т.д.), а s — количество различных символов, доступных при каждой выборке (по сути, длина области сообщений).

Khan Academy

Всё ещё не совсем современная теория информации, но мы уже твёрдо установили следующее:

Теория информации предоставляет способ количественной оценки неожиданностей для коммуникационных событий.
Энтропия или неопределённость — это мера минимального числа вопросов типа “да/нет”, необходимых для определения значения символа.
Двоичное число, он же бит, имеет энтропию 1 и, следовательно, является базовой единицей этой области математики.
Вывели раннюю функцию информации, которая принимает набор равномерно распределённых значений символов.

До этого момента мы предполагали, что каждое значение в наборе символов является случайным образом дискретным, однако на самом деле это целесообразное упрощение. Как мы знаем, реальность не так аккуратна, и значения символов не эквиваленты. Существуют органичные, измеримые модели нашего языка и других форм коммуникации. В качестве быстрого мысленного эксперимента вычислим количество букв “e” в предыдущем предложении. Является ли это распределение равномерным распределением 1/26?

Когда символы не случайны — цепи Маркова

Перенесёмся в 1948 год, когда отец современной теории информации, Клод Шеннон, в своей новаторской работе “Математическая теория связи” предположил, что существуют модели в коммуникации, которые можно использовать для вывода одного и того же сообщения или значения в несколько шагов, то есть битов.

Письменный язык предлагает шаблоны, которые делают следующее значение в последовательности более предсказуемым благодаря предыдущим значениям.

Другими словами, предыдущее значение делает следующее менее неопределённым, то есть уменьшает энтропию. Наилучшим примером является предсказуемость появления буквы ‘U’ после ‘Q’ в английском письменном языке. Если за ‘Q’ следует ‘U’ в 90% случаях, потенциальный выход следующей буквы больше не находится в равновесии со всей системой, он смещается к значению ‘Q’ со скоростью 90%.

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

Анализ частоты повторения букв

С учётом зависимости “За ‘Q’ следует ‘U’ с вероятностью 9/10 ‘U’” (P(Xi)), энтропия, или неопределённость появления ‘U’ за ‘Q’, равна H(X) = 0.13 бит. Энтропия любого значения полностью случайного алфавита равна H(X) = 4.7 бит. С этим подходом энтропия уменьшается на поразительные 4.57 бита. Вместо деления алфавита пополам на первом этапе вопрос, разрешающий большинство информационных состояний, будет сформулирован как “Значение равно ‘U’?”. В 90% случаев это будет правдой, а энтропия будет только 1 бит, что позволяет убрать лишние вопросы и понизить общую энтропию системы. Благодаря компьютерному анализу миллионов текстов, были выведены стандартные распределения каждой буквы английского языка. Это стандартные вероятности, которые можно использовать для независимых событий. Принимая во внимание зависимые выходные значения (цепь Маркова), были установлены также частотные зависимости повторения букв.

Повторный вывод формулы информации/энтропии

Шеннон модернизировал теорию информации, развивая функцию Хартли. Для набора случайных равномерных значений X мы вычисляем энтропию кодирования единичного символа с помощью log от X по основанию 2. Для набора взаимосвязанных значений X мы вычисляем энтропию единичного символа, складывая индивидуальные значения энтропии для каждого индивидуального возможного значения символа в наборе:

Однако вышеприведённая формула предполагает равномерное распределение, что, как мы знаем благодаря цепи Маркова, не является истиной. Чтобы учесть это, в формулу нужно добавить умножение на частотную вероятность каждого значения символа x, (p(x)):

Наконец, нужно заменить n внутри логарифма. Мы рассчитываем количество вопросов типа “да/нет”, необходимых для получения каждого отдельного символа, а не общего результата. Продолжая пример с алфавитом, мы знаем из цепи Маркова, что для угадывания символа e или z требуется неравное количество битов. Следовательно, для каждой суммы нам нужно число конкретных результатов, и мы знаем, что это не 26, а (1 / p(x)):

Формула, которую мы только что вывели — это формула, выведенная Клодом Шенноном и сделавшая его отцом теории информации. Он немного переставил символы выше. Вот это уравнение лежит в основе современной теории информации:

Ian Stewart

H(x) — это энтропия, мера неопределённости, связанная с установленной переменной X. P(x) — это вероятность вывода x в переменной X. И log(1/p(x)) по основанию 2 — это количество битов, необходимое для расшифровки вывода x переменной X. Ещё раз: базовая единица, которой равна H(x), определяется в битах.

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

Напомним, что мы рассчитали энтропию H(x) = 4.7 для единичного символа алфавита. Давайте сравним ее с H(x), вычисленной по обновлённой формуле:

Использованные здесь марковские % — это значения из графика выше

Как видим из суммы справа внизу, это интуитивное значение проверяется итоговым значением энтропии H(x) = 4.18. Уже с этой формулой энтропии теория информации и её приложения развиваются всё быстрее с 1950-х.

Посмотрим на приложения

Изученные здесь концепции, построенные на математическом понятии, узнаваемы и мощны в цифровую эпоху. Вероятно одним из наиболее распространённых и влиятельных применений теории информации является сжатие информации без потерь. Эта форма сжатия используется в записях баз данных, текстовых файлах, изображениях и видеофайлах. В этой форме данные можно полностью восстановить до исходного состояния. Используя принципы энтропии Шеннона и цепи Маркова,можно получить безошибочную информацию. Эта способность к сжатию позволила массово производить устройства, способные хранить огромные объёмы данных. Особенно впечатляет это в музыкальных файлах. В ранние годы звукозапись опиралась на виниловые пластинки — несжатый формат информации. Запись на пластинке хранит альбом в несжатом состоянии без потерь. С современными технологиями музыкальные файлы сжимаются и содержат биты, относящиеся к высоте, громкости, резонансу и т.д. Другой убедительный пример — это увеличение возможностей аппаратного хранения.

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