Усредненная энтропия


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

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

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

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


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

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

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

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

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

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

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


$ -Ksum_{i=1}^np(i)log_2 p(i) $

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

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

В общем случае b-арная энтропия (где b равно 2,3,… ) источника $ mathcal{S} $ = (S,P) с исходным алфавитом S = {a1, …, an} и дискретным распределением вероятности P = {p1, …, pn} где pi является вероятностью ai (pi = p(ai)) определяется формулой:


$ H_b(mathcal{S}) = — sum_{i=1}^n p_i log_b p_i $

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

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

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

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

$ 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 $ был предыдущим символом.


Так, для русского алфавита без буквы «ё» $ H_0=5, H_1=4,358, H_2=3,52, H_3=3,01 $[1]

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются т.н. канальные матрицы. Так, для описания потерь со стороны источника (т.е. известен посланный сигнал), рассматривают условную вероятность $ displaystyle p(b_j|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|a_1) $ $ displaystyle p(b_2|a_1) $ $ displaystyle p(b_j|a_i) $ $ displaystyle p(b_m|a_1) $
$ displaystyle a_2 $ $ displaystyle p(b_1|a_2) $ $ displaystyle p(b_2|a_2) $ $ displaystyle p(b_j|a_2) $ $ displaystyle p(b_m|a_2) $
$ displaystyle a_i $ $ displaystyle p(b_1|a_i) $ $ displaystyle p(b_2|a_i) $ $ displaystyle p(b_j|a_i) $ $ displaystyle p(b_m|a_i) $
$ displaystyle a_m $ $ displaystyle p(b_1|a_m) $ $ displaystyle p(b_2|a_m) $ $ displaystyle p(b_j|a_m) $ $ displaystyle p(b_m|a_m) $

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

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

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

$ displaystyle H(B|A)=sum_i p(a_i)H(B|a_i) $

$ displaystyle H(B|A) $ означает энтропию со стороны источника, аналогично рассматривается $ displaystyle H(A|B) $ — энтропия со стороны приёмника: вместо $ displaystyle p(b_j|a_i) $ всюду указывается $ displaystyle p(a_i|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_i 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_ib_j) $ событий $ displaystyle a_i $ и $ displaystyle b_j $ вычисляется как произведение исходной и условной вероятности,

$ displaystyle p(a_ib_j)=p(a_i)p(b_j|a_i)=p(b_j)p(a_i|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) $

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

$ 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|A) = H(B)+H(A|B). $

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

Свойства


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

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

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

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

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


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

$ 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) Для целых положительных bi, где b1 + … + bn = n, должно выполняться равенство:

$ 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 году.

Литература

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

См. также

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

Источник: math.wikia.org

Этот пост является вольным переводом ответа, который Mark Eichenlaub дал на вопрос What’s an intuitive way to understand entropy?, заданный на сайте Quora

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

Если в двух словах, то

Энтропия — это то, как много информации вам не известно о системе

Например, если вы спросите меня, где я живу, и я отвечу: в России, то моя энтропия для вас будет высока, всё-таки Россия большая страна. Если же я назову вам свой почтовый индекс: 603081, то моя энтропия для вас понизится, поскольку вы получите больше информации.
почтовый индекс
Почтовый индекс содержит шесть цифр, то есть я дал вам шесть символов информации. Энтропия вашего знания обо мне понизилась приблизительно на 6 символов. (На самом деле, не совсем, потому что некоторые индексы отвечают большему количеству адресов, а некоторые — меньшему, но мы этим пренебрежём).
игральные кости
Или рассмотрим другой пример. Пусть у меня есть десять игральных костей (шестигранных), и выбросив их, я вам сообщаю, что их сумма равна 30. Зная только это, вы не можете сказать, какие конкретно цифры на каждой из костей — вам не хватает информации. Эти конкретные цифры на костях в статистической физике называют микросостояниями, а общую сумму (30 в нашем случае) — макросостоянием. Существует 2 930 455 микросостояний, которые отвечают сумме равной 30. Так что энтропия этого макросостояния равна приблизительно 6,5 символам (половинка появляется из-за того, что при нумерации микросостояний по порядку в седьмом разряде вам доступны не все цифры, а только 0, 1 и 2).

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

Пусть теперь я вам скажу, что сумма первых пяти костей 13, а сумма остальных пяти — 17, так что общая сумма снова 30. У вас, однако, в этом случае имеется больше информации, поэтому энтропия системы для вас должна упасть. И, действительно, 13 на пяти костях можно получить 420-ю разными способами, а 17 — 780-ю, то есть полное число микросостояний составит всего лишь 420х780 = 327 600. Энтропия такой системы приблизительно на один символ меньше, чем в первом примере.

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

