情報理論における不等式
Concept in information theory

不等式は情報理論の研究において非常に重要です。これらの不等式が現れる状況は多岐にわたります。

エントロピー不等式

同じ確率空間上にある有限個（あるいはせいぜい可算個）の確率変数の組を考えてみましょう。2 n個の部分集合があり、それらに対して（結合）エントロピーを計算できます。例えば、n  = 2 の場合、エントロピーと を考えてみましょう。これらは以下の不等式を満たします（これらを合わせると、2つの確率変数の周辺エントロピーと結合エントロピーの範囲が定義されます）。 X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} n {\displaystyle n} H ( X 1 ) , {\displaystyle H(X_{1}),} H ( X 2 ) , {\displaystyle H(X_{2}),} H ( X 1 , X 2 ) {\displaystyle H(X_{1},X_{2})}

  • H ( X 1 ) ≥ 0 {\displaystyle H(X_{1})\geq 0}
  • H ( X 2 ) ≥ 0 {\displaystyle H(X_{2})\geq 0}
  • H ( X 1 ) ≤ H ( X 1 , X 2 ) {\displaystyle H(X_{1})\leq H(X_{1},X_{2})}
  • H ( X 2 ) ≤ H ( X 1 , X 2 ) {\displaystyle H(X_{2})\leq H(X_{1},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}).}

実際、これらはすべて、条件付き相互情報量を含む単一の不等式の特別なケースとして表現できます。つまり、

I ( A ; B | C ) ≥ 0 , {\displaystyle I(A;B|C)\geq 0,}

ここで、、、はそれぞれ、確率変数の集合の任意の（空である可能性もある）部分集合の結合分布を表します。この線形結合として導出できる不等式は、シャノン型不等式として知られています。 A {\displaystyle A} B {\displaystyle B} C {\displaystyle C}

より大きい場合、エントロピーの取り得る値にはさらなる制約があります。正確に言うと、のサブセットでインデックス付けされた のベクトルは、各サブセット について、それらの結合エントロピーとなるようなn個のランダム変数の結合離散分布がある場合に、エントロピーがあると言われます。エントロピーベクトルの集合は、Yeung の表記に従って と表されます。[1] これは に対して閉じておらず凸でもありませんが、その位相閉包は凸であることが知られており、したがって、すべてのエントロピーベクトルが満たす（無限個の）線型不等式、つまりエントロピー不等式によって特徴付けることができます。 n {\displaystyle n} h {\displaystyle h} R 2 n {\displaystyle \mathbb {R} ^{2^{n}}} { 1 , … , n } {\displaystyle \{1,\dots ,n\}} X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}} h I = H ( X i : i ∈ I ) {\displaystyle h_{I}=H(X_{i}\colon i\in I)} I {\displaystyle I} Γ n ∗ {\displaystyle \Gamma _{n}^{*}} n ≥ 3 {\displaystyle n\geq 3} Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}}

シャノン型不等式（ただし他のエントロピー不等式は必ずしも満たさない）を満たすすべてのベクトルの集合には が含まれる。この包含は に対して厳密であり、それ以外の不等式は非シャノン型不等式として知られている。ZhangとYeungは最初の非シャノン型不等式を報告した[2]。これはしばしばZhang-Yeung不等式と呼ばれる。Matus [3]は、有限の不等式集合では（線形結合によって）すべてのエントロピー不等式を特徴づけることはできないことを証明した。言い換えれば、領域は多面体ではない。 Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}} n ≥ 4 {\displaystyle n\geq 4} Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}}

カルバック・ライブラー距離の下限

情報理論における重要な不等式の多くは、実はカルバック・ライブラー距離の下限値です。シャノン型不等式でさえ、このカテゴリの一部と見なすことができます。なぜなら、相互作用情報は、結合分布の周辺分布の積に関するカルバック・ライブラー距離として表すことができるため、これらの不等式はギブスの不等式の特殊なケースと見なすことができるからです。

