北海道大学 Hokkaido University 1 情報理論 講義資料 2016/06/22 情報エレクトロニクス学科共通科目・２年次・第 1 学期〔必修 科目〕 講義「情報理論」第 5 回 第 3 章 情報源のモデル [ 後半 ] 3.5 情報源のエントロピー.

Presentation on theme: "北海道大学 Hokkaido University 1 情報理論 講義資料 2016/06/22 情報エレクトロニクス学科共通科目・２年次・第 1 学期〔必修 科目〕 講義「情報理論」第 5 回 第 3 章 情報源のモデル [ 後半 ] 3.5 情報源のエントロピー."— Presentation transcript:

1 北海道大学 Hokkaido University 1 情報理論 講義資料 2016/06/22 情報エレクトロニクス学科共通科目・２年次・第 1 学期〔必修 科目〕 講義「情報理論」第 5 回 第 3 章 情報源のモデル [ 後半 ] 3.5 情報源のエントロピー

2 北海道大学 Hokkaido University 2 情報理論 講義資料 2016/06/22 [ 復習 ] 情報源の統計的表現 離散的 M 元情報源 –M 個の元を持つ情報源アルファベット A={a 1,a 2,…,a M } から – 時点 0 より情報源記号を発生する（時点は整数値） – 時点 i の情報源の出力を X i （ i = 0, 1, 2, ・・・）で表す – 時点 n-1 まで（長さ n ）の情報源系列 X 0 X 1 X 2 …X n-1 を考える 確率変数 離散的 M 元情報源 A={a 1,a 2,…,a M } P X 0, X 1 …X n-1 (x 0, x 1, …, x n-1 )= 〔 X 0 = x 0, X 1 = x 1, …, X n-1 = x n-1 となる確率〕 X 0, X 1, …, X n-1 の結合確率分布 時点 0 1 2 3 n-1 n-2 … X0X0 X1X1 X2X2 X3X3 X n-2 X n-1 情報源系列 この情報系列の統計的性質は X 0 X 1 X 2 …X n-1 の結合確率分布で完全に定まる。

3 北海道大学 Hokkaido University 3 情報理論 講義資料 [ 復習 ] 扱いやすい情報源の性質 記憶のない情報源記憶のない情報源 記憶のある情報源記憶のある情報源 定常 情報源 マルコフ情報源 エルゴード 情報源 定常情報源 – 時間をずらしても、統計的性質の変わらない情報源 – 任意の正整数 n と i および情報源アルファベットの任意の元 x 0, x 1, …, x n-1 に対 し、以下が成立。 P X 0 X 1 ・・・ X n-1 (x 0, x 1, …, x n-1 ) = P X i X i+1 ・・・ X i+n-1 (x 0, x 1, …, x n-1 ) エルゴード情報源 – それが発生する十分長い任意の系列に、その情報源の統計的性質が完全に現れ ている定常情報源 – 集合平均と時間平均が一致する。 2016/06/22

4 北海道大学 Hokkaido University 4 情報理論 講義資料 2016/06/22 [ 復習 ] よく用いられる情報源 記憶のない定常情報源 – 各時点における情報源記号の発生が、他の時点と独立で、各時点におけ る情報源記号の発生が同一の確率分布 P X (x) に従う情報源 正規マルコフ情報源 – 記憶のある情報源。 – 閉じた状態集合からなる非周期的なマルコフ情報源 – 初期分布としてどんな分布を与えても十分時間がたてば定常情報源であ りエルゴード情報源とみなせる。 記憶のない情報源記憶のない情報源 定常 情報源 マルコフ情報源 エルゴード 情報源 記憶のある情報源記憶のある情報源 P X 0 ・・・ X n-1 (x 0, …, x n-1 ) = Π P X (x i ) i = 0 n-1 s0s0 s1s1 1/ 0.6 0/ 0.4 0/ 0.3 s2s2 1/ 0.71/ 0.2 0/ 0.8

5 北海道大学 Hokkaido University 5 情報理論 講義資料 2016/06/22 [ 復習 ] 確率変数のエントロピー 確率変数 X の取りうる値を a 1, a 2, ・・・, a M とし、 X がそれ ぞれの値をとる確率が p 1, p 2, ・・・, p M （ただし、 p 1 +p 2 + ・・・ +p M =1) であるとき、確率変数 X のエントロ ピー H(X) は、 H(X) ＝－ ∑ p i log 2 p i と定義される。 i =1 M

6 北海道大学 Hokkaido University 定常情報源の１次エントロピー 6 情報理論 講義資料 2016/06/22 各時点に情報源記号 a 1,a 2,…,a M を出力する確率がそれぞれ p 1,p 2,…,p M であるような M 元定常情報源 S の１次エントロピー H 1 (S) を と定義する。 情報源記号列 X 0,X 1,… を出力する情報源 S のエントロピーは どのように定義すればよいか？ 定常情報源であれば、 P Xi (x) は時点 i によらず同じであるから、 X i のエントロピー H(X i ) は時点 i によらず一定 定常情報源 S のエントロピーを H(X i ) で定義してはどうか。

7 北海道大学 Hokkaido University １次エントロピーで情報源の曖昧さは測れる か？ 7 情報理論 講義資料 2016/06/22 どの時点でも出力情報源記号 X の確率分布 P X (x) が同じであれば その情報源から出力される記号列 X 0 X 1 ・・・の曖昧さは同じ？ s0s0 s1s1 0 / 0.91 / 0.61 / 0.1 0 / 0.4 マルコフ情報源 S および w 0 +w 1 ＝ 1 から、 w 0 ＝ 0.8 、 w 1 ＝ 0.2 S の定常分布 (w 0, w 1 ) は、 (w 0, w 1 ) 0.9 0.1 0.4 0.6 ＝ (w 0, w 1 ) P X (0)=0.8×0.9+0.2×0.4=0.8 P X (1)=0.8×0.1+0.2×0.6=0.2 無記憶定常情報源 S P X (0)=0.8 P X (1)=0.2 ともに各時点において 0, 1 が出 力される確率はそれぞれ 0,8 と 0.2 どちらも１次エントロピーは同じ H 1 (S)=-0.8log 2 0.8-0.2log 2 0.2=0.7219

