めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

トップ > 情報・数理 > 情報理論、エントロピーからガウス型通信路まで：2

情報理論、エントロピーからガウス型通信路まで：2

情報・数理

情報理論のメモ

あくまでメモなので、"定義域を○×として、..."といった記述はないです。

参考文献

  • ELEMENTS OF INFORMATION THEORY : Thomas M.Cover, Joy A.Thomas
  • 情報理論 基礎と広がり: Thomas M.Cover, Joy A.Thomas, 山本 博資, 古賀 弘樹, 有村 光晴　他


前回


情報理論、エントロピーからガウス型通信路まで：1 - 雑なメモ

漸近等分割性

AEP(漸近等分割性)の定義

{ \displaystyle X_i (i \in R, i.i.d.) は 分布p(x)に従うとする。 また任意の実数を \epsilon とする。このとき \\ Pr\{ | H(X) - (-\frac{\log \frac{1}{p(X_1,X_2, \dots ,X_n) | }}{n}) \leq \epsilon \} → 0 }

が成り立つ、そしてこの性質をAEP(漸近等分割性)と言う。
※参考文献p43より参照。

証明：i.i.d.つまり独立で同一の分布に従う確率変数の列の同時分布は { \displaystyle p(X_1,\dots,X_n) = \prod_{i=0}^n p(X_i) }で記述されるので、

{ \displaystyle Pr\{ | H(X) - (-\frac{\log \frac{1}{p(X_1,X_2, \dots ,X_n)}}{n}) | \leq \epsilon \} \\ = Pr\{ | H(X) + \frac{\log \frac{1}{\prod_{i=0}^n p(X_i)}}{n} | \leq \epsilon \} \\ = Pr\{ | H(X) - \frac{\sum_{i = 1}^n \log p(X_i)}{n} | \leq \epsilon \} \\ }

と式を書き換えることができる。さらに

{ \displaystyle Pr\{ | -\frac{\sum_{i = 1}^n \log p(X_i)}{n} - E(-\log p(X)) | \leq \epsilon \} -> 0 }


であることを考慮すると、

{ \displaystyle Pr\{ | H(X) - (-\frac{\log \frac{1}{p(X_1,X_2, \dots ,X_n)}}{n}) | \leq \epsilon \} \\ = Pr\{ | H(X) - \frac{\sum_{i = 1}^n \log p(X_i)}{n} | \leq \epsilon \} \\ → Pr\{ | H(X) - E(-\log p(X)) | \leq \epsilon \} \\ = Pr\{ | H(X) - H(X) | \leq \epsilon \} \\ = 0 }
■

典型的集合の定義

ここで、すべての長さnの確率変数列の内でとくに”よく出る”nの長さをもつ文字列の集合Tは以下の性質をもつだろうと考える...

  • もしも{ \displaystyle x_1 x_2 \dots x_n \in T }ならば { \displaystyle -\frac{\log p(x_1 x_2 \dots x_n)}{n} }はほぼみんな同じくらい。
  • 長さnの文字列のうち{ \displaystyle x_1 x_2 \dots x_n \in T }となる率は1に近い
  • Tの要素数は上限あり（ないと全要素いれればいいことになってしまう）

そしてここで典型的集合を定義する。英語版p59参照。
典型的集合(typical set){ \displaystyle {A_{\epsilon}}^{(n)} }
{ \displaystyle (x_1 x_2 \dots x_n) \in {A_{\epsilon}}^{(n)} }であるなら
{ \displaystyle 2^{-n(H(X) + \epsilon)} \leq p(x_1 x_2 \dots x_n) \leq 2^{-n(H(X) - \epsilon)} }
となるような集合{ \displaystyle {A_{\epsilon}}^{(n)} }を典型的集合と定義。

こうすることで、

  • もしも{ \displaystyle x_1 x_2 \dots x_n \in T }ならば { \displaystyle -\frac{\log p(x_1 x_2 \dots x_n)}{n} }はほぼみんな同じくらい。

　これは定義が{ \displaystyle 2^{-(H(X) + \epsilon)} \leq p(x_1 x_2 \dots x_n) \leq 2^{-(H(X) - \epsilon)} }としているのだからみんな{ \displaystyle 2^{-H(X)} }に近い確率を持つ。

  • 長さnの文字列のうち{ \displaystyle x_1 x_2 \dots x_n \in T }となる率は1に近い

{ \displaystyle 2^{-n(H(X) + \epsilon)} \leq p(x_1 x_2 \dots x_n) \leq 2^{-n(H(X) - \epsilon)} \\ \Leftrightarrow \log 2^{-n(H(X) + \epsilon)} \leq \log p(x_1 x_2 \dots x_n) \leq \log 2^{-n(H(X) - \epsilon)} \\ \Leftrightarrow -(H(X) + \epsilon) \leq \frac{\log p(x_1 x_2 \dots x_n)}{n} \leq -(H(X) - \epsilon) }
この式と漸近等分割性の式を比べると成り立つことが分かる。

  • Tの要素数は上限あり（ないと全要素いれればいいことになってしまう）

