Неравенства в теории информации

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

Энтропийные неравенства

Рассмотрим кортеж $X_{1},X_{2},\dots ,X_{n}$ из $n$ конечно (или не более чем счетно) поддерживаемые случайные величины в одном и том же вероятностном пространстве . Есть 2 ^н подмножества, для которых ( совместную можно вычислить ) энтропию. Например, когда n = 2, мы можем рассматривать энтропии $H(X_{1}),$ $H(X_{2}),$ и $H(X_{1},X_{2})$ . Они удовлетворяют следующим неравенствам (которые в совокупности характеризуют диапазон предельной и совместной энтропии двух случайных величин):

$H(X_{1})\geq 0$
$H(X_{2})\geq 0$
$H(X_{1})\leq H(X_{1},X_{2})$
$H(X_{2})\leq H(X_{1},X_{2})$
$H(X_{1},X_{2})\leq H(X_{1})+H(X_{2}).$

Фактически, все это можно выразить как частные случаи одного неравенства, включающего условную взаимную информацию , а именно:

I(A;B|C)\geq 0,

где $A$ , $B$ , и $C$ каждый обозначает совместное распределение некоторого произвольного (возможно, пустого) подмножества нашей коллекции случайных величин. Неравенства, которые можно получить как линейные комбинации этих уравнений, известны как типа Шеннона неравенства .

Для большего $n$ существуют дополнительные ограничения на возможные значения энтропии.Чтобы быть точным, вектор $h$ в $\mathbb {R} ^{2^{n}}$ индексируется подмножествами $\{1,\dots ,n\}$ называется энтропийным , если существует совместное дискретное распределение n случайных величин. $X_{1},\dots ,X_{n}$ такой, что $h_{I}=H(X_{i}\colon i\in I)$ — их совместная энтропия для каждого подмножества $I$ .Множество энтропийных векторов обозначается $\Gamma _{n}^{*}$ , следуя обозначениям Юнга. ^[1]Оно не является ни замкнутым, ни выпуклым для $n\geq 3$ , но его топологическое замыкание ${\overline {\Gamma _{n}^{*}}}$ известно, что он выпуклый и, следовательно, может характеризоваться (бесконечным множеством) линейными неравенствами, которым удовлетворяют все энтропийные векторы, называемыми энтропийными неравенствами .

Набор всех векторов, удовлетворяющих неравенствам типа Шеннона (но не обязательно другим энтропийным неравенствам), содержит ${\overline {\Gamma _{n}^{*}}}$ .Это сдерживание является строгим для $n\geq 4$ и дальнейшие неравенства известны как неравенства нешенноновского типа .Чжан и Юнг сообщили о первом неравенстве нешенноновского типа: ^[2] часто называют неравенством Чжана-Юна. Матус ^[3] доказал, что никакой конечный набор неравенств не может характеризовать (линейными комбинациями) все энтропийные неравенства. Другими словами, регион ${\overline {\Gamma _{n}^{*}}}$ не является многогранником .

Нижние оценки расходимости Кульбака–Лейблера

Очень многие важные неравенства в теории информации на самом деле являются нижними оценками расходимости Кульбака – Лейблера . Даже неравенства типа Шеннона можно считать частью этой категории, поскольку информация о взаимодействии может быть выражена как расхождение Кульбака – Лейблера совместного распределения относительно произведения маргиналов, и, таким образом, эти неравенства можно рассматривать как особое случай неравенства Гиббса .

С другой стороны, оказывается, гораздо труднее получить полезные верхние оценки расходимости Кульбака–Лейблера. связано с тем, что дивергенция Кульбака-Лейблера D _KL ( P || Q ) очень чувствительно зависит от событий, которые очень редки в эталонном распределении Q. Это D _KL ( P || Q ) неограниченно увеличивается, поскольку событие с конечной ненулевой вероятностью в распределении P становится чрезвычайно редким в эталонном распределении Q , и фактически D _KL ( P || Q ) даже не определяется, если событие ненулевой вероятности в P имеет нулевую вероятность в Q . (Отсюда и требование, чтобы P было абсолютно непрерывным относительно Q. )

Неравенство Гиббса

Это фундаментальное неравенство утверждает, что расхождение Кульбака – Лейблера неотрицательно.

Неравенство Кульбака

Другое неравенство, касающееся расхождения Кульбака – Лейблера, известно как неравенство Кульбака . ^[4] Если P и Q — распределения вероятностей на действительной прямой с P абсолютно непрерывным относительно Q и первые моменты которых существуют, то