S = log Ω

Это есть ничто иное как формула Больцмана (с точностью до множителя k, который зависит от выбранных единиц измерения) для энтропии. Если макросостоянию отвечают одно микросостояние, его энтропия по этой формуле равна нулю. Если у вас есть две системы, то полная энтропия равна сумме энтропий каждой из этих систем, потому что log(AB) = log A + log B.
больцман
Из приведённого выше описания становится понятно, почему не следует думать об энтропии как о собственном свойстве системы. У системы есть опеделённые внутренняя энергия, импульс, заряд, но у неё нет определённой энтропии: энтропия десяти костей зависит от того, известна вам только их полная сумма, или также и частные суммы пятёрок костей.

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

Классической системой, которую рассматривают в физике, является газ, находящийся в сосуде под поршнем. Микросостояние газа — это положение и импульс (скорость) каждой его молекулы. Это эквивалентно тому, что вы знаете значение, выпавшее на каждой кости в рассмотренном раньше примере. Макросостояние газа описывается такими величинами как давление, плотность, объём, химический состав. Это как сумма значений, выпавших на костях.
газ в сосуде под поршнем
Величины, описывающие макросостояние, могут быть связаны друг с другом через так называемое «уравнение состояния». Именно наличие этой связи позволяет, не зная микросостояний, предсказывать, что будет с нашей системой, если начать её нагревать или перемещать поршень. Для идеального газа уравнение состояния имеет простой вид:

p = ρT

хотя вы, скорее всего, лучше знакомы с уравнением Клапейрона — Менделеева pV = νRT — это то же самое уравнение, только с добавлением пары констант, чтобы вас запутать. Чем больше микросостояний отвечают данному макросостоянию, то есть чем больше частиц входят в состав нашей системы, тем лучше уравнение состояния её описывают. Для газа характерные значения числа частиц равны числу Авогадро, то есть составляют порядка 1023.

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

Как меняется энтропия с изменением макросостояния? Это легко понять. Например, если мы немного нагреем газ, то скорость его частиц возрастёт, следовательно, возрастёт и степень нашего незнания об этой скорости, то есть энтропия вырастет. Или, если мы увеличим объём газа, отведя поршень, увеличится степень нашего незнания положения частиц, и энтропия также вырастет.

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

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

Второй закон термодинамики утверждает, что энтропия (замкнутой системы) никогда не уменьшается. Мы теперь можем понять, почему: потому что невозможно внезапно получить больше информации о микросостояниях. Как только вы потеряли некую информацию о микросостоянии (как во время удара куска металла об землю), вы не можете вернуть её назад.
нельзя просто так взять и объяснить второй закон термодинамики
Давайте вернёмся обратно к игральным костям. Вспомним, что макросостояние с суммой 59 имеет очень низкую энтропию, но и получить его не так-то просто. Если бросать кости раз за разом, то будут выпадать те суммы (макросостояния), которым отвечает большее количество микросостояний, то есть будут реализовываться макросостояния с большой энтропией. Самой большой энтропией обладает сумма 35, и именно она и будет выпадать чаще других. Именно об этом и говорит второй закон термодинамики. Любое случайное (неконтролируемое) взаимодействие приводит к росту энтропии, по крайней мере до тех пор, пока она не достигнет своего максимума.

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

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

Ну и напоследок рассмотрим решение в рамках нашей парадигмы знаменитого парадокса демона Максвелла. Напомню, что он заключается в следующем. Пусть у нас есть перемешанные газы из синих и красных молекул. Поставим обратно перегородку, проделав в ней небольшое отверстие, в которое посадим воображаемого демона. Его задача — пропускать слева направо только красных, и справа налево только синих. Очевидно, что через некоторое время газы снова будут разделены: все синие молекулы окажутся слева от перегородки, а все красные — справа.
демон максвелла
Получается, что наш демон понизил энтропию системы. С демоном ничего не случилось, то есть его энтропия не изменилась, а система у нас была закрытой. Получается, что мы нашли пример, когда второй закон термодинамики не выполняется! Как такое оказалось возможно?

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

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

Источник: habr.com

Пусть имеются две зависимые системы (или два множества сообщений) X и Y. Обозначим условную вероятность Усредненная энтропия того, что система Y примет состояние yj при условии, что система X приняла xi.

Определим условную частную энтропию системы Y относительно отдельного события xi. При этом должны быть известны условные вероятности .

Усредненная энтропия

