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

Ожидаемый объем информации, необходимый для определения выходных данных стохастического источника данных

В теории информации энтропия случайной величины количественно определяет средний уровень неопределенности или информации, связанной с потенциальными состояниями переменной или возможными результатами. Это измеряет ожидаемое количество информации, необходимое для описания состояния переменной, учитывая распределение вероятностей по всем потенциальным состояниям. Учитывая дискретную случайную величину , которая принимает значения в наборе и распределена в соответствии с , энтропия равна , где обозначает сумму по возможным значениям переменной. ^{[Примечание 1]} Выбор основания для , логарифма , различается для разных приложений. Основание 2 дает единицу бит (или « шенноны »), в то время как основание e дает «естественные единицы» nat , а основание 10 дает единицы «дит», «бан» или « хартли ». Эквивалентное определение энтропии — это ожидаемое значение собственной информации переменной. ^[1] ${\displaystyle X}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle p\colon {\mathcal {X}}\to [0,1]}$ $${\displaystyle \mathrm {H} (X):=-\sum _{x\in {\mathcal {X}}}p(x)\log p(x),}$$ ${\displaystyle \Sigma }$ ${\displaystyle \log }$

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

Понятие информационной энтропии было введено Клодом Шенноном в его статье 1948 года « Математическая теория связи » ^{[2] [3]} и также называется энтропией Шеннона . Теория Шеннона определяет систему передачи данных , состоящую из трех элементов: источника данных, канала связи и приемника. «Фундаментальная проблема связи» — как выразился Шеннон — заключается в том, чтобы приемник мог идентифицировать, какие данные были сгенерированы источником, на основе сигнала, который он получает через канал. ^{[2] [3]} Шеннон рассмотрел различные способы кодирования, сжатия и передачи сообщений из источника данных и доказал в своей теореме о кодировании источника , что энтропия представляет собой абсолютный математический предел того, насколько хорошо данные из источника могут быть без потерь сжаты в совершенно бесшумный канал. Шеннон значительно усилил этот результат для шумных каналов в своей теореме о кодировании шумного канала .

Энтропия в теории информации напрямую аналогична энтропии в статистической термодинамике . Аналогия возникает, когда значения случайной величины обозначают энергии микросостояний, поэтому формула Гиббса для энтропии формально идентична формуле Шеннона. Энтропия имеет отношение к другим областям математики, таким как комбинаторика и машинное обучение . Определение можно вывести из набора аксиом, устанавливающих, что энтропия должна быть мерой того, насколько информативен средний результат переменной. Для непрерывной случайной величины дифференциальная энтропия аналогична энтропии. Определение обобщает вышесказанное. ${\displaystyle \mathbb {E} [-\log p(X)]}$

Введение

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

Информационное содержание , также называемое неожиданностью или самоинформацией, события является функцией, которая увеличивается по мере уменьшения вероятности события. Когда близко к 1, неожиданность события низкая, но если близко к 0, неожиданность события высокая. Эта связь описывается функцией , где — логарифм , который дает 0 неожиданностей, когда вероятность события равна 1. ^[4] Фактически, log — единственная функция, которая удовлетворяет определенному набору условий, определенных в разделе § Характеристика . ${\displaystyle E}$ ${\displaystyle p(E)}$ ${\displaystyle p(E)}$ ${\displaystyle p(E)}$ $${\displaystyle \log \left({\frac {1}{p(E)}}\right),}$$ ${\displaystyle \log }$

Следовательно, мы можем определить информацию или неожиданность события с помощью или эквивалентно, ${\displaystyle E}$ $${\displaystyle I(E)=-\log _{2}(p(E)),}$$ $${\displaystyle I(E)=\log _{2}\left({\frac {1}{p(E)}}\right).}$$

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

Рассмотрим монету с вероятностью p выпадения орла и вероятностью 1 − p выпадения решки. Максимальный сюрприз наступает при p = 1/2 , при котором один результат не ожидается по сравнению с другим. В этом случае подбрасывание монеты имеет энтропию в один бит . (Аналогично, один трит с равновероятными значениями содержит (около 1,58496) бит информации, поскольку он может иметь одно из трех значений.) Минимальный сюрприз наступает при p = 0 или p = 1 , когда исход события известен заранее, а энтропия равна нулю бит. Когда энтропия равна нулю бит, это иногда называют единицей, когда нет никакой неопределенности вообще — никакой свободы выбора — никакой информации . Другие значения p дают энтропию от нуля до одного бита. ${\displaystyle \log _{2}3}$

