エントロピーベクトル

エントロピーベクトルまたはエントロピー関数は、情報理論に現れる概念です。これは、ある確率変数の集合のサブセットが取り得るシャノンの情報エントロピーの値を表します。どのベクトルがエントロピーであるかを理解することは、様々なサブセットのエントロピー間のあらゆる不等式を表す方法です。例えば、任意の2つの確率変数 について、それらの結合エントロピー（ペアを表す確率変数のエントロピー）は、とのエントロピーの和以下になります。 X 1 , X 2 {\displaystyle X_{1},X_{2}} X 1 , X 2 {\displaystyle X_{1},X_{2}} X 1 {\displaystyle X_{1}} X 2 {\displaystyle X_{2}}

H ( X 1 , X 2 ) ≤ H ( X 1 ) + H ( X 2 ) {\displaystyle H(X_{1},X_{2})\leq H(X_{1})+H(X_{2})}

条件付き情報量、相互情報量、全相関といった他の情報理論的尺度は、結合エントロピーで表現することができ、対応する不等式によって関連付けられます。エントロピーベクトルが満たす多くの不等式は、シャノン型不等式と呼ばれるいくつかの基本的な不等式の線型結合として導くことができます。しかし、変数に対して、すべてのエントロピーベクトルを特徴付けるのに十分な線型不等式の有限集合は存在しないことが既に証明されています。 n = 4 {\displaystyle n=4}

意味

シャノンの確率変数の情報エントロピーはと表記される。確率変数の組 に対して、部分集合 の結合エントロピーは、より簡潔には と表記される。ここで は組 を表す確率変数と理解できる。空集合 に対して、はエントロピー0の決定論的変数を表す。 X {\displaystyle X} H ( X ) {\displaystyle H(X)} X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\ldots ,X_{n}} X i 1 , X i 2 , … , X i k {\displaystyle X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}}} H ( X i 1 , X i 2 , … , X i k ) {\displaystyle H(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})} H ( X I ) {\displaystyle H(X_{I})} I = { i 1 , i 2 , … , i k } {\displaystyle I=\{i_{1},i_{2},\dots ,i_{k}\}} X I {\displaystyle X_{I}} ( X i 1 , X i 2 , … , X i k ) {\displaystyle (X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})} I = ∅ {\displaystyle I=\emptyset } X I {\displaystyle X_{I}}

のサブセットでインデックス付けされたのベクトルhは、各サブセットに対して となるランダム変数の組が存在する場合、のエントロピー ベクトルと呼ばれます。 R 2 n {\displaystyle \mathbb {R} ^{2^{n}}} { 1 , 2 , … , n } {\displaystyle \{1,2,\dots ,n\}} n {\displaystyle n} X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\ldots ,X_{n}} h ( I ) = H ( X I ) {\displaystyle h(I)=H(X_{I})} I ⊆ { 1 , 2 , … , n } {\displaystyle I\subseteq \{1,2,\dots ,n\}}

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

例

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

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

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

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

(2 つの変数は独立しているため、ペアはにわたって均一に分布しています。) 対応するエントロピー ベクトルは次のようになります。 ( X 1 , X 2 ) {\displaystyle (X_{1},X_{2})} ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 ) {\displaystyle (0,0),(0,1),(1,0),(1,1)}

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

一方、ベクトルはエントロピーではありません（つまり、）。これは、ランダム変数の任意のペア（独立かどうかに関係なく）が を満たす必要があるためです。 ( 0 , 1 , 1 , 3 ) T {\displaystyle (0,1,1,3)^{\mathsf {T}}} ( 0 , 1 , 1 , 3 ) T ∉ Γ 2 ∗ {\displaystyle (0,1,1,3)^{\mathsf {T}}\not \in \Gamma _{2}^{*}} H ( X , Y ) ≤ H ( X ) + H ( Y ) {\displaystyle H(X,Y)\leq H(X)+H(Y)}

エントロピーベクトルの特徴：Γ領域n*

シャノン型不等式とΓn

ランダム変数の組の場合、そのエントロピーは次の式を満たします。 X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\ldots ,X_{n}}

