Энтропийный вектор

Энтропийный вектор или энтропийная функция — понятие, возникающее в теории информации . Он представляет возможные значения Шеннона информационной энтропии , которые могут принимать подмножества одного набора случайных величин. Понимание того, какие векторы являются энтропийными, — это способ представить все возможные неравенства между энтропиями различных подмножеств. Например, для любых двух случайных величин $X_{1},X_{2}$, их совместная энтропия (энтропия случайной величины, представляющей пару $X_{1},X_{2}$) не более чем сумма энтропий $X_{1}$ и из $X_{2}$:

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

Другие меры теории информации, такие как условная информация , взаимная информация или полная корреляция , могут быть выражены через совместную энтропию и, таким образом, связаны соответствующими неравенствами.Многие неравенства, которым удовлетворяют энтропийные векторы, могут быть получены как линейные комбинации нескольких основных неравенств, называемых неравенствами типа Шеннона .Однако доказано, что уже для $n=4$ переменных, никакого конечного набора линейных неравенств недостаточно, чтобы охарактеризовать все энтропийные векторы.

Определение

Шеннона Информационная энтропия случайной величины $X$ обозначается $H(X)$.Для кортежа случайных величин $X_{1},X_{2},\ldots ,X_{n}$, мы обозначаем совместную энтропию подмножества $X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}}$ как $H(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})$или, более кратко, как $H(X_{I})$, где $I=\{i_{1},i_{2},\dots ,i_{k}\}$. Здесь $X_{I}$ можно понимать как случайную величину, представляющую кортеж $(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})$.Для пустого подмножества $I=\emptyset$, $X_{I}$ обозначает детерминированную переменную с энтропией 0.

Вектор h в $\mathbb {R} ^{2^{n}}$ индексируется подмножествами $\{1,2,\dots ,n\}$ называется энтропийным вектором порядка $n$ если существует кортеж случайных величин $X_{1},X_{2},\ldots ,X_{n}$ такой, что $h(I)=H(X_{I})$ для каждого подмножества $I\subseteq \{1,2,\dots ,n\}$.

Набор всех энтропийных векторов порядка $n$ обозначается $\Gamma _{n}^{*}$.Чжан и Юнг доказано, что оно не замкнуто (ибо $n\geq 3$), но его закрытие , ${\bar {\Gamma _{n}^{*}}}$, является выпуклым конусом и, следовательно, характеризуется (бесконечным множеством) линейными неравенствами, которым он удовлетворяет.Описание региона ${\bar {\Gamma _{n}^{*}}}$ таким образом, эквивалентно описанию всех возможных неравенств относительно совместных энтропий.

Пример

Пусть X , Y — две независимые случайные величины с дискретным равномерным распределением по множеству $\{0,1\}$. Затем

$H(X)=H(Y)=1$

(поскольку каждый из них равномерно распределен по набору из двух элементов) и

$H(X,Y)=H(X)+H(Y)=2$

(поскольку две переменные независимы, что означает, что пара $(X_{1},X_{2})$ равномерно распределен по $(0,0),(0,1),(1,0),(1,1)$.)Таким образом, соответствующий энтропийный вектор:

$v=(0,1,1,2)^{\mathsf {T}}\in \Gamma _{2}^{*}$

С другой стороны, вектор $(0,1,1,3)^{\mathsf {T}}$ не является энтропийным (т. $(0,1,1,3)^{\mathsf {T}}\not \in \Gamma _{2}^{*}$), поскольку любая пара случайных величин (независимых или нет) должна удовлетворять $H(X,Y)\leq H(X)+H(Y)$.

Характеризующие энтропийные векторы: область Γ _n ^*

Неравенства типа Шеннона и Γ _n

Для кортежа случайных величин $X_{1},X_{2},\ldots ,X_{n}$, их энтропии удовлетворяют:

$1)\quad H(X_{\emptyset })=0$

$2)\quad H(X_{I})\leq H(X_{J})$, для любого $I\subseteq J\subseteq \{1,\dots ,n\}$

В частности, $H(X_{I})\geq 0$, для любого $I\subseteq \{1,\dots ,n\}$.

Неравенство Шеннона утверждает, что энтропийный вектор субмодулярен :

$3)\quad H(X_{I})+H(X_{J})\geq H(X_{I\cup J})+H(X_{I\cap J})$, для любого $I,J\subseteq \{1,\dots ,n\}$

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

${\begin{aligned}I(X;Y\mid Z)&=H(X\mid Z)-H(X\mid Y,Z)\\&=H(X\mid Z)+H(Y\mid Z)-H(X,Y\mid Z)\\&=H(X,Z)+H(Y,Z)-H(X,Y,Z)-H(Z)\\&\geq 0\end{aligned}}$

(Для одного направления обратите внимание на то, что последняя форма выражает неравенство Шеннона для подмножеств $X,Z$ и $Y,Z$ кортежа $X,Y,Z$; для другого направления замените $X=X_{I}$, $Y=X_{J}$, $Z=X_{I\cap J}$).

Многие неравенства могут быть получены как линейные комбинации неравенств Шеннона; они называются неравенствами типа Шеннона или базовыми информационными неравенствами информационных мер Шеннона. Множество векторов, удовлетворяющее им, называется $\Gamma _{n}$; он содержит $\Gamma _{n}^{*}$.

