2016 年度情報理論レポート問題解答 (締め切り 7 月 21 日) ※ 以下の

2016 年度情報理論レポート問題解答 (締め切り 7 月 21 日)
※ 以下の問題では，実際に log 2 等の計算を実行し，答はすべて数値により得ること．
１．事象系 A と事象系 B の結合確率が下表の様に与えられているとき，以下の各問に答えなさい．
事象系 A
事象系
B
a1
a2
b1
0.36
0.02
b2
0.07
0.55
(1) 周辺確率 P ( a1 ) , P ( a2 ) , P ( b1 ) , P ( b2 ) の値を求めなさい．
P ( a1 ) = 0.43,
P ( b1 ) = 0.38,
P ( a2 ) = 0.57 ,
P ( b2 ) = 0.62.
(2) 条件付き確率 P ( b1 a1 ) , P ( b2 a1 ) , P ( b1 a2 ) , P ( b2 a2 ) の値を求めなさい．
P ( b1 a1 ) =
P ( b1 a2 ) =
P ( a1 , b1 )
P ( a1 )
P ( a2 , b1 )
P ( a2 )
=
=
P ( a1 , b2 ) 0.07
0.36
≈ 0.84, P ( b2 a1 ) =
=
≈ 0.16,
P ( a1 )
0.43
0.43
P ( a2 , b2 ) 0.55
0.02
≈ 0.04, P ( b2 a2 ) =
=
≈ 0.96.
P ( a2 )
0.57
0.57
(3) 条件付き確率 P ( a1 b1 ) , P ( a2 b1 ) , P ( a1 b2 ) , P ( a2 b2 ) の値を求めなさい．
P ( a1 b1 ) =
P ( a1 b2 ) =
P ( a1 , b1 )
P ( b1 )
P ( a1 , b2 )
P ( b2 )
=
=
P ( a2 , b1 ) 0.02
0.36
≈ 0.95, P ( a2 b1 ) =
=
≈ 0.05,
0.38
P ( b1 )
0.38
P ( a2 , b2 ) 0.55
0.07
≈ 0.11, P ( a2 b2 ) =
=
≈ 0.89.
0.62
P ( b2 )
0.62
(4) H ( A ) , H ( B ) の値を求めなさい．
H ( A ) = − P ( a1 ) log 2 P ( a1 ) − P ( a2 ) log 2 P ( a2 ) = −0.43log 2 0.43 − 0.57 log 2 0.57 ≈ 0.99 [ビット] ,
H ( B ) = − P ( b1 ) log 2 P ( b1 ) − P ( b2 ) log 2 P ( b2 ) = −0.38log 2 0.38 − 0.62 log 2 0.62 ≈ 0.96 [ビット] .
(5) H ( B a1 ) , H ( B a2 ) , H ( B A ) の値を求めなさい．
また，この問題における H ( B A ) の意味について説明しなさい．
H ( B a1 ) = − P ( b1 a1 ) log 2 P ( b1 a1 ) − P ( b2 a1 ) log 2 P ( b2 a1 ) = −
0.36
0.36 0.07
0.07
−
≈ 0.64 [ビット] ,
log 2
log 2
0.43
0.43 0.43
0.43
0.02
0.02 0.55
0.55
−
≈ 0.22 [ビット] ,
H ( B a2 ) = − P ( b1 a2 ) log 2 P ( b1 a2 ) − P ( b2 a2 ) log 2 P ( b2 a2 ) = −
log 2
log 2
0.57
0.57 0.57
0.57
H ( B A ) = P ( a1 ) H ( B a1 ) + P ( a2 ) H ( B a2 ) ≈ 0.40 [ビット] .
H ( B | A) は‘事象 A ’について知っている場合の‘事象 B ’に関する曖昧度(予測し難さ)を意味する．
(6) H ( A b1 ) , H ( A b2 ) , H ( A B ) の値を求めなさい．
また，この問題における H ( A B ) の意味について説明しなさい．
H ( A b1 ) = − P ( a1 b1 ) log 2 P ( a1 b1 ) − P ( a2 b1 ) log 2 P ( a2 b1 ) = −
0.36
0.36 0.02
0.02
log 2
−
log 2
≈ 0.30 [ビット] ,
0.38
0.38 0.38
0.38
0.07
0.07 0.55
0.55
H ( A b2 ) = − P ( a1 b2 ) log 2 P ( a1 b2 ) − P ( a2 b2 ) log 2 P ( a2 b2 ) = −
log 2
−
log 2
≈ 0.51 [ビット] ,
0.62
0.62 0.62
0.62
H ( A B ) = P ( b1 ) H ( A b1 ) + P ( b2 ) H ( A b2 ) ≈ 0.43 [ビット] .
H ( A | B ) は‘事象 B ’について知っている場合の‘事象 A ’に関する曖昧度(予測し難さ)を意味する．
(7) H ( A, B ) の値を定義に従って求めなさい．
H ( A, B ) = − P ( a1 , b1 ) log 2 P ( a1 , b1 ) − P ( a1 , b2 ) log 2 P ( a1 , b2 ) − P ( a2 , b1 ) log 2 P ( a2 , b1 ) − P ( a2 , b2 ) log 2 P ( a2 , b2 ) ,
= −0.36 log 2 0.36 − 0.07 log 2 0.07 − 0.02 log 2 0.02 − 0.55log 2 0.55
≈ 1.4 [ビット] .
(8) I ( A; B ) の値を求め，この問題における意味について説明しなさい．
I ( A; B ) = H ( A ) − H ( A B ) = H ( B ) − H ( B A ) ≈ 0.56 [ビット] .
相互情報量 I ( A; B) は‘事象 A ’と‘事象 B ’との間の相関(関連)の強さを表す．
2．ある地方の天気を調べたところ，直前の連続する 2 日間の天気に依存して，下表の確率で天気が
変化することが判った．
天気
直
前
2
日
間
の
天
気
晴
雨
晴晴
0.10
0.90
晴雨
0.30
0.70
雨晴
0.80
0.20
雨雨
0.90
0.10
例えば，天気が“晴”
，
“雨”である確率は，直前の連続する 2 日間の天気が“晴雨”であった
(
)
場合，それぞれ P 晴晴雨 = 0.30, P (雨晴雨 ) = 0.70 （遷移確率という）である．
このことを，
“晴雨”という状態にある情報源（マルコフ情報源という）が，
確率 0.30 で“晴”を出力し，状態“雨晴“へ遷移
確率 0.70 で“雨”を出力し，状態“雨雨“へ遷移
と解釈しよう．
(1) 4 つの状態間の状態遷移図を描きなさい．
晴/0.10
晴晴
雨/0.90 晴雨
晴/0.30
晴/0.80
雨晴
雨/0.2
晴/0.90
雨/0.70
雨雨
雨/0.10
次に，情報源がそれぞれの状態にある定常確率 P ( 晴晴 ) , P ( 晴雨 ) , P (雨晴 ) , P (雨雨 ) を求めよう．
例えば，情報源が状態“晴晴”にある為には，
状態“晴晴”から確率 0.10 で“晴”を出力
状態“雨晴”から確率 0.80 で“晴”を出力
すればよい．このことを式で表すと，以下が得られる．
P ( 晴晴 ) = 0.10 × P ( 晴晴 ) + 0.80 × P (雨晴 )
(2) 定常確率間の残りの 3 つの関係式を求めなさい．
P ( 晴雨 ) = 0.90 × P ( 晴晴 ) + 0.20 × P (雨晴 ) ,
P (雨晴 ) = 0.30 × P ( 晴雨 ) + 0.90 × P (雨雨 ) ,
P (雨雨 ) = 0.70 × P ( 晴雨 ) + 0.10 × P (雨雨 ) .
(3) 定常確率間の合計 4 つの関係式は，それぞれ独立ではない．
そこで，それらから 3 つを選び，
P ( 晴晴 ) + P ( 晴雨 ) + P (雨晴 ) + P (雨雨 ) = 1
と連立することにより，4 つの定常確率を小数第 3 位まですべて求めなさい．
(2)の 3 つの式と上式を連立させて解くと，
P ( 晴晴 ) ≈ 0.242, P ( 晴雨 ) ≈ 0.273, P (雨晴 ) ≈ 0.273, P (雨雨 ) ≈ 0.212.
(4) 次の 4 つのエントロピーを求めなさい．
(
)
(
)
(
)
H 天気晴晴 = − P 晴晴晴 log 2 P 晴晴晴 − P (雨晴晴 ) log 2 P (雨晴晴 ) ,
(
)
= −0.10 log 2 0.10 − 0.90 log 2 0.90 ≈ 0.47 ビット/情報源記号  ,
(
)
(
)
H 天気晴雨 = − P 晴晴雨 log 2 P 晴晴雨 − P (雨晴雨 ) log 2 P (雨晴雨 ) ,
(
)
= −0.30 log 2 0.30 − 0.70 log 2 0.70 ≈ 0.88 ビット/情報源記号  ,
(
)
(
)
H 天気雨晴 = − P 晴雨晴 log 2 P 晴雨晴 − P (雨雨晴 ) log 2 P (雨雨晴 ) ,
(
)
= −0.80 log 2 0.80 − 0.20 log 2 0.20 ≈ 0.72 ビット/情報源記号  ,
(
)
(
)
H 天気雨雨 = − P 晴雨雨 log 2 P 晴雨雨 − P (雨雨雨 ) log 2 P (雨雨雨 ) ,
= −0.90 log 2 0.90 − 0.10 log 2 0.10 ≈ 0.47 ビット/情報源記号  .
(5) (3), (4) の結果を用いて，この情報源のエントロピー(3 日目の天気の予測し難さ)： H Markov ( 天気 )
を求めなさい．
(
)
(
H Markov ( 天気 ) = P ( 晴晴 ) H 天気晴晴 + P ( 晴雨 ) H 天気晴雨
(
)
(
)
)
+ P (雨晴 ) H 天気雨晴 + P (雨雨 ) H 天気雨雨 ,
≈ 0.65 ビット/情報源記号  .
(6) 表の遷移確率と(3)で求めた定常確率から，次のように 3 日目の天気の確率が得られる．
P ( 晴) =