Пример

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

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

Определение

Названный в честь Η-теоремы Больцмана , Шеннон определил энтропию Η (греческая заглавная буква эта ) дискретной случайной величины , которая принимает значения в наборе и распределена в соответствии с таким образом, что : ${\textstyle X}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle p:{\mathcal {X}}\to [0,1]}$ ${\displaystyle p(x):=\mathbb {P} [X=x]}$

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

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

Энтропия может быть явно записана как: где b — основание используемого логарифма . Обычные значения b — 2, число Эйлера e и 10, а соответствующие единицы энтропии — биты для b = 2 , наты для b = e и запреты для b = 10. [ ^9] $${\displaystyle \mathrm {H} (X)=-\sum _{x\in {\mathcal {X}}}p(x)\log _{b}p(x),}$$

В случае для некоторого значение соответствующего слагаемого 0 log _b (0) принимается равным 0 , что согласуется с пределом : ^{[10] : 13} ${\displaystyle p(x)=0}$ ${\displaystyle x\in {\mathcal {X}}}$ $${\displaystyle \lim _{p\to 0^{+}}p\log(p)=0.}$$

Можно также определить условную энтропию двух переменных и , принимающих значения из множеств и соответственно, как: ^{[10] : 16} где и . Эту величину следует понимать как остаточную случайность в случайной величине при заданной случайной величине . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {Y}}}$ $${\displaystyle \mathrm {H} (X|Y)=-\sum _{x,y\in {\mathcal {X}}\times {\mathcal {Y}}}p_{X,Y}(x,y)\log {\frac {p_{X,Y}(x,y)}{p_{Y}(y)}},}$$ ${\displaystyle p_{X,Y}(x,y):=\mathbb {P} [X=x,Y=y]}$ ${\displaystyle p_{Y}(y)=\mathbb {P} [Y=y]}$ ${\displaystyle X}$ ${\displaystyle Y}$

Теория меры

Энтропию можно формально определить на языке теории меры следующим образом: ^[11] Пусть будет вероятностным пространством . Пусть будет событием . Удивительно , что ${\displaystyle (X,\Sigma ,\mu )}$ ${\displaystyle A\in \Sigma }$ ${\displaystyle A}$ $${\displaystyle \sigma _{\mu }(A)=-\ln \mu (A).}$$

Ожидаемый сюрприз - это ${\displaystyle A}$ $${\displaystyle h_{\mu }(A)=\mu (A)\sigma _{\mu }(A).}$$

Почти разбиение — это семейство множеств, такое что и для всех различных . (Это ослабление обычных условий для разбиения.) Энтропия равна ${\displaystyle \mu }$ ${\displaystyle P\subseteq {\mathcal {P}}(X)}$ ${\displaystyle \mu (\mathop {\cup } P)=1}$ ${\displaystyle \mu (A\cap B)=0}$ ${\displaystyle A,B\in P}$ ${\displaystyle P}$ $${\displaystyle \mathrm {H} _{\mu }(P)=\sum _{A\in P}h_{\mu }(A).}$$

Пусть будет сигма-алгеброй на . Энтропия равна Наконец, энтропия вероятностного пространства равна , то есть энтропия относительно сигма-алгебры всех измеримых подмножеств . ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle M}$ $${\displaystyle \mathrm {H} _{\mu }(M)=\sup _{P\subseteq M}\mathrm {H} _{\mu }(P).}$$ ${\displaystyle \mathrm {H} _{\mu }(\Sigma )}$ ${\displaystyle \mu }$ ${\displaystyle X}$

Пример

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

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

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

Энтропия неизвестного результата следующего подбрасывания монеты максимальна, если монета честная (то есть, если и орел, и решка имеют одинаковую вероятность 1/2). Это ситуация максимальной неопределенности, поскольку предсказать результат следующего подбрасывания труднее всего; результат каждого подбрасывания монеты дает один полный бит информации. Это потому, что $${\displaystyle {\begin{aligned}\mathrm {H} (X)&=-\sum _{i=1}^{n}{p(x_{i})\log _{b}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}}}$$

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

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

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

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

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

Шеннон обнаружил, что подходящий выбор дается формулой: ^[13] ${\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}$