Разработано программное обеспечение для автоматизации задачи доказательства неравенств типа Шеннона. Учитывая неравенство, такое программное обеспечение способно определить, является ли данное неравенство допустимым неравенством типа Шеннона (т. е. содержит ли оно конус $\Gamma _{n}$).

Неравенства нешенноновского типа

Вопрос о том, являются ли неравенства типа Шеннона единственными, то есть полностью ли они характеризуют регион $\Gamma _{n}^{*}$, впервые спросил Тэ Су Хань в 1981 году. а точнее Николасом Пиппенджером в 1986 году. Нетрудно показать, что это верно для двух переменных, т. е. $\Gamma _{2}^{*}=\Gamma _{2}$.Для трех переменных Чжан и Юнг доказал, что $\Gamma _{3}^{*}\neq \Gamma _{3}$; однако это по-прежнему асимптотически верно, а это означает, что замыкание равно: ${\overline {\Gamma _{3}^{*}}}=\Gamma _{3}$.В 1998 году Чжан и Юнг показал, что ${\overline {\Gamma _{n}^{*}}}\neq \Gamma _{n}$ для всех $n\geq 4$, доказав, что следующее неравенство для четырех случайных величин (с точки зрения условной взаимной информации) верно для любого энтропийного вектора, но не относится к типу Шеннона:

$2I(X_{3};X_{4})\leq I(X_{1};X_{2})+I(X_{1};X_{3},X_{4})+3I(X_{3};X_{4}|X_{1})+I(X_{3};X_{4}|X_{2})$

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

аналогичные вопросы для энтропии фон Неймана в квантовой теории информации . Рассмотрены

Внутренние границы

Некоторые внутренние границы ${\overline {\Gamma _{n}^{*}}}$ также известны.Одним из примеров является то, что ${\overline {\Gamma _{4}^{*}}}$ содержит все векторы в $\Gamma _{4}$ которые дополнительно удовлетворяют следующему неравенству (и полученному перестановкой переменных), известному как неравенство Инглтона для энтропии :

$I(X_{1};X_{2})+I(X_{3};X_{4}\mid X_{1})+I(X_{3};X_{4}\mid X_{2})-I(X_{3};X_{4})\geq 0$

Энтропия и группы

Группово-характеризуемые векторы и квазиравномерные распределения

Рассмотрим группу $G$ и подгруппы $G_{1},G_{2},\dots ,G_{n}$ из $G$.Позволять $G_{I}$ обозначать $\bigcap _{i\in I}G_{i}$ для $I\subseteq \{1,\dots ,n\}$; это тоже подгруппа $G$.Можно построить распределение вероятностей для $n$ случайные величины $X_{1},\dots ,X_{n}$ такой, что

$H(X_{I})=\log {\frac {|G|}{|G_{I}|}}$.

(Конструкция по существу принимает элемент $a$ из $G$ равномерно случайным образом и позволяет $X_{i}$ быть соответствующим смежным классом $aG_{i}$). Таким образом, любое теоретико-информационное неравенство подразумевает теоретико-групповое неравенство. Например, основное неравенство $H(X,Y)\leq H(X)+H(Y)$ подразумевает, что

$|G|\cdot |G_{1}\cap G_{2}|\geq |G_{1}|\cdot |G_{2}|.$

Оказывается, по сути верно обратное. Точнее, вектор называется группово-характеризуемым, если его можно получить из набора подгрупп, как указано выше.Множество группохарактеризуемых векторов обозначается $\Upsilon ^{n}$.Как было сказано выше, $\Upsilon ^{n}\subseteq \Gamma _{n}^{*}$.С другой стороны, $\Gamma _{n}^{*}$ (и таким образом ${\overline {\Gamma _{n}^{*}}}$) содержится в топологическом замыкании выпуклого замыкания $\Upsilon ^{n}$. Другими словами, линейное неравенство справедливо для всех энтропийных векторов тогда и только тогда, когда оно справедливо для всех векторов $h$ формы $h_{I}=\log {\frac {|G|}{|G_{I}|}}$, где $I$ перебирает подмножества некоторого набора подгрупп $G_{1},G_{2},\dots ,G_{n}$ в группе $G$.

Группово-характеризуемые векторы, происходящие из абелевой группы, удовлетворяют неравенству Инглтона.

Колмогоровская сложность

Колмогоровская сложность удовлетворяет по существу тем же неравенствам, что и энтропия.А именно, обозначим колмогоровскую сложность конечной строки $x$ как $K(x)$ (то есть длина самой короткой программы, которая выводит $x$).Совместная сложность двух струн $x,y$, определяемый как сложность кодирования пары $\langle x,y\rangle$, можно обозначить $K(x,y)$.Аналогично условную сложность можно обозначить $K(x|y)$ (длина самой короткой программы, которая выводит $x$ данный $y$). Андрей Колмогоров заметил, что эти понятия ведут себя аналогично энтропии Шеннона, например:

$K(a)+K(b)\geq K(a,b)-O(\log |a|+\log |b|)$

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

См. также

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

Ссылки

• Томас М. Ковер, Джой А. Томас. Элементы теории информации Нью-Йорк: Wiley, 1991. ISBN   0-471-06259-6
• Рэймонд Юнг. Первый курс теории информации , Глава 12, Информационное неравенство , 2002, Печать ISBN   0-306-46791-7