Тогда частная условная энтропия будет равна

Усредненная энтропия

Частную условную энтропию можно выразить через математическое ожидание Усредненная энтропия

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

Усредненная энтропия

Усредненная энтропия

Усредненная энтропия (1.6)

Понятие условной энтропии широко используется для определения информационных потерь при передаче информации. Пусть по каналу связи передаются сообщения с помощью алфавита Х. В результате воздействия помех приемником будет восприниматься другой алфавит Y (см.рис. 1.2).

Усредненная энтропия

Рис.1.2. Передача информации по каналу связи при воздействии помех

Усредненная энтропия выражает неопределенность того что, отправив xi, мы получим yj, а понятие Усредненная энтропия — неуверенность, которая остается после получения yj в том, что было отправлено именно xi. Если в канале связи помехи отсутствуют, то всегда посланному символу x1 соответствует принятый символ y1, x2 — y2, . . . , xn — yn. При этом энтропия источника H(X) равна энтропии приемника H(Y). Если в канале связи присутствуют помехи, то они уничтожают часть передаваемой информации.

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

Усредненная энтропия (1.7)

Энтропия объединения и условная энтропия связаны между собой следующими соотношениями:

H(X,Y) = H(X) + H(X/Y) = H(Y) + H(X/Y) (1.8)

В случае если X и Y между собой независимы, то условная энтропия равняется безусловной H(Y/X)=H(Y) и H(X,Y)=H(X)+H(Y).

В общем случае энтропия объединенной системы H(X,Y)≤ H(X)+H(Y), это следует из того что: H(Y/X)≤H(Y) условная энтропия меньше безусловной. Энтропия объединенной системы достигает максимум, только в случае если системы независимы.

В случае полной зависимости систем, состояния одной системы полностью определяют состояния другой (они эквивалентны): H(X,Y)=H(X)=H(Y), так как H(Y/X)=0.

Источник: studopedia.ru

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

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

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

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

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

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

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

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

$ -Ksum_{i=1}^np(i)log_2 p(i) $

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

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

В общем случае b-арная энтропия (где b равно 2,3,… ) источника $ mathcal{S} $ = (S,P) с исходным алфавитом S = {a1, …, an} и дискретным распределением вероятности P = {p1, …, pn} где pi является вероятностью ai (pi = p(ai)) определяется формулой:

$ H_b(mathcal{S}) = — sum_{i=1}^n p_i log_b p_i $

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

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

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

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

$ 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 $ был предыдущим символом.

Так, для русского алфавита без буквы «ё» $ H_0=5, H_1=4,358, H_2=3,52, H_3=3,01 $[1]

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются т.н. канальные матрицы. Так, для описания потерь со стороны источника (т.е. известен посланный сигнал), рассматривают условную вероятность $ displaystyle p(b_j|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|a_1) $ $ displaystyle p(b_2|a_1) $ $ displaystyle p(b_j|a_i) $ $ displaystyle p(b_m|a_1) $
$ displaystyle a_2 $ $ displaystyle p(b_1|a_2) $ $ displaystyle p(b_2|a_2) $ $ displaystyle p(b_j|a_2) $ $ displaystyle p(b_m|a_2) $
$ displaystyle a_i $ $ displaystyle p(b_1|a_i) $ $ displaystyle p(b_2|a_i) $ $ displaystyle p(b_j|a_i) $ $ displaystyle p(b_m|a_i) $
$ displaystyle a_m $ $ displaystyle p(b_1|a_m) $ $ displaystyle p(b_2|a_m) $ $ displaystyle p(b_j|a_m) $ $ displaystyle p(b_m|a_m) $

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

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

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

$ displaystyle H(B|A)=sum_i p(a_i)H(B|a_i) $

$ displaystyle H(B|A) $ означает энтропию со стороны источника, аналогично рассматривается $ displaystyle H(A|B) $ — энтропия со стороны приёмника: вместо $ displaystyle p(b_j|a_i) $ всюду указывается $ displaystyle p(a_i|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_i 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_ib_j) $ событий $ displaystyle a_i $ и $ displaystyle b_j $ вычисляется как произведение исходной и условной вероятности,

$ displaystyle p(a_ib_j)=p(a_i)p(b_j|a_i)=p(b_j)p(a_i|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) $

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

$ 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|A) = H(B)+H(A|B). $

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

Свойства

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

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

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

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

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

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

$ 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) Для целых положительных bi, где b1 + … + bn = n, должно выполняться равенство:

$ 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 году.

Литература

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

См. также

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

Источник: math.wikia.org


You May Also Like

About the Author: admind

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.