Различные единицы информации ( биты для двоичного логарифма log ₂ , nats для натурального логарифма ln , bans для десятичного логарифма log ₁₀ и т. д.) являются постоянными кратными друг другу. Например, в случае честного подбрасывания монеты орел дает log ₂ (2) = 1 бит информации, что составляет приблизительно 0,693 nats или 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 -арной энтропии. См. также Избыточность (теория информации) .

Характеристика здесь налагает аддитивное свойство по отношению к разделу множества . Между тем, условная вероятность определяется в терминах мультипликативного свойства, . Заметьте, что логарифм является посредником между этими двумя операциями. Условная энтропия и связанные с ней величины наследуют простое отношение, в свою очередь. Теоретико-мерное определение в предыдущем разделе определило энтропию как сумму по ожидаемым неожиданностям для экстремального раздела. Здесь логарифм является ad hoc, и энтропия сама по себе не является мерой. По крайней мере в теории информации двоичной строки, поддается практическим интерпретациям. ${\displaystyle P(A\mid B)\cdot P(B)=P(A\cap B)}$ ${\displaystyle \mu (A)\cdot \ln \mu (A)}$ ${\displaystyle \log _{2}}$

Мотивированные такими отношениями, были определены многочисленные связанные и конкурирующие величины. Например, анализ Дэвида Эллермана «логики разделов» определяет конкурирующую меру в структурах, двойственных подмножествам универсального множества. ^[14] Информация квантифицируется как «разницы» (различия), мера по разделам. «Разницы» можно преобразовать в биты Шеннона , чтобы получить формулы для условной энтропии и т. д.

Альтернативная характеристика через аддитивность и субаддитивность

Другая краткая аксиоматическая характеристика энтропии Шеннона была дана Ацелем , Форте и Нг ^[15] с помощью следующих свойств:

1. Субаддитивность: для совместно распределенных случайных величин . ${\displaystyle \mathrm {H} (X,Y)\leq \mathrm {H} (X)+\mathrm {H} (Y)}$ ${\displaystyle X,Y}$
2. Аддитивность: когда случайные величины независимы. ${\displaystyle \mathrm {H} (X,Y)=\mathrm {H} (X)+\mathrm {H} (Y)}$ ${\displaystyle X,Y}$
3. Расширяемость: т. е. добавление результата с вероятностью ноль не изменяет энтропию. ${\displaystyle \mathrm {H} _{n+1}(p_{1},\ldots ,p_{n},0)=\mathrm {H} _{n}(p_{1},\ldots ,p_{n})}$
4. Симметрия: инвариантна относительно перестановки . ${\displaystyle \mathrm {H} _{n}(p_{1},\ldots ,p_{n})}$ ${\displaystyle p_{1},\ldots ,p_{n}}$
5. Мало для малых вероятностей: . ${\displaystyle \lim _{q\to 0^{+}}\mathrm {H} _{2}(1-q,q)=0}$

Обсуждение

Было показано, что любая функция, удовлетворяющая вышеуказанным свойствам, должна быть постоянным множителем энтропии Шеннона, с неотрицательной константой. ^[15] По сравнению с ранее упомянутыми характеристиками энтропии, эта характеристика фокусируется на свойствах энтропии как функции случайных величин (субаддитивность и аддитивность), а не на свойствах энтропии как функции вектора вероятности . ${\displaystyle \mathrm {H} }$ ${\displaystyle p_{1},\ldots ,p_{n}}$

Стоит отметить, что если мы отбросим свойство «мал для малых вероятностей», то должна быть неотрицательная линейная комбинация энтропии Шеннона и энтропии Хартли . ^[15] ${\displaystyle \mathrm {H} }$

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

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

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

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

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

${\displaystyle \mathrm {H} (p_{1},\dots ,p_{n})\leq \log _{b}n}$. ^{[10] : 29}

• Энтропия или количество информации, выявленной путем оценки ( X , Y ) (то есть одновременной оценки X и Y ), равна информации, выявленной путем проведения двух последовательных экспериментов: сначала оценивая значение Y , затем выявляя значение X, при условии, что вы знаете значение Y. Это можно записать как: ^{[10] : 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 \mathrm {H} (f(X)|X)=0}$ ${\displaystyle \mathrm {H} (X,f(X))}$

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

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

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

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

• В более общем смысле, для любых случайных величин X и Y мы имеем