D_{KL}(P\parallel Q)\geq \Psi _{Q}^{*}(\mu '_{1}(P)),

где $\Psi _{Q}^{*}$ — больших уклонений функция скорости , т.е. выпуклая функция, сопряженная к кумулянтной производящей функции Q , и $\mu '_{1}(P)$ первый момент P . это

Оценка Крамера –Рао является следствием этого результата.

Неравенство Пинскера

Неравенство Пинскера связывает расхождение Кульбака – Лейблера и общее вариационное расстояние . Он утверждает, что если P , Q — два распределения вероятностей , то

{\sqrt {{\frac {1}{2}}D_{KL}^{(e)}(P\parallel Q)}}\geq \sup\{|P(A)-Q(A)|:A{\text{ is an event to which probabilities are assigned.}}\}.

где

D_{KL}^{(e)}(P\parallel Q)

– это расхождение Кульбака–Лейблера в nats и

\sup _{A}|P(A)-Q(A)|

– полное расстояние вариации.

Другие неравенства

Неопределенность Хиршмана

В 1957 году ^[5] Хиршман показал, что для (достаточно хорошей) функции $f:\mathbb {R} \rightarrow \mathbb {C}$ такой, что $\int _{-\infty }^{\infty }|f(x)|^{2}\,dx=1,$ и его преобразование Фурье $g(y)=\int _{-\infty }^{\infty }f(x)e^{-2\pi ixy}\,dx,$ сумма энтропий дифференциальных $|f|^{2}$ и $|g|^{2}$ неотрицательен, т.е.

-\int _{-\infty }^{\infty }|f(x)|^{2}\log |f(x)|^{2}\,dx-\int _{-\infty }^{\infty }|g(y)|^{2}\log |g(y)|^{2}\,dy\geq 0.

Хиршман предположил, и позже это было доказано: ^[6] что более резкая граница $\log(e/2),$ которое достигается в случае распределения Гаусса , могло бы заменить правую часть этого неравенства. Это особенно важно, поскольку оно подразумевает и является более сильным, чем формулировка Вейля принципа неопределенности Гейзенберга .

Неравенство Дао

Даны дискретные случайные величины $X$ , $Y$ , и $Y'$ , такой, что $X$ принимает значения только в интервале [−1, 1] и $Y'$ определяется $Y$ (такой, что $H(Y'|Y)=0$ ), у нас есть ^[7]^[8]

\operatorname {E} {\big (}{\big |}\operatorname {E} (X|Y')-\operatorname {E} (X\mid Y){\big |}{\big )}\leq {\sqrt {I(X;Y\mid Y')\,2\log 2}},

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

Машинная проверка доказательств теоретико-информационных неравенств

Теперь доступно несколько алгоритмов машинной проверки доказательств. Алгоритмы проверки доказательств обычно проверяют неравенства как истинные или ложные. Более продвинутые алгоритмы проверки доказательств могут создавать доказательства или контрпримеры. ^[9]ITIP — это средство проверки доказательств на основе Matlab для всех неравенств типа Шеннона. Xitip — это более быстрая версия того же алгоритма с открытым исходным кодом, реализованная на C, с графическим интерфейсом. Xitip также имеет встроенную функцию синтаксического анализа языка, которая поддерживает более широкий диапазон описаний случайных величин в качестве входных данных. AITIP и oXitip — это облачные реализации для проверки неравенств типа Шеннона. oXitip использует оптимизатор GLPK и имеет серверную часть C++ на основе Xitip с пользовательским веб-интерфейсом. AITIP использует решатель Gurobi для оптимизации и сочетание Python и C++ в внутренней реализации. Он также может обеспечить каноническое разрушение неравенства с точки зрения основных информационных показателей. ^[9]

См. также

Ссылки

^ Юнг, RW (1997). «Основы линейного информационного неравенства». Транзакции IEEE по теории информации . 43 (6): 1924–1934. дои : 10.1109/18.641556 . )
^ Чжан, З.; Юнг, RW (1998). «О характеризации функции энтропии с помощью информационных неравенств». Транзакции IEEE по теории информации . 44 (4): 1440–1452. дои : 10.1109/18.681320 .
^ Матус, Ф. (2007). Бесконечно множество информационных неравенств . 2007 Международный симпозиум IEEE по теории информации.
^ Фукс, Эме; Летта, Джорджио (1970). «Неравенство КУЛЛБАКА. Приложение к теории оценивания». Семинар по теории вероятностей IV Страсбургского университета . Конспект лекций по математике. Полет. 124. Страсбург. стр. 108–131. дои : 10.1007/bfb0059338 . ISBN 978-3-540-04913-5 . МР 0267669 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Хиршман, II (1957). «Заметка об энтропии». Американский журнал математики . 79 (1): 152–156. дои : 10.2307/2372390 . JSTOR 2372390 .
^ Бекнер, В. (1975). «Неравенства в анализе Фурье». Анналы математики . 102 (6): 159–182. дои : 10.2307/1970980 . JSTOR 1970980 .
^ Тао, Т. (2006). «Еще раз к лемме о регулярности Семереди». Вклад. Дискретная математика . 1 :8–28. arXiv : math/0504472 . Бибкод : 2005math......4472T .
^ Альсведе, Рудольф (2007). «Окончательная форма неравенства Дао, связывающего условное ожидание и условную взаимную информацию» . Достижения в области математики связи . 1 (2): 239–242. дои : 10.3934/amc.2007.1.239 .
^ Jump up to: ^а ^б Хо, Юго-Запад; Линг, Л.; Тан, CW; Юнг, RW (2020). «Доказательство и опровержение информационного неравенства: теория и масштабируемые алгоритмы». Транзакции IEEE по теории информации . 66 (9): 5525–5536. дои : 10.1109/TIT.2020.2982642 . S2CID 216530139 .

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

Томас М. Ковер, Джой А. Томас. Элементы теории информации , глава 16, «Неравенства в теории информации», John Wiley & Sons, Inc., 1991 г. Печать ISBN 0-471-06259-6 Онлайн ISBN 0-471-20061-1
Амир Дембо, Томас М. Ковер, Джой А. Томас. Теоретико-информационные неравенства. Транзакции IEEE по теории информации, Vol. 37, № 6, ноябрь 1991 г. pdf
ИТИП: http://user-www.ie.cuhk.edu.hk/~ITIP/
XITIP: http://xitip.epfl.ch
Н. Р. Пай, Сухас Диггави, Т. Гласле, Э. Перрон, Р. Пуликкунатту, Р. В. Йенг, Ю. Ян, oXitip: онлайн-доказательство теоретико-информационного неравенства http://www.oxitip.com
Сиу Вай Хо, Линь Лин, Чи Вэй Тан и Рэймонд В. Юнг, AITIP (доказательство теоретического информационного неравенства): https://aitip.org
Ниведита Ретнакар, Сухас Диггави, Раймонд. В. Юнг, InformationInequalities.jl: Исследование теоретико-информационного неравенства, Пакет Джулии, 2021 г. [1]

[1] Юнг, RW (1997). «Основы линейного информационного неравенства». Транзакции IEEE по теории информации . 43 (6): 1924–1934. дои : 10.1109/18.641556 . )

