情報理論 - 定常情報源

概要

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

すなわち、任意の正整数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 \,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}}$

エルゴード情報源

エルゴード情報源とは

エルゴード情報源は、時間平均と空間平均 (アンサンブル平均) が一致するという性質がある。

エルゴード性とは、十分に長い時間観測を行うことにより、その情報源の統計的性質を完全に把握できるということである。
例えば、ある文字の出現確率を知りたい場合、十分に長い系列を観測することにより、その確率を正確に推定することができる。

応用例として、音声信号の分析がある。
短時間で見ると、音声信号はエルゴード性を持つと仮定できる。

• 統計的予測可能性

  将来の挙動を過去のデータから予測することが可能

• 解析の簡便性

  時間平均で分析することにより、システム全体の特性を理解できる。

エルゴード情報源は、定常確率過程において、時間シフト作用素Tに関する不変測度が一意的である場合、その過程はエルゴード的であるとされる。
この性質は、エルゴード性があることで長い系列に対する最適な符号化方式を設計することが可能となるため、情報圧縮や通信路符号化において重要な役割を果たす。

エルゴード情報源の性質を利用して、通信システムの設計や性能評価が行われている。
例えば、デジタル通信システムにおける誤り訂正符号の設計では、チャネルのエルゴード性を仮定することにより、効率的な符号化方式を実現している。

また、パターン認識や機械学習の分野でも、データの定常性とエルゴード性は重要な仮定となっている。
これらの性質があることで、学習アルゴリズムの収束性が保証されて、実用的なシステムの構築が可能となる。

定常情報源におけるエルゴード情報源の計算例

定常マルコフ情報源とは、確率過程の1つであり、以下のような特徴を持つ。

• マルコフ性

  次の状態は、現在の状態にのみ依存する。(1次マルコフ性の場合)

  つまり、それ以前の状態には直接依存しない。

• 定常性

  状態遷移の確率が時間によって変化しない。

  つまり、同じ状態からの遷移は、いつでも同じ確率分布に従う。

例えば、文字列生成を考える場合、"A"の次に"B"が来る確率が30[%]、"C"が来る確率が70[%]というように確率的に次の状態が決まる時、この確率は時間によらず一定である。

定常マルコフ情報源の例:

文字列 {a, b} を出力する定常情報源において、遷移確率行列が以下に示す場合
$P(a|a)=0.7,\,\,P(b|a)=0.3$
$P(a|b)=0.4,\,\,P(b|b)=0.6$

この情報源の定常性とエルゴード性の確認する。

定常分布の計算:

$\pi (a)=0.7\pi (a)+0.4\pi (b)$
$\pi (a)+\pi (b)=1$

したがって、
$\pi (a)=0.57$
$\pi (b)=0.43$

次に、エルゴード性を確認する。

時間平均の計算: 
長さnの系列で'a'の出現回数/n : $0.57(n\rightarrow \infty )$

空間平均の計算:
$\pi (a)=0.57$

両者が一致することから、エルゴード性が確認できる。

定常二元情報源の例:

{0, 1}を出力する定常情報源があり、出力確率が次のとき
$P(0)=0.6,\,\,P(1)=0.4$

時間平均は、長さnの出力系列中の'0'の出現頻度 : 0.6
空間平均は、確率 $P(0)=0.6$

両者が一致することから、エルゴード性を示している。

例: 日本語文書の文字出現頻度分析の場合

• ある十分長い文書での「あ」の出現頻度（時間平均）
• 多数の文書での「あ」の出現確率（空間平均）

これらが一致することを利用して、文字コードの効率的な設計が可能となる。

上記の例から、エルゴード情報源の重要な特徴は、長時間の観測 (時間平均) と多数のサンプルの観測 (空間平均) が同じ結果をもたらすという点にある。

マルコフ情報源

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

例題: マルコフ情報源の場合
次の遷移確率を持つ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$