${\displaystyle \mathrm {H} (X|Y)\leq \mathrm {H} (X)}$. ^{[10] : 29}

• Энтропия двух одновременных событий не больше суммы энтропий каждого отдельного события, т.е. , с равенством тогда и только тогда, когда два события независимы. ^{[10] : 28} ${\displaystyle \mathrm {H} (X,Y)\leq \mathrm {H} (X)+\mathrm {H} (Y)}$
• Энтропия вогнута в функции массы вероятности , т.е. ^{[10] : 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})}$

для всех функций масс вероятности и . ^{[10] : 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). ^[16]

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

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

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

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

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

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

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

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

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

Определение энтропии Шеннона, применяемое к источнику информации, может определить минимальную пропускную способность канала, необходимую для надежной передачи источника в виде закодированных двоичных цифр. Энтропия Шеннона измеряет информацию, содержащуюся в сообщении, в отличие от части сообщения, которая определена (или предсказуема). Примерами последнего являются избыточность в языковой структуре или статистические свойства, относящиеся к частотам появления пар букв или слов, триплетов и т. д. Минимальная пропускная способность канала может быть реализована в теории с использованием типичного набора или на практике с использованием кодирования Хаффмана , Лемпеля–Зива или арифметического кодирования . (См. также сложность Колмогорова .) На практике алгоритмы сжатия намеренно включают некоторую разумную избыточность в виде контрольных сумм для защиты от ошибок. Скорость энтропии источника данных — это среднее количество бит на символ, необходимое для его кодирования. Эксперименты Шеннона с людьми-предикторами показывают скорость информации от 0,6 до 1,3 бит на символ в английском языке; ^[21] Алгоритм сжатия PPM может достичь коэффициента сжатия 1,5 бита на символ в английском тексте.

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

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

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

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

Энтропия — один из нескольких способов измерения биоразнообразия, применяемый в форме индекса Шеннона . ^[23] Индекс разнообразия — это количественная статистическая мера того, сколько различных типов существует в наборе данных, например, видов в сообществе, с учетом экологического богатства , равномерности и доминирования . В частности, энтропия Шеннона — это логарифм ¹ 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 бит энтропии. Также требуется (в среднем) несколько догадок, чтобы взломать его методом грубой силы. Энтропия не может охватить количество требуемых догадок, если возможные ключи не выбираются равномерно. ^{[24] [25]} Вместо этого для измерения усилий, необходимых для атаки методом грубой силы, можно использовать меру, называемую догадкой . ^[26] ${\displaystyle 2^{127}}$

Другие проблемы могут возникнуть из-за неравномерных распределений, используемых в криптографии. Например, 1 000 000-разрядный двоичный одноразовый блокнот, использующий исключающее ИЛИ. Если блокнот имеет 1 000 000 бит энтропии, он идеален. Если блокнот имеет 999 999 бит энтропии, равномерно распределенных (каждый отдельный бит блокнота имеет 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).}$

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

Исходный набор с неравномерным распределением будет иметь меньшую энтропию, чем тот же набор с равномерным распределением (т.е. «оптимизированный алфавит»). Этот дефицит энтропии может быть выражен как отношение, называемое эффективностью: ^[27] ${\displaystyle {\mathcal {X}}}$

${\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 ) с конечным или бесконечным носителем на действительной прямой определяется по аналогии, используя вышеуказанную форму энтропии в качестве ожидания: ^{[10] : 224} ${\displaystyle \mathbb {X} }$

${\displaystyle \mathrm {H} (X)=\mathbb {E} [-\log f(X)]=-\int _{\mathbb {X} }f(x)\log f(x)\,\mathrm {d} x.}$

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

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

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

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

Для этого начнем с непрерывной функции f, дискретизированной в ячейки размером . По теореме о среднем значении существует значение x _i в каждой ячейке, такое, что интеграл функции f может быть приближен (в римановом смысле) с помощью , где этот предел и «размер ячейки стремится к нулю» эквивалентны. ${\displaystyle \Delta }$ $${\displaystyle f(x_{i})\Delta =\int _{i\Delta }^{(i+1)\Delta }f(x)\,dx}$$ $${\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 \mathrm {H} =\int _{-\infty }^{\infty }f(x)\log(f(x)\,\Delta )\,dx,}$$

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

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

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

Использование в теории чисел