1 ) H ( X ∅ ) = 0 {\displaystyle 1)\quad H(X_{\emptyset })=0}
2 ) H ( X I ) ≤ H ( X J ) {\displaystyle 2)\quad H(X_{I})\leq H(X_{J})} 、任意の I ⊆ J ⊆ { 1 , … , n } {\displaystyle I\subseteq J\subseteq \{1,\dots ,n\}}

特に、任意の に対して が成り立ちます 。 H ( X I ) ≥ 0 {\displaystyle H(X_{I})\geq 0} I ⊆ { 1 , … , n } {\displaystyle I\subseteq \{1,\dots ,n\}}

シャノン不等式によれば、エントロピーベクトルは劣モジュラである。

3 ) H ( X I ) + H ( X J ) ≥ H ( X I ∪ J ) + H ( X I ∩ J ) {\displaystyle 3)\quad H(X_{I})+H(X_{J})\geq H(X_{I\cup J})+H(X_{I\cap J})} 、任意の I , J ⊆ { 1 , … , n } {\displaystyle I,J\subseteq \{1,\dots ,n\}}

これは、条件付き相互情報量が非負である ことを示す不等式と同等です。

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 ) ≥ 0 {\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}}}

(一方向では、最後の形式がタプル のサブセットとに対するシャノンの不等式を表していることに注意してください。他方向では、、、を置き換えてください)。 X , Z {\displaystyle X,Z} Y , Z {\displaystyle Y,Z} X , Y , Z {\displaystyle X,Y,Z} X = X I {\displaystyle X=X_{I}} Y = X J {\displaystyle Y=X_{J}} Z = X I ∩ J {\displaystyle Z=X_{I\cap J}}

多くの不等式はシャノン不等式の線形結合として導くことができ、それらはシャノン型不等式またはシャノン情報測度の基本情報不等式と呼ばれる。 [2]これらを満たすベクトルの集合は と呼ばれ、 を含む。 Γ n {\displaystyle \Gamma _{n}} Γ n ∗ {\displaystyle \Gamma _{n}^{*}}

シャノン型不等式の証明作業を自動化するソフトウェアが開発されている。[3] [4] 不等式が与えられると、そのようなソフトウェアは、与えられた不等式が有効なシャノン型不等式であるかどうか（つまり、円錐が含まれているかどうか）を判定することができる。 Γ n {\displaystyle \Gamma _{n}}

非シャノン型不等式

シャノン型不等式が唯一のものであるかどうか、つまり、領域 を完全に特徴付けるかどうかという問題は、1981 年に Te Su Han [2]によって初めて提起され、より正確にはNicholas Pippengerによって1986 年に提起されました[5]。 2 変数の場合、つまり の場合にこれが成り立つことを示すのは難しくありません。3 変数の場合、Zhang と Yeung [1]はであることを証明しました。しかし、これは依然として漸近的には真であり、閉包が に等しいことを意味します。1998 年に、Zhang と Yeung [2] [6]は、4 つのランダム変数に関する次の不等式 (条件付き相互情報量の観点から) は任意のエントロピー ベクトルに対して成り立ちますが、シャノン型ではないことを証明することにより、すべてのに対して であることを示しました。 Γ n ∗ {\displaystyle \Gamma _{n}^{*}} Γ 2 ∗ = Γ 2 {\displaystyle \Gamma _{2}^{*}=\Gamma _{2}} Γ 3 ∗ ≠ Γ 3 {\displaystyle \Gamma _{3}^{*}\neq \Gamma _{3}} Γ 3 ∗ ¯ = Γ 3 {\displaystyle {\overline {\Gamma _{3}^{*}}}=\Gamma _{3}} Γ n ∗ ¯ ≠ Γ n {\displaystyle {\overline {\Gamma _{n}^{*}}}\neq \Gamma _{n}} n ≥ 4 {\displaystyle n\geq 4}