一方、カルバック・ライブラー情報量の有用な上限を導出するのは、はるかに困難であるように思われます。これは、カルバック・ライブラー情報量D KL ( P || Q ) が、基準分布Qにおいて非常に稀な事象に非常に敏感に依存するためです。 分布Pにおいて有限の非ゼロ確率の事象が基準分布Qにおいて極めて稀になると、 D KL ( P || Q ) は無制限に増加します。実際、Pにおいて非ゼロ確率の事象がQにおいてゼロ確率を持つ場合、 D KL ( P || Q ) は定義されません。（したがって、 P はQに関して絶対連続である必要があります。）

ギブスの不等式

この基本的な不等式は、カルバック・ライブラー距離が非負であることを示しています。

カルバックの不等式

カルバック・ライブラー情報に関するもう一つの不等式はカルバックの不等式として知られている。[4] PとQが実数直線上の確率分布 で、 P がQに関して絶対連続であり、その第一モーメントが存在する場合、

D K L ( P ∥ Q ) ≥ Ψ Q ∗ ( μ 1 ′ ( P ) ) , {\displaystyle D_{KL}(P\parallel Q)\geq \Psi _{Q}^{*}(\mu '_{1}(P)),}

ここで、 はQの大偏差速度関数、つまりキュムラント生成関数の凸共役であり、はPの第一モーメントです。 Ψ Q ∗ {\displaystyle \Psi _{Q}^{*}} μ 1 ′ ( P ) {\displaystyle \mu '_{1}(P)}

Cramér -Rao 境界はこの結果の帰結です。

ピンスカーの不等式

ピンスカーの不等式は、カルバック・ライブラー情報と全変動距離を関連付ける。これは、P、Q が2つの確率分布である場合、

1 2 D K L ( e ) ( P ∥ Q ) ≥ sup { | P ( A ) − Q ( A ) | : A  is an event to which probabilities are assigned. } . {\displaystyle {\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 K L ( e ) ( P ∥ Q ) {\displaystyle D_{KL}^{(e)}(P\parallel Q)}

ナチュラルズと ​

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

総変動距離です。

その他の不平等

ハーシュマン不確実性

1957年[5]に、ハーシュマンは、（十分に振る舞いの良い）関数とそのフーリエ変換に対して、と微分エントロピーの和が非負であることを示した。 f : R → C {\displaystyle f:\mathbb {R} \rightarrow \mathbb {C} } ∫ − ∞ ∞ | f ( x ) | 2 d x = 1 , {\displaystyle \int _{-\infty }^{\infty }|f(x)|^{2}\,dx=1,} g ( y ) = ∫ − ∞ ∞ f ( x ) e − 2 π i x y d x , {\displaystyle g(y)=\int _{-\infty }^{\infty }f(x)e^{-2\pi ixy}\,dx,} | f | 2 {\displaystyle |f|^{2}} | g | 2 {\displaystyle |g|^{2}}

− ∫ − ∞ ∞ | f ( x ) | 2 log ⁡ | f ( x ) | 2 d x − ∫ − ∞ ∞ | g ( y ) | 2 log ⁡ | g ( y ) | 2 d y ≥ 0. {\displaystyle -\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 ) , {\displaystyle \log(e/2),}

タオの不等式

離散確率変数、、が区間[−1, 1]のみの値をとり、 によって決定される（となる）とすると、[7] [8] X {\displaystyle X} Y {\displaystyle Y} Y ′ {\displaystyle Y'} X {\displaystyle X} Y ′ {\displaystyle Y'} Y {\displaystyle Y} H ( Y ′ | Y ) = 0 {\displaystyle H(Y'|Y)=0}

E ⁡ ( | E ⁡ ( X | Y ′ ) − E ⁡ ( X ∣ Y ) | ) ≤ I ( X ; Y ∣ Y ′ ) 2 log ⁡ 2 , {\displaystyle \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は、条件付き相互情報量をnatsではなくbitsで測定しているために生じる。）

情報理論的不等式の機械ベース証明チェッカー

現在、いくつかの機械ベースの証明チェッカーアルゴリズムが利用可能です。証明チェッカーアルゴリズムは通常、不等式が真か偽かを検証します。より高度な証明チェッカーアルゴリズムは、証明または反例を生成することができます。[9]量子情報理論における不等式は、縮約写像証明法によって検証できます。[10]

参照

参考文献

  1. ^ Yeung, RW (1997). 「線形情報不等式の枠組み」. IEEE Transactions on Information Theory . 43 (6): 1924– 1934. doi :10.1109/18.641556.）
  2. ^ Zhang, Z.; Yeung, RW (1998). 「情報不等式によるエントロピー関数の特徴づけについて」. IEEE Transactions on Information Theory . 44 (4): 1440– 1452. doi :10.1109/18.681320.
  3. ^ Matus, F. (2007).無限の情報不等式. 2007 IEEE 国際情報理論シンポジウム.
  4. ^ フックス、エメ;レッタ、ジョルジオ (1970)。 「カルバックのガリット。推定理論の応用」。 Séminaire de Probabilités IV Université de Strasbourg。数学の講義ノート。 Vol. 124. ストラスブール。ページ 108–131。土井:10.1007/bfb0059338。ISBN 978-3-540-04913-5. MR  0267669。{{cite book}}: CS1 maint: location missing publisher (link)
  5. ^ ハーシュマン, II (1957). 「エントロピーに関するノート」.アメリカ数学ジャーナル. 79 (1): 152– 156. doi :10.2307/2372390. JSTOR  2372390.
  6. ^ Beckner, W. (1975). 「フーリエ解析における不等式」Annals of Mathematics . 102 (6): 159– 182. doi :10.2307/1970980. JSTOR  1970980.
  7. ^ Tao, T. (2006). 「Szemerédiの正則性補題の再考」.論文集. 離散数学. 1 : 8–28 . arXiv : math/0504472 . Bibcode :2005math......4472T.
  8. ^ アルスウェーデ、ルドルフ(2007). 「条件付き期待値と条件付き相互情報量に関するタオの不等式の最終形」.通信数学の進歩. 1 (2): 239– 242. doi : 10.3934/amc.2007.1.239 .
  9. ^ Ho, SW; Ling, L.; Tan, CW; Yeung, RW (2020). 「情報不等式の証明と反証：理論とスケーラブルなアルゴリズム」. IEEE Transactions on Information Theory . 66 (9): 5525– 5536. doi :10.1109/TIT.2020.2982642. S2CID  216530139.
  10. ^ Bao, N; Naskar, J;, 「ホログラフィックエンタングルメントエントロピー不等式の収縮マップの特性」、J. High Energ. Phys. 06(2024), 3, DOI: https://doi.org/10.1007/JHEP06(2024)039、2024年6月7日。
  • トーマス・M・カバー、ジョイ・A・トーマス著『情報理論の要素』第16章「情報理論における不等式」John Wiley & Sons, Inc. 1991年ISBN 0-471-06259-6オンラインISBN 0-471-20061-1
  • アミール・デンボ、トーマス・M・カバー、ジョイ・A・トーマス「情報理論的不等式」 IEEE Transactions on Information Theory、第37巻、第6号、1991年11月。pdf
  • ITIP: http://user-www.ie.cuhk.edu.hk/~ITIP/ 2008年8月7日アーカイブ、Wayback Machine
  • XITIP: http://xitip.epfl.ch
  • NR Pai、Suhas Diggavi、T. Gläßle、E. Perron、R.Pulikkoonattu、RW Yeung、Y. Yan、oXitip: オンライン情報理論的不平等証明者 http://www.oxitip.com
  • Siu Wai Ho、Lin Ling、Chee Wei Tan、Raymond W. Yeung、AITIP (情報理論的不平等証明者): https://aitip.org
  • Nivedita Rethnakar、Suhas Diggavi、Raymond. W. Yeung、「InformationInequalities.jl：情報理論的不等式の探究」、Julia Package、2021年 [1]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Inequalities_in_information_theory&oldid=1309433075"