Энтропия (теория информации) - Entropy (information theory)

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

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

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

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

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

куда ${displaystyle Sigma}$ обозначает сумму возможных значений переменной, а ${журнал displaystyle}$ это логарифм, выбор базы различается для разных приложений. База 2 дает единицу биты (или же "Shannons "), а база е дает "натуральные единицы" нац, а основание 10 дает единицу, называемую "dits", "bans" или "Hartleys ". Эквивалентным определением энтропии является ожидаемое значение из самоинформация переменной.^[3]

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

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

Вступление

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

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

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

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

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

Определение

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

${displaystyle mathrm {H} (X) = имя оператора {E} [имя оператора {I} (X)] = имя оператора {E} [-log (mathrm {P} (X))].}$

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

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

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

В случае П(Икс_я) = 0 для некоторых я, значение соответствующего слагаемого 0 журнал_б(0) считается 0, что согласуется с предел:^[9]:13

${displaystyle lim _ {p o 0 ^ {+}} plog (p) = 0.}$

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

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

Пример

Энтропия Η (Икс) (т.е. ожидал неожиданный ) подбрасывания монеты, измеряемой в битах, в зависимости от отклонения монеты Pr (Икс = 1), куда Икс = 1 представляет собой результат голов.^[9]:14–15

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

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

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

${displaystyle {egin {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)} = 1end {выровнено}}}$

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

$${displaystyle {egin {выравнивается} mathrm {H} (X) & = - plog _ {2} (p) -qlog _ {2} (q) & = - 0.7log _ {2} (0.7) -0.3log _ {2} (0,3) & приблизительно -0,7 кадра (-0,515) -0,3 кадра (-1,737) & = 0,8816 <1end {выровнено}}}$$

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

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

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

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

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

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

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

${displaystyle operatorname {I} (p) = log left ({frac {1} {p}} ight) = - log (p)}$

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

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

Позволять ${extstyle operatorname {I}}$ - информационная функция, которую предполагается дважды непрерывно дифференцируемой, имеет: ${displaystyle {egin {align} & operatorname {I} (p_ {1} p_ {2}) & = & operatorname {I} (p_ {1}) + operatorname {I} (p_ {2}) && quad {ext {Начиная с свойство 4}} & p_ {2} operatorname {I} '(p_ {1} p_ {2}) & = & operatorname {I}' (p_ {1}) && quad {ext {взятие производной относительно}} p_ {1 } & operatorname {I} '(p_ {1} p_ {2}) + p_ {1} p_ {2} operatorname {I}' '(p_ {1} p_ {2}) & = & 0 && quad {ext { производная по отношению к}} p_ {2} & operatorname {I} '(u) + uoperatorname {I}' '(u) & = & 0 && quad {ext {введение}}, u = p_ {1} p_ {2} & ( umapsto uoperatorname {I} '(u))' & = & 0end {выровнено}}}$ Этот дифференциальное уравнение приводит к решению ${displaystyle operatorname {I} (u) = klog u}$ для любого ${displaystyle kin mathbb {R}}$. Свойство 2 приводит к ${displaystyle k <0}$. Тогда также сохраняются свойства 1 и 3.

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

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

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

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

1. Преемственность: ЧАС должно быть непрерывный, так что изменение значений вероятностей на очень малую величину должно изменять только энтропию на небольшую величину.
2. Симметрия: ЧАС должны быть неизменными, если результаты Икс_я переупорядочены. То есть, ${displaystyle mathrm {H} _ {n} left (p_ {1}, p_ {2}, ldots p_ {n} ight) = mathrm {H} _ {n} left (p_ {i_ {1}}, p_ { i_ {2}}, ldots, p_ {i_ {n}} ight)}$ для любого перестановка ${displaystyle {i_ {1}, ..., i_ {n}}}$ из ${displaystyle {1, ..., n}}$.
3. Максимум: H_n должен быть максимальным, если все исходы одинаково вероятны, т.е. ${displaystyle mathrm {H} _ {n} (p_ {1}, ldots, p_ {n}) leq mathrm {H} _ {n} left ({frac {1} {n}}, ldots, {frac {1 }{ночь)}$.
4. Увеличение количества исходов: для равновероятных событий энтропия должна увеличиваться с увеличением количества исходов, т.е. ${displaystyle mathrm {H} _ {n} {igg (} underbrace {{frac {1} {n}}, ldots, {frac {1} {n}}} _ {n} {igg)}$
5. Аддитивность: учитывая ансамбль п равномерно распределенные элементы, которые делятся на k ящики (подсистемы) с б₁, ..., б_k Для каждого элемента энтропия всего ансамбля должна быть равна сумме энтропии системы ящиков и индивидуальных энтропий ящиков, каждая из которых взвешена с вероятностью нахождения в этом конкретном ящике.

Правило аддитивности имеет следующие последствия: для положительные целые числа б_я куда б₁ + … + б_k = п,

${displaystyle mathrm {H} _ {n} left ({frac {1} {n}}, ldots, {frac {1} {n}} ight) = mathrm {H} _ {k} left ({frac {b_ {1}} {n}}, ldots, {frac {b_ {k}} {n}} ight) + sum _ {i = 1} ^ {k} {frac {b_ {i}} {n}}, mathrm {H} _ {b_ {i}} left ({frac {1} {b_ {i}}}, ldots, {frac {1} {b_ {i}}} ight).}$

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

Другие свойства

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

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

${displaystyle mathrm {H} _ {n + 1} (p_ {1}, ldots, p_ {n}, 0) = mathrm {H} _ {n} (p_ {1}, ldots, p_ {n})}$.

• Это можно подтвердить с помощью Неравенство Дженсена который

${displaystyle mathrm {H} (X) = имя оператора {E} left [log _ {b} left ({frac {1} {p (X)}} ight) ight] leq log _ {b} left (имя оператора {E } left [{frac {1} {p (X)}} ight] ight) = log _ {b} (n)}$.^[9]:29

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

• Энтропия или количество информации, обнаруженной при оценке (Икс,Y) (то есть оценка Икс и Y одновременно) равна информации, полученной в результате проведения двух последовательных экспериментов: сначала оценивается значение Y, затем раскрывая ценность Икс учитывая, что вы знаете ценность 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)}$, энтропия переменной может уменьшаться только тогда, когда последняя передается через функцию.

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

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

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

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

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

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

Аспекты

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

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

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

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

куда k_B это Постоянная Больцмана, и п_я это вероятность микросостояние. В Энтропия Гиббса был определен Дж. Уиллард Гиббс в 1878 г. после более ранней работы Больцман (1872).^[11]

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

${displaystyle S = -k_ {ext {B}}, {m {Tr}} (ho ln ho),}$

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

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

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

${displaystyle S = k_ {ext {B}} ln (Вт)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle mathrm {H} ({mathcal {S}}) = - сумма p_ {i} log p_ {i},}$

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

${displaystyle mathrm {H} ({mathcal {S}}) = - sum _ {i} p_ {i} sum _ {j} p_ {i} (j) log p_ {i} (j),}$^{[нужна цитата ]}

куда я это государственный (некоторые предыдущие символы) и ${displaystyle p_ {i} (j)}$ это вероятность 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}))} {журнал _ {b} (n)}}}$

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

