¾ðÊóÍýÏÀ

情報理論
第5回
情報理論
1 / 27
1
情報源のモデル
情報源のモデル
マルコフ情報源
エントロピーレート
定常情報源のエントロピーレート
2
練習問題
情報理論
2 / 27
情報源
語句
情報源：情報を発生する源
アルファベット：情報源から発生される記号の集合
q 元アルファベット：アルファベットの要素数が q
例：コインを 1 秒毎に投げ，表なら 1，裏なら 0 を出力する情報源を考え
る．これは 2 元アルファベット {0, 1} となる．
情報理論
3 / 27
確率過程
確率過程：確率変数の列のこと．時刻 i の確率変数が Xi とすると，
X1 , X2 , X3 , · · · , Xn
各確率変数 Xi が値 xi をとるときの確率は，
P ((X1 , X2 , · · · , Xn ) = (x1 , x2 , · · · , xn )) = P (x1 , x2 , · · · , xn )
と同時確率により書ける．
例：コインを 1 秒毎に投げ，表なら 1，裏なら 0 を出力する情報源を考え
る．コインを 5 回投げた結果が，0, 1, 1, 0, 1 のとき，
P ((X1 , X2 , X3 , X4 , X5 ) = (0, 1, 1, 0, 1)) = P (0, 1, 1, 0, 1) =
情報理論
1
32
4 / 27
定常情報源
定常情報源
定常情報源とは，任意の正整数 n と k ，(x1 , x2 , · · · , xn ) ∈ An に対して以
下を満たす情報源をいう．
P (X1 = x1 , X2 = x2 , · · · , Xn = xn )
= P (X1+k = x1 , X2+k = x2 , · · · , Xn+k = xn )
つまり，時間のシフトに対して同時確率が変化しない情報源である．
例：n = 1 としたときに，任意の正整数 k > 0 に対して以下が成り立つ．
P (X1 = x1 ) = P (X1+k = x1 )
独立したコイン投げは定常情報源．
情報理論
5 / 27
定常無記憶情報源
定常無記憶情報源
アルファベット A の値をとる確率変数列 X1 , X2 , · · · , Xn が互いに独立
で，同一の確率分布 Q に従うとき，その情報源を定常無記憶情報源とい
う．すなわち，以下を満たす．
P (X1 = x1 , X2 = x2 , · · · , Xn = xn ) = Q(x1 )Q(x2 ) · · · Q(xn )
つまり，前の確率変数に今の確率変数の値が依存しない．
例：独立したコイン投げは定常無記憶情報源．
情報理論
6 / 27
マルコフ情報源
マルコフ情報源
任意の正整数 n に対し，アルファベット A の値をとる確率変数列
X1 , X2 , · · · , Xn がすべての，(x1 , x2 , · · · , xn ) ∈ An について以下を満た
すとき，その情報源をマルコフ情報源という．
P (Xn = xn | Xn−1 = xn−1 , Xn−2 = xn−2 , · · · , X1 = x1 )
= P (Xn = xn | Xn−1 = xn−1 )
つまり，時刻 i における確率変数 Xi の確率分布が時刻 i − 1 の確率変数
Xi−1 のとった値のみに依存する．
例：アルファベット {0, 1} 上の情報源を考える．1 つ前の文字が 0 であれ
ば，1 がでる確率が 23 ，1 つ前の文字が 1 であれば，1 がでる確率が 13 で
あるような情報源はマルコフ情報源である．
情報理論
7 / 27
定常マルコフ情報源
定常マルコフ情報源
マルコフ情報源かつ，任意の正整数 n と任意の x, x′ ∈ A に対して以下の
2 つをみたすとき，その情報源を定常マルコフ情報源という．
P (Xn = x) = P (x1 = x)
P (Xn = x′ | Xn−1 = x) = P (X2 = x′ | X1 = x)
つまり，時刻 n で記号 x が出現する確率と時刻 n − 1 で x が出現したと
きに時刻 n で x が出現する確率が時刻 n によって変化しない．
情報理論
8 / 27
定常マルコフ情報源における同時確率
定常マルコフ情報源における同時確率
定常マルコフ情報源における同時確率 P (x1 , x2 , · · · , xn ) は以下のように
書ける．
P (x1 , x2 , · · · , xn ) = P (xn | xn−1 )P (xn−1 | xn−2 ) · · · P (x2 | x1 )P (x1 )
【証明】条件つき確率の公式より，
P (x1 , x2 , · · · , xn ) = P (xn | x1 , x2 , · · · xn−1 )P (x1 , x2 , · · · , xn−1 )
ここでマルコフ情報源の条件より，右辺は，
P (xn | x1 , x2 , · · · xn−1 )P (x1 , x2 , · · · , xn−1 )
= P (xn | xn−1 )P (x1 , x2 , · · · , xn−1 )
となる．あとは同様の式変形を繰り返せば上記の等式を得る．
情報理論
9 / 27
マルコフ情報源の特徴
2 元アルファベット {0, 1} 上の 2 元定常マルコフ情報源を考える．定常マ
ルコフ情報源を定めるためには，まず各条件付き確率を定める必要が
ある．
P (0|0) = 1 − a, P (1|0) = a, P (0|1) = b, P (1|1) = 1 − b
それと，時刻 1 における各記号の出現確率も定めないといけない．
P (X1 = 0) = w, P (X1 = 1) = 1 − w
これを状態遷移図（またはシャノン線図）で表すと以下のようになる．
1/a
0/1
a
0
1
1/1
b
0/b
情報理論
10 / 27
マルコフ情報源の特徴
定常確率分布の一意性
定常確率分布 P (0) = P (X1 = 0) と P (1) = P (X0 = 1) は，条件付き確率
を定めると一意に定まる．
（注意）a = b = 0 などの特別な場合は定めることができない．定めるこ
とのできないマルコフ情報源を非定常マルコフ情報源とよぶ．
【証明】定常マルコフ情報源なので以下を満たす．
P (Xn = 0) = P (X1 = 0) = w
P (Xn = 1) = P (X1 = 1) = 1 − w
今，条件確率が時刻によらず一定なので，以下が成り立つ必要がある．
P (X2 = 0) = P (X1 = 0) = w
P (X2 = 1) = P (X1 = 1) = 1 − w
情報理論
11 / 27
一意性の証明の続き
ここで，P (X2 = 0) を周辺確率の定義式より書き直すと，
P (X2 = 0) = P (X2 = 0, X1 = 0) + P (X2 = 0, X1 = 1)
= P (0|0)P (X1 = 0) + P (0|1)P (X1 = 1)
= (1 − a)w + b(1 − w)
となる，今，P (x2 = 0) = w を満たすので，
(1 − a)w + b(1 − w) = w
より，
w=
b
a+b
となり，a と b の値が決まれば一意に決まることがわかる．P (X2 = 1) の
方からも同様の導出ができるので各自行うこと．
情報理論
12 / 27
マルコフ情報源の特徴
問
2 元アルファベット {0, 1} 上の 2 元定常マルコフ情報源の条件付き確率が
以下で与えられている．
2
1
1
1
P (0|0) = , P (1|0) = , P (0|1) = , P (1|1) =
3
3
2
2
このとき，定常確率分布 P (0) と P (1) を求めよ．
問
2 元アルファベット {0, 1} 上の 2 元定常マルコフ情報源の条件付き確率が
以下で与えられている．
3
1
1
2
P (0|0) = , P (1|0) = , P (0|1) = , P (1|1) =
4
4
3
3
このとき，定常確率分布 P (0) と P (1) を求めよ．
情報理論
13 / 27
エントロピーレート
エントロピーレート
情報源 X からの出力列を表す確率変数列 X1 , X2 , · · · , Xn に対して，同
時エントロピーに関する以下の極限が存在するとき，H(X) を情報源 X
のエントロピーレートという．
1
H(X1 , X2 , · · · , Xn )
x→∞ n
H(X) = lim
同時エントロピーの収束値のこと．
情報理論
14 / 27
エントロピーの加法性の一般化
エントロピーの加法性の一般化
H(X1 , X2 , · · · , Xn ) =
H(X1 ) + H(X2 |X1 ) + H(X3 |X1 , X2 ) + · · · + H(Xn |X1 , X2 , · · · , Xn−1 )
【証明】確率変数が 2 個のときのエントロピーの加法性を用いると，
H(X1 , X2 , · · · , Xn ) = H(X1 , X2 , · · · , Xn−1 ) + H(Xn |X1 , X2 , · · · , Xn−1 )
となるので，後は同時エントロピーの部分に繰り返し，確率変数が 2 個
のエントロピーの加法性を利用すると結論の式が導かれる．
情報理論
15 / 27
定常無記憶情報源のエントロピーレート
エントロピーの加法性の一般化を用いることで，エントロピーレートを
求めることができる．
定常無記憶情報源のエントロピーレート
X を定常無記憶情報源とする．このとき，エントロピーレート H(X) は
以下を満たす．
H(X) = H(X1 )
【証明】情報源 X が定常無記憶情報源なので，出力列を表す確率変数列
X1 , X2 , · · · , Xn は互いに独立かつ同一の確率分布 P に従うことより，
H(Xn |X1 , X2 , · · · , Xn−1 ) = H(Xn ) n = 2, 3, · · ·
が成り立つ．
情報理論
16 / 27
証明
【証明のつづき】これより，
H(X1 , X2 , · · · , Xn )
= H(X1 ) + H(X2 |X1 ) + H(X3 |X1 , X2 ) + · · · + H(Xn |X1 , X2 , · · · , Xn−1 )
= H(X1 ) + H(X2 ) + · · · + H(Xn )
となり，各確率変数は独立かつ同じ確率分布に従うので，
H(X1 ) = H(X2 ) = · · · = H(Xn )
であるから，
H(X1 , X2 , · · · , Xn ) = nH(X1 )
これより，
1
H(X1 , X2 , · · · , Xn ) = H(X1 )
n
あとは両辺の n → ∞ の極限をとれば，H(X) = H(X1 ) を得る．
情報理論
17 / 27
定常マルコフ情報源のエントロピーレート
定常マルコフ情報源のエントロピーレート
X を定常マルコフ情報源とする．このとき，エントロピーレート H(X)
は以下を満たす．
H(X) = H(X2 | X1 )
【証明】情報源 X が定常マルコフ情報源なので，出力列を表す確率変数
列 X1 , X2 , · · · , Xn において，確率変数 Xn は 1 つ前の確率変数 Xn−1 以
外とは独立であるので，
H(Xn |X1 , X2 , · · · , Xn−1 ) = H(Xn |Xn−1 ) n = 2, 3, · · ·
が成り立つ．
情報理論
18 / 27
証明
【証明のつづき】これより，
H(X1 , X2 , · · · , Xn )
= H(X1 ) + H(X2 |X1 ) + H(X3 |X1 , X2 ) + · · · + H(Xn |X1 , X2 , · · · , Xn−1 )
= H(X1 ) + H(X2 |X1 ) + H(X3 |X2 ) · · · + H(Xn |Xn−1 )
となる．また定常性より，
H(X2 |X1 ) = H(X3 |X2 ) = · · · = H(Xn |Xn−1 )
であるから，
H(X1 , X2 , · · · , Xn ) = H(X1 ) + (n − 1)H(X2 |X1 )
となる．
情報理論
19 / 27
証明
【証明のつづき】よって，
1
H(X1 , X2 , · · · , Xn ) =
n
1
n−1
H(X1 ) +
H(X2 |X1 )
n
n
H(X1 )，H(X2 |X1 ) は n によらない定数なので，n → ∞ を考えると，
1
1
n−1
H(X1 , X2 , · · · , Xn ) = lim H(X1 ) + lim
H(X2 |X1 )
n→∞ n
n→∞ n
n→∞
n
= H(X2 |X1 )
lim
となり，証明される．
情報理論
20 / 27
定常マルコフ情報源のエントロピーレートの計算
条件付き確率が以下で与えられ，
P (0|0) = 1 − a, P (1|0) = a, P (0|1) = b, P (1|1) = 1 − b
ならびに定常確率分布が以下で与えられる定常マルコフ情報源 X を考
える．
P (0) =
b
a
, P (1) =
a+b
a+b
このとき，エントロピーレートは，
H(X) =
b
a
h(a) +
h(b)
a+b
a+b
となる．ここで，h(x) = −x log x − (1 − x) log(1 − x) の 2 元エントロ
ピー関数である．
情報理論
21 / 27
定常マルコフ情報源のエントロピーレートの計算
問
条件付き確率が以下で与えられる定常マルコフ情報源を考える．
1
2
3
1
P (0|0) = , P (1|0) = , P (0|1) = , P (1|1) =
3
3
4
4
このとき，定常確率分布 P (0)，P (1) と，エントロピーレート H(X) を
求めよ．
情報理論
22 / 27
定常情報源のエントロピーレート
定常情報源のエントロピーレート
X を定常情報源とする．X の出力列を表す確率変数を X1 , X2 , · · · , Xn と
する．このとき，
1
H(X1 , X2 , · · · , Xn ), n = 1, 2, · · ·
n
は，n について非増加な数列であり，n → ∞ で収束する．すなわち，X
が定常情報源であれば，必ずエントロピーレート H(X) は存在する．
【証明】略．
情報理論
23 / 27
練習問題
練習問題 1
以下の情報源が，定常無記憶情報源，マルコフ情報源，定常情報源のい
ずれかを答えなさい．
(a) 公平なサイコロを単位時間ごとに振って出た目を出力する情報源
(b) コイン投げを単位時間ごとに行う．最初は公平なコインを投げる．
各時刻のコイン投げで表が出れば次は公平なコインを投げ，裏が出
れば偏りのあるコインを投げる試行を繰り返し，表を 1，裏を 0 とし
て出力する情報源
(c) 最初にコインを投げ，表が出ればそれ以降公平なサイコロを，裏が
出ればそれ以降偏りのあるサイコロを振り続け，出た目を出力する
情報源
情報理論
24 / 27
練習問題
練習問題 2
2 つの偏りのあるコイン A とコイン B を投げて表が出れば 1，裏がでれ
ば 0 を表す確率変数をそれぞれ X と Y とする．また X と Y は以下の確
率分布に従うものとする．
2
1
P (X = 1) = x, P (X = 0) = 1 − x, P (Y = 1) = , P (Y = 0) =
3
3
最初にコイン A から投げ始め，各時刻において表がでれば次の時刻には
コイン A を，裏がでればコイン B を投げるという操作を繰り返す．この
とき，以下の問いに答えよ．
(a) この試行が定常マルコフ状態であるための x の値を求めよ．
(b) 定常マルコフ状態のとき，この情報源に対するエントロピーレート
を求めよ．
情報理論
25 / 27
練習問題
練習問題 3
公平なコインを投げて，表が出れば公平なサイコロを n 回振り，裏が出
れば 1 しか出ないサイコロを n 回振る．i 回目に振ったサイコロの目を表
す確率変数を Xi とするとき，エントロピーレート
1
H(X1 , X2 , · · · , Xn )
n→∞ n
lim
を求めよ．
情報理論
26 / 27
練習問題
練習問題 4
Xi は A = {0, 1} の要素を次の規則に従ってとる確率変数であるとする．
Xi = Xi−1 + Xi−2 + Zi mod 2
ただし，X0 = X−1 = 0 であり，Zi は等確率（一様に）{0, 1} の要素をと
る確率変数である．また各 Zi は独立であるとする．このとき，エントロ
ピーレート
lim
n→∞
1
H(X1 , X2 , · · · , Xn )
n
を求めよ．
情報理論
27 / 27

Download Report