エントロピーベクトル

エントロピー ベクトルまたはエントロピー関数は、情報理論で生じる概念です。これは、1 つのランダム変数の集合のサブセットが取り得るシャノンの情報エントロピーの値を表します。どのベクトルがエントロピーであるかを理解することは、さまざまなサブセットのエントロピー間のすべての可能な不等式を表す方法です。たとえば、任意の 2 つのランダム変数 について、それらの結合エントロピー (ペア を表すランダム変数のエントロピー) は、最大で のエントロピーと のエントロピーの合計になります。 ${\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}$

ランダム変数のシャノンの情報エントロピーは と表されます。ランダム変数の組 の場合、サブセットの結合エントロピーは、またはより簡潔には と表されます。ここでです。ここで は組 を表すランダム変数として理解できます。空のサブセット の場合、 はエントロピー 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}}$

のサブセットによってインデックス付けされた のベクトルh は、各サブセットに対してとなるランダム変数の組が存在する場合、の順序のエントロピー ベクトルと呼ばれます。 ${\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\}}$

の順序エントロピーベクトル全体の集合は で表されます。Zhang と Yeung ^{[1] は}、この集合は ( に対して) 閉じていないが、この閉包,は凸錐であり、したがってこの集合が満たす (無限個の) 線形不等式によって特徴付けられることを証明しました。したがって、この領域を記述することは、結合エントロピーに関するすべての可能な不等式を特徴付けることに相当します。 ${\displaystyle n}$${\displaystyle \Gamma _{n}^{*}}$${\displaystyle n\geq 3}$${\displaystyle {\bar {\Gamma _{n}^{*}}}}$ ${\displaystyle {\bar {\Gamma _{n}^{*}}}}$

X、Y を集合上の離散一様分布に従う2つの独立した確率変数とする。すると、 ${\displaystyle \{0,1\}}$

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

（それぞれが2要素の集合に均一に分布しているため）

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

(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)}$

ランダム変数の組の場合、そのエントロピーは次の式を満たします。 ${\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\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}}}$

(一方向では、最後の形式がタプル の部分集合とに対するシャノンの不等式を表していることに注意してください。他方向では、、、 を代入します)。 ${\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 年に Te Su Han ^[2]によって初めて提起され、より正確には1986 年にNicholas Pippenger ^[5]によって提起されました。 2 変数の場合、つまり の場合にこれが真であることを示すのは難しくありません。 3 変数の場合、Zhang と Yeung ^{[1] は}であることを証明しました。しかし、これは依然として漸近的には真であり、閉包は に等しいことを意味します。1998 年に、Zhang と Yeung ^{[2] [6] は}、4 つのランダム変数に関する次の不等式 (条件付き相互情報量の観点から) は任意のエントロピー ベクトルに対して真であるが、シャノン型ではないことを証明することにより、 すべての に対して であることを示しました。${\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年に、Matusは、変数に対して、線形不等式の有限集合は（すべてを線形結合として演繹するには）十分ではないことを証明した。言い換えれば、領域は多面体ではない。^[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}\mid X_{1})+I(X_{3};X_{4}\mid 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}$

アーベル群から得られる群特徴付け可能なベクトルは、イングルトンの不等式を満たします。

コルモゴロフ複雑度は、本質的にはエントロピーと同じ不等式を満たします。つまり、有限文字列のコルモゴロフ複雑度を(つまり、 を出力する最短プログラムの長さ)と表します。2 つの文字列の結合複雑度は、ペア のエンコードの複雑度として定義され、 と表すことができます。同様に、条件付き複雑度は( が与えられた場合に を出力する最短プログラムの長さ) と表すことができます。Andrey Kolmogorov は、これらの概念がシャノン エントロピーに似た動作をすることに気づきました。たとえば、 次のようになります。${\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年に、Hammerら^[16]は、エントロピーベクトルに対して不等式が成立するのは、コルモゴロフ複雑性に関する対応する不等式がすべての文字列の組に対して対数項まで成立する場合のみであることを証明した。

• 情報理論における不等式

• トーマス・M・カバー、ジョイ・A・トーマス。情報理論の要素ニューヨーク：ワイリー、1991年。ISBN 0-471-06259-6 
• レイモンド・ユン著『情報理論入門』第12章「情報不等式」2002年、印刷ISBN 0-306-46791-7