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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  теория информации «Энтропия»  -  новости  · газеты  · книги  · ученый  · JSTOR ( февраль 2019 г. ) ( Узнайте, как и когда удалить это шаблонное сообщение )

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

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

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

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

где обозначает сумму возможных значений переменной, а - логарифм , выбор базы зависит от разных приложений. База 2 дает единицу битов (или « шеннонов »), в то время как основание e дает «естественные единицы» nat , а основание 10 дает единицу, называемую «точками», «банами» или « хартли ». Эквивалентное определение энтропии является ожидаемым значением из собственной информации переменного. ^[3]${\ displaystyle \ Sigma}$${\ displaystyle \ log}$

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

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

Введение [ править ]

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

Информационное содержание (также называется surprisal ) о событии является функцией , которая уменьшается по мере вероятности А.Н. увеличения событий, определяемых или , что эквивалентно , где представляет собой логарифм . Энтропия измеряет ожидаемый (т.е. средний) объем информации, передаваемой путем определения результата случайного испытания. ^{[4] : 67} Это означает, что бросок кубика имеет более высокую энтропию, чем бросание монеты, потому что каждый результат подбрасывания кубика имеет меньшую вероятность (примерно ), чем каждый исход подбрасывания монеты ( ).${\ displaystyle E}$${\ displaystyle p (E)}$${\ Displaystyle I (E) = - \ log _ {2} (p (E))}$${\ Displaystyle I (E) = \ журнал _ {2} (1 / p (E))}$${\ displaystyle \ log}$${\ displaystyle p = 1/6}$${\ displaystyle p = 1/2}$

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

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

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

Если передать последовательности, состоящие из 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 бита последовательных единиц. В этом случае «А»будет закодирован как '0' (один бит), 'B' как '10' и 'C' и 'D' как '110' и '111', соответственно. Легко видеть, что в 70% случаев необходимо отправить только один бит, в 26% случаев - два бита и только в 4% случаев - 3 бита. В среднем требуется менее 2 бит, поскольку энтропия ниже (из-за высокой распространенности буквы «А», за которой следует «В» - вместе 96% символов). Расчет суммы логарифмических вероятностей, взвешенных по вероятности, измеряет и фиксирует этот эффект.требуется менее 2 бит, поскольку энтропия ниже (из-за высокой распространенности буквы «А», за которой следует «В» - вместе 96% символов). Расчет суммы логарифмических вероятностей, взвешенных по вероятности, измеряет и фиксирует этот эффект.требуется менее 2 бит, поскольку энтропия ниже (из-за высокой распространенности буквы «А», за которой следует «В» - вместе 96% символов). Расчет суммы логарифмических вероятностей, взвешенных по вероятности, измеряет и фиксирует этот эффект.

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

Определение [ править ]

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

${\displaystyle \mathrm {H} (X)=\operatorname {E} [\operatorname {I} (X)]=\operatorname {E} [-\log(\mathrm {P} (X))].}$

Вот это ожидаемый оператор значение , и я это содержание информации из X . ^{[6] : 11 [7] : 19–20} сама по себе является случайной величиной.${\displaystyle \operatorname {E} }$${\displaystyle \operatorname {I} (X)}$

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

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

В случае P ( x _i ) = 0 для некоторого i значение соответствующего слагаемого 0 log _b (0) принимается равным 0 , что согласуется с пределом : ^{[9] : 13}

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

Можно также определить условную энтропию двух событий и принимать значения и соответственно как: ^{[9] : 16}${\displaystyle X}$${\displaystyle Y}$${\displaystyle x_{i}}$${\displaystyle y_{j}}$

${\displaystyle \mathrm {H} (X|Y)=-\sum _{i,j}p(x_{i},y_{j})\log {\frac {p(x_{i},y_{j})}{p(y_{j})}}}$

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

Пример [ править ]

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

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

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

$${\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}}}$$

Равномерная вероятность дает максимальную неопределенность и, следовательно, максимальную энтропию. Таким образом, энтропия может уменьшаться только от значения, связанного с равномерной вероятностью. Крайний случай - это двуглавая монета, у которой никогда не выпадает решка, или двусторонняя монета, у которой никогда не выпадает решка. Тогда нет никакой неопределенности. Энтропия равна нулю: каждое подбрасывание монеты не дает новой информации, поскольку результат каждого подбрасывания монеты всегда определен. ^{[9] : 14–15}

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

Характеристика [ править ]

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

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

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

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

${\displaystyle \operatorname {I} (p)=\log \left({\tfrac {1}{p}}\right)=-\log(p)}$

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

Доказательство