2 I ( X 3 ; X 4 ) ≤ I ( X 1 ; X 2 ) + I ( X 1 ; X 3 , X 4 ) + 3 I ( X 3 ; X 4 | X 1 ) + I ( X 3 ; X 4 | X 2 ) {\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]これらを他の方法で特徴付けることができるかどうか（ベクトルがエントロピー的であるかどうかを効果的に判断できるかどうか）は未解決の問題 である。 Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}} Γ n {\displaystyle \Gamma _{n}} n ≥ 4 {\displaystyle n\geq 4} Γ 4 ∗ ¯ {\displaystyle {\overline {\Gamma _{4}^{*}}}}

量子情報理論におけるフォン・ノイマン・エントロピーについても同様の疑問が検討されてきた。[12]

内側の境界

の内界もいくつか知られている。例えば、 は、以下の不等式（および変数を並べ替えることで得られる不等式）を満たすベクトルをすべて含む。これはエントロピーに関するイングルトンの不等式として知られる。[13] Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}} Γ 4 ∗ ¯ {\displaystyle {\overline {\Gamma _{4}^{*}}}} Γ 4 {\displaystyle \Gamma _{4}}

I ( X 1 ; X 2 ) + I ( X 3 ; X 4 ∣ X 1 ) + I ( X 3 ; X 4 ∣ X 2 ) − I ( X 3 ; X 4 ) ≥ 0 {\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]

エントロピーとグループ

群特徴付け可能なベクトルと準一様分布

の群 と部分群を考える。に対してと記す。これも の部分群である。確率変数の確率分布を次のように 構成することができる。 G {\displaystyle G} G 1 , G 2 , … , G n {\displaystyle G_{1},G_{2},\dots ,G_{n}} G {\displaystyle G} G I {\displaystyle G_{I}} ⋂ i ∈ I G i {\displaystyle \bigcap _{i\in I}G_{i}} I ⊆ { 1 , … , n } {\displaystyle I\subseteq \{1,\dots ,n\}} G {\displaystyle G} n {\displaystyle n} X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}}

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

（この構成は本質的にの元を一様ランダムに取り、を対応する剰余類とする。）したがって、情報理論的不等式は群論的不等式を必然的に伴う。例えば、基本不等式は以下を意味する 。 a {\displaystyle a} G {\displaystyle G} X i {\displaystyle X_{i}} a G i {\displaystyle aG_{i}} H ( X , Y ) ≤ H ( X ) + H ( Y ) {\displaystyle H(X,Y)\leq H(X)+H(Y)}

| G | ⋅ | G 1 ∩ G 2 | ≥ | G 1 | ⋅ | G 2 | . {\displaystyle |G|\cdot |G_{1}\cap G_{2}|\geq |G_{1}|\cdot |G_{2}|.}

逆は本質的に真であることがわかります。より正確には、ベクトルが上記のように部分群の組から得られる場合、そのベクトルは群特徴付け可能であるといいます。群特徴付け可能なベクトルの集合は と表記されます。上で述べたように、 です。一方、（したがって）は の凸閉包の位相閉包に含まれます。[15] 言い換えれば、線型不等式がすべてのエントロピーベクトルに対して成立する場合、かつそれが の形式のベクトルすべてに対して成立する場合に限ります。ここで は、群 の一部の部分群の組の部分集合にわたります。 Υ n {\displaystyle \Upsilon ^{n}} Υ n ⊆ Γ n ∗ {\displaystyle \Upsilon ^{n}\subseteq \Gamma _{n}^{*}} Γ n ∗ {\displaystyle \Gamma _{n}^{*}} Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}} Υ n {\displaystyle \Upsilon ^{n}} h {\displaystyle h} h I = log ⁡ | G | | G I | {\displaystyle h_{I}=\log {\frac {|G|}{|G_{I}|}}} I {\displaystyle I} G 1 , G 2 , … , G n {\displaystyle G_{1},G_{2},\dots ,G_{n}} G {\displaystyle G}

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

コルモゴロフ複雑性