[:1-2] Чжан, З.; Юнг, RW (1998). «О характеризации функции энтропии с помощью информационных неравенств». Транзакции IEEE по теории информации . 44 (4): 1440–1452. дои : 10.1109/18.681320 .

[3] Матус, Ф. (2007). Бесконечно множество информационных неравенств . 2007 Международный симпозиум IEEE по теории информации.

[4] Фукс, Эме; Летта, Джорджио (1970). «Неравенство КУЛЛБАКА. Приложение к теории оценивания». Семинар по теории вероятностей IV Страсбургского университета . Конспект лекций по математике. Полет. 124. Страсбург. стр. 108–131. дои : 10.1007/bfb0059338 . ISBN 978-3-540-04913-5 . МР 0267669 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[5] Хиршман, II (1957). «Заметка об энтропии». Американский журнал математики . 79 (1): 152–156. дои : 10.2307/2372390 . JSTOR 2372390 .

[6] Бекнер, В. (1975). «Неравенства в анализе Фурье». Анналы математики . 102 (6): 159–182. дои : 10.2307/1970980 . JSTOR 1970980 .

[7] Тао, Т. (2006). «Еще раз к лемме о регулярности Семереди». Вклад. Дискретная математика . 1 :8–28. arXiv : math/0504472 . Бибкод : 2005math......4472T .

[8] Альсведе, Рудольф (2007). «Окончательная форма неравенства Дао, связывающего условное ожидание и условную взаимную информацию» . Достижения в области математики связи . 1 (2): 239–242. дои : 10.3934/amc.2007.1.239 .

[IEEE-66-9-9] Jump up to: ^а ^б Хо, Юго-Запад; Линг, Л.; Тан, CW; Юнг, RW (2020). «Доказательство и опровержение информационного неравенства: теория и масштабируемые алгоритмы». Транзакции IEEE по теории информации . 66 (9): 5525–5536. дои : 10.1109/TIT.2020.2982642 . S2CID 216530139 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]