Теренс Тао использовал энтропию, чтобы создать полезную связь, пытаясь решить проблему расхождения Эрдёша . ^{[28] [29]}

Интуитивно идея доказательства заключалась в том, что если между последовательными случайными величинами имеется низкая информация с точки зрения энтропии Шеннона (здесь случайная величина определяется с помощью функции Лиувилля (которая является полезной математической функцией для изучения распределения простых чисел) X _H = . И в интервале [n, n+H] сумма по этому интервалу может стать сколь угодно большой. Например, последовательность +1 (которые являются значениями X _H' ) имеет тривиально низкую энтропию, и их сумма станет большой. Но ключевое понимание заключалось в том, чтобы показать уменьшение энтропии на не пренебрежимо малые величины по мере того, как кто-то расширяет H, приводящее в свою очередь к неограниченному росту математического объекта по этой случайной величине, что эквивалентно демонстрации неограниченного роста согласно проблеме расхождения Эрдёша . ${\displaystyle \lambda (n+H)}$

Доказательство довольно сложное и оно объединило прорывы не только в новом использовании энтропии Шеннона, но также использовало функцию Лиувилля вместе со средними модулированными мультипликативными функциями Архивировано 28 октября 2023 года на Wayback Machine в короткие интервалы. Доказывая, что оно также сломало «барьер четности» Архивировано 7 августа 2023 года на Wayback Machine для этой конкретной проблемы.

Хотя использование энтропии Шеннона в доказательстве является новым, оно, вероятно, откроет новые исследования в этом направлении.

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

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

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

Простым примером этого является альтернативное доказательство неравенства Лумиса–Уитни : для каждого подмножества 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 | , где | A | обозначает мощность 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).}$^{[30] : 43}

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

Использование в машинном обучении

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

Алгоритмы обучения на основе деревьев решений используют относительную энтропию для определения правил принятия решений, которые управляют данными в каждом узле. ^[32] Прирост информации в деревьях решений , который равен разнице между энтропией и условной энтропией заданного , количественно определяет ожидаемую информацию или снижение энтропии от дополнительного знания значения атрибута . Прирост информации используется для определения того, какие атрибуты набора данных предоставляют наибольшую информацию и должны использоваться для оптимального разделения узлов дерева. ${\displaystyle IG(Y,X)}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$

Байесовские модели вывода часто применяют принцип максимальной энтропии для получения априорных распределений вероятностей . ^[33] Идея заключается в том, что распределение, которое наилучшим образом представляет текущее состояние знаний о системе, имеет наибольшую энтропию и, следовательно, подходит в качестве априорного.

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

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

• Математический портал

• Приблизительная энтропия (ApEn)
• Энтропия (термодинамика)
• Перекрестная энтропия – это мера среднего числа битов, необходимых для идентификации события из набора возможностей между двумя распределениями вероятностей.
• Энтропия (стрела времени)
• Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы длины кодов соответствовали вероятностям символов.
• Оценка энтропии
• Неравенство энтропийной мощности
• Информация о Фишере
• Графическая энтропия
• Расстояние Хэмминга
• История энтропии
• История теории информации
• Сложность флуктуации информации
• Информационная геометрия
• Энтропия Колмогорова–Синая в динамических системах
• Расстояние Левенштейна
• Взаимная информация
• Недоумение
• Качественная вариация – другие меры статистической дисперсии для номинальных распределений
• Квантовая относительная энтропия – мера различимости двух квантовых состояний.
• Энтропия Реньи — обобщение энтропии Шеннона; это один из семейства функционалов для количественной оценки разнообразия, неопределенности или случайности системы.
• Случайность
• Энтропия выборки (SampEn)
• индекс Шеннона
• индекс Тейла
• Типогликемия

Примечания

1. Это определение допускает события с вероятностью 0, что приводит к неопределенному . Мы видим и можно предположить, что равно 0 в этом контексте. В качестве альтернативы можно определить , не допуская событий с вероятностью, равной точно 0. ${\displaystyle \log(0)}$ ${\displaystyle \lim \limits _{x\rightarrow 0}x\log(x)=0}$ ${\displaystyle 0\log(0)}$ ${\displaystyle p\colon {\mathcal {X}}\to (0,1]}$

Ссылки