Пусть - информационная функция, которую предполагается дважды непрерывно дифференцируемой, имеет:${\textstyle \operatorname {I} }$ ${\displaystyle {\begin{aligned}&\operatorname {I} (p_{1}p_{2})&=\ &\operatorname {I} (p_{1})+\operatorname {I} (p_{2})&&\quad {\text{Starting from property 4}}\\&p_{2}\operatorname {I} '(p_{1}p_{2})&=\ &\operatorname {I} '(p_{1})&&\quad {\text{taking the derivative w.r.t}}\ p_{1}\\&\operatorname {I} '(p_{1}p_{2})+p_{1}p_{2}\operatorname {I} ''(p_{1}p_{2})&=\ &0&&\quad {\text{taking the derivative w.r.t}}\ p_{2}\\&\operatorname {I} '(u)+u\operatorname {I} ''(u)&=\ &0&&\quad {\text{introducing}}\,u=p_{1}p_{2}\\&(u\mapsto u\operatorname {I} '(u))'&=\ &0\end{aligned}}}$ Это дифференциальное уравнение приводит к решению для любого . Свойство 2 приводит к . Тогда также сохраняются свойства 1 и 3.${\displaystyle \operatorname {I} (u)=k\log u}$${\displaystyle k\in \mathbb {R} }$${\displaystyle k<0}$

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

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

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

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

1. Непрерывность: H должно быть непрерывным , так что изменение значений вероятностей на очень небольшое количество должно изменять энтропию только на небольшую величину.
2. Симметрия: H должно быть неизменным, если результаты x _i переупорядочиваются. То есть, для любой перестановки из .${\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 \{i_{1},...,i_{n}\}}$${\displaystyle \{1,...,n\}}$
3. Максимум: должно быть максимальным , если все исходы равновероятны есть .${\displaystyle \mathrm {H} _{n}}$${\displaystyle \mathrm {H} _{n}(p_{1},\ldots ,p_{n})\leq \mathrm {H} _{n}\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)}$
4. Увеличение количества исходов: для равновероятных событий энтропия должна увеличиваться с увеличением количества исходов, т.е. ${\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 равномерно распределенных элементов, которые разделены на k блоков (подсистем) с b ₁ , ..., b _k элементами в каждом, энтропия всего ансамбля должна быть равна сумме энтропии система ящиков и индивидуальные энтропии ящиков, каждая из которых взвешена с вероятностью попадания в эту конкретную ячейку.

Правило аддитивности имеет следующие последствия: для натуральных чисел b _i, где b ₁ +… + b _k = n ,

${\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).}$

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

Другие свойства [ править ]

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

• Добавление или удаление события с нулевой вероятностью не влияет на энтропию:

${\displaystyle \mathrm {H} _{n+1}(p_{1},\ldots ,p_{n},0)=\mathrm {H} _{n}(p_{1},\ldots ,p_{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)}$. ^{[9] : 29}

Эта максимальная энтропия log _b ( n ) эффективно достигается исходным алфавитом, имеющим равномерное распределение вероятностей: неопределенность максимальна, когда все возможные события равновероятны.

• Энтропия или количество информации, полученной при оценке ( X , Y ) (то есть при одновременном оценивании X и Y ), равно информации, полученной при проведении двух последовательных экспериментов: сначала оценивается значение Y , а затем раскрывается значение X при условии , что вы знаете , значение Y . Это можно записать как: ^{[9] : 16}

${\displaystyle \mathrm {H} (X,Y)=\mathrm {H} (X|Y)+\mathrm {H} (Y)=\mathrm {H} (Y|X)+\mathrm {H} (X).}$

• Если где - функция, то . Применение предыдущей формулы к доходности${\displaystyle Y=f(X)}$${\displaystyle f}$${\displaystyle H(f(X)|X)=0}$${\displaystyle H(X,f(X))}$

${\displaystyle \mathrm {H} (X)+\mathrm {H} (f(X)|X)=\mathrm {H} (f(X))+\mathrm {H} (X|f(X)),}$

Итак , энтропия переменной может уменьшаться только тогда, когда последняя передается через функцию.${\displaystyle H(f(X))\leq H(X)}$

• Если X и Y - две независимые случайные величины, то знание значения Y не влияет на наши знания о значении X (поскольку они не влияют друг на друга по своей независимости):

${\displaystyle \mathrm {H} (X|Y)=\mathrm {H} (X).}$

• Энтропия двух одновременных событий - это не более чем сумма энтропий каждого отдельного события, т. Е. С равенством тогда и только тогда, когда два события независимы. ^{[9] : 28}${\displaystyle \mathrm {H} (X,Y)\leq \mathrm {H} (X)+\mathrm {H} (Y)}$
• Энтропия является вогнутой в функции вероятности массового , т.е. ^{[9] : 30}${\displaystyle \mathrm {H} (p)}$${\displaystyle p}$

${\displaystyle \mathrm {H} (\lambda p_{1}+(1-\lambda )p_{2})\geq \lambda \mathrm {H} (p_{1})+(1-\lambda )\mathrm {H} (p_{2})}$

для всех вероятностных массовых функций и . ^{[9] : 32}${\displaystyle p_{1},p_{2}}$${\displaystyle 0\leq \lambda \leq 1}$

• Соответственно, функция отрицательной энтропии (негэнтропии) является выпуклой, а ее выпуклым сопряженным элементом является LogSumExp .

Аспекты [ править ]

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

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

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

${\displaystyle S=-k_{\text{B}}\sum p_{i}\ln p_{i}\,}$

где k _B - постоянная Больцмана , а p _i - вероятность микросостояния . Энтропия Гиббса была определена Гиббс в 1878 г. после ранней работы Больцмана (1872 г.). ^[11]

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

${\displaystyle S=-k_{\text{B}}\,{\rm {Tr}}(\rho \ln \rho )\,}$

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

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

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

${\displaystyle S=k_{\text{B}}\ln(W)}$

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

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

Сжатие данных [ править ]

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

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

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

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

В исследовании 2011 года, проведенном в Science, оценивается мировая технологическая способность хранить и передавать оптимально сжатую информацию, нормализованную по наиболее эффективным алгоритмам сжатия, доступным в 2007 году, таким образом оценивая энтропию технологически доступных источников. ^{[13] : 60–65}

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

Энтропия как мера разнообразия [ править ]

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

Ограничения энтропии [ править ]

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

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

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

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

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

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

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

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

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

Данные как марковский процесс [ править ]

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

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

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

${\displaystyle \mathrm {H} ({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}\ p_{i}(j)\log p_{i}(j),}$^{[ необходима цитата ]}

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

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

${\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 \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)=-\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})})}$

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

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

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

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