P ( 晴,以前2日間の天気 ) ,

P 晴以前2日間の天気 P ( 以前2日間の天気 ) ,
以前2日間の天気
=
以前2日間の天気
(
(
)
)
(
)
(
)
(
)
= P 晴晴晴 P ( 晴晴 ) + P 晴晴雨 P ( 晴雨 ) + P 晴雨晴 P (雨晴 ) + P 晴雨雨 P (雨雨 ) .
P (雨 ) = P (雨晴晴 ) P ( 晴晴 ) + P (雨晴雨 ) P ( 晴雨 ) + P (雨雨晴 ) P (雨晴 ) + P (雨雨雨 ) P (雨雨 ) .
これらの値を用いて，情報源を‘独立生起情報源’と見なした場合のエントロピー(3 日目の天気の
予測し難さ)：
H memoryless ( 天気 ) = − P ( 晴 ) log 2 P ( 晴 ) − P (雨 ) log 2 P (雨 ) ,
の値を求めなさい．また， H memoryless ( 天気 ) が H Markov ( 天気 ) より大きい理由について説明しなさい．
(答)
P ( 晴 ) = P ( 晴晴晴 ) P ( 晴晴 ) + P ( 晴晴雨 ) P ( 晴雨 ) + P ( 晴雨晴 ) P (雨晴 ) + P ( 晴雨雨 ) P (雨雨 ) ≈ 0.515.
P (雨 ) = P (雨晴晴 ) P ( 晴晴 ) + P (雨晴雨 ) P ( 晴雨 ) + P (雨雨晴 ) P (雨晴 ) + P (雨雨雨 ) P (雨雨 ) ≈ 0.485.
H memoryless ( 天気 ) = −0.515log 2 0.515 − 0.484 log 2 0.484,
≈ 0.999 ビット/情報源記号  ,
マルコフ情報源では，過去に出力された記号に依存して次に出力される記号が決定されるので，
どの記号が出力されるかについて予測が立てやすい．
従って，次の出力が過去の出力の履歴に依存せず，予測の立てにくい独立生起情報源に比べて，
マルコフ情報源のエントロピーは小さい．
3．情報源記号 0 と1 の発生確率が，それぞれ 0.7, 0.3 の 2 元独立生起情報源 S がある．
(1) 2 元ハフマン符号の平均符号長 L1 を求めなさい．
(2) この情報源からの出力を 2 つずつまとめた 4 種類の通報を，
2 元ハフマン符号で符号化しなさい．
また，1 情報源記号あたりの平均符号長 L2 を求めなさい．
(3) この情報源からの出力を 3 つずつまとめた 8 種類の通報を，
2 元ハフマン符号で符号化しなさい．
また，1 情報源記号あたりの平均符号長 L3 を求めなさい．
(4) 平均符号長 L1 , L2 , L3 と情報源のエントロピー H ( S ) との大小関係について述べなさい．
(1) 情報源記号 0 と 1 のそれぞれに，符号語 0 または 1 を割り当てれば良いので，平均符号長は
以下の通りである．
符号語
0
(1.0)
1
0(0.7)
0
1(0.3)
1
L1 = 1× 0.7 + 1× 0.3 = 1[ビット/情報源記号]
(2) 情報源からの出力を 2 つずつまとめた，4 種類の通報による事象系は，
01
10
11 
 00


 0.49 0.21 0.21 0.09 
