情報理論 - 定常情報源

概要

定常情報源とは、時間的な特性が一定している情報の発生源を指す。
例えば、シンボルの出現確率が時間によって変化せず、一定の統計的性質を保持している情報源のことを意味する。

すなわち、任意の正整数nとiおよび情報源アルファベットの任意の元 $x_{0},x_{1},\cdots ,x_{n-1}$ に対して、
$P_{X0\,X1\,\cdots \,Xn-1}(x_{0},x_{1},\cdots ,x_{n-1})=P_{Xi\,Xi+1\,\cdots \,Xi+n-1}(x_{0},x_{1},\cdots ,x_{n-1})$ が成立するとき、この情報源を定常情報源という。

定常情報源の特徴として、以下に示すような性質が挙げられる。

• 時間不変性

  シンボルの出現確率が時間に依存せず、常に一定の確率分布を保持する。

  これは、例えば"A"という文字が出現する確率がいつ観測しても同じであることを意味する。

• エルゴード性

  十分長い時間で観測する時、時間平均が集合平均に一致する性質を持つ。

  これにより、長期的な統計的性質を予測することが可能になる。

定常情報源の出力は、各時点において同一の確率分布に従う。
この確率分布を定常分布という。

定常情報源は、通信システムの設計や情報圧縮において重要となる。
例えば、テキストデータの圧縮を考える場合、英語のテキストでは各文字の出現頻度がおおよそ一定であるという性質を利用して、効率的な圧縮方式を設計することができる。

また、定常情報源のエントロピーは、その情報源から生成される情報の平均的な情報量を表す。
これは、シャノンの情報理論において、通信に必要な最小のビット数を決定する重要な指標となっている。

応用例として、音声通信システムがある。
人間の話し声は、短時間で見ると定常的な特性を持つと仮定できるため、この性質を利用して効率的な音声符号化が可能となる。

また、データ圧縮や誤り訂正符号の設計において、定常情報源の概念の理解が必要となる。

• データ圧縮アルゴリズムの設計

  ハフマン符号やアリスマティック符号等の設計

• 通信システムの性能評価

  チャネル容量や符号化効率の分析

• パターン認識

  音声認識や文字認識等における確率モデルの構築

定常情報源の結合確率分布

記憶のない定常情報源における長さnの系列の結合確率分布は、次式で表すことができる。

$P_{X0}\cdots P_{Xn-1}(x_{0},\cdots ,x_{n-1}=\prod _{i=0}^{n-1}P_{X}(x_{i})$

例題:
サイコロの出目において、
目が6の場合はa、それ以外の場合はbを出力する定常情報源Sが系列aabaを出力する確率を求めよ。

解答:
$A=\{a,b\}$ の2元情報源で、かつ a, bの発生確率が ${\dfrac {1}{6}},\,\,{\dfrac {5}{6}}$ となる定常情報源になる。
したがって、$P(a,a,b,a)={\dfrac {1}{6}}\times {\dfrac {1}{6}}\times {\dfrac {5}{6}}\times {\dfrac {1}{6}}={\dfrac {5}{1296}}$

定常情報源のエントロピー

定常情報源エントロピーは、情報源から出力される1シンボルあたりの平均情報量を表す。
これは、情報源の不確実性を定量化する指標となる。

例題: 二元定常情報源の場合
シンボル {0, 1} を出力する情報源があり、$P(0)=0.7,\,P(1)=0.3$ とする。
${\begin{Bmatrix}0&1\\0.7&0.3\end{Bmatrix}}$

この時、エントロピーH(X)は次式のように計算できる。
${\begin{aligned}H(X)&=-\sum P(x)\log _{2}P(x)\\&=-(0.7\log _{2}0.7+0.3\log _{2}0.3)\\&\approx 0.8813\,\,{\mbox{[bits/symbol]}}\end{aligned}}$

マルコフ情報源

マルコフ情報源は、現在の状態が直前の状態にのみ依存する情報源である。
これは、実用的なシステムのモデル化に使用されている。

例題: マルコフ情報源の場合
次の遷移確率を持つ2状態マルコフ情報源を考える。

$P(0|0)=0.8,\,\,P(1|0)=0.2$
$P(0|1)=0.3,\,\,P(1|1)=0.7$

この場合、定常分布 π(x) は、以下に示す連立方程式を解くことで求めることができる。

$\pi (0)=0.8\pi (0)+0.3\pi (1)$
$\pi (0)+\pi (1)=1$

これを解くと、
$\pi (0)=0.6$
$\pi (1)=0.4$