コルモゴロフ複雑度は、本質的にエントロピーと同じ不等式を満たします。つまり、有限文字列のコルモゴロフ複雑度を（つまり、 を出力する最短プログラムの長さ）と表記します。2つの文字列 の結合複雑度は、ペア の符号化の複雑度として定義され、 と表記できます。同様に、条件付き複雑度は（与えられたを出力する最短プログラムの長さ） と表記できます。アンドレイ・コルモゴロフは、これらの概念がシャノンエントロピーに類似していることに注目しました。例えば、 x {\displaystyle x} K ( x ) {\displaystyle K(x)} x {\displaystyle x} x , y {\displaystyle x,y} ⟨ x , y ⟩ {\displaystyle \langle x,y\rangle } K ( x , y ) {\displaystyle K(x,y)} K ( x | y ) {\displaystyle K(x|y)} x {\displaystyle x} y {\displaystyle y}

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

2000年に、Hammerら[16]は、エントロピーベクトルに対して不等式が成立するのは、コルモゴロフ複雑性に関する対応する不等式がすべての文字列の組に対して対数項まで成立する場合のみであることを証明した。

参照

参考文献

  1. ^ ab Zhang, Z.; Yeung, RW (1997). 「非シャノン型条件付き情報量不等式」. IEEE Trans. Inf. Theory . 43 (6): 1982– 1986. doi :10.1109/18.641561.
  2. ^ abcd Zhang, Z.; Yeung, RW (1998). 「情報不等式によるエントロピー関数の特性評価について」IEEE Trans. Inf. Theory . 44 (4): 1440– 1452. doi :10.1109/18.681320.
  3. ^ Yeung, RW; Yan, YO (1996). 「ITIP - 情報理論的不等式証明器」.
  4. ^ プリッコナトゥ、R.; E.ペロン、E. S.ディガヴィ、S. (2007)。 「Xitip - 情報理論的不平等証明者」。
  5. ^ Kaced, Tarik (2013).非シャノン型不等式に対する2つの証明手法の同値性. 2013 IEEE 国際情報理論シンポジウム. arXiv : 1302.2994 .
  6. ^ Yeung.情報理論入門、定理14.7
  7. ^ Dougherty, R.; Freiling, C .; Zeger, K. (2006). 6つの新しい非シャノン情報不等式. 2006 IEEE国際情報理論シンポジウム.
  8. ^ Matus, F. (1999). 「4つの確率変数間の条件付き独立性 III: 最終結論」.組合せ論、確率、計算. 8 (3): 269– 276. doi :10.1017/s0963548399003740. S2CID  121634597.
  9. ^ Makarychev, K.; et al. (2002). 「エントロピーに対する非シャノン型不等式の新しいクラス」. Communications in Information and Systems . 2 (2): 147– 166. doi : 10.4310/cis.2002.v2.n2.a3 .
  10. ^ Zhang, Z. (2003). 「新たな非シャノン型情報不等式について」. Communications in Information and Systems . 3 (1): 47– 60. doi : 10.4310/cis.2003.v3.n1.a4 .
  11. ^ Matus, F. (2007).無限の情報不等式. 2007 IEEE 国際情報理論シンポジウム.
  12. ^ Linden; Winter (2005). 「フォン・ノイマン・エントロピーに関する新たな不等式」. Commun. Math. Phys . 259 (1): 129– 138. arXiv : quant-ph/0406162 . Bibcode :2005CMaPh.259..129L. doi :10.1007/s00220-005-1361-2. S2CID  13279358.
  13. ^ Yeung.情報理論入門、386ページ
  14. ^ Yeung.情報理論入門、定理16.16
  15. ^ Yeung.情報理論入門、定理16.22
  16. ^ Hammer; Romashchenko; Shen; Vereshchagin (2000). 「シャノンエントロピーとコルモゴロフ複雑度の不等式」. Journal of Computer and System Sciences . 60 (2): 442– 464. doi : 10.1006/jcss.1999.1677 .
  • トーマス・M・カバー、ジョイ・A・トーマス著『情報理論の要素』ニューヨーク：ワイリー、1991年。ISBN 0-471-06259-6
  • レイモンド・ユン著『情報理論入門』第12章「情報不等式」、2002年、印刷ISBN 0-306-46791-7
Retrieved from "https://en.wikipedia.org/w/index.php?title=Entropic_vector&oldid=1298640694"