1. Патрия, РК; Бил, Пол (2011). Статистическая механика (третье изд.). Academic Press. стр. 51. ISBN 978-0123821881.
2. Шеннон, Клод Э. (июль 1948 г.). "Математическая теория связи" . Bell System Technical Journal . 27 (3): 379–423. doi :10.1002/j.1538-7305.1948.tb01338.x. hdl : 10338.dmlcz/101429 .(PDF, архив отсюда Архивировано 20 июня 2014 г. на Wayback Machine )
3. Шеннон, Клод Э. (октябрь 1948 г.). "Математическая теория связи" . Bell System Technical Journal . 27 (4): 623–656. doi :10.1002/j.1538-7305.1948.tb00917.x. hdl : 11858/00-001M-0000-002C-4317-B .(PDF, архив отсюда Архивировано 10 мая 2013 г. на Wayback Machine )
4. "Энтропия (для науки о данных) Ясно объяснено!!!". Архивировано из оригинала 5 октября 2021 г. Получено 5 октября 2021 г. – через YouTube .
5. MacKay, David JC (2003). Теория информации, вывод и алгоритмы обучения. Cambridge University Press. ISBN 0-521-64298-1. Архивировано из оригинала 17 февраля 2016 . Получено 9 июня 2014 .
6. Шнайер, Б.: Прикладная криптография , второе издание, John Wiley and Sons.
7. Борда, Моника (2011). Основы теории информации и кодирования. Springer. ISBN 978-3-642-20346-6.
8. Хан, Те Сан; Кобаяши, Кинго (2002). Математика информации и кодирования. Американское математическое общество. ISBN 978-0-8218-4256-0.
9. Шнайдер, ТД, Учебник по теории информации с приложением о логарифмах ^{[ постоянная неработающая ссылка ]} , Национальный институт рака, 14 апреля 2007 г.
10. Томас М. Кавер; Джой А. Томас (1991). Элементы теории информации . Хобокен, Нью-Джерси: Wiley. ISBN 978-0-471-24195-9.
11. Энтропия в n -лаборатории
12. Картер, Том (март 2014 г.). Введение в теорию информации и энтропию (PDF) . Санта-Фе. Архивировано (PDF) из оригинала 4 июня 2016 г. Получено 4 августа 2017 г.{{cite book}}: CS1 maint: location missing publisher (link)
13. Чакрабарти, К. Г. и Индранил Чакрабарти. «Энтропия Шеннона: аксиоматическая характеристика и применение». Международный журнал математики и математических наук 2005. 17 (2005): 2847-2854 url ​​Архивировано 5 октября 2021 г. в Wayback Machine
14. Эллерман, Дэвид (октябрь 2017 г.). «Логическая теория информации: новые логические основы теории информации» (PDF) . Logic Journal of the IGPL . 25 (5): 806–835. doi :10.1093/jigpal/jzx022. Архивировано (PDF) из оригинала 25 декабря 2022 г. . Получено 2 ноября 2022 г. .
15. Aczél, J.; Forte, B.; Ng, CT (1974). "Почему энтропии Шеннона и Хартли являются "естественными"". Достижения в прикладной теории вероятностей . 6 (1): 131–146. doi :10.2307/1426210. JSTOR  1426210. S2CID  204177762.
16. Сравните: Больцман, Людвиг (1896, 1898). Vorlesungen über Gastheorie: 2 тома – Лейпциг, 1895/98 UB: O 5262-6. Английская версия: Лекции по теории газов. Перевод Стивена Г. Браша (1964) Беркли: Издательство Калифорнийского университета; (1995) Нью-Йорк: ISBN Дувра 0-486-68455-5 
17. Жычковский, Кароль (2006). Геометрия квантовых состояний: введение в квантовую запутанность . Cambridge University Press. стр. 301.
18. Шарп, Ким; Мачински, Франц (2015). «Перевод статьи Людвига Больцмана «О связи между второй фундаментальной теоремой механической теории тепла и вероятностными расчетами относительно условий теплового равновесия»». Энтропия . 17 : 1971–2009. doi : 10.3390/e17041971 .
19. Jaynes, ET (15 мая 1957 г.). «Теория информации и статистическая механика». Physical Review . 106 (4): 620–630. Bibcode : 1957PhRv..106..620J. doi : 10.1103/PhysRev.106.620. S2CID  17870175.
20. Ландауэр, Р. (июль 1961 г.). «Необратимость и выделение тепла в вычислительном процессе». IBM Journal of Research and Development . 5 (3): 183–191. doi :10.1147/rd.53.0183. ISSN  0018-8646. Архивировано из оригинала 15 декабря 2021 г. . Получено 15 декабря 2021 г. .
21. Марк Нельсон (24 августа 2006 г.). «Премия Хаттера». Архивировано из оригинала 1 марта 2018 г. Получено 27 ноября 2008 г.
22. «Технологические возможности мира по хранению, передаче и вычислению информации» Архивировано 27 июля 2013 г. в Wayback Machine , Мартин Хильберт и Присцила Лопес (2011), Science , 332(6025); свободный доступ к статье здесь: martinhilbert.net/WorldInfoCapacity.html
23. Спеллерберг, Ян Ф.; Федор, Питер Дж. (2003). «Дань уважения Клоду Шеннону (1916–2001) и призыв к более строгому использованию видового богатства, видового разнообразия и индекса «Шеннона–Винера»». Глобальная экология и биогеография . 12 (3): 177–179. Bibcode :2003GloEB..12..177S. doi : 10.1046/j.1466-822X.2003.00015.x . ISSN  1466-8238. S2CID  85935463.
24. Massey, James (1994). "Guessing and Entropy" (PDF) . Proc. IEEE International Symposium on Information Theory . Архивировано (PDF) из оригинала 1 января 2014 года . Получено 31 декабря 2013 года .
25. Malone, David; Sullivan, Wayne (2005). «Догадки не заменяют энтропию» (PDF) . Труды конференции по информационным технологиям и телекоммуникациям . Архивировано (PDF) из оригинала 15 апреля 2016 г. . Получено 31 декабря 2013 г. .
26. Pliam, John (1999). "Selected Areas in Cryptography". Международный семинар по Selected Areas in Cryptography . Lecture Notes in Computer Science. Vol. 1758. pp. 62–77. doi : 10.1007/3-540-46513-8_5 . ISBN 978-3-540-67185-5.
27. Индексы качественной вариации. AR Wilcox - 1967 https://www.osti.gov/servlets/purl/4167340
28. Кларрайх, Эрика (1 октября 2015 г.). «Волшебный ответ на 80-летнюю головоломку». Журнал Quanta . Получено 18 августа 2014 г.
29. Тао, Теренс (28 февраля 2016 г.). "Проблема расхождения Эрдёша". Дискретный анализ . arXiv : 1509.05363v6 . doi : 10.19086/da.609. S2CID  59361755. Архивировано из оригинала 25 сентября 2023 г. Получено 20 сентября 2023 г.
30. Аоки, Новые подходы к макроэкономическому моделированию.
31. Вероятность и вычисления, М. Митценмахер и Э. Упфал, Cambridge University Press
32. Батра, Мридула; Агравал, Рашми (2018). «Сравнительный анализ алгоритмов дерева решений». В Паниграхи, Биджая Кетан; Хода, МН; Шарма, Винод; Гоэль, Шивендра (ред.). Nature Inspired Computing . Advances in Intelligent Systems and Computing. Vol. 652. Сингапур: Springer. стр. 31–36. doi :10.1007/978-981-10-6747-1_4. ISBN 978-981-10-6747-1. Архивировано из оригинала 19 декабря 2022 г. . Получено 16 декабря 2021 г. .
33. Jaynes, Edwin T. (сентябрь 1968 г.). «Априорные вероятности». IEEE Transactions on Systems Science and Cybernetics . 4 (3): 227–241. doi :10.1109/TSSC.1968.300117. ISSN  2168-2887. Архивировано из оригинала 16 декабря 2021 г. . Получено 16 декабря 2021 г. .
34. Рубинштейн, Реувен Й.; Крезе, Дирк П. (9 марта 2013 г.). Метод кросс-энтропии: унифицированный подход к комбинаторной оптимизации, моделированию Монте-Карло и машинному обучению. Springer Science & Business Media. ISBN 978-1-4757-4321-0.

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

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

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

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

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

• «Энтропия», Энциклопедия математики , EMS Press , 2001 [1994]
• «Энтропия» Архивировано 4 июня 2016 г. в Wayback Machine в Rosetta Code — репозитории реализаций энтропии Шеннона на разных языках программирования.
• Энтропия Архивировано 31 мая 2016 г. в Wayback Machine — междисциплинарном журнале по всем аспектам концепции энтропии. Открытый доступ.