${displaystyle eta (X) = - sum _ {i = 1} ^ {n} {frac {p (x_ {i}) log _ {b} (p (x_ {i}))} {log _ {b} (n)}} = сумма _ {i = 1} ^ {n} {frac {log _ {b} (p (x_ {i}) ^ {- p (x_ {i})})} {log _ { b} (n)}} = сумма _ {i = 1} ^ {n} log _ {n} (p (x_ {i}) ^ {- p (x_ {i})}) = log _ {n} (продукт _ {i = 1} ^ {n} p (x_ {i}) ^ {- p (x_ {i})})}$

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

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

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

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

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

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

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

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

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

Для этого начнем с непрерывной функции ж дискретизируется на бункеры по размеру ${displaystyle Delta}$.Согласно теореме о среднем значении существует значение Икс_я в каждом бункере так, чтобы

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

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

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

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

Обозначим

${displaystyle mathrm {H} ^ {Delta}: = - sum _ {i = -infty} ^ {infty} f (x_ {i}) Журнал дельты влево (f (x_ {i}) Delta ight)}$

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

${displaystyle mathrm {H} ^ {Delta} = - sum _ {i = -infty} ^ {infty} f (x_ {i}) Delta log (f (x_ {i})) - sum _ {i = -infty } ^ {infty} f (x_ {i}) Журнал дельты (дельта).}$

При ∆ → 0 имеем

${displaystyle {egin {align} sum _ {i = -infty} ^ {infty} f (x_ {i}) Delta & o int _ {- infty} ^ {infty} f (x), dx = 1 sum _ {i = -infty} ^ {infty} f (x_ {i}) Delta log (f (x_ {i})) & o int _ {- infty} ^ {infty} f (x) log f (x), dx.end {выровнено}}}$

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

${displaystyle h [f] = lim _ {Delta o 0} left (mathrm {H} ^ {Delta} + log Delta ight) = - int _ {- infty} ^ {infty} f (x) log f (x) , dx,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

куда п_я это ортогональная проекция в я-я координата:

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

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

${displaystyle mathrm {H} [(X_ {1}, ldots, X_ {d})] leq {frac {1} {r}} sum _ {i = 1} ^ {n} mathrm {H} [(X_ { j}) _ {jin S_ {i}}]}$

куда ${displaystyle (X_ {j}) _ {jin S_ {i}}}$ - декартово произведение случайных величин Икс_j с индексами j в S_я (так что размерность этого вектора равна размеру S_я).

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

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

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

${displaystyle {frac {2 ^ {nmathrm {H} (q)}} {n + 1}} leq {binom {n} {k}} leq 2 ^ {nmathrm {H} (q)},}$

куда

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

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

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

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

Смотрите также

Рекомендации

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

дальнейшее чтение

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

• Обложка, Т., Томас, Дж. (2006), Элементы теории информации - 2-е изд., Wiley-Interscience, ISBN  978-0-471-24195-9
• MacKay, D.J.C. (2003), Теория информации, логические выводы и алгоритмы обучения , Издательство Кембриджского университета, ISBN  978-0-521-64298-9
• Арндт, К. (2004), Информационные меры: информация и ее описание в науке и технике, Спрингер, ISBN  978-3-540-40855-0
• Грей, Р. М. (2011), Энтропия и теория информации, Springer.
• Мартин, Натаниэль Ф.Г. И Англия, Джеймс У. (2011). Математическая теория энтропии. Издательство Кембриджского университета. ISBN  978-0-521-17738-2.CS1 maint: использует параметр авторов (связь)
• Шеннон, К., Уивер, В. (1949) Математическая теория коммуникации, Univ of Illinois Press. ISBN  0-252-72548-4
• Стоун, Дж. В. (2014), Глава 1 Теория информации: Введение в учебное пособие, Университет Шеффилда, Англия. ISBN  978-0956372857.

внешняя ссылка

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