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

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

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

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

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

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

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

Множество всех энтропийных векторов порядка обозначено . Чжан и Енг ^[1] доказал , что он не закрыт (для ), но его закрытие , является выпуклым конусом и , следовательно , характеризуется (бесконечно много) линейных неравенств она удовлетворяет. Таким образом, описание области эквивалентно характеристике всех возможных неравенств совместных энтропий.${\displaystyle n}$${\displaystyle \Gamma _{n}^{*}}$${\displaystyle n\geq 3}$${\displaystyle {\bar {\Gamma _{n}^{*}}}}$ ${\displaystyle {\bar {\Gamma _{n}^{*}}}}$

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

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

${\displaystyle H(X)=H(Y)=1}$

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

${\displaystyle H(X,Y)=H(X)+H(Y)=2}$

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

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

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

Характеристика энтропийных векторов: область Γ _n ^* [ править ]

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

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

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

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

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

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

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

Это эквивалентно неравенству о неотрицательности условной взаимной информации :

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

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

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

Программное обеспечение было разработано для автоматизации задачи доказательства неравенств типа Шеннона. ^{[3] [4]} Учитывая неравенство, такое программное обеспечение способно определить, является ли данное неравенство допустимым неравенством типа Шеннона (т. Е. Содержит ли оно конус ).${\displaystyle \Gamma _{n}}$

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

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

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

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

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

Внутренние границы [ править ]

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

${\displaystyle I(X_{1};X_{2})+I(X_{3};X_{4}|X_{1})+I(X_{3};X_{4}|X_{2})-I(X_{3};X_{4})\geq 0}$^[2]

Энтропия и группы [ править ]

Векторы, характеризуемые группами, и квазиравномерные распределения [ править ]

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

${\displaystyle H(X_{I})=\log {\frac {|G|}{|G_{I}|}}}$. ^[14]

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

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

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

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

Колмогоровская сложность [ править ]

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

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

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

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

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

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

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