情報理論の復習

情報理論

情報理論

第3章 情報源と通信路のモデルの 3.1, 3.2 の復習。

記憶のない情報源

各時点における情報源記号の発生確率が、他の時点とは独立である情報源。

記憶のない定常情報源

任意の時刻における各状態の出力確率が同一の確率分布を持つ情報源。
時刻tだろうが、時刻t+1だろうが、情報源記号の出力確率は変わらない。

エルゴード性

記憶のない定常情報源における十分長い出力系列に対してその情報源の統計的な性質が完全に現れているという性質。この性質が成り立つ情報源では、
集合平均(ensemble average)  \overline{f(X)} = \Sigma_{x} f(x) P_{X}(x)
時間平均(time average) \langle f(X) \rangle = lim_{n \rightarrow \infty} \frac{1}{n} \Sigma^{n}_{i=0} f(x_i)
が一致する。このことから、一般的に計算するのが難しい集合平均を時間平均から求めることができる。
また定常情報源であっても、エルゴード性を持たない情報源はいくらでもある。例:1/2の確率で0,1の系列を出力する二元定常情報源において、長時間ずっと0を出力したとき、その確率はp(0)=1となり、p(0)=1/2とは一致せず、統計的性質を求めることができない。

マルコフ情報源

任意の時刻における出力の確率分布が直前のm個の出力に依存するとき、その情報源をm元マルコフ情報源と呼ぶ。直前の出力列によって各状態の確率分布が異るので、定常情報源ではない。
m重マルコフq元情報源の場合、直前のm個それぞれにおいて出力がq通りあるので、q^m通りの状態があると見なせる。とすると、ある状態においてある記号を出力したとき、直前のm個が変わり、別の状態に移る(状態遷移)と見なせる。状態遷移と言えばオートマトンということで、マルコフ情報源に対して状態や状態遷移確率などを定義することができて、マルコフ情報源を状態図で記述することができる。マルコフ情報源の状態遷移にのみに着目する場合をマルコフ連鎖と呼ぶ。

ここで、情報理論形式言語理論がつながった。

しかし、正規マルコフ情報源では、はじめにどんな状態分布が与えられても、十分時間が経過すれば、状態の遷移は定常的になり、従って出力も定常的になる。さらに、エルゴード的であることも証明することができる(らしい)。つまり、正規マルコフ情報源は十分時間が経過すれば、エルゴード情報源と見なすことができる。*1

マルコフ情報源がエルゴード性をもつ条件はエルゴード性 - 機械学習の「朱鷺の杜Wiki」によると、

  • Irreducible:どの状態から始めても,全ての状態に到達可能
  • aperiodic:定時間後に確率1で戻ってくるような状態がない
  • 状態数は有限

これは、正規マルコフ情報源の定義すなわち「閉じた状態集合に対して、非周期的なマルコフ情報源」であることを考えると、同じことを言っていることがわかる。

*1:途中で力つきたので、またp.32から読む。。