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

редактировать
Средняя скорость, с которой создается информация из стохастического источника данных

Два бита энтропии: в случае двух справедливых подбрасываний монеты информационная энтропия в битах представляет собой логарифм по основанию 2 числа результатов результатов; с двумя монетами есть четыре результата и два бита энтропии. Как правило, информационная энтропия - это средний объем информации, предназначенной для использования с учетом всех результатов.

В теории информации, энтропия случайной величины - средний уровень «информации», «неожиданности» или «неопределенности», присущий возможным результатам измерений. Концепция информационной энтропии была введена Клодом Шенноном в его статье 1948 года «Математическая теория коммуникации ». В качестве примера рассмотрим смещенную монету с вероятностью p выпадения орла и вероятностью 1-p выпадения решки. Максимальный сюрприз - для p = 1/2, когда нет ожидаемого результата над другими, и в этом случае подбрасывание монеты имеет энтропию в один бит. Минимальный сюрприз - это когда p = 0 или p = 1, когда событие известно, а энтропия равна нулю битов. Другие значения p дают разные энтропии между нулем и единицей битов.

Дана дискретная случайная величина X {\ displaystyle X}X , с возможными результатами x 1,..., x n {\ displaystyle x_ {1},..., x_ {n}}x_ {1},..., x_ {n} , которые совпадают с вероятностью P (x 1),..., P (xn) {\ displaystyle \ mathrm {P} (x_ {1}),..., \ mathrm {P} (x_ {n})}{\ displaystyle \ mathrm {P} (x_ {1}),..., \ mathrm {P} (x_ {n})} , энтропия X {\ displaystyle X}X формально определяется как:

H (X) = - ∑ i = 1 n P (xi) log ⁡ P (xi) {\ displaystyle \ mathrm {H} (X) = - \ sum _ {i = 1} ^ {n} {\ mathrm {P} (x_ {i}) \ log \ mathrm {P} (x_ {i})}}{\ displaystyle \ mathrm {H} (X) = - \ sum _ {i = 1} ^ {n} {\ mathrm {P} (x_ {i}) \ log \ mathrm {P} (x_ {i})}}

где Σ {\ displaystyle \ Sigma}\ Sigma обозначает использованные свойства, а log {\ displaystyle \ log}\ log - логарифм, выбор база различается между разными приложениями. База 2 дает единицу измерения бит (или «шэннонов »), а база е дает «натуральные единицы» нат, и основание 10 дает единицу, называемые "dits", "bans" или "hartleys ". Эквивалентным определением энтропии является ожидаемое значение самоинформации модели.

Энтропия была установлена ​​Шенноном как часть его теории коммуникации., в которой система передачи данных состоит из трех элементов: источника данных, канала связи и приемника. В теории Шеннона «фундаментальная проблема коммуникации», как выразился Шеннон, заключается в том, чтобы приемник мог определить, какие данные были сгенерированы, на основе сигнала, который он получает через канал. Шеннон рассмотрел различные способы кодирования данных, ограничения передачи сообщений из источника и доказал в своей знаменитой теореме кодирования источника, что энтропия представляет собой абсолютный математический того, насколько хорошо данные могут быть без потерь, мощности в совершенно бесшумный канал. Шеннон значительно усиливает этот результат для зашумленных каналов в своей теореме кодирования зашумленного канала..

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