${\displaystyle h[f]=\operatorname {E} [-\ln(f(x))]=-\int _{\mathbb {X} }f(x)\ln(f(x))\,dx.}$

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

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

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

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

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

${\displaystyle f(x_{i})\Delta =\int _{i\Delta }^{(i+1)\Delta }f(x)\,dx}$

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

${\displaystyle \int _{-\infty }^{\infty }f(x)\,dx=\lim _{\Delta \to 0}\sum _{i=-\infty }^{\infty }f(x_{i})\Delta }$

где этот предел и «размер ячейки стремится к нулю» эквивалентны.

Обозначим

${\displaystyle \mathrm {H} ^{\Delta }:=-\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log \left(f(x_{i})\Delta \right)}$

и раскладывая логарифм, имеем

${\displaystyle \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 имеем

${\displaystyle {\begin{aligned}\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{aligned}}}$

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

${\displaystyle 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 (т.е. «размер ячейки») и, следовательно, имеет те же единицы, то модифицированная дифференциальная энтропия может быть записана в надлежащей форме как:

${\displaystyle H=\int _{-\infty }^{\infty }f(x)\log(f(x)\,\Delta )\,dx}$

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

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

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

${\displaystyle D_{\mathrm {KL} }(p\|m)=\int \log(f(x))p(dx)=\int f(x)\log(f(x))m(dx).}$

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

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

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

Неравенство Лумиса – Уитни [ править ]

Простым примером этого является альтернативное доказательство неравенства Лумиса – Уитни : для любого подмножества A ⊆ Z ^d мы имеем

${\displaystyle |A|^{d-1}\leq \prod _{i=1}^{d}|P_{i}(A)|}$

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

${\displaystyle P_{i}(A)=\{(x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{d}):(x_{1},\ldots ,x_{d})\in A\}.}$

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

${\displaystyle \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 (поэтому размерность этого вектора равна размеру S _i ).${\displaystyle (X_{j})_{j\in S_{i}}}$

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

Приближение к биномиальному коэффициенту [ править ]

Для целых чисел 0 < k < n положим q = k / n . потом

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

куда

${\displaystyle \mathrm {H} (q)=-q\log _{2}(q)-(1-q)\log _{2}(1-q).}$^{[17] : 43}

Доказательство (эскиз)

Обратите внимание, что это один член выражения${\displaystyle {\tbinom {n}{k}}q^{qn}(1-q)^{n-nq}}$ ${\displaystyle \sum _{i=0}^{n}{\tbinom {n}{i}}q^{i}(1-q)^{n-i}=(q+(1-q))^{n}=1.}$ Перестановка дает верхнюю границу. Что касается нижней границы, сначала с помощью некоторой алгебры показывают, что это наибольший член в суммировании. Но потом, ${\displaystyle {\binom {n}{k}}q^{qn}(1-q)^{n-nq}\geq {\frac {1}{n+1}}}$ поскольку в суммировании содержится n + 1 слагаемых. Перестановка дает нижнюю границу.

Хорошая интерпретация этого состоит в том, что количество двоичных строк длины n с ровно k множеством единиц приблизительно . ^[18]${\displaystyle 2^{n\mathrm {H} (k/n)}}$

См. Также [ править ]

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

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

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

Дальнейшее чтение [ править ]

Учебники по теории информации [ править ]

• Cover, TM , Thomas, JA (2006), Элементы теории информации - 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: uses authors parameter (link)
• Шеннон, CE , Уивер, W. (1949) Математическая теория коммуникации , Univ of Illinois Press. ISBN 0-252-72548-4 
• Стоун, СП (2014), Глава 1 теории информации: Введение в учебное пособие , Университет Шеффилда, Англия. ISBN 978-0956372857 . 

Внешние ссылки [ править ]

• "Энтропия" , Математическая энциклопедия , EMS Press , 2001 [1994]
• «Энтропия» в Rosetta Code - хранилище реализаций энтропии Шеннона на различных языках программирования.
• Энтропия междисциплинарный журнал по всем аспектам концепции энтропии. Открытый доступ.