符号語
0
0
(1.0)
1
(0.51)
0
1
(0.3)
1
00(0.49)
0
01(0.21)
10
10(0.21)
110
11(0.09)
111
1 情報源記号あたりの平均符号長 L2 は，
L2 = {1× 0.49 + 2 × 0.21 + 3 × ( 0.21 + 0.09 )} ÷ 2 ≈ 0.91[ビット/情報源記号 ]
(3) 情報源からの出力を 3 つずつまとめた，8 種類の通報による事象系は，
001
010
100
011
101
110
111 
 000


 0.343 0.147 0.147 0.147 0.063 0.063 0.063 0.027 
符号語
0
0
0
(0.637)
0
1
(1.0)
(0.294) 1
1
(0.363)
1
(0.216)
0
0
(0.126) 1
0
1
(0.090) 1
000(0.343)
00
001(0.147)
10
010(0.147)
010
100(0.147)
011
011(0.063)
1100
101(0.063)
1101
110(0.063)
1110
111(0.027)
1111
1 情報源記号あたりの平均符号長 L3 は，
L3 = {2 × ( 0.343 + 0.147 ) + 3 × 0.147 × 2 + 4 × ( 0.063 × 3 + 0.027 )} ÷ 3 ≈ 0.91 ビット/情報源記号 
(4) 情報源のエントロピー H ( S ) は，
H ( S ) = −0.7 log 2 0.7 − 0.3log 2 0.3 ≈ 0.88 ビット/情報源記号 
従って，平均符号長 L1 , L2 , L3 とエントロピー H ( S ) との関係は H ( S ) < L3 < L2 < L1 である．
情報源からの出力を多くまとめて符号化するほど，1 情報源記号あたりの平均符号長は短くなり，
下限 H ( S ) へ近づく．

Download Report