Содержание

  • 1 Введение
  • 2
  • 3 Пример
  • 4 Характеристика
    • 4.1 Альтернативная характеристика
  • 5 Дополнительные свойства
  • 6 Аспекты
    • 6.1 Связь с термодинамической энтропией
    • 6.2 Сжатие данных
    • 6.3 Энтропия как мера разнообразия
    • 6.4 Ограничение энтропии
    • 6.5 Ограничение энтропии в криптографии
    • 6.6 Данные как марковский процесс
  • 7 Эффективность (нормализованная энтропия)
  • 8 Энтропия для 8, 1 Относительная энтропия
  • 9 Использование в комбинаторике
    • 9.1 Неравенство Лумиса - Уитни
    • 9.2 Приближение к биномиальный коэффициент
  • 10 См. также
  • 11 Ссылки
  • 12 Дополнительная литература
    • 12.1 Учебники по теории информации
  • 13 Внешние ссылки
  • Введение

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

    информационное содержание (также называемое неожиданностью) события E {\ displaystyle E}E - это функция, которая уменьшает как вероятность p (E) {\ displaystyle p (E)}{\ displaystyle p (E)} увеличения события, определяемого как I (E) = - log 2 ⁡ (p (E)) {\ displaystyle I (E) = - \ log _ { 2} (p (E))}{\ displaystyle I (E) = - \ log _ {2} (p (E))} или эквивалентно I (E) = log 2 ⁡ (1 / p (E)) {\ displaystyle I (E) = \ log _ {2} (1 / p (E))}{\ displaystyle I (E) = \ log _ {2 } (1 / p (E))} , где log {\ displaystyle \ log}\ log - это логарифм. Энтропия измеряет ожидаемый (т.е. средний) объем информации, получаемый через достижение результата случайного испытания. Это означает, что бросок кубика имеет более высокую вероятность, чем бросание, потому что каждый результат броска кубика имеет меньшую вероятность (примерно p = 1/6 {\ displaystyle p = 1/6}{\ displaystyle p = 1/6} ), чем каждый результат подбрасывания монеты (p = 1/2 {\ displaystyle p = 1/2}p = 1/2 ).

    Рассмотрим пример подбрасывания монеты. Если вероятность выпадения орла такая же, как и вероятность выпадения решений, то энтропия подбрасывания монеты настолько высока, насколько это могло бы быть для испытаний с двумя исходами. Невозможно заранее предсказать результат подбрасывания монеты: если нужно выбирать, нет никаких средних преимуществ, можно получить предсказание, что при подбрасывании будет решка или орел, поскольку любой прогноз будет верным с вероятностью 1/2 {\ displaystyle 1/2}1/2 . Такой подбрасывание монеты имеет энтропию I (E) = 1 {\ displaystyle I (E) = 1}{\ displaystyle I (E) = 1} (в битах), поскольку существует два результата, которые достигаются с равной вероятностью, и изучение Фактический результат содержит один бит информации. Напротив, подбрасывание монеты с использованием монеты с двумя орлами и без решки имеет энтропию I (E) = 0 {\ displaystyle I (E) = 0}{\ displaystyle I (E) = 0} , поскольку монета всегда будет выпадать. головы, и исход можно предсказать отлично. Точно так же один trit с равновоятными значениями содержит log 2 ⁡ 3 {\ displaystyle \ log _ {2} 3}\ log _ {2} 3 (около 1,58496) битов информации, потому что что что что что он может иметь один трех значений.

    Английский текст, рассматриваемый как строка символов, имеет довольно низкую энтропию, т. Е. Довольно предсказуем. Если мы не знаем точно, что будет дальше, мы можем быть вполне уверены, что, например, «е» будет гораздо более распространенным, чем «z», что комбинация «qu» будет гораздо более распространенной, чем любая другая. комбинация с «q» в нем, и что комбинация «th» будет более распространенной, чем «z», «q» или «qu». Часто после первых букв можно угадать остаток слова. Английский текст имеет от 0,6 до 1,3 бита энтропии на символ сообщения.

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

    Если бы нужно было было, содержащее 4 символа «A», «B», «C» и «D», передаваемое сообщение могло бы быть «ABADDCAB». Теория информации дает способ вычисления минимально возможного количества информации, которая это передаст. Если все 4 буквы равновероятны (25%), нельзя сделать лучше (по двоичному каналу), чем иметь 2 бита, кодирующие (в двоичном) каждую букву: 'A' может кодироваться как '00', 'B' как «01», «C» как «10» и «D» как «11». Если 'A' встречается с вероятностью 70%, 'B' - с 26%, 'C' и 'D' - с 2% каждый, можно было бы назначить стандарты стандартной длины, так что получение '1' говорит о том, что нужно посмотреть на другой бит если еще не было получено 2 бита последовательных последовательностей. В этом случае «A» будет закодирован как «0» (один бит), «B» - как «10», а «C» и «D» - как «110» и «111» соответственно. Легко видеть, что в 70% случаев необходимо отправить только один бит, в 26% случаев - два бита и только в 4% случаев - 3 бита. В среднем требуется менее 2 битов, так как энтропия ниже (из-за распространенности буквы «А», за которой следует «В» - вместе 96% символов). Расчет суммы логарифмических вероятностей, взвешенных по вероятности, измеряет и фиксирует этот эффект.

    Теорема Шеннона также подразумевает, что никакая схема сжатия без потерь не может сократить все сообщения. Если некоторые сообщения выходят короче, по крайней мере одно должно выходить длиннее из-за принципа «голубятни». В от бессмысленного текста или цифровых фотографий, а не шума, и неважно, если размер данных маловероятных или неинтересных последовательностей.

    Определение

    Названный в честь Η-теоремы Больцмана, Шеннон определил энтропию Η (греческая заглавная буква эта ) дискретного случайного переменная X {\ textstyle X}{\ textstyle X} с возможными значениями {x 1,…, xn} {\ textstyle \ left \ {x_ {1}, \ ldots, x_ {n} \ right \}}{\ textstyle \ left \ {x_ {1}, \ ldots, x_ {n } \ right \}} и функция массы вероятности P (X) {\ textstyle \ mathrm {P} (X)}{\ textstyle \ mathrm {P} (X)} как:

    H (X) = E ⁡ [I ⁡ (X)] = E ⁡ [- журнал ⁡ (P (X))]. {\ displaystyle \ mathrm {H} (X) = \ operatorname {E} [\ operatorname {I} (X)] = \ operatorname {E} [- \ log (\ mathrm {P} (X))].}{\ displaystyle \ mathrm {H} (X) = \ operatorname {E} [\ operatorname {I} (X)] = \ operatorname {E } [- \ log (\ mathrm {P} (X))].}

    Здесь E {\ displaystyle \ operatorname {E}}\ operatorname {E} - это оператор ожидаемого значения, а I - информационное содержание X. I ⁡ (X) {\ displaystyle \ operatorname {I} (X)}{\ displaystyle \ имя оператора {I} (X)} сам по себе является случайной величиной.

    Энтропия может быть явно записана как:

    H (X) = - ∑ i = 1 n P (xi) log b ⁡ P (xi) {\ displaystyle \ mathrm {H} (X) = - \ sum _ {i = 1} ^ {n} {\ mathrm {P} (x_ {i}) \ log _ {b} \ mathrm {P} (x_ {i})}}{\ displaystyle \ mathrm {H} (X) = - \ sum _ { я = 1} ^ {n} {\ mathrm {P} (x_ {i}) \ log _ {b} \ mathrm {P} (x_ {i})}}

    где b является основанием используемой логарифма . Обычными значениями являются 2, число Эйлера e и 10, поставщиками единицами энтропии являются биты для b = 2, nats для b = e, а запрещает для b = 10.

    В случае P (x i) = 0 для некоторого i соответствующее слагаемое 0 log b (0) принимается равным 0, что соответствует пределу :

    lim p → 0 + p log ⁡ (p) = 0. {\ displaystyle \ lim _ {p \ to 0 ^ {+}} p \ log (p) = 0.}\ lim _ {{p \ to 0 ^ {+}}} p \ log (p) = 0.

    Можно также определить условную энтропию двух событий X {\ displaystyle X}X и Y {\ displaystyle Y}Y , принимающие значения xi {\ displaystyle x_ {i}}x_ {i} и yj {\ displaystyle y_ {j}}y_ {j} соответственно, как:

    H (X | Y) знак равно - ∑ я, jp (xi, yj) журнал ⁡ p (xi, yj) p (yj) {\ displaystyle \ mathrm {H} (X | Y) = - \ sum _ {i, j} p (x_ {i}, y_ {j}) \ log {\ frac {p (x_ {i}, y_ {j})} {p (y_ {j})}}}{\ Displaystyle \ mathrm {H} (X | Y) = - \ сумма _ {я, j} р (x_ {i}, y_ {j}) \ log {\ frac {p (x_ {i}, y_ {j})} {p (y_ {j})}}}

    где p (xi, yj) {\ displaystyle p (x_ {i}, y_ {j})}{\ displaystyle p (x_ {i}, y_ {j})} - вер оятность того, что X = xi {\ displ аистайл X = x_ {i}}{\ displaystyle X = x_ {i}} и Y = yj {\ displaystyle Y = y_ {j}}{\ displaystyle Y = y_ {j}} . Это следует понимать как количество случайности в случайной величине X {\ displaystyle X}X с учетом случайной величины Y {\ displaystyle Y}Y .

    Пример

    Энтропия Η (X) ( т. Е. ожидаемый неожиданный ) подбрасывания монеты, измеренный в битах, на графике в зависимости от ущерба монеты Pr (X = 1), где X = 1 представляет результат голов... Здесь энтропия составляет не более 1 бит, и для сообщений результата подбрасывания монеты (2 преступных значения) потребуется в среднем не более 1 бит (ровно 1 бит для честная монета). Результат правильного кубика (6 случаев) будет иметь журнал энтропии 2 6 бит.

    Рассмотрим подбрасывание монеты с известной, не обязательно справедливой, вероятностью выпадения орла или решки; это можно смоделировать как процесс Бернулли.

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

    H (X) = - ∑ i = 1 n P (xi) log b ⁡ P (xi) = - ∑ i = 1 2 1 2 log 2 ⁡ 1 2 = - ∑ i = 1 2 1 2 ⋅ (- 1) = 1 {\ displaystyle {\ begin {align} \ mathrm {H} (X) = - \ sum _ {i = 1} ^ {n} {\ mathrm {P} (x_ { i}) \ log _ {b} \ mathrm {P} (x_ {i})} \\ = - \ sum _ {i = 1} ^ {2} {{\ frac {1} {2}} \ log _ {2} {\ frac {1} {2}}} \\ = - \ sum _ {i = 1} ^ {2} {{\ frac {1} {2}} \ cdot (-1) } = 1 \ end {align}}}{\ displaystyle {\ begin {align} \ mathrm {H} (X) = - \ sum _ {i = 1} ^ {n} {\ mathrm {P} (x_ {i}) \ log _ {b} \ mathrm {P} (x_ {i})} \\ = - \ sum _ {i = 1} ^ {2} {{\ frac {1} {2}} \ log _ {2} {\ frac {1} {2}}} \\ = - \ sum _ {i = 1} ^ {2} {{\ frac {1} {2}} \ cdot (-1)} = 1 \ end {align}}}

    Однако, если мы знаем, что монета несправедлива, но выпадает орел или решка с вероятностями p и q, где p ≠ q, то неопределенности меньше. Каждый раз, когда его бросают, одна сторона с большей вероятностью поднимается, чем другая. Сниженная неопределенность количественно выражается в более низкой энтропии: в среднем каждый бросок монеты дает менее полного бита информации. Например, если p = 0,7, то

    H (X) = - p log 2 ⁡ (p) - q log 2 ⁡ (q) = - 0,7 log 2 ⁡ (0,7) - 0, 3 log 2 ⁡ (0,3) ≈ - 0,7 (- 0,515) - 0,3 ⋅ (- 1,737) = 0,8816 < 1 {\displaystyle {\begin{aligned}\mathrm {H} (X)=-p\log _{2}(p)-q\log _{2}(q)\\=-0.7\log _{2}(0.7)-0.3\log _{2}(0.3)\\\approx -0.7\cdot (-0.515)-0.3\cdot (-1.737)\\=0.8816<1\end{aligned}}}{\ displaystyle {\ begin {align} \ mathrm {H} (X) = -p \ log _ {2} (p) -q \ log _ {2} (q) \\ = - 0,7 \ log _ {2} (0,7) -0,3 \ log _ {2} (0,3) \ \ \ приблизительно -0,7 \ cdot (-0,515) -0,3 \ cdot (-1,737) \\ = 0,8816 <1 \ end {align}}}

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

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

    Характеристика

    Чтобы понять значение -∑ p i log (p i), сначала определите информационную функцию I в терминах события i с вероятностью p я. Объем информации, полученной в результате наблюдения события i, следует из решения Шеннона фундаментальные Свойства информации информации :

    1. I (p) является монотонно уменьшающимся в p: увеличение вероятности события информации о происшествии события и наоборот.
    2. I (p) ≥ 0: информация является неотрицательной величиной.
    3. I (1) = 0: всегда происходящие события не передают информацию.
    4. I (p 1, p 2) = I (p 1) + I (p 2) : информация, полученная из независимых событий, представляет собой сумму информации, полученной из каждого события.

    Данные два независимых события, если первое событие может дать один из исходов имеет равновероятных исходов, а другое из них равновероятных исходов, то имеется mn равновероятных исходов совместных событий. Это означает, что если log 2 (n) битов необходимы для кодирования первого значения и log 2 (m) для кодирования второго, необходимо log 2 (mn) = log 2 (m) + log 2 (n) для кодирования обоих.

    Шеннон обнаружил, подходящий выбор I {\ displaystyle \ operatorname {I}}{\ displaystyle \ operatorname {I}} дается следующим образом:

    I ⁡ (p) = log ⁡ (1 p) = - журнал ⁡ (p) {\ displaystyle \ operatorname {I} (p) = \ log \ left ({\ tfrac {1} {p}} \ right) = - \ log (p)}{\ displaystyle \ operatorname {I} (p) = \ log \ left ({\ tfrac {1} {p}} \ right) = - \ log (p)}

    Фактически, единственные возможные значения I {\ displaystyle \ operatorname {I}}{\ displaystyle \ operatorname {I}} : I ⁡ (u) = k log ⁡ u {\ displaystyle \ operatorname {I} (u) = k \ log u}{\ displaystyle \ operatorname {I} (u) = k \ log u} для k < 0 {\displaystyle k<0}k <0 . Кроме того, выбор значений для k эквивалентен выбору значения x>1 {\ displaystyle x>1}x>1 для k = - 1 / log ⁡ x {\ displaystyle k = -1 / \ log x}{\ displaystyle k = -1 / \ log x} , так что x соответствует основанию логарифма. Таким образом, энтропия представляет четырьмя вышеуказанных свойств.

    Различные единицы (биты свойства для двоичного логарифма log 2, nats для натурального логарифма ln, запреты для десятичного логарифма log 10 и так далее) являются постоянными кратными друг другу. Например, в случае правильного подбрасывания монеты орел используется log 2 (2) = 1 бит информации, что составляет примерно 0,693 ната или 0,301 десятичной цифры. Из-за аддитивности бросков предоставляет битов информации, что примерно 0,693 натов или 0,301 десятичных цифр.

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

    Альтернативная характеристика

    Другая характеристика энтропии использует следующие свойства. Обозначим p i = Pr (X = x i) и Η n(p1,…, p n) = Η (X).

    1. Непрерывность: H должна быть непрерывной, так что изменить значения вероятностей на очень небольшое количество изменить энтропию только на небольшое значение.
    2. Симметрия: H должна быть не изменяется, если результаты x i переупорядочиваются. То есть H n (p 1, p 2,… pn) = H n (pi 1, pi 2,…, pin) {\ displaystyle \ mathrm {H} _ {n} \ left (p_ {1}, p_ {2}, \ ldots p_ {n} \ right) = \ mathrm {H} _ {n} \ left (p_ {i_ {1}}, p_ {i_ {2}}, \ ldots, p_ {i_ {n}} \ right)}{\ displaystyle \ mathrm {H} _ {n} \ left ( p_ {1}, p_ {2}, \ ldots p_ {n} \ right) = \ mathrm {H} _ {n} \ left (p_ {i_ {1}}, p_ {i_ {2}}, \ ldots, p_ {i_ {n}} \ right)} для любого перестановки {i 1,..., я n} {\ displaystyle \ {i_ {1},..., i_ {n} \}}{\ displaystyle \ {i_ {1},..., i_ {n} \}} из {1,..., n} {\ displaystyle \ {1,..., n \}}\ { 1,..., n \} .
    3. Максимум: H_n должно быть максимальным, если все результаты одинаково вероятны, т.е. ЧАС N (p 1,…, pn) ≤ H n (1 n,…, 1 n) {\ displaystyle \ mathrm {H} _ {n} (p_ {1}, \ ldots, p_ {n}) \ leq \ mathrm {H} _ {n} \ left ({\ frac {1} {n}}, \ ldots, {\ frac {1} {n}} \ right)}{\ displaystyle \ mathrm {H} _ {n} (p_ {1}, \ ldots, p_ {n}) \ leq \ mathrm {H} _ {n} \ left ({ \ frac {1} {n}}, \ ldots, {\ frac {1} {n}} \ right)} .
    4. Увеличение количества исходов: для равновероятных событий энтропия должна увеличиваться с увеличением количества исходов, т.е. H n (1 n,…, 1 n ⏟ n) < H n + 1 ( 1 n + 1, …, 1 n + 1 ⏟ n + 1). {\displaystyle \mathrm {H} _{n}{\bigg (}\underbrace {{\frac {1}{n}},\ldots,{\frac {1}{n}}} _{n}{\bigg)}<\mathrm {H} _{n+1}{\bigg (}\underbrace {{\frac {1}{n+1}},\ldots,{\frac {1}{n+1}}} _{n+1}{\bigg)}.}{\ displaystyle \ mathrm {H} _ {n} {\ bigg (} \ underbrace { {\ frac {1} {n}}, \ ldots, {\ frac {1} {n}}} _ {n} {\ bigg)} <\ mathrm {H} _ {n + 1} {\ bigg ( } \ underbrace {{\ frac {1} {n + 1}}, \ ldots, {\ frac {1} {n + 1}}} _ {n + 1} {\ bigg)}.}
    5. Аддитивность: дан ансамбль из n равномерно распределенных элементов, которые разделены на блоки (подсистем) с b 1,..., b k элементов каждого, энтропия всего ансамбля должна быть равна сумме энтропии системы ящиков и индивидуальных энтропий ящиков, каждую из которых взвешена с вероятностью в конкретном поле.

    Правило аддитивности имеет следующие последствия: для положительных целых чисел bi, где b 1 +… + b k = n,

    H n (1 n,…, 1 n) = H k (b 1 n,…, bk n) + ∑ i = 1 kbin H bi (1 bi,…, 1 bi). {\ displaystyle \ mathrm {H} _ {n} \ left ({\ frac {1} {n}}, \ ldots, {\ frac {1} {n}} \ right) = \ mathrm {H} _ { k} \ left ({\ frac {b_ {1}} {n}}, \ ldots, {\ frac {b_ {k}} {n}} \ right) + \ sum _ {i = 1} ^ {k } {\ frac {b_ {i}} {n}} \, \ mathrm {H} _ {b_ {i}} \ left ({\ frac {1} {b_ {i}}}, \ ldots, {\ frac {1} {b_ {i}}} \ right).}\ mathrm {H} _ {n} \ left ({\ frac {1} {n}}, \ ldots, {\ frac {1} {n}} \ right) = \ mathrm {H} _ {k} \ left ({\ frac {b_ {1}} {n}}, \ ldots, {\ frac {b_ {k}} {n}} \ right) + \ sum _ {i = 1} ^ {k} {\ frac {b_ {i}} {n}} \, \ mathrm {H} _ {b_ {i}} \ left ({\ frac {1} {b_ { i}}}, \ ldots, {\ frac {1} {b_ {i}}} \ rig ht).

    Выбор k = n, b 1 =… = b n = 1 это означает, что энтропия Определено исхода равенство нулю: Η 1 (1) = 0. Это означает, что эффективность исходного алфавита с n символами может быть определена просто как равная его n-арной энтропии. См. Избыточность (теория информации).

    Дополнительные свойства

    Энтропия Шеннона реализует следующие свойства, которые могут интерпретировать энтропию как объем изученной информации (или устраненную неопределенность) путем использования значений случайной величины X:

    • Добавление или удаление события с нулевой вероятностью не влияет на энтропию:
    H n + 1 (p 1,…, pn, 0) = H n (p 1,…, pn) {\ displaystyle \ mathrm {H} _ { n + 1} (p_ {1}, \ ldots, p_ {n}, 0) = \ mathrm {H} _ {n} (p_ {1}, \ ldots, p_ {n})}\ mathrm {H} _ {n + 1} ( p_ {1}, \ ldots, p_ {n}, 0) = \ mathrm {H} _ {n} (p_ {1}, \ ldots, p_ {n}) .
    H (X) = E ⁡ [log b ⁡ (1 p (X))] ≤ журнал б ⁡ (Е ⁡ [1 п (X)]) = журнал б ⁡ (N) {\ Displaystyle \ mathrm {H} (X) = \ OperatorName {E} \ left [\ log _ {b} \ left ({\ frac {1} {p (X)}} \ right) \ right] \ leq \ log _ {b} \ left (\ operatorname {E} \ left [{\ frac {1} {p (X)}} \ right] \ right) = \ log _ {b} ( n)}\ mathrm {H} (X) = \ operatorname {E} \ left [\ log _ {b} \ left ({\ frac { 1} {p (X)}} \ right) \ right] \ leq \ log _ {b} \ left (\ operatorname {E} \ left [{\ frac {1} {p (X)}} \ right] \ right) = \ log _ {b} (n) .
    Эта максимальная энтропия log b (n) эффективно имеет и сходным алфавитом, имеющим унифо rm распределение вероятностей: неопределенность максимальна, когда все возможные события равновероятны.
    • Энтропия или количество информации, полученной при оценке (X, Y) (то есть при одновременной оценке X и Y), равно информации, полученной при проведении последовательных экспериментов: сначала оценка значения Y, выявление значений X при условии, что вы можно записать как:
    H (X, Y) = H (X | Y) + H (Y) = H (Y | X) + H (X). {\ Displaystyle \ mathrm {H} (X, Y) = \ mathrm {H} (X | Y) + \ mathrm {H} (Y) = \ mathrm {H} (Y | X) + \ mathrm {H} (X).}\ mathrm {H} (X, Y) = \ mathrm {H} (X | Y) + \ mathrm {H} (Y) = \ mathrm {H} (Y | X) + \ mathrm {H} (X).
    • Если Y = f (X) {\ displaystyle Y = f (X)}Y = f (X) , где f {\ displaystyle f}f является функцией, тогда H (f (X) | X) = 0 {\ displaystyle H (f (X) | X) = 0}{\ displaystyle H (f (X) | X) = 0} . Применение предыдущей формулы к H (X, f (X)) {\ displaystyle H (X, f (X))}{\ Displaystyle H (X, f (X))} дает
    H (X) + H (f (X) | Икс) знак равно ЧАС (е (Икс)) + ЧАС (Икс | е (Х)), {\ Displaystyle \ mathrm {H} (X) + \ mathrm {H} (F (X) | X) = \ mathrm {H} (е (X)) + \ mathrm {H} (X | f (X)),}\ mathrm {H} (X) + \ mathrm {H} (f (X) | X) = \ mathrm {H} (f (X)) + \ mathrm {H } (X | f (X)),
    поэтому H (f (X)) ≤ H (X) {\ displaystyle H ( f (X)) \ leq H (X)}{\ displaystyle H (f (X)) \ leq H (X)} , энтропия может уменьшаться только тогда, когда последняя передается через функцию.
    • Если X и Y - независимые случайные величины, то две знания значения Y не влияют на наши знания о значении X (поскольку они не влияют на друга по независимости):
    H (X | Y) = H (X). {\ displaystyle \ mathrm {H} (X | Y) = \ mathrm {H} (X).}\ mathrm {H} (X | Y) = \ mathrm {H} (X).
    • Энтропия двух одновременных событий не больше, чем сумма энтропий каждого отдельного события, т.е. ЧАС (Икс, Y) ≤ ЧАС (Икс) + ЧАС (Y) {\ Displaystyle \ mathrm {H} (X, Y) \ leq \ mathrm {H} (X) + \ mathrm {H} (Y)}{\ displaystyle \ mathrm {H} (X, Y) \ leq \ mathrm {H} (X) + \ mathrm {H} (Y)} с равенством тогда и только тогда, когда два события независимы.
    • Энтропия H (p) {\ displaystyle \ mathrm {H} (p)}{\ displaystyle \ mathrm {H} (p)} является вогнутым в функции массы вероятности p {\ displaystyle p}p , т.е.
    ЧАС (λ п 1 + (1 - λ) п 2) ≥ λ ЧАС (п 1) + (1 - λ) ЧАС (п 2) {\ Displaystyle \ mathrm {H} (\ lambda p_ {1} + (1- \ lambda) p_ {2}) \ geq \ lambda \ mathrm {H} (p_ {1}) + (1- \ lambda) \ mathrm {H} (p_ {2})}{\ displaystyle \ mathrm {H} (\ lambda p_ {1} + ( 1- \ lambda) p_ {2}) \ geq \ lambda \ mathrm {H} (p_ {1}) + (1- \ lambda) \ mathrm {H} (p_ {2})}
    для всех вероятностно-массовых функций p 1, p 2 {\ displaystyle p_ {1}, p_ {2}}{\ displaystyle p_ {1}, p_ {2}} и 0 ≤ λ ≤ 1 {\ displaystyle 0 \ leq \ lambda \ leq 1}{\ displaystyle 0 \ leq \ lambda \ leq 1} .

    Asp ects

    Связь с термодинамической энтропией

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

    В статистическая термодинамика формула для термодинамической энтропии S термодинамической системы - это энтропия Гиббса,

    S = - k B ∑ pi ln ⁡ pi {\ displaystyle S = -k _ {\ текст {B} } \ sum p_ {i} \ ln p_ {i} \,}{\ displaystyle S = -k _ {\ text {B}} \ sum p_ {i} \ пер п_ {я} \,}

    где k B - Больцман константа, а p i - вероятность микросостояния. Энтропия Гиббса была определена Дж. Уиллард Гиббс в 1878 году после более ранней работы Больцмана (1872).

    Энтропия Гиббса почти без изменений переносится в мир квантовой физики, чтобы дать энтропия фон Неймана, введенная Джоном фон Нейманом в 1927 году,

    S = - k BT r (ρ ln ⁡ ρ) {\ displaystyle S = -k _ {\ text {B }} \, {\ rm {Tr}} (\ rho \ ln \ rho) \,}{\ displaystyle S = -k _ {\ текст {B}} \, {\ rm {Tr}} (\ rho \ ln \ rho) \,}

    где ρ - матрица плотности квантово-механической системы, а Tr - след.

    На повседневном практическом уровне связи между информационной энтропией и термодинамической энтропией не очевидны. Физики и химики склонны больше интересоваться изменениями энтропии по мере того, как система спонтанно эволюционирует от своих начальных условий, в соответствии со вторым законом термодинамики, а не соответствует распределением вероятностей. Как показывает мельчайшая величина постоянной Больцмана kB, изменения S / k B даже для крошечных процессов количества веществ в химических и физических величинах, которые имеют количество энтропии, которые превосходят велики по сравнению с чем-либо в сжатие данных или обработка сигналов. В классической термодинамике информационных энтропий определено значение в терминах макроскопических измерений.

    Связь между термодинамикой и тем, что сейчас известно как теория информации, была впервые установлена ​​Людвигом Больцманном и выражена его знаменитым уравнением :

    S = k B ln ⁡ ( W) {\ displaystyle S = k _ {\ text {B}} \ ln (W)}{\ displaystyle S = k _ {\ text {B} } \ ln (W)}

    где S {\ displaystyle S}S - термодинамическая энтропия определенного макросостояния (определяет термодинамические параметры, такие как температура, объем, энергия и т. д.), W - количество микросостояний (различные комбинации частиц в различных энергетических состояниях), которые могут дать данное состояние, а k B равно Постоянная Больцмана. Предполагается, что каждая микросостояние имеет вероятность того, что эта микросостояния соответствует p i = 1 / W. Когда эти вероятности подставляются в приведенное выше выражение для энтропии Гиббса (или эквивалентно k B, умноженное на энтропию Шеннона), уравнение Больцмана. В терминах теории информации информационнаятропия системы - «недостающей» информации.

    С точки зрения Джейнса (1957), термодинамическую энтропию, как объясняет статистическая механика, следует рассматривать как приложение теории информации Шеннона: термодинамическая энтропия интерпретируется как пропорциональная количеству дополнительной информации Постоянная Больцмана. Добавление тепла увеличивает ее термодинамику, потому что увеличивает количество микроскопических состояний, которые с измеримыми значениями ее макроскопических чисел, делают любое полное описание состояния более длинным. (См. Статью: термодинамика максимальной энтропии ). демон Максвелла может (гипотетически) уменьшить термодинамическую энтропию, используя информацию о состоянии отдельных молекул; но, как показали Ландауэр (с 1961 г.) и его сотрудники, для функционирования демон сам должен увеличивать термодинамическую энтропию в процессе, по крайней мере на уровне информации Шеннона, которую он предлагает сначала получить и сохранить; и поэтому полная термодинамическая энтропия не уменьшается (что разрешает парадокс). Принцип Ландауэра накладывает нижний предел на количество тепла, компьютер должен генерировать для обработки заданного количества информации, хотя современные компьютеры намного менее эффективны.

    Сжатие данных

    Энтропия определяется в контексте вероятностной модели. Независимые честные подбрасывания монеты энтропию 1 бит на подбрасывание. Источник, который всегда генерирует длинную строку B, имеет энтропию 0, поскольку следующим символом всегда будет буква «B».

    коэффициент энтропии источника данных означает среднее количество битов на символ, необходимое для его кодирования. Эксперименты Шеннона с человеческими предсказателями показывают скорость передачи от 0,6 до 1,3 бита на символ на английском языке; Алгоритм сжатия PPM может обеспечить коэффициент сжатия 1,5 бит на символ в английском тексте.

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

    Минимальная пропускная способность канала может быть теоретически реализована с помощью типичного набора или на практике с использованием Huffman, Lempel – Ziv или арифметического кодирования. См. Также Колмогоровская сложность. На практике алгоритмы сжатия намеренно включают некоторую разумную избыточность в виде контрольных сумм для защиты от ошибок.

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

    Все цифры в энтропийно сжатых эксабайтах
    Тип информации19862007
    Хранение2,6295
    Трансляция4321900
    Телекоммуникации0.28165

    Авторы оценивают технологические возможности человечества по хранению информации (полностью энтропийно сжатые) в 1986 году и снова в 2007 году. Они разбивают информацию на три категории - для хранения информации на носителе, для получения информации через односторонние широковещательные сети или для обмена информацией через двухсторонние путь телекоммуникации сетиs.

    Энтропия как мера разнообразия

    Энтропия - один из нескольких способов для измерения разнообразия. В частности, энтропия Шеннона - это логарифм D, индекс истинного разнообразия с параметром, равным 1.

    Ограничения энтропии

    Существует ряд концепций, связанных с энтропией которые математически определяют количество информации каким-либо образом:

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

    Важно не путать приведенные выше понятия. Часто только из контекста ясно, о чем идет речь. Например, когда кто-то говорит, что «энтропия» английского языка составляет около 1 бита на символ, они фактически моделируют английский язык как стохастический процесс и говорят о его скорости энтропии. Сам Шеннон использовал этот термин таким образом.

    Если используются очень большие блоки, оценка скорости энтропии для каждого символа может стать искусственно заниженной, потому что распределение вероятностей последовательностей точно не известно; это только оценка. Если рассматривать текст каждой книги, когда-либо опубликованной, как последовательность, где каждый представляет собой текст всей книги, и каждая книга публикуется только один раз, оценка вероятности каждой книги будет 1 / N, а энтропия (в битах) равна −log 2 (1 / N) = log 2 (N). На практике это присвоение каждой книги уникального текста и использование его вместо книги всякий раз, когда кто-то сослаться на книгу. Это очень полезно для разговоров о книгах. отдельной книги или языка в целом: невозможно восстановить книгу по ее идентификатору без зной распределения вероятностей, то есть есть полный текст всех книг. Ключевая идея состоит в том, что необходимо задействовать сложность вероятностной модели. Колмогоровская сложность - это теоретическое обобщение этой идеи, которое позволяет учитывать информационное содержание независимо от какой-либо конкретной вероятностной модели; он рассматривает самую короткую программу для универсального компьютера, который завершит последовательность. Код, который показывает скорость энтропии для данной модели, плюс кодовая книга (то есть есть вероятностная модель), одна из программ таких, но может быть не самой короткой.

    Последовательность Фибоначчи - это 1, 1, 2, 3, 5, 8, 13,.... если рассматривать последовательность как сообщение, каждое число как символ, существует почти столько же символов, сколько есть символов в сообщении, что дает энтропию приблизительно log 2 (n). Первые 128 символов последовательности Фибоначчи имеют энтропию примерно 7 бит / символ, но последовательность может быть выражена с помощью формулы [F (n) = F (n - 1) + F (n - 2) для n = 3., 4, 5, …, F (1) = 1, F (2) = 1], и эта формула имеет гораздо более низкую энтропию и применима к любой длине показывает Фибоначчи.

    Ограничения энтропии в криптографии

    В криптоанализе энтропия часто грубо используется как мера непредсказуемости криптографического ключа, хотя его реальная неопределенность неизмеримо. Например, 128-битный ключ, который генерируется равномерно и случайным образом, имеет 128 бит энтропии. Также требуется (в среднем) 2 127 {\ displaystyle 2 ^ {127}}{\ displaystyle 2 ^ { 127}} попытка взлома с помощью грубой силы. Энтропия не может уловить необходимое количество догадок, если возможные ключи не выбраны единообразно. Вместо этого для измерения усилий, требуемых для атаки методом грубой силы, может установить мера, предполагаемое предположение.

    Другие проблемы из-за неоднородных распределений, используемых в криптографии. Например, двоичный код из 1000000 цифр одноразовый блокнот с использованием исключающего или. Если блокнот имеет 1000000 бит энтропии, это прекрасно. Если блокнот имеет 999999 бит энтропии, равномерно распределенный (каждый отдельный бит блока имеет 0,999999 бит энтропии), это может обеспечить хорошую безопасность. Но если блокнот имеет 999 999 бит энтропии, где первый фиксирован, а остальные 999 999 абсолютно случайны, первый бит зашифрованного текста не будет зашифрован вообще.

    Данные как марковский процесс

    Обычный способ определения энтропии для текста основан на марковской модели текста. Для источника порядка 0 (каждый символ выбирается независимо от последних символов) двоичная энтропия равна:

    H (S) = - ∑ pi log ⁡ pi, {\ displaystyle \ mathrm {H} ({\ mathcal {S}}) = - \ sum p_ {i} \ log p_ {i},}{\ displaystyle \ mathrm {H } ({\ mathcal {S}}) = - \ sum p_ {i} \ log p_ {i},}

    где p i - вероятность i. Для марковского источника первого порядка (в котором вероятность выбора символа зависит только от самого предшествующего символа) коэффициент энтропии равенство:

    ЧАС (S) = - ∑ ipi ∑ jpi (j) журнал ⁡ пи (j), {\ displaystyle \ mathrm {H} ({\ mathcal {S}}) = - \ sum _ {i} p_ {i} \ sum _ {j} \ p_ {i} (j) \ log p_ {i} (j),}{\ displaystyle \ mathrm {H} ({\ mathcal {S}}) = - \ sum _ {i} p_ {i} \ sum _ {j} \ p_ {i} (j) \ log p_ {i} (j),}

    где i - состояние (некоторые предыдущие символы) и pi (j) {\ displaystyle p_ {i} (j)}p_ {i} (j) - вероятность того, что j задан i в предыдущем символе.

    Для марковского источника второго порядка скорости энтропии соответствует

    H (S) = - i p i ∑ j p i (j) ∑ k p i, j (k) log ⁡ p i, j (k). {\ displaystyle \ mathrm {H} ({\ mathcal {S}}) = - \ sum _ {i} p_ {i} \ sum _ {j} p_ {i} (j) \ sum _ {k} p_ { i, j} (k) \ \ log \ p_ {i, j} (k).}{\ displaystyle \ mathrm {H} ({\ mathcal {S}}) = - \ sum _ {i} p_ {i} \ sum _ {j} p_ {i} (j) \ sum _ {k} p_ {i, j} (k) \ \ log \ p_ {i, j} ( k).}

    Эффективность (нормализованная энтропия)

    Исходный алфавит с неравномерным распределением будет иметь меньшую энтропию, чем если бы эти символы имели равномерное распределение (т.е. «оптимизированный алфавит»). Этот дефицит энтропии может быть выражен как коэффициент, называемый эффективностью:

    η (X) = HH max = - ∑ i = 1 np (xi) log b ⁡ (p (xi)) log b ⁡ (n) {\ displaystyle \ eta (X) = {\ frac {H} {H_ {max}}} = - \ sum _ {i = 1} ^ {n} {\ frac {p (x_ {i}) \ log _ {b} (p (x_ {i}))} {\ log _ {b} (n)}}}{\ displaystyle \ eta (X) = {\ frac {H} {H_ {max}}} = - \ sum _ {i = 1} ^ {n} {\ frac {p (x_ {i}) \ log _ {b} (p (x_ {i}))} {\ журнал _ {b} (n)}}}

    Применяя основные свойства логарифма, это также можно выразить как:

    η (X) = - ∑ i = 1 np (xi) log b ⁡ (p (xi)) log b ⁡ (n) = ∑ i = 1 n log b ⁡ (p (xi) - p (xi)) log b ⁡ (n) Знак равно ∑ я знак равно 1 N журнал N ⁡ (п (xi) - p (xi)) = журнал N ⁡ (∏ я = 1 np (xi) - p (xi)) {\ Displaystyle \ eta (X) = - \ sum _ {i = 1} ^ {n} {\ frac {p (x_ {i}) \ log _ {b} (p (x_ {i}))} {\ log _ {b} (n)}} = \ sum _ {i = 1} ^ {n} {\ frac {\ log _ {b} (p (x_ {i}) ^ {- p (x_ {i})})} {\ log _ {b} ( n)}} = \ sum _ {i = 1} ^ {n} \ log _ {n} (p (x_ {i}) ^ {- p (x_ {i})}) = \ log _ {n} (\ prod _ {i = 1} ^ {n} p (x_ {i}) ^ {- p (x_ {i})})}{\ displaystyle \ eta (X) = - \ sum _ {i = 1} ^ {n} {\ frac {p (x_ {i}) \ log _ {b} (p (x_ {i}))} {\ log _ {b} (n) }} = \ sum _ {i = 1} ^ {n} {\ frac {\ log _ {b} (p (x_ {i}) ^ {- p (x_ {i})})} {\ log _ {b} (n)}} = \ sum _ {i = 1} ^ {n} \ log _ {n} (p (x_ {i}) ^ {- p (x_ {i})}) = \ log _ {n} (\ prod _ {i = 1} ^ {n} p (x_ {i}) ^ {- p (x_ {i})})}

    Эффективность полезна для количественной оценки эффектив Использование канал связи. Эта формулировка также называется нормализованной энтропией, поскольку энтропия делится на максимальную энтропию log b ⁡ (n) {\ displaystyle {\ log _ {b} (n)}}{\ log _ {b} (n)} . Кроме того, эффективность безразлична к выбору (положительного) основания b, на что указывает нечувствительность в пределах последнего логарифма над ним.

    Энтропия для непрерывных случайных величин

    Дифференциальная энтропия

    Энтропия Шеннона ограничена случайными величинами, принимающими дискретные значения. Соответствующая формула для непрерывной случайной величины с функция плотности вероятности f (x) с конечной или бесконечной поддержкой X {\ displaystyle \ mathbb {X}}\ mathbb {X} на действительной прямой определяется по аналогии с использованием вышеупомянутой формы энтропии в математическом ожидании:

    h [f] = E ⁡ [- ln ⁡ (f (x))] = - ∫ X f (x) ln ⁡ (f (х)) dx. {\ displaystyle h [f] = \ operatorname {E} [- \ ln (f (x))] = - \ int _ {\ mathbb {X}} f (x) \ ln (f (x)) \, dx.}h [f] = \ operatorname {E} [- \ ln (f (x))] = - \ int _ {\ mathbb {X}} f (Икс) \ пер (е (х)) \, dx.

    Это дифференциальная энтропия (или непрерывная энтропия). Предшественником непрерывной энтропии h [f] является выражение для функционала в H-теореме из Больцмана.

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

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

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

    Для этого начните с непрерывной функции f, дискретизированной по ячейкам размера Δ {\ displaystyle \ Delta}\ Delta . По теореме о среднем значении в каждом бункере существует такое значение x i, что

    f (xi) Δ = ∫ i Δ (i + 1) Δ f (x) dx {\ displaystyle f (x_ {i}) \ Delta = \ int _ {i \ Delta} ^ {(i + 1) \ Delta} f (x) \, dx}f (x_ {i}) \ Delta = \ int _ {я \ Delt a} ^ {(i + 1) \ Delta} f (x) \, dx

    интеграл функции f может быть приближен (в римановом смысле) по

    ∫ - ∞ ∞ е (x) dx = lim Δ → 0 ∑ я = - ∞ ∞ f (xi) Δ {\ displaystyle \ int _ {- \ infty} ^ {\ infty} f (x) \, dx = \ lim _ {\ Delta \ to 0} \ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta}\ int _ {- \ infty} ^ {\ infty} f (x) \, dx = \ lim _ {\ Delta \ to 0} \ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta

    где этот предел и "размер bin уходит в ноль" эквивалентны.

    Обозначим

    H Δ: = - ∑ я = - ∞ ∞ f (xi) Δ log ⁡ (f (xi) Δ) {\ displaystyle \ mathrm {H} ^ {\ Delta}: = - \ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log \ left (f (x_ {i}) \ Delta \ right)}{\ displaystyle \ mathrm {H} ^ {\ Delta}: = - \ sum _ {я = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log \ left (f (x_ {i}) \ Delta \ right)}

    и расширение логарифм, имеем

    H Δ = - ∑ i = - ∞ ∞ f (xi) Δ log ⁡ (f (xi)) - ∑ i = - ∞ ∞ f (xi) Δ log ⁡ (Δ). {\ Displaystyle \ mathrm {H} ^ {\ Delta} = - \ sum _ {я = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log (f (x_ {i})) - \ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log (\ Delta).}\ mathrm {H} ^ { \ Delta} = - \ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log (f (x_ {i})) - \ sum _ {i = - \ infty } ^ {\ infty} f (x_ {i}) \ Delta \ log (\ Delta).

    При Δ → 0 имеем

    ∑ i = - ∞ ∞ f (xi) Δ → ∫ - ∞ ∞ f (x) dx = 1 ∑ i = - ∞ ∞ f (xi) Δ log ⁡ (f (xi)) → ∫ - ∞ ∞ f (x) log ⁡ f (х) dx. {\ displaystyle {\ begin {align} \ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ to \ int _ {- \ infty} ^ {\ infty} f (x) \, dx = 1 \\\ сумма _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log (f (x_ {i})) \ to \ int _ {- \ infty} ^ {\ infty} е (х) \ журнал е (х) \, dx. \ end {align}}}{\ begin {align} \ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ to \ int _ {- \ infty } ^ {\ infty} f (x) \, dx = 1 \\\ sum _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log (f (x_ {i})) \ to \ int _ {- \ infty} ^ {\ infty} f (x) \ log f (x) \, dx. \ end {align}}

    Примечание; log (Δ) → −∞ при Δ → 0, требует специальных определений дифференциальной или непрерывной энтропии:

    h [f] = lim Δ → 0 (H Δ + log ⁡ Δ) = - ∫ - ∞ ∞ f (Икс) журнал ⁡ е (Икс) dx, {\ Displaystyle H [f] = \ lim _ {\ Delta \ to 0} \ left (\ mathrm {H} ^ {\ Delta} + \ log \ Delta \ right) = - \ int _ {- \ infty} ^ {\ infty} f (x) \ log f (x) \, dx,}h [f] = \ lim _ {\ Delta \ to 0} \ left (\ mathrm {H} ^ {\ Delta} + \ log \ Delta \ right) = - \ int _ {- \ infty} ^ {\ infty} f (x) \ log f (x) \, dx,

    , которая, как было сказано ранее, называется дифференциальной энтропией. Это означает, что дифференциальная энтропия не является пределом энтропии Шеннона при n → ∞. Скорее, он отличается от предела энтропии Шеннона бесконечным смещением (см. Также статью о информационном измерении ).

    Предельная точность дискретных точек

    В результате получается отличие от энтропии Шеннона, отличная энтропия, как правило, не является хорошей мерой неопределенности или информации. Например, дифференциальная энтропия может быть отрицательной; также он не инвариантен относительно непрерывных преобразований координат. Эта проблема может быть проиллюстрирована изменением, когда x - размерная переменная. Тогда f (x) будет иметь единицу 1 / x. Аргумент должен быть безразмерным, в противном случае он неверен, так что приведенная выше энтропия будет неправильной. Если Δ - некоторое "стандартное" значение x (т.е. "размер ячейки") и, следовательно, имеет те же единицы измерения, модифицированная дифференциальная энтропия может быть записана в надлежащей форме как:

    H = ∫ - ∞ ∞ е (Икс) журнал ⁡ (е (х) Δ) dx {\ displaystyle H = \ int _ {- \ infty} ^ {\ infty} f (x) \ log (f (x) \, \ Delta) \, dx}{\ displaystyle H = \ int _ {- \ infty} ^ {\ infty} е (Икс) \ журнал (е (х) \, \ Дельта) \, dx}

    и результат будет одинаковым при любом выборе для x. Фактически, предел дискретной энтропии как N → ∞ {\ displaystyle N \ rightarrow \ infty}{\ displaystyle N \ rightarrow \ infty} также будет член log ⁡ (N) {\ displaystyle \ log (N)}{\ displaystyle \ log (N)} , который в общем случае может быть бесконечным. Ожидается, что непрерывные переменные обычно бесконечную энтропию при дискретизации. Предельная плотность дискретных точек на самом деле является мерой того, насколько проще использовать распределение, чем распределение, которое является однородным по схеме квантования.

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

    Другой полезный показатель энтропии, который одинаково хорошо работает в дискретном и непрерывном случаях, - это относительная энтропия распределения. Он определен как расхождение Кульбака - Лейблера от распределения до эталонной меры m следующим образом. Предположим, что распределение вероятностей p абсолютно непрерывно по отношению к мере m, то есть есть вид p (dx) = f (x) m (dx) для некоторой неотрицательной m-интегрируемой функции f с m-интегралом 1, то относительную энтропию можно определить как

    DKL (p ‖ m) = ∫ log ⁡ (f (x)) p (dx) = ∫ f (x) log ⁡ (f (x)) m (dx). {\ Displaystyle D _ {\ mathrm {KL}} (п \ | м) = \ int \ log (f (x)) p (dx) = \ int f (x) \ log (f (x)) m ( dx).}D _ {\ mathrm {KL}} (p \ | m) = \ int \ log (f (x)) p (dx) знак равно \ int е (х) \ журнал (е (х)) м (дх).

    В этой форме относительной энтропии обобщает (с точностью до изменения знака) как дискретную энтропию, где мера m является считающей мерой, так и дифференциальную энтропию, где мера m равна мера Лебега. Если мера m сама является распределением вероятностей, относительная энтропия неотрицательна и равна нулю, если p = m в качестве меры. Он определен для любого пространства мер, следовательно, не зависит от координат и инвариантен по отношению к перепараметризации координат, если правильно во внимание преобразование меры m. Относительная энтропия, а также неявная энтропия и дифференциальная энтропия зависит от «эталонной» меры м.

    Использование в комбинаторике

    Энтропия стала полезной величиной в комбинаторике.

    Неравенство Лумиса - Уитни

    Простой пример этого альтернативным доказательством Неравенство Лумиса - Уитни : для каждого подмножества A ⊆ Z мы имеем

    | А | d - 1 ≤ ∏ i = 1 d | P i (A) | {\ displaystyle | А | ^ {d-1} \ leq \ prod _ {i = 1} ^ {d} | P_ {i} (A) |}| А | ^ {d-1} \ leq \ prod _ {i = 1} ^ {d} | P_ {i} (A) |

    , где P i - ортогональная проекция в i-й координате:

    P i (A) = {(x 1,…, Xi - 1, xi + 1,…, xd): (x 1,…, xd) ∈ A}. {\ Displaystyle P_ {я} (A) = \ {(x_ {1}, \ ldots, x_ {i-1}, x_ {i + 1}, \ ldots, x_ {d}) :( x_ {1}, \ ldots, x_ {d}) \ in A \}.}P_ {i} (A) = \ {(x_ {1}, \ ldots, x_ {i-1}, x_ {i + 1}, \ ldots, x_ {d}) :( x_ {1}, \ ldots, x_ {d}) \ in A \}.

    Доказательство следует как простое следствие из неравенства Ширера : если X 1,…, X d - случайные величины, а S 1,…, S n - подмножества {1,…, d}, такие, что каждое целое число от 1 до d лежит точно в этих подмножеств, то

    H [(X 1,…, X d)] ≤ 1 r ∑ i = 1 n H [(X j) j ∈ S i] {\ displaystyle \ mathrm {H} [( X_ {1}, \ ldots, X_ {d})] \ leq {\ frac {1} {r}} \ sum _ {i = 1} ^ {n} \ mathrm {H} [(X_ {j}) _ {j \ in S_ {i}}]}\ mathrm {H} [(X_ {1}, \ ldots, X_ {d})] \ leq {\ frac {1} {r}} \ sum _ {i = 1} ^ {n} \ mathrm {H} [(X_ {j}) _ {j \ in S_ { i}}]

    где (X j) j ∈ S i {\ displaystyle (X_ {j}) _ {j \ in S_ {i}}}(X_ {j}) _ {j \ in S_ {i}} - декартово произведение случайных величин X j с индексами j в S i (поэтому размерность этого вектора равна размеру S i).

    Мы набросаем, как из этого Лумис - Уитни:, пусть X - равномерно распределенная случайная величина со значениями в A, и каждая точка в A встречается с равной вероятностью. Тогда (в силу других свойств энтропии, упомянутых выше) Η (X) = log | A |, где | А | обозначает мощность A. Пусть S i = {1, 2,…, i - 1, i + 1,…, d}. Диапазон (X j) j ∈ S i {\ displaystyle (X_ {j}) _ {j \ in S_ {i}}}(X_ {j}) _ {j \ in S_ {i}} содержится в P i (A) и, следовательно, H [(X j) j ∈ S i] ≤ log ⁡ | P i (A) | {\ displaystyle \ mathrm {H} [(X_ {j}) _ {j \ in S_ {i}}] \ leq \ log | P_ {i} (A) |}\ mathrm {H} [(X_ {j }) _ {j \ in S_ {i}}] \ leq \ log | P_ {i} (A) | . Теперь используйте это, чтобы ограничить правую часть неравенства Ширера и возвести в степень противоположные стороны неравенного неравенства.

    Аппроксимация биномиального коэффициента

    Для целых чисел 0 < k < n let q = k/n. Then

    2 n H (q) n + 1 ≤ (nk) ≤ 2 n H (q), {\ displaystyle {\ frac { 2 ^ {n \ mathrm {H} (q)}} {n + 1}} \ leq {\ tbinom {n} {k}} \ leq 2 ^ {n \ mathrm {H} (q)},}{\ frac {2 ^ {n \ mathrm {H} (q)}} {n + 1}} \ leq {\ tbinom {n} { k}} \ leq 2 ^ {п \ mathrm {H} (q)},

    где

    H (q) = - q log 2 ⁡ (q) - (1 - q) log 2 ⁡ (1 - q). {\ displaystyle \ mathrm {H} (q) = - q \ log _ {2} (q) - (1-q) \ log _ {2} (1-q).}\ mathrm {H} (q) = - q \ log _ {2} (q) - (1-q) \ log _ {2} (1-q).

    Хорошая интерпретация этого состоит в том, что количество двоичных линий длины n с ровно k множеством единиц приблизительно равно

    2 n H (k / n) {\ displaystyle 2 ^ {n \ mathrm {H} (k / n)}}2 ^ {n \ mathrm {H} (k / n)} .

    См. также

    • значок Портал математики
    Викиучебнике есть книга на тему: Интуитивное руководство к концепции энтропии, развивающей в различных секторах науки

    Ссылки

    Эта статья включает материал из энтропии Шеннона на PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.

    Дополнительная литература

    Учебники по теории информации

    • Обложка, TM, Thomas, JA (2006), Elements of Information Теория - 2-е изд., Wiley-Interscience, ISBN 978-0-471-24195-9
    • Маккей, DJC (2003), Теория информации, логический вывод и алгоритмы обучения, Cambridge University Press, ISBN 978-0-521-64298-9
    • Арндт, К. (2004), Информационные меры: информация и ее описание в науке и технике, Springer, ISBN 978-3-540-40855-0
    • Грей, Р.М. (2011), Энтропия и теория информации, Springer.
    • Мартин, Натаниэль Ф.Г. И Англия, Джеймс У. (2011). Математическая теория энтропии. Издательство Кембриджского университета. ISBN 978-0-521-17738-2. CS1 maint: использует параметр авторов (ссылка )
    • Шеннон, CE, Уивер, W. (1949) The Mathematical Theory of Communication, Univ of Illinois Press. ISBN 0-252-72548-4
    • Stone, JV (2014), Глава 1 из Теория информации: Введение в учебное пособие, Университет Шеффилда, Англия. ISBN 978-0956372857.

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

    Последняя правка сделана 2021-05-19 11:38:11
    Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
    Обратная связь: support@alphapedia.ru
    Соглашение
    О проекте