{ \displaystyle \sum_{(x_1 x_2 \dots x_n) \in {A_{\epsilon}}^{(n)}} p(x_1 x_2 \dots x_n) \\ \leq \sum_{(x_1 x_2 \dots x_n) \in {A_{\epsilon}}^{(n)}} 2^{-n(H(X) + \epsilon)} \\ = 2^{-n(H(X) + \epsilon)}| {A_{\epsilon}}^{(n)} | }

さらにすべての確率を足したら1になるはずなので

{ \displaystyle 1 \geq \sum_{(x_1 x_2 \dots x_n) \in {A_{\epsilon}}^{(n)}} p(x_1 x_2 \dots x_n) }

が（明らかに、あまり使うべきではない言葉だけど...!）わかる。よって

{ \displaystyle 1 \geq 2^{-n(H(X) + \epsilon)}| {A_{\epsilon}}^{(n)} |　\\ \Leftrightarrow 2^{n(H(X) + \epsilon)} \geq | {A_{\epsilon}}^{(n)} | }

である。そして

も同様の式変形で導かれる。

確率変数列を符号化したときの平均符号長

　以下、{(x_1 x_2 \dots x_n) を x^n}と記述する。これらを0,1のみを使って符号化するときにどれくらいの長さのコードが必要かを調べるために、情報源から出現しうる{ x^n}のパターン{ K^n (情報源符号の数をKとした)}を典型的集合である{ A_{\epsilon}^{(n)} }とそうでない{ {A_{\epsilon}^{(n)}}^c }に分けて符号化することを考える。
　まず、典型的集合の要素数には上界と下界があって、もっとも符号が長くなり売るのは要素数が最大の時で{ 2^{n(H(X) + \epsilon)} }の数の要素がある場合が最大である。今は二ビットコードで符号化することにしているから、典型的集合を要素の重複無く符号化するには最低で{ n(H(X) + \epsilon) + 1}の長さの符号があればいい。1ビット分は{ n(H(X) + \epsilon)}が整数で無い場合も成り立つことを保証するために必要。

　さらに、典型的集合に含まれる列かどうかを示すフラグを立てるビットをもう一つつけて{ n(H(X) + \epsilon) + 2}ビットが典型的集合に含まれる列の符号化に必要なビット数とする。このとき、長さnのすべてのパターンを符号化するときの平均符号長は...

{ E(length(X^n)) \\ = \sum_{x^n \in \chi^n} p(x^n)length(x^n) \\ = \sum_{x_n \in A_{\epsilon}^{(n)}}p(x^n)length(x^n) + \sum_{x_n \in {A_{\epsilon}^{(n)}}^c}p(x^n)length(x^n) \\ \leq \sum_{x_n \in A_{\epsilon}^{(n)}} Pr[ x^n \in A_{\epsilon}^{(n)}] (n(H(X) + \epsilon) + 2) \\ \ \ \ \ \ \ + \sum_{x_n \in {A_{\epsilon}^{(n)}}^c} (1 - Pr[ x^n \in A_{\epsilon}^{(n)}] )(nlog_2 K + 2) \\ =Pr[ X^n \in A_{\epsilon}^{(n)}] (n(H(X) + \epsilon) + 2) + (1 - Pr[ X^n \in A_{\epsilon}^{(n)}] )(nlog_2 K + 2)\\ \leq n\{(H(X) \epsilon (log_2 K + 1))\} + 2 }■

と求められる。上の式の両辺をnで割って極限をとれば、一情報源符号あたりの平均符号帳がその情報源のエントロピーに近づくことが確認できる。

エントロピーレート

エントロピーレートの定義

数列のように添字をつけて順番付けした確率変数列{ \{X_i\} }がある時に

{ H(\chi) = \lim_{x \to \infty} \frac{H(x_1,x_2,\dots,x_n)}{n} }

をその確率変数列（以下、これを確率過程Xと言う）のエントロピーレートと定義する。

ステーショナリー(定常性)

確率過程Xがステージョナリーとは
{ Pr\{(X_1,X_2,\dots,X_n) = (x_i,x_2,\dots,x_n)\} = Pr\{(X_{k+1},X_{k+2},\dots,X_{k+n}) = (x_i,x_2,\dots,x_n)\} }
が任意の整数kについて成り立つ状態。つまり、出力される順番が同じならば添字に関係なく次に出力される記号の確率が決定できる確率過程。

マルコフ過程

確率過程Xがマルコフ過程であるとは、
{ Pr\{X_{n+1} = x_{n+1}|(X_1,X_2,\dots,X_n) \\ = (x_i,x_2,\dots,x_n)\} = Pr\{X_{n+1} = x_{n+1}|X_n = x_n\} }
つまり、次の出力は直前の出力のみに依存する確率過程。

time invariantなマルコフ過程

{ Pr\{X_{n+1} = x_{n+1}|X_n = x_n\} = Pr\{X_{k+1} = x_{n+1}|X_k = x_n\} }
つまり、直前の記号が次の出力の分布を決めるマルコフ過程。

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス（Googleアドセンス、A8.net）を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー（Cookie）を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ：このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。