情報理論 3 5 相互情報量 3.5相互情報量 ¦¦ ¦ ¦¦ ¦m ¦¦ ¦¦ ¦¦ ¦¦ ¦¦ ¦¦ ¦¦ ¦¦ ¦¦ ¦¦ ¦¦ 4

I ( A; B)
n
m
¦¦ P (ak , bl ) log 2 P(ak )
k 1 l 1
n
m
¦¦ P (ak , bl ) log 2 P(ak | bl )
k 1 l 1
᝟ሗ⌮ㄽ
n
¦¦ P(a , b ) log
k
k 1 l 1
n
l
P(ak | bl )
P ( ak )
2
P(ak , bl )
P(ak ) P(bl )
m
¦¦ P(a , b ) log
2011/10/28
2
m
k
k 1 l 1
l
䛣䛾䜘䛖䛻ᒎ㛤䛷䛝䜛 (p.90 ᘧ(7.29))
4
3 5 ┦஫᝟ሗ㔞
3.5┦஫᝟ሗ㔞
• H(A)
H(A),H(B),H(A|B),H(B|A),H(A,
H(B) H(A|B) H(B|A) H(A B),
B) I(A; B)
䛾㛫䛾㛵ಀ
• ┦஫᝟ሗ㔞
┦ ᝟ሗ㔞 (MutualInformation)
I(A;
( ; B)) = H(A)
( ) – H(A|B)
( | )
= (஦㇟⣔A䛾᝟ሗ㔞)
䛜ศ䛛䛳䛯᫬䛾
䛯᫬䛾 A 䛾᝟ሗ㔞)
– (஦๓᝟ሗ䛸䛧䛶 B 䛜ศ䛛
= (஦๓᝟ሗ B 䜢▱䜛䛣䛸䛷ᚓ䜙䜜䜛᝟ሗ㔞)
1 H(A|B) ӌ H(A)
1.
H(B|A) ӌ H(B)
я ஦๓᝟ሗ䜢ᚓ䜛䛣䛸䛷᝟ሗ㔞䛜ῶ䜛
2. H(A, B) = H(A) + H(B|A) = H(B) + H(A|B)
3. H(A) – H(A|B) = H(B) – H(B|A)
= H(A)
( ) + H(B)
( ) – H(A,
( , B))
= H(A, B) – H(A|B) – H(B|A)
= I(A;
( B))
1
5
4 ᝟ሗ※
4.
• 䛥䛔䛣䜝䛾౛
H ( A) log 2 6 䍦 2.58
2 58
• 4.1⠇
⠇ 䡚 4.6⠇
⠇ 䛸 4.8⠇
⠇
• 4.7⠇
4 7⠇ 䛸 4.10⠇
4 10⠇ (ḟᅇ 11᭶8᪥(ⅆ))
• 4.9⠇䛿┬␎
H ( A | B ) log 2 3 䍦1.58
I ( A; B)
2.58 1.58 1.00
஦๓᝟ሗ B (അᩘ䛛ወᩘ䛛) 䜢▱䜛䛣䛸䛷
ᚓ䜙䜜䜛᝟ሗ㔞
2
I ( A; B)
6
H ( A) H ( A | B)
4 1 ᝟ሗ※䝰䝕䝹
4.1᝟ሗ※䝰䝕䝹
n
¦ P (ak ) logg 2 P(ak )
• 䝅䝱䝜䞁䞉䝣䜯䝜䛾㏻ಙ䝅䝇䝔䝮
㏻ಙ
k 1
­
½
® ¦¦ P(ak , bl ) log
l 2 P(ak | bl )¾
¯ k1l1
¿
n
䛣䛣䛷䠈 P (a k )
I ( A; B)
n
m
(㞧㡢)
እ஘
m
¦ P(ak , bl ) 䛾㛵ಀ䜢⏝䛔䛶
᝟ሗ※
l 1
m
¦¦ P(ak , bl ) log 2 P(ak )
᝟
ሗ
※
➢
ྕ
໬
㏻
ಙ
㊰
➢
ྕ
໬
㏻ಙ㊰
㏻
ಙ
㊰
᚟
ྕ
໬
᝟
ሗ
※
᚟
ྕ
໬
ཷಙ⪅
k 1 l 1
n
m
¦¦ P(ak , bl ) log 2 P(ak | bl )
k 1 l 1
3
7
• 䝬䝹䝁䝣㐣⛬(Markovprocess)
䝬䝹䝁䝣㐣⛬(Markov process)
• ᝟ሗ※
• 䛒䜛஦㇟䛾⏕㉳䛩䜛☜⋡䛜䠈┤๓䛾 m ᅇ䛾஦㇟
䛻౫Ꮡ䛩䜛☜⋡㐣⛬
• m㝵䝬䝹䝁䝣㐣⛬ (m㔜䝬䝹䝁䝣㐣⛬)
• ┤๓䛾 m ᅇ䛾஦㇟䜢䜂䛸䜎䛸䜎䜚䛸⪃䛘䜜䜀䠈
༢⣧䝬䝹䝁䝣㐣⛬䛸䛧䛶⾲⌧ྍ⬟
• 㞳ᩓⓗ᝟ሗ※
• 㐃⥆ⓗ᝟ሗ※
• ᝟ሗ※䛷Ⓨ⏕䛩䜛グྕิ
S = {s1, s2, 䞉䞉䞉, sn}
グྕ sk ( k = 1, 2, 䞉䞉䞉, n)
э ᝟ሗ※グྕ 䜎䛯䛿 ᝟ሗ※䝅䞁䝪䝹
• ༢⣧䝬䝹䝁䝣㐣⛬ (m
( m=11 )
• ⌧ᅾ䛾஦㇟ Xn 䛿䠈୍䛴๓䛾஦㇟ Xn-1 䛻౫Ꮡ
э ᮲௳䛴䛝☜⋡ P(Xn|Xn-1) 䛸䛧䛶⾲⌧ྍ⬟
᝟ሗ※
᝟ሗ※䜰䝹䝣䜯䝧䝑䝖
8
12
4 3 ↓グ᠈᝟ሗ※䝰䝕䝹
4.3↓グ᠈᝟ሗ※䝰䝕䝹
• ᝟ሗ※䝰䝕䝹
䠙 ᝟ሗ※䜰䝹䝣䜯䝧䝑䝖 䠇 ☜⋡ⓗᛶ㉁
• ↓グ᠈᝟ሗ※䝰䝕䝹
↓ ᠈᝟ሗ
䝕
• ☜⋡ⓗᛶ㉁
• グྕ䛾Ⓨ⏕☜⋡ (↓グ᠈᝟ሗ※ 4.3⠇)
• グྕ䛾᮲௳௜䛝Ⓨ⏕☜⋡ (䝬䝹䝁䝣᝟ሗ※ 4.5⠇)
᝟ሗ※䜰䝹䝣䜯 䝑䝖:S
᝟ሗ※䜰䝹䝣䜯䝧䝑䝖:
S = {s1, s2, 䞉䞉䞉,, sn}
Ⓨ⏕☜⋡:P(sk) ( k = 1, 2, 䞉䞉䞉, n)
S
­ s1 , s2 , , sn ½
®
¾
¯ P( s1 ), P( s2 ), , P( sn )¿
9
4 2 ᝟ሗ※䛾✀㢮
4.2᝟ሗ※䛾✀㢮
13
• グྕ䛒䛯䜚䛾Ⓨ⏕ᖹᆒ᝟ሗ㔞
(Ⓨ⏕䜶䞁䝖䝻䝢䞊)
• グ᠈䛾䛺䛔᝟ሗ※
(↓グ᠈᝟ሗ※䠈⊂❧᝟ሗ※)
n
¦ P ( sk ) log 2 P ( sk )
H (S )
• ⌧ᅾ䛾᝟ሗ䛜㐣ཤ䛻౫Ꮡ䛧䛺䛔᝟ሗ※
(
)
• Ⓨ⏕䛩䜛グྕ䛿⊂❧ (᮲௳௜䛝☜⋡䛿୙せ)
[[bit //᝟ሗ※グྕ]]
k 1
• ༢఩᫬㛫ᙜ䛯䜚䛾Ⓨ⏕ᖹᆒ᝟ሗ㔞
• グ᠈䛾䛒䜛᝟ሗ※ ((䝬䝹䝁䝣᝟ሗ※)
䝹 䝣᝟ሗ※)
H * (S )
• ⌧ᅾ䛾≧ែ䛜㐣ཤ䛻౫Ꮡ䛩䜛᝟ሗ※
• 䝬䝹䝁䝣㐃㙐䛸࿧䜀䜜䜛☜⋡㐣⛬䛻䜘䜚≉ᚩ䛵
䛡䜙䜜䜛
r *H (S )
[bit /༢఩᫬㛫]
r * :グྕ䛾Ⓨ⏕㏿ᗘ
[ಶ /༢఩᫬㛫]
10
14
4 4 ㏻ሗ
4.4㏻ሗ
• 䝬䝹䝁䝣ᛶ
• ☜⋡㐣⛬䛾≧ែ Xn+1 䛜䠈⌧ᅾ䛾≧ែ Xn 䛾䜏䛻
౫Ꮡ䛧 X0, X1, 䞉䞉䞉,
౫Ꮡ䛧䠈X
䞉䞉䞉 Xn-1 䛸䛿↓㛵ಀ䛷䛒䜛䜘䛖䛺
ᛶ㉁䛾䛣䛸
• ㏻ሗ (message)
э ᝟ሗ※䛛䜙Ⓨ⏕䛩䜛グྕิ
౛)㛗䛥 n 䛾㏻ሗ
xt
X0
X1
䞉䞉䞉
Xn-1
Xn
(n)
xt ( n 1) xt ( n 2 ) xt 1 xt
xt: ᫬้ t 䛷䛾Ⓨ⏕グྕ
Xn+1
11
15
౛)㛗䛥 n 䛾㏻ሗ
xt
(n)
(ཧ) ↓グ᠈᝟ሗ※
xt ( n 1) xt ( n 2 ) xt 1 xt
• ⌧ᅾ䛾᝟ሗ䛜㐣ཤ䛻౫Ꮡ䛧䛺䛔᝟ሗ※
t , n
xt: ᫬้ t 䛷䛾Ⓨ⏕グྕ
(n)
P( xt | xt 1 )
᫬้ t 䛛䜙㐣ཤ n ಶ䛾グྕ䛛䜙ᵓᡂ䛥䜜䜛グྕิ
(n)
᫬้䛜ၥ㢟䛸䛺䜙䛺䛔ሙྜ: x
x1 x2 xn 1 xn
P( xt )
t , n
(n)
P( xt | xt 1 )
P( xt | xt 1 )
16
4 5 䝬䝹䝁䝣᝟ሗ※
4.5䝬䝹䝁䝣᝟ሗ※
4 6 䝬䝹䝁䝣㐃㙐 (䝬䝹䝁䝣䝏䜵䞊䞁)
4.6䝬䝹䝁䝣㐃㙐
• ㏻ሗ䛻䜘䜛᮲௳௜䛝Ⓨ⏕☜⋡䛻䜘䜛⾲⌧
㏻ሗ
䜛᮲௳ 䛝 ⏕☜⋡
䜛⾲
• ᵓᡂせ⣲
ᵓᡂ ⣲
t , n(t m)
(n)
P( xt | xt 1 )
P( xt | xt 1
(m)
20
)
ᕥ㎶: 㛗䛥 n 䛾㏻ሗ䛜Ⓨ⏕䛧䛯ᚋ䛻 xt 䛜Ⓨ⏕䛩䜛☜⋡
ᕥ㎶:㛗䛥
ྑ㎶:㛗䛥 m 䛾㏻ሗ䛜Ⓨ⏕䛧䛯ᚋ䛻 xt 䛜Ⓨ⏕䛩䜛☜⋡
•
•
•
•
᫬้ t 䛷䛾≧ែ䜢⾲䛩☜⋡ኚᩘ
≧ែ䜢⾲䛩☜⋡ኚᩘ x(t)
()
≧ែ㞟ྜ Q = {q1, q2, 䞉䞉䞉, qN}
≧ែ☜⋡䝧䜽䝖䝹 u(t) = (u1(t),
(t) u2(t),
(t) 䞉䞉䞉,
䞉䞉䞉 uN(t))
≧ែ㑄⛣☜⋡⾜ิ
P
§ P11 P1N ·
¨
¸
¨ ¸
¨
¸
© PN 1 PNN ¹
17
t , n(t m)
(n)
P( xt | xt 1 )
P( xt | xt 1
(m)
21
• ≧ែ☜⋡䝧䜽䝖䝹 u(t) = (u1(t), u2(t), 䞉䞉䞉, uN(t))
)
0 d uk (t ) d 1 (k 1, , N ),
)
ᕥ㎶:㛗䛥 n 䛾㏻ሗ䛜Ⓨ⏕䛧䛯ᚋ䛻 xt 䛜Ⓨ⏕䛩䜛☜⋡
ྑ㎶:㛗䛥 m 䛾㏻ሗ䛜Ⓨ⏕䛧䛯ᚋ䛻 xt 䛜Ⓨ⏕䛩䜛☜⋡
N
¦u
k 1
k
(t ) 1
┤๓䛾 m ಶ䛾≧ែ䛻䜘䛳䛶⌧ᅾ䛾≧ែ䛜Ỵ䜎䜛
m 㔜䝬䝹䝁䝣᝟ሗ※
18
• ≧ែ㑄⛣☜⋡⾜ิ
• ┤๓䛾 m ಶ䛾≧ែ䛷⌧ᅾ䛾≧ែ䛜Ỵ䜎䜛
t , n
༢⣧䝬䝹䝁䝣᝟ሗ※
(n)
P( xt | xt 1 )
§ P11 P1N ·
¨
¸
¨ ¸
¨P
¸
© N 1 PNN ¹
P
m 㔜䝬䝹䝁䝣᝟ሗ※
• m=1 䛾䛸䛝
22
࿴䛿 1
0 d Pkl d 1 (k,l 1, , N ),
P( xt | xt 1 )
Pkl
P(ql | qk )
N
¦P
l 1
kl
1
P(qk o ql )
≧ែ㑄⛣☜⋡
( )
(ཧ)↓グ᠈᝟ሗ※
t , n
((nn )
P( xt | xt 1 )
P( xt )
19
23
• ≧ែ䛾㑄⛣䜢ᅗ䛷⾲䛩 э ≧ែ㑄⛣ᅗ
౛)
P11
q1
q3
P13
P32
P21
• ᝟ሗ※䜰䝹䝣䜯䝧䝑䝖 S = {0, 1}
• ≧ែ㞟ྜ Q = {q1, q2, q3, q4} = {00,
{00 01
01, 10
10, 11}
q4
P54
q2
q5
qN
• ᝟ሗ※䛻ᑐ䛧䛶䛿䝅䝱䝜䞁⥺ᅗ(4.8⠇)䛸䜒
24
4 8 䝅䝱䝜䞁⥺ᅗ
4.8䝅䝱䝜䞁⥺ᅗ
• ≧ែ㑄⛣☜⋡ (᮲௳௜䛝Ⓨ⏕☜⋡)
P(0|00) = a, P(1|00) = 1-a
P(0|01) = b,
b P(1|01) = 1-b
1b
P(0|10) = c, P(1|10) = 1-c
P(0|11) = d, P(1|11) = 1-d
• ≧ែ㑄⛣☜⋡⾜ิ
§ a 1 a 0
• ᝟ሗ※䛻䛚䛡䜛≧ែ㑄⛣ᅗ
᝟ሗ
䛚 䜛≧ែ ⛣
౛)᝟ሗ※ S = {0, 1}
≧ែ㑄⛣⾜ิ
§ a
P
¨¨
©1 b
28
1 a ·
¸
b ¸¹
P
P(0|0) = a, P(1|0) = 1-a
P(0|1) = 1-b, P(1|1) = b
0 ·
¨
¸
0
b 1 b ¸
¨0
¨ c 1 c 0
0 ¸
¨
¸
¨0
0
d 1 d ¸¹
©
25
䛣䛾᝟ሗ※䛻ᑐ䛩䜛䝅䝱䝜䞁⥺ᅗ
1-a
a
0
1
b
1-b
⮬ᕫ㑄⛣
29
㑄⛣
᪂䛧䛔≧ែ
㑄⛣☜⋡
000
00
P(0|00) = a
001
01
P(1|00) = 1-a
010
10
P(0|01) = b
01 1
011
11
P(1|01) = 1-b
100
00
P(0|10) = c
10 1
01
P(1|10) = 1-c
11 0
0
10
P(0|11) = d
11 1
111
11
P(1|11) = 11-dd
26
30
䝅䝱䝜䞁⥺ᅗ
౛)2㔜䝬䝹䝁䝣᝟ሗ※
౛)
2㔜䝬䝹䝁䝣᝟ሗ※
э┤๓䛾 2 ಶ䛾≧ែ䛷⌧ᅾ䛾≧ែ䛜Ỵᐃ
a
1-a
00
c
᝟ሗ※䜰䝹䝣䜯䝧䝑䝖 S = {{0,, 1}} 䛸䛩䜛
b
≧ែ䛾㑄⛣䛿
≧ែ䛾㑄⛣䛿䠈
000,001
010,011
10 0 10 1
100,10
1
11 0,111
01
10
1-c
1-b
11
d
1d
1-d
27
31
((4.6⠇䛻ᡠ䜛)
⠇䛻ᡠ䜛)
• ึᮇ᫬้ 0 䛻䛚䛔䛶≧ែ q1 䛻䛔䛯䜒䛾䛜䠈
᫬้ t 䛾䛸䛝䛻 䛒䜛≧ែ䛻Ꮡᅾ䛩䜛☜⋡
• ึᮇ᫬้ 0 䛻䛚䛔䛶≧ែ q1 䛻䛔䜛
u(0) = (1, 0, 䞉䞉䞉, 0)
• ᫬้ t 䛻䛚䛡䜛≧ែ☜⋡
䛻䛚䛡䜛≧ែ☜⋡䝧䜽䝖䝹
䜽䝖䝹
u(t) = (u1(t), u2(t), 䞉䞉䞉, uN(t))
u(0) 䛸 u(t) 䛾㛵ಀ䜢≧ែ㑄⛣☜⋡䜢౑䛳䛶⪃䛘䜛
32
1 u(0) u(1)
1.
u(1) = u(0)P
2. u(1)
( ) u(2)
( )
2
u(2) = u(1)P = u(0)PP = u(0)P
(᫬้ t 䜎䛷⧞䜚㏉䛩)
3. u(t-1)
( ) u(t)
()
2
t
u(t) = u(t-1)P = u(t-2)P = 䞉䞉䞉 = u(0)P
33
t
• u(t) = u(0)P
ึᮇ≧ែ䛸≧ែ㑄⛣☜⋡⾜ิ䛛䜙䠈
ึᮇ≧ែ䛸≧ែ㑄⛣☜⋡⾜ิ䛛䜙
᫬้ t 䛾≧ែ䛜Ỵᐃ䛷䛝䜛
34