平均情報量の性質(3章)
1
(参考)画像の情報量
4×4の画素数を持ち、個々の画素が16階調の輝度値
を持つ画の情報量を考える。
16
16
16
16
3
16
1
このとき、各画素がある輝度値を持つ確率は、16 であ
る。よって、この画像が持つ情報量I(画)は次式で表され
る。
16
I (画) =å i(画素j ) = 16 ´ log 16 = 64[bit ] = 8[byte ]
j=1
2
前のスライドでは、輝度値が全ての画素で確率が均等で
あると仮定してあった。
実は、風景画、人物画等では、画素における輝度値の出
現確率が一様でないことがある。
このような場合、より少ない情報量しか持たない。
すなわち、確率が一様でない場合には、1画素あたりの平
均情報量は、一様な場合より小さくなる。
3
練習
(1)
256 ´ 256
の画素で、各画素が
像の自己情報量を求めよ。
16
階調の白黒画
(1)
256 ´ 256
の画素のカラー画像の自己情報量を求
めよ。ただし、1画素は赤、緑、青(RGB)の各色で表され、
各色はそれぞれ16階調で表されるものとする。
4
1記号あたりの平均情報量例
A = {a, b, c, L , z }
アルファベット
個々の記号の出現確率を考えよう。
記号
a Î A =の出現する確率を P ( a ) =と書く。
例えば、
辞書
に対して、
P (a ) =:a
P (b) =: b
の現れる確率
の現れる確率
このとき、一般の英文において、各記号の出現
確率は異なる。すなわち、以下である。
1
P (a ) ¹ P (b) ¹ L ¹ P (z ) ¹
26
5
A = {a, b, c, L , z } は一種
もちろん、アルファベット
の情報源とみなすことができる。
A
n 個の文字からなる英文
S = s1s2 L sn
の情報量 I (S ) を考えよう。
I (S ) は各記号が S に出現する自己情報量の総和である。
n
今、
の
I (S ) =
å
i (si )
i= 1
一方、
の情報量の期待値
の積である。
H (A =
)
S
I (S ) は、 n とエントロピー
I (S ) = nH (A )
6
以上のようなことを踏まえると、アルファベットの(1記号あたりの)
平均情報量(エントロピー)が以下の式で表されることが確認できる。
z
H (A ) =
å
{P (a ) ´ i(a )}
a=a
= P (a )i (a ) + P (b)i (b) + L + P (z )i (z )
= - P (a ) log P (a ) - P (b) log P (b) - L - P (z ) log P (z )
z
= -
å
P (a ) log P ( a )
[bit/記号]
a=a
A
したがって、英文長は情報源
のエントロピー
を”単位”とした情報量で表される。
H (A =
)
7
練習
次の事象系のエントロピー(平均情報量)を求めよ。
(1)
ìï a1 , a 2 , a 3 ü
ïï
ïï
ï
A= í1
2
2ý
ïï
ïï
,
,
ïî 5
5
5 ïþ
(2)
(3)
ìï b1 , b2 , b3 , b4 ü
ïï
ïï
ï
B = í1
ý
2
2
5
ïï
ïï
,
,
,
ïî 9
9
9
9 ïþ
C
「甲君はある1時間中、10分を休憩、20分を教科書読み、
30分は計算するとする。この1時間中のある適当な時刻で
の甲君の行動から構成される事象系」
8
エントロピーの性質
事象系
, a1
, L
ìï a1
A = ïí
ïï P (a1 ) , P (a1 ) , L
î
ü
ïï
ý
, P (a1 )ïï
þ
, an
のエントロピーは次式で表される。
H (A ) = -
å
n
P (a ) log P (a ) = -
aÎ A
å
P (ai ) log P (ai )
k= 1
このとき、次式が成り立つ。
0 £ H (A ) £ log n
ある事象が必ず起きるとき。
a1 = 1, a2 = L = an = 0
全ての事象が等確率のとき。
1
a1 = a 2 = L = a n =
n
9
前のスライドの式を導出するために、
次の2つの事象系を考える。
ìï a1 , a1 , L
A = ïí
ïï P1 , P2 , L
î
, an ü
ïï n
, å Pi = 1
ý
, Pn ï i = 1
ïþ
ìï b1 , b1 , L
B = ïí
ïï Q1 , Q2 , L
î
, bn ü
ïï n
ý , å Qi = 1
, Qn ïï i = 1
þ
10
補題1(lemma1)
n
-
å
n
Pi log Pi £ -
i= 1
証明
å
i= 1
Pi log Qi
i= 1
エントロピー
n
å
別の事象系の自己情報量を
元の事象系の確率で平均す
る。
Qi
Qi
1 n
Pi log
=
Pi ln
å
Pi
ln 2 i = 1
Pi
不等式の利用。
ln x £ x - 1
11
12
n
å
i= 1
Qi
Qi
1 n
Pi log
=
Pi ln
å
Pi
ln 2 i = 1
Pi
æQi
ö÷
1 n
£
Pi çç - 1÷
å
÷
ln 2 i = 1 çè Pi
ø÷
1 n
=
(Qi - Pi )
å
ln 2 i = 1
æ
ö
÷
ç
n
÷
1 çç n
÷
=
ççå Qi - å Pi ÷
÷
÷
ln 2 ç{
i= 1
i
=
1
{ ÷
÷
çè
ø
1
この変形で、
Qi
x=
Pi
n
として 回不等式を
利用いる。
1
= 0
13
n
Qi
åi = 1 Pi log P i £ 0
n æ
ö
1
1
÷
\ å ççPi log - Pi log ÷
£ 0
÷
ç
Pi
Qi ÷
ø
i= 1 è
n
\ -
å
i= 1
n
\ -
å
i= 1
n
(Pi log Pi ) +
å
(Pi log Qi ) £ 0
i= 1
n
(Pi log Pi ) £ -
å
(Pi log Qi )
i= 1
QED
14
エントロピー最大となる情報源
定理1
0 £ H (A ) £ log n
証明
(左の不等号)
0 £ P (ai ) £ 1
(1 £ i £ n ) なので、
n
H (A ) = -
å
P (ai ) log P (ai ) ³ 0
i= 1
15
(右の不等号)
ìï b1 , b1 , L
B = ïí
ïï Q1 , Q2 , L
î
, bn ü
ï
ïý
=
, Qn ïï
þ
ìï b1 , b1 , L
ïíï
ïï 1 , 1 , L
ïî n
n
, bn ü
ïï
ïý
1ï
,
ï
n ïþ
とおく。補題1より、
n
-
å
n
Pi log Pi
å
£ -
i= 1
Pi log Qi
i= 1
n
=
å
Pi log n
i= 1
æn
ö÷
= log n ççå Pi ÷
çè i = 1 ø÷
= log n
QED
16
練習
次の事象系のエントロピー(平均情報量)を求めよ。
(1)
ìï a1 , a 2 , a 3 , a 4 ü
ïï
ï
A= í
ý
0
,
0
,
1
,
0
ïï
ïï
î
þ
ìï a '1 , a '2 , a '3 , a '4 ü
ïï
ïï
ï
A'= í1
ý
1
1
1
ïï
ïï
,
,
,
ïî 8
8
4
2 ïþ
ìï a ''1 , a ''2 , a ''3 , a '' 4 ü
ïï
ïï
ï
A '' = í 1
ý
1
1
1
ïï
ïï
,
,
,
ïî 4
4
4
4 ïþ
17
様々なエントロピー
複数の事象系が互いに関係している場合に、それぞれの事象
系に関する様々なエントロピー(平均情報量)が定義できる。
次のようなゲームを考える。
サイコロゲーム:
「甲と乙がサイコロを振り合って、サイコロの目の大き
い方が勝ち」
この勝ち負けに関する情報を2つの事象としてとらえる。
18
サイコロゲームの勝敗表
サイコロゲーム:「甲と乙がサイコロを振り合って、サイコロの目
の大きい方が勝ち」
甲
甲 1
2
3
4
5
6
乙
○:勝ち
1
△
○
○
○
○
○ △:引分け
×:負け
2
×
○
○
○
○
△
3
×
×
△
4
×
×
×
5
×
×
6
×
×
○
○
○
△
○
○
×
×
△
○
×
×
×
△
19
サイコロゲームを2つの二つの事象系として捕らえる。
事象系A:甲の勝負に関する事象系
ìï ○ , △ , × ü
ïï
ïï
ï
A = í 15
ý
6
15
ïï
ïï
,
,
ïîï 36
36
36 ïïþ
この2つの事象系
は独立ではなく、
互いに密接に関
係している。
事象系B:甲のサイコロの目に関する事象系
ìï 1 , 2 , 3 , 4 , 5 , 6 ü
ïï
ïï
ïý
B = í1
1
1
1
1
1ï
ïï
,
,
,
,
,
ï
ïî 6
6
6
6
6
6 ïþ
20
サイコロゲームにおける様々なエントロピー
甲の勝負けの情報
H (A ) = 1.483
甲の出た目の情報
H (B ) = 2.584
H (B | A )
= 2.221
H (A | B )
= 1.12
Aを条件
とするB
の情報量
Bを条件
とするA
の情報量
I (A; B ) = 0.363
H (A, B ) = 3.70
勝ち負けと目の情報の両方
Aの事象から間接的に
21
Bを知る情報量
条件付エントロピー1
甲の出た目の事象系を条件とする、
甲の勝ち負けの事象系の平均情報量
H (A | b ) = -
å
条件付確率で定義さ
れるエントロピー
P (a | b ) logP (a | b )
aÎ A
H (A | B ) =
å
P ( b )H (A | b )
bÎ B
= -
å
bÎ B
= -
P ( b )å P (a | b ) logP ( a | b )
aÎ A
å
P ( b )P (a | b ) logP ( a | b )
å
P (a , b ) logP ( a | b )
a Î A ,b Î B
= -
a Î A ,b Î B
Bを条件とすることによって、情報源Aの情報量がBと
関係している分減少する。したがって、減少分は、AとB22
の共通の情報。
条件付エントロピー2
甲の勝ち負けの事象系を条件とする甲の目の事象系の平均情報量
H (B | a ) = -
å
P (b | a ) logP (b | a )
bÎ B
H (B | A ) =
å
P (a )H (B | a )
aÎ A
= -
å
aÎ A
= -
P (a )å P ( b | a ) logP ( b | a )
bÎ B
å
P ( b )P ( b | a ) logP ( b | a )
å
P (a , b ) logP ( b | a )
a Î A ,b Î B
= -
a Î A ,b Î B
Aを条件とすることによって、情報源Bの
情報量がAと関係している分減少する。
したがって、減少分は、AとBの共通の
情報。
23
相互情報量
I (A; B ) = H (A ) - H (A | B ) = H (B ) - H (B | A ) = I (B ; A )
AとBが互いに関係している情報量。
Aを知ることによって、間接的にBに関する情報が得られる。
同様に、Bを知ることによって、間接的にAの情報が得られる。
これらは、等しい。
24
結合エントロピー
H (A, B ) = -
å
P (a , b ) logP (a , b ) = H (A ) + H (B ) - I (A; B )
a Î A ,b Î B
と b が同時に起こる確率。
結合確率。
a
å
P (a , b ) = 1
a Î A ,b Î B
AとBがのすべての情報量。
Aだけの情報量と、Bだけの情報量を加えて、
関係する相互情報量を減ずる。
25
まず、2つの事象系のエントロピーを求める。
H (A ) = -
å
P (a ) log P (a )
aÎ A
=
=
=
;
15
36
6
36 15
36
log
+
log
+
log
36
15 36
6
36
15
5
1
(log 4 + log 3 - log 5) + (log 2 + log 3)
6
6
11
5
+ log 3 - log 5
6
6
(1.833) + (1.585) - (1.93)
= 1.4833 L
H (B ) = -
å
P ( b ) log P ( b )
bÎ B
1
1
1
1
1
1
= log 6 + log 6 + log 6 + log 6 + log 6 + log 6
6
6
6
6
6
6
= log 6
; 2.5849 L
26
次に、Bの事象系において、事象が既知である場合の個々の
エントロピーを求める。
H (A | 1) = -
å
P (a | 1) log P (a | 1)
aÎ A
= - P (○ | 1) log P (○ | 1) - P (△ | 1) log P (△ | 1) - P (× | 1)P (× | 1)
= 0+
1
5
6
log 6 + log
6
6
5
H (A | 2) = -
å
P (a | 2) log P ( a | 2)
aÎ A
=
1
1
4
6
log 6 + log 6 + log
6
6
6
4
H (A | 3) = -
å
P ( a | 3) log P ( a | 3)
aÎ A
2
6 1
3
6
= log + log 6 + log
6
2 6
6
3
27
H (A | 4) = -
å
P (a | 4) log P ( a | 4)
aÎ A
=
3
6 1
2
6
log + log 6 + log
6
3 6
6
2
H (A | 5) = -
å
P (a | 5) log P ( a | 5)
aÎ A
=
4
6 1
1
log + log 6 + log 6
6
4 6
6
H (A | 6) = -
å
P (a | 6) log P ( a | 6)
aÎ A
=
5
6 1
log + log 6 + 0
6
5 6
28
以上より、事象系Bを条件とする、条件付エントロピー H (A | B )
が求められる。
H (A | B ) =
å
P ( b )H (A | b )
bÎ B
=
=
=
=
=
;
1
1
1
1
1
1
H (A | 1) + H (A | 2) + H (A | 3) + H (A | 4) + H (A | 5) + H (A | 6)
6
6
6
6
6
6
1 1
5
6
1 2
4
6
1 3
6 1
2
6
( log 6 + log ) + ( log 6 + log ) + ( log + log 6 + log )
3 6
6
5
3 6
6
4
3 6
3 6
6
2
1
5
2
1
1
(3 log 6 - log 5 - log 4 - log 3 - log 2)
3
6
3
2
3
5
1
5
log 6 log 5 - log 3 18
6
9
4 5
5
+ log 3 log 5
9 6
18
(0.444) + (1.321) - (0.645)
= 1.12
29
今度は、逆にAの事象系において、事象が既知である場合の個々の
エントロピーを求める。
H (B | ○) = -
å
P ( b | ○) log P ( b | ○)
bÎ B
= - P (1 | ○) log P (1 | ○) - P (2 | ○) log P (2 | ○) - L - P (6 | ○) log P (6 | ○)
=
=
=
=
1
2
15
3
15
0+
log 15 +
log
+
log
+
15
15
2
15
3
2
3
4
log 15 log 2 log 3 log 4 15
15
15
12
10
10
log 3 +
log 5 15
15
15
4
2
2
log 3 + log 5 5
3
3
4
15
5
15
log
+
log
15
4
15
5
5
log 5
15
30
H (B | △) = -
å
P ( b | △) log P ( b | △)
bÎ B
1
log 6
6
= log 6
= 6´
H (B | ×) = -
å
P ( b | ×) log P ( b|×)
bÎ B
=
4
2
2
log 3 + log 5 5
3
3
以上より、事象系Aを条件とする、条件付エントロピー
が求められる。
H (B | A ) =
å
H (B | A )
P (a )H (B | a )
aÎ A
30 4
2
2
1
=
( log 3 + log 5 - ) + log 6
36 5
3
3
6
5
5
7
= log 3 + log 5 6
9
18
; (1.321) + (1.290) - (0.389)
= 2.221
31
H (A ) - H (A | B )
æ11
5
ö
÷
ç
= ç + log 3 - log 5÷è6
ø
6
25 1
5
=
+ log 3 - log 5
18 6
9
H (B ) - H (B | A )
æ4 5
5
ö
çç + log 3 log 5÷
÷
è9 6
ø
18
æ5
5
7÷
ö
= log 6 - çç log 3 + log 5 ÷
è6
9
18 ø
25 1
5
=
+ log 3 - log 5
18 6
9
\ I (A ; B ) = H (A ) - H (A | B ) = H (B ) - H ( B | A )
25 1
5
=
+ log 3 - log 5
18 6
9
; (1.389) + (0.264) - (1.290)
= 0.363
32
結合エントロピーを求めるためには、A、Bの積の事象系を考え
ても良い。サイコロゲームの勝敗表より以下の事象系が得られ
る。
ìï (○, 1) , (△, 1) , ( ×, 1) ,
ïï
(A , B ) = í
1
5
ïï 0
,
,
,
ïïî
36
36
(○, 3) , (△, 3) , ( ×, 3) , (○, 4) ,
(○, 2) , (△, 2) , (×, 2) ,
1
1
4
,
,
36
36
36
(△, 4) , (×, 4) ,
,
2
1
3
3
1
2
,
,
,
,
,
,
36
36
36
36
36
36
(○, 5) , (△, 5) , (×, 5) , (○, 6) , (△, 6) , (×, 6)ü
ïï
ï
ý
4
1
1
5
1
ïï
,
,
,
,
, 0
ïïþ
36
36
36
36
36
33
H (A , B ) = -
å
P (a , b ) logP (a , b )
a Î A ,b Î B
8
4
36 6
36 8
36 10
36
=
log 36 +
log +
log +
log +
log
36
36
2 36
3 36
4 36
5
36
1
1
2
5
=
log 36 - log 2 - log 3 - log 4 log 5
36
9
6
9
18
13 11
5
=
+ log 3 log 5
9
6
18
H ( A , B ) = H (A ) + H (B ) - I (A ; B )
æ11
5
ö
= çç + log 3 - log 5÷÷+ (log 6) è6
ø
6
13 11
5
=
+ log 3 log 5
9
6
18
æ25 1
5
ö
çç + log 3 - log 5÷÷
è18 6
ø
9
34
練習
コインゲームを考える。
「甲と乙がそれぞれコインを投げる。
表より裏が強いとする。」
このゲームを次の2つの事象系としてとらえる。
事象系 (コA):
「甲の勝負けを表す事象系」
事象系 (コB):
「甲の出したコインの裏表を表す事象系」
次の各種エントロピーを求めよ。
H (コ A ), H (コ B ), H (コ A | コ B ), H (コ B | コ A ), I (コ A;コ B )
35
部分的な情報源
サイコロを投げて出た目に従って、以下の2つの情報源を考える。
ìï 1 , 2 , 3 , 4 , 5 , 6 ü
ïï
ïï
ïý
A = í1
1
1
1
1
1ï
ïï
,
,
,
,
,
ï
ïî 6
6
6
6
6
6 ïþ
ìï 偶数 , 奇数ü
ïï
ïï
ï
B = í1
1 ý
ïï
ïï
,
ïîï 2
2 ïþ
ï
36
6
1
H (A ) = å
log 6 = log 6 ; 2.58[bit ]
i= 1 6
2
1
H (B ) = å
log 2 = log 2 = 1[bit ]
i= 1 2
1
1
1
H (A | 偶数) = 0{ + log 3 + 0{ + log 3 + 0{ + log 3 = log 3
3 42 443 3 14
3 42 443 5 14
3 42 443
1
14
2
4
6
1
1
1
H (A | 奇数) = log 3 + 0{ + log 3 + 0{ + log 3 + 0{ = log 3
3 42 443 2 14
3 42 443 4 14
3 42 443 6
14
1
3
5
1
1
H (A | B ) = log 3 + log 3 = log 3 ; 1.58[bit ]
2
2
I (A; B ) = H (A ) - H (A | B ) = 1[bit ]
Bのエントロピーと等しい。
37
I (B ; A ) = H (B ) - H ( B | A )
\ H (B | A ) = H (B ) - I (B ; A ) = 0
Aを条件とすれば、Bに関する残された情報が無いこ
とを意味する。すなわち、サイコロの目がわかれば、
偶数か奇数かもわかる。
H (B | 1) = -144
142log
042log
44413 -144
44403 = 0
奇数
偶数
M
H (B | 6) = -144
042log
142log
44403 -144
44413 = 0
奇数
\ H (B | A ) =
å
aÎ A
偶数
P (a )H (B | a ) = 0
38
練習
試行T「トランプから1枚カードを引く」
この試行Tを次の2つの事象系としてとらえる。
事象系 (TA):
「引いたカードの数」
事象系 (TB):
「引いたカードが絵札かどうか」
次の各種エントロピーを求めよ。
H (T A ), H (T B ), H (T A | T B ), H (T B | T A ), I (T A;T B )
39
独立な情報源
サイコロを投げて得られる情報源と、コインを投げて得られる情報源
を考える。
ìï 1 , 2 , 3 , 4 , 5 , 6 ü
ïï
ïï
ï
A = í1
1
1
1
1
1ý
ïï
ïï
,
,
,
,
,
ïî 6
6
6
6
6
6 ïþ
ìï 表 , 裏ü
ïï
ïï
ï
B = í1
1 ý
ïï
ïï
,
ïîï 2
2 ïþ
ï
40
6
1
H (A ) = å
log 6 = log 6 ; 2.58[bit ]
i= 1 6
2
1
H (B ) = å
log 2 = log 2 = 1[bit ]
i= 1 2
6
1
H (A | 表) = å
log 6 = log 6
i= 1 6
6
1
H (A | 裏) = å
log 6 = log 6
i= 1 6
1
1
H (A | B ) = log 6 + log 6 = log 6
2
2
I (A; B ) = H (A ) - H (A | B ) = 0[bit ]
コインの試行からは、サイコロに関する情報
が得られないことを意味する。
41
I (B ; A ) = H (B ) - H (B | A )
H (B | A ) = H (B ) - I (B ; A ) = log 2 = 1[bit ]
Aを条件としても、Bに関する平均情報量に変化がな
い。
42
ダウンロード

ppt