情報理論

様々な情報源（４章）
1
情報源の役割
情報
情報源
伝送路
(通信路）
受信者
今回扱う。
☆無記憶情報源
（前の記号に依存しない情報
源。サイコロのような情報源）
☆マルコフ情報源
（前の結果に依存する情報源。
英文等は、こっちの方）
2
情報源モデル
情報源アルファベット
S = {s1, s2, L , sn }
情報源：
離散的な時刻に従い、
ある記号の集合から、
各時刻に一つの記号
を（ある確率的性格
で）出力する。
t
情報源から発生する記号の
集合
情報源シンボル（記号）
情報源から発生する記号。
情報源アルファベットの要素
記号 st Î S は、時刻 t i
i
で発生した情報源記号
st 1 s t 2 s t 3 s t 4 L
時間軸
3
情報源例１
サイコロを振る試行
による記号の生成。
情報源アルファベット
D = {1, 2, 3, 4, 5, 6}
st1 = 3 s t 2 = 5 st 3 = 2
L
t
4
情報源例２
英文からアルファ
ベットを拾って記号を
生成。
情報源アルファベット
A = {a, b, c, L , z }
s t 1 = i st 2 = n s t 3 = f
L
t
5
通報
通報
情報源
情報源から生成される
記号の列
st 1 s t 2 s t 3 s t 4
s
(n )
L
n
= st1st2 L stn
t
時間軸
n
s
(n )
t
= st - (n - 1)st - (n - 2) L st
n
6
情報源における記憶
無記憶情報源
st 1 s t 2 s t 3 s t 4
記号の生成確率が、
以前の記号に無関係
L
記憶のある情報源
st 1 s t 2 s t 3 s t 4
L
記号の生成確率が、
生成した記号で変化する
7
無記憶情報源（独立情報源）
無記憶情報源
, L
ìï s1
S = ïí
ïï P (s1 ) , L
î
st 1 s t 2 s t 3 s t 4
üï
ïý
, P (sn )ïï
þ
, sn
記号の生成確率が、
以前の記号に無関係
L
無記憶情報源の１記号あたりの（平均）情報量は、
次式で表される。
n
H (S ) = -
å
P (sk ) log P (sk )
[bit / 記号]
k= 1
8
１記号の発生速度を
r*
[記号 / 単位時間]
とする。このとき、単位時間あたりの発生平均情報量は、
次式であらわされる。
H * (S ) = r *H (S )
n
= - r * å P (sk ) log P (sk )
[bit / 単位時間]
k= 1
9
クイズ
次の四角に入るアルファベットを求めよ。
(1)
(2)
m
t
m
n
e
t
in
is
m
il
t
at
(3)
speake
teache
manne
10
記憶のある情報源
記号の生成確率が、
以前の記号で変化する
記憶ある情報
S = {s1, s2, L , sn }
{P 1(s1), L , P 1(sn )} {P 2(s1), L , P 2(sn )}
{P 3(s1), L , P 3(sn )}
4
4
P
(
s
),
L
,
P
(sn )}
{ 1
st 1 s t 2 s t 3 s t 4
L
11
（単純）マルコフ情報源
直前の生成された記号よって、次記号の発生確率が変化
する情報源を単純マルコフ情報源という。
発生した記号を条件とする条件付確率で定式化される。
すなわち、
に対して条件付確率
" s, s ' Î S
P (s ' | s )
で定められる情報源である。
s ' は今度発生する記号
s
は発生した記号
12
マルコフ情報源における状態の遷移
S = {s1, L , sn }
P (s1 | s1 )
s1
s1
s2
P (s2 | s1 )
P (sn | s1 )
P (s1 | s2 )
s2
P (s2 | s2 )
P (sn | s2 )
sn
s1
s2
sn
sn
13
状態遷移（確率）行列
éP (s1 | s1 ) P (s 2 | s1 )
ê
êP (s | s ) P (s | s )
2
2
ê 1 2
P = ê
ê M
O
ê
êP (s | s )
L
êë 1 n
L
L
O
L
P (sn | s1 ) ù
ú
P (sn | s 2 ) ú
ú
ú=
M ú
ú
P (sn | sn )ú
ú
û
éP1 ù
ê ú
êP ú
ê 2ú
ê ú
ê Mú
ê ú
êPn ú
êë ú
û
行ベクトルはすべて、確率ベクトル（要素は全て０から１
の値を持ち、要素の総和が１）。すなわち、確率ベクトル
p = ( p1, p2, L , pn ) に対して次式が成り立つ。
1 £ i £ n,
0 £ pi £ 1
n
å
i= 1
pi = 1
14
状態遷移確率行列のイメージ
次の記号
sj
P
前の記号
si
条件付確率
pij = P (s j | si )
各行で総和は１
si , s j Î S = {s1, L , sn }
なので正方行列
15
シャノン線図（状態遷移図）
S = {s1, L , sn }
P (s1 | s1 )
S1
P (s2 | s1 )
P (si | s1 )
P (sn | s1 )
P (sn | sn )
Sn
P (s1 | si )
Si
記号を状態と
みなし、条件
付確率を矢
印で表したも
の。
S2
P (s2 | s2 )
S3
P (s 3 | s 3 )
16
マルコフ情報源例（アルファベット）
A = {a, b, c, L , z }
a
P (a | a )
b
a
P (b | a )
P (z | a )
P (a | b)
b
P (b | b)
P (z | b)
z
a
b
z
z
17
状態遷移行列
éP (a | a ) P (b | a )
ê
êP (a | b) P (b | b)
ê
P= ê
ê M
O
ê
êP (a | z )
L
êë
辞書
L P (z | a ) ù
ú
ú
L P (z | z ) ú
ú=
O
M ú
ú
ú
L P (z | z ) ú
û
a
aa
éPa ù
ê ú
êP ú
ê bú
ê ú
ê Mú
ê ú
êPz ú
êë úû
ab
b
az
18
シャノン線図（アルファベット）
A = {a, b, c, L , z }
z
a
b
c
bÎ A
P (b | a )
a Î A
P (a | a )
19
マルコフ情報源例（２元単純マルコフ情報源）
生成記号が生成記号が
B = {0,1}
０の列
P (0 | 0) = 1/ 4
0
P (1 | 0) = 3/ 4
P (0 | 1) = 2/ 3
1
P (1 | 1) = 1/ 3
0
1
0
1
１の列
状態（記号）
が０の行
P =
é1/ 4 3/ 4ù
ê
ú
ê2/ 3 1/ 3 ú
êë
ú
û
状態（記号）
が１の行
20
２元単純マルコフ情報源のシャノン線図
3
4
1
4
1
0
1
3
2
3
21
練習１
次の状態遷移確率行列で表されるマルコフ情報源を、シャ
ノン線図で表せ。
é1/ 2 1/ 4
0
0
0 1/ 4 ù
ê
ú
ê1/ 4 1/ 2 1/ 4
ú
0
0
0
ê
ú
ê
ú
ê 0 1/ 4 1/ 2 1/ 4
0
0 ú
ú
P = êê
ú
0
0
1/
4
1/
2
1/
4
0
ê
ú
ê
ú
ê0
0
0 1/ 4 1/ 2 1/ 4 ú
ê
ú
ê1/ 4
ú
0
0
0
1/
4
1/
2
êë
ú
û 22
練習２
次のシャノン線図で表されるマルコフ情報源の状態
遷移確率行列を求めよ。
0.5
0.6
0.2
S1
0.2
0.1
0.7
S2
0.8
0.1
0.4
0.1
S4
0.2
S5
S6
0.1
1.0
0.7
S3
0.3
23
練習３
次のようなマルコフ情報源の、
状態遷移確率行列およびシャノン線図を求めよ。
手 = {グー、チョキ、パー}
自分が出した手の次の手は、
・前の手に勝つような手を出す確率が1/2である。
・前の手に引き分ける手を出す確率が1/3である。
・前の手に負ける手を出す確率が1/6である。
24
（参考）無記憶情報源の状態遷移行列
均等なサイコロを振ったときの状態遷移行列
次出る目
今の目
1
2
3
4
5
6
1 é1/ 6 1/ 6 1/ 6 1/ 6 1/ 6 1/ 6ù
2
P =
3
4
5
6
ê
ê1/
ê
ê
ê1/
ê
ê1/
ê
ê
ê1/
ê
ê1/
êë
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
ú
6ú
ú
ú
6ú 条件付
ú 確率
6ú
ú
ú
6ú
ú
6ú
ú
û
25
偶数の出やすいサイコロ（無記憶情報源）
次出る目
今の目
1
2
3
4
5
6
1 é1/ 12 1/ 4 1/ 12 1/ 4 1/ 12 1/ 4 ù
2
P =
3
4
5
6
ê
ê1/ 12
ê
ê
ê1/ 12
ê
ê1/ 12
ê
ê
ê1/ 12
ê
ê1/ 12
êë
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
ú
4ú
ú
ú
4 ú 条件付
ú 確率
4ú
ú
ú
4ú
ú
4ú
ú
û
26
練習
（１）コインを振って得られる状態遷移関数を求めよ。
（２）表の出る確率が、裏のでる確率の２倍であるコインを
振って得られる状態遷移関数を求めよ。
27
定常分布
情報源アルファベット S = {s1, s2, L , sn } に対して、
出現確率が時刻 t
と時刻 t + 1 で変化しないよう
な記号の分布を定常分布という。
t
P (s1 )
P t (sn )
P
s1
sn
" si Î S
t
P (s i ) = P
t
P (si )
P
(sn )
t+1
(s i )
t+1
s1
sn
s2
si Î S
t+1
s2
si Î S
P
t+1
(si )
28
(s1 )
定常分布の求め方
定常分布は、状態遷移確率行列から求めることができる。
定常分布をz = (z 1, z 2, L , z n ) とし、状態遷移確率行列を
Pとする。このとき、次式が成り立つ。
= [pij ]
時刻 t からt + 1になっても変化しない。
常に一定の出現確率となる。
z = zP
記号の出現確率。
生成した記号の確率と状
態遷移確率積なので、次
の記号の出現確率を表す。
29
z = zP
の意味。
éP (s1 | s1 ) P (s 2 | s1 )
ê
êP (s | s ) P (s | s )
2
2
ê 1 2
ê
(P (s1 ), L , P (sn )) = (P (s1 ), L , P (sn ))
ê M
M
ê
êP (s | s )
L
êë 1 n
L
L
O
L
P (sn | s1 ) ù
ú
M ú
ú
ú
M ú
ú
P (sn | sn )ú
ú
û
情報理論では、慣用的に確率ベクトルは行ベ
クトルで表される。
t
t
t
z = P z
æP (s1 ) ÷
ö
çç
÷
ççP (s ) ÷
÷
çç 2 ÷
÷
÷
=
çç
÷
÷
çç M ÷
÷
÷
çç
÷
P
(
s
)
çèç n ÷
÷
ø
÷
転置を用いて左式のようにも表せる。
éP (s1 | s1 ) P (s1 | s 2 )
ê
êP (s | s ) P (s | s )
2
2
ê 2 1
ê
ê M
M
ê
êP (s | s )
L
êë n 1
L
L
O
L
P (s1 | s n ) ùæ
P (s1 ) ö
÷
ç
úç
÷
÷
ç
ú
M úççP (s 2 ) ÷
÷
÷
ç
÷
úç
÷
ç
ú
M ç M÷
÷
÷
úçç
÷
÷
ú
÷
P (sn | sn )úèççP (s n )ø
÷
÷
ûç
30
定常分布例
情報源アルファベットB = {0,1} に対する２元マルコフ情報
源の状態遷移確率関数が次式で与えられている。
é1/ 4 3 / 4ù
ê
ú
P = ê
ú
êë2 / 3 1/ 3 ú
û
このとき、定常分布 z = (z 0, z 1 ) = (P (0), P (1)) を求めよ。
解）
é1/ 4 3/ 4ù
ú
(z 0, z 1 ) = (z 0, z 1 ) êê
ú
2/
3
1/
3
êë
ú
û
より、
æz 0 ö
çç ÷
÷=
÷
çèz 1 ø
÷
é1/ 4 2/ 3ùæz 0 ö
ê
úç ÷
÷
ç
ê3/ 4 1/ 3 úçz 1 ÷
÷
è ø
êë
ú
û
31
ìï 3
2
ïï z 0 = z 1
3
\ ïí 4
ïï 2
3
z
=
z0
ïï 1
4
î3
\ 9z 0 = 8z 1
一方、z
全ての行ベクトルが確率ベクトルなので遷移
確率行列は正則でなく逆行列を持たない。
よって、このように必ず不定の解になる。
は確率ベクトルなので、
前のスライドとこの式か
ら求める。
z 0 + z1 = 1
が成り立つ。
9
\ z0 + z0 = 1
8
8
\ z0 =
17
9
\ z1 =
17
検算
é1/ 4 3 / 4ù
ú
8 / 17 9 / 17 êê
ú
2
/
3
1/
3
êë
ú
û
(
(
= (8 / 17
)
= 2 / 17 + 6 / 17 6 / 17 + 9 / 17
9 / 17
)
32
)
練習
次の状態遷移確率行列で表される情報源の定常分布を求めよ。
（１）
（２）
é2 / 5 3 / 5ù
ê
ú
P1 = ê
ú
êë1/ 2 1/ 2 ú
û
é1/ 2 1/ 2
ù
0
ê
ú
ê
ú
P2 = ê 0 1/ 3 2 / 3ú
ê
ú
ê3 / 4
ú
0
1/
4
êë
ú
û
33
無記憶情報源における定常分布
無記憶情報源における定常分布は、出現確率と一致する。
無記憶情報源が次式で表されているとする。
, L
ìï s1
S = ïí
ïï P (s1 ) , L
î
üï
ïý
, P (sn )ïï
þ
, sn
このとき、状態遷移確率行列は次式で表される。
éP (s1 ) L
ê
êP (s ) L
ê 1
P= ê
ê M
ê
êP (s ) L
êë 1
P (sn )ù
ú
P (sn )úú
ú
Mú
ú
P (sn )úú
û
すべての行が同一な
状態遷移行列。
逆に、このような行列
で表される情報源が
無記憶情報源。
34
(P (s )
1
L
éP (s1 ) L
ê
êP (s ) L
ê 1
P (sn ) ê
ê M
ê
êP (s ) L
êë 1
)
æ
çç
n
= ççP (s1 ) å P (si ) L
çç
i = 142 4443
144
çè
1
(
= P (s1 ) L
P (sn )
P (sn )ù
ú
P (sn )úú
ú
Mú
ú
ú
P (sn )ú
û
ö÷
n
÷
÷
P (sn ) å P (si )÷
÷
÷
i144
= 142 4443÷
÷
ø
1
)
35
マルコフ情報源の随伴（無記憶）情報源
マルコフ情報源 S の定常分布を確率分布とするような
無記憶情報源を元のマルコフ情報源の随伴情報源 S
という。
例
情報源アルファベット B
遷移確率行列が
= {0,1}
é1/ 4 3/
PB = êê
êë2/ 3 1/
で表されるマルコフ情報源を S
このとき、随伴情報源
B
SB
を持ち、状態
4ù
ú
ú
3ú
û
とする。
は次式で表される。
ìï 0
,
1 ü
ï
ï
ïý
SB = í
ïï 8 / 17 , 9 / 17ïï
î
þ
36
（補足）マルコフ情報源のエントロピー
S に対して、 S
H (S | S )
マルコフ情報源
付きエントロピー
トロピーという。
H (S | S ) =
å
S
を条件とする
の条件
をマルコフ情報源のエン
P (s i )H (S | s i )
si Î S
= -
å
si Î S
= -
P (s i )å P (s j | s i ) log P (s j | s i )
sj Î S
å
P (s i )P (s j | s i ) log P (s j | s i )
å
P (s j , si ) log P (s j | s i )
si ,s j Î S
= -
si ,s j Î S
37
マルコフ情報源のエントロピー例
状態遷移確率行列
PB =
é1/ 4 3/ 4ù
ê
ú
ê2/ 3 1/ 3 ú
êë
ú
û
で定まるマルコフ情報源 S B のエントロピーを求める。
まず、定常分布
z
は以下で与えられる。
æ8 9 ö
z = (P (0), P (1)) = çç , ÷
÷
è17 17 ø
状態０におけるエントロピー（０を条件とする条件付きエントロピー）
および状態１におけるエントロピー
H (Sを求める。
H
(S B | 0)
B | 1)
38
H (S B | 0) = - P (0 | 0) log P (0 | 0) - P (1 | 0) log P (1 | 0)
æ1 ö
÷
= H ç
ç
è4 ÷
ø
; 0.811
０の時のエントロピー
H (S B | 1) = - P (0 | 1) log P (0 | 1) - P (1 | 1) log P (1 | 1)
æ1 ÷
ö
ç
= H ç ÷
è3 ø
; 0.918
１の時のエントロピー
\ H (S B | S B ) = P (0)H (S B | 0) + P (1)H (S B | 1)
8
æ1 ö
9
÷
=
H ç
+
H
÷
ç
è4 ø 17
17
; 0.382 + 0.486
= 0.868
æ1 ö
ç ÷
÷
ç3 ø
è
マルコフ情報源のエントロピー
39
マルコフ情報源のエントロピーの意味
1
4
P (0)
P (1)
０状態の一種の
存在確率
１状態の一種の
存在確率
0
H (S B | 0)
０状態において、
記号出力に注目し
た平均情報量
3
4
2
3
1
1
3
H (S B | 1)
１状態において、
記号出力に注目し
た平均情報量
40
イメージ
０を取ったら次は０の箱から取り、１を取ったら次は１の箱からと
る。取った玉は元に戻す。
マルコフ情報源
0
1
1
1
SB
0
0
1
41
練習
次の状態遷移確率行列で表される情報源のエントロピーを求めよ。
（１）
（２）
é2 / 5 3 / 5ù
ê
ú
P1 = ê
ú
êë1/ 2 1/ 2 ú
û
é1/ 2 1/ 2
ù
0
ê
ú
ê
ú
P2 = ê 0 1/ 3 2 / 3ú
ê
ú
ê3 / 4
ú
0
1/
4
êë
ú
û
42
マルコフ情報源のエントロピーの性質
S
S
マルコフ情報源
に対して、随伴情報源を
とす
る。このとき、随伴情報源のエントロピーは、マルコフ情報源
のエントロピー以上である。すなわち、次式が成り立つ。
H (S | S ) £ H (S )
出現確率は同じでも、マルコフ情報源の方は記号の
現れ方に制限がある。（すなわち、記号の出現の予測
が無記憶情報源比べて行いやすい。）したがって、
マルコフ情報源の方が平均情報量が少なくなる。
43
随伴情報源のエントロピー例
é1/ 4 3/ 4ù
ú
PB = êê
ú
の随伴情報源は
2/
3
1/
3
êë
ú
û
ìï 0
,
1 ü
ïï
ï
SB = í
ý
ïï 8 / 17 , 9 / 17ïï
î
þ
である。
したがて、エントロピー H (S B ) は次式で求められる。
æ8 ÷
ö
H (S B ) = H çç ÷ ; 0.997
è17 ø
\ 0.868 ; H (S B | S B ) £ H (S B ) ; 0.997
44
練習
（１）
（２）
次の状態遷移確率行列で現されるマルコフ情報源
の随伴情報源のエントロピーを求めよ。
é2 / 5 3 / 5ù
ê
ú
P1 = ê
ú
êë1/ 2 1/ 2 ú
û
é1/ 2 1/ 2
ù
0
ê
ú
ê
ú
P2 = ê 0 1/ 3 2 / 3ú
ê
ú
ê3 / 4
ú
0
1/
4
êë
ú
û
45

Download Report