8 北海道大学 Hokkaido University もう少し長い系列の分布でみたら 8 情報理論 講義資料 2016/06/22 定常情報源であれば X i X i+1 の結合確率分布 P X i X i+1 (x,y) も 時点 i によらず一定 s0s0 s1s1 0 / 0.91 / 0.61 / 0.1 0 / 0.4 マルコフ情報源 S S の定常分布 :(w 0, w 1 )=(0.8,0.2) P X (0)=0.8 P X (1)=0.2 無記憶定常情報源 S P X (0)=0.8 P X (1)=0.2 X 0 と X 1 の結合エントロピーに情報源の曖昧さの差が現れるのでは？ P X0X1 (0,0)=0.64 P X0X1 (0,1)=0.16 P X0X1 (1,0)=0.16 P X0X1 (1,1)=0.04 P X0X1 (0,0)=0.8×0.9×0.9+0.2×0.4×0.9=0.72 P X0X1 (0,1)=0.8×0.9×0.1+0.2×0.4×0.1=0.08 P X0X1 (1,0)=0.8×0.1×0.4+0.2×0.6×0.4=0.08 P X0X1 (1,1)=0.8×0.1×0.6+0.2×0.6×0,6=0.12 H(X 0,X 1 )=1.444 H(X 0,X 1 )=1.291 無記憶定常情報源の方 が曖昧さがおおきい！

9 北海道大学 Hokkaido University n 次エントロピー 9 情報理論 講義資料 2016/06/22 M 元情報源 S の n 次拡大情報源 S n S が出力する連続する n 個の情報源記号をまとめて１つの 情報源記号とみたとき、それを発生する M n 元情報源 n 次拡大情報源 S n の１次エントロピー H 1 (S n ) H 1 (S n )=H(X 0,X 1,…,X n-1 ) 情報源 S の n 次エントロピー H n (S) H n (S)=H 1 (S n )/n=H(X 0,X 1,…,X n-1 )/n n 確率変数の結合エントロピー 無記憶定常情報源 S P X (0)=0.8 P X (1)=0.2 H 2 (S)=H(X 0,X 1 )/2=1.444/2=0.722 s0s0 s1s1 0 / 0.91 / 0.61 / 0.1 0 / 0.4 マルコフ情報源 S H 2 (S)=H(X 0,X 1 )/2=1.291/2=0.646

10 北海道大学 Hokkaido University 情報源のエントロピー 10 情報理論 講義資料 2016/06/22 H(S)= 情報源 S から得られる１記号あたりの平均情報量 －

11 北海道大学 Hokkaido University 無記憶定常情報源のエントロピー 11 情報理論 講義資料 2016/06/22 無記憶 0 0 0

12 北海道大学 Hokkaido University 12 情報理論 講義資料 2016/06/22 マルコフ情報源のエントロピー 図のマルコフ情報源 S のエントロピーを考える s0s0 s1s1 0 / 0.91 / 0.61 / 0.1 0 / 0.4 図 : マルコフ情報源 S いま S が状態 s 0 にあるときだけに注目すると、この情報源は 1, 0 を 0.1, 0.9 の確率で発生する無記憶情報源とみなせる。 その場合のエントロピーを Hs 0 (S) と書くと Hs 0 (S) ＝ H (0.1) ＝ 0.4690 同様に、 S が状態 s 1 にあるときだけを注目すれば Hs 1 (S) ＝ H (0.6) ＝ 0.9710 （定常分布では） s 0 にいる確率が 0.8 、 s 1 にいる確率が 0.2 だから、 H(S) は H(S) ＝ 0.8×0.4690 + 0.2×0.9710 ＝ 0.5694 になると考えられる。 S の定常分布 (w 0, w 1 ) は、 (0.8,0.2) 。 H (x)= － xlog x － (1 － x)log(1 － x)

13 北海道大学 Hokkaido University 13 情報理論 講義資料 2016/06/22 一般のマルコフ情報源のエントロピー 情報源アルファベット {a 1, a 2, ・・・, a M } 状態 s 0, s 1, ・・・, s N － 1 定常分布 (w 0, w 1, ・・・, w N － 1 ) 状態 s i にあるときに記号 a j を発生する確率 P(a j | s i ) この情報源に対するエントロピー H(S) は H(S) ＝ ∑ w i － ∑ P(a j | s i ) log 2 P(a j | s i ) i=0 N – 1 j =1 M 一般のマルコフ情報源のエントロピー

14 北海道大学 Hokkaido University 14 情報理論 講義資料 2016/06/22 マルコフ情報源の n 次エントロピー n を大きくしていくと、図 1 のマルコフ情報源 S の n 次エントロピー H n (S)=H 1 (S n )/n は図 2 のように 0.5694 に収束していく。 図 2 ：マルコフ情報源のエントロピー 1 0.722 0.646 S と同じ出力記号の 定常分布 (P(0),P(1))=(0.8,0.2) をもつ無記憶定常情報源 S’ の エントロピー H(S’) 記憶がある分だけ曖昧さが減っている 予想しやすくなっている （圧縮しやすくなっている） s0s0 s1s1 0 / 0.91 / 0.61 / 0.1 0 / 0.4 図 1: マルコフ情報源 S