情報理論

3.エントロピーの性質と各種情報量
1
エントロピーの性質
事象系
, a2
, L
ìï a1
A = ïí
ïï P (a1 ) , P (a 2 ) , L
î
ü
ïï
, P (an )ý
ïï
þ
, 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
2
前のスライドの式を導出するために、
次の2つの事象系を考える。
ìï a1 , a 2 , L
A = ïí
ïï P1 , P2 , L
î
ìï b1 , b2 , L
B = ïí
ïï Q1 , Q2 , L
î
, an ü
ïï
,
ý
, Pn ï
ïþ
, bn ü
ïï
ý,
, Qn ïï
þ
カンマ“,”は
“AND(かつ)”
の意味
n
å
Pi = 1
i= 1
n
å
Qi = 1
i= 1
3
補題1(lemma1)
n
-
å
n
Pi log Pi £ -
i= 1
å
Pi log Qi
i= 1
対数と係数の
違いに注意する。
エントロピー
証明
n
左辺 - 右辺=å Pi log
i= 1
Qi
P
i
Qi
1 n
=
Pi ln
å
ln 2 i = 1
Pi
4
不等式の利用。
ln x £ x - 1
5
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
6
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
7
エントロピー最大となる情報源
定理1
0 £ H (A ) £ log n
証明
(左の不等号)
各 i,(1 £ i £ n ) に対して、次式が成り立つ。
0 £ P (ai ) £ 1
1
\ 1£
P (ai )
\ 0 £ - log P (ai )
よって、
n
H (A ) = -
å
i= 1
P (ai ) log P (ai ) ³ 0
8
(右の不等号)
ìï b1 , b2 , L
B = ïí
ïï Q1 , Q2 , L
î
, bn ü
ïï
ý=
, Qn ïï
þ
ìï b1 , b2 , 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
9
定理1より、全ての記号が均等に現れる情報源が最大の
エントロピー(1記号あたりの平均情報量)を持つ。
しかし、実世界のアルファベットなどは、均等に現れない。
実世界の文章には、その分の冗長性が含まれている。
(実は、人間の理解においてある程度の冗長性があった方
がよい。)
ある情報形態に対して、同じ情報量を持つより小さい
(短い)情報表現を得ることを圧縮という。圧縮からもと
の情報形態を得ることを解凍という。
10
練習
次の事象系のエントロピー(平均情報量)を求めよ。
(1)
ìï a1 , a 2 , a 3 , a 4 ü
ïï
ï
A= í
ý
ïï 0 , 0 , 1 , 0 ïï
î
þ
ìï b1 , b2
ïï
B = í1
1
ïï
,
ïî 8
8
, b3
,
1
4
, b4 ü
ïï
ï
1ý
ïï
,
2 ïþ
ìï c1 , c2 , c3 , c4 ü
ïï
ïï
ï
C = í1
1
1
1ý
ïï
ïï
,
,
,
ïî 4
4
4
4 ïþ
11
各種情報量
複数の事象系が互いに関係している場合に、それぞれの事象
系に関する様々なエントロピー(平均情報量)が定義できる。
• 条件付きエントロピー
• 結合エントロピー
• 相互情報量
条件付き確率に基づい
た平均情報量。
結合確率に基づいた平
均情報量。
事象系同士の(情報量としての)関わりを表す。エントロピー、
条件付きエントロピー、結合エントロピーにより定義される。
これらの情報量を例題を通じて調べたのちに、定義する。
12
例題
次のようなゲームを考える。
サイコロゲーム:
「甲と乙がサイコロを振り合って、サイコロの目の大き
い方が勝ち」
この勝ち負けに関する情報を2つの事象系としてとらえる。
13
サイコロゲームの勝敗表
サイコロゲーム:「甲と乙がサイコロを振り合って、サイコロの目
の大きい方が勝ち」
甲
甲 1
2
3
4
5
6
乙
○:勝ち
1
△
○
○
○
○
○ △:引分け
×:負け
2
×
○
○
○
○
△
3
×
×
△
4
×
×
×
5
×
×
6
×
×
○
○
○
△
○
○
×
×
△
○
×
×
×
△
14
サイコロゲームより次の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 ïþ
15
補足1:条件付き確率
ある条件の下で事象がおこる確率を条件付き確率といい、
P (事象 | 条件) と表す。
甲 1
1
2
3
4
5
6
甲が3を出している
条件の下で、
甲が勝つ確率。
○
2
○
3
△
4
×
5
×
6
×
2
P (○ | 3) =
6
1
P (△ | 3) =
6
3
P (× | 3) =
6
16
補足2:同時確率(結合確率)
2つ以上の事象が同時におこる確率を同時確率(結合確率)という。
P (事象1, 事象2 ) のように表す。
甲が3を出してしかも
勝つ確率。
“And”の意味
甲 1
2
3
1
○
2
○
3
4
5
6
2
P (○,3) =
36
分母に注意する。
4
5
6
17
補足3:独立な事象における同時確率(結合確率)
定義
事象1と事象2の同時確率がそれぞれの事象の確率の積
で表わされるとき、事象1と事象2は独立であるという。
P (事象1, 事象2 ) = P (事象1)gP (事象2)
事象系1と事象系2の任意の2つの事象が独立のときに、
事象系1と事象系2は独立である。
甲 1 2 3 4 5 6 事象系C:乙のサイコロの目
乙
に関する事象系
1
2
3
4
5
6
ìï 乙=1 , 乙=2 , 乙=3 , 乙=4 , 乙=5 , 乙=6ü
ïï
ïï
ï
C = í1
ý
1
1
1
1
1
ïï
ïï
,
,
,
,
,
ïî 6
ïþ
6
6
6
6
6
P (甲=3, 乙=2 ) = P (甲=3)P (乙=2)
1 1
g
6 6
1
=
36
=
事象系Bと事象系Cは独立。
18
問題
確率を計算することにより、
事象系Aと事象系Bが独立でないことを示せ。
19
サイコロゲームにおける様々なエントロピー
甲の勝負けの情報
甲の出た目の情報
H (A ) = 1.48
H (B ) = 2.58
H (B | A )
= 2.22
H (A | B )
= 1.12
Aを条件
とするB
の情報量
Bを条件
とするA
の情報量
I (A; B ) = 0.363
H (A, B ) = 3.70
勝ち負けと目の情報の両方
Aの事象から間接的に
20
Bを知る情報量
条件付エントロピー1(条件付エントロピーの定義)
甲の出た目の事象系を条件とする、
甲の勝ち負けの事象系の平均情報量
H (A | b ) = -
å
条件付確率で定義さ
れるエントロピー
P (a | b ) logP (a | b )
aÎ A
H (A | B ) =
å
P ( b )H (A | b )
bÎ B
= -
å
P ( b )å P (a | b ) logP ( a | b )
bÎ 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とB
の共通の情報。
21
甲 1
1
2
3
○
2
○
3
△
4
×
5
×
6
×
4
5
6
条件付エントロピー
は、条件付き確率の
平均の平均として定
義される。
条件を1度固定しエ
ントロピーを計算し、
すべての条件で平
均を求める。
H (A | 3) = - P (○|
3) log P (○|
3) - P (△|
3) log P (△|
3) - P (×
|
3) log P (×
|
3)
H (A | B ) = P (1)H (A | 1) + P (2)H (A | 2) + P (3)H (A | 3)
+ P (4)H (A | 4) + P (4)H (A | 4) + P (4)H (A | 4)
22
条件付エントロピー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
甲 1
乙
2
1
○ ○ ○ ○ ○
2
○ ○ ○ ○
3
○ ○ ○
4
○ ○
5
○
3
4
5
6
2
P (3 | ○) =
15
6
H (B | ○) = - P (1|○) log P (1 | ○) - P (2|○) log P (2 | ○) - P (3|○) log P (3 | ○)
- P (4|○) log P (4 | ○) - P (5|○) log P (5 | ○) - P (6|○) log P (6 | ○)
H (B | A ) = P (○)H (B | ○+
) P (△)H (B | △) + P (×)H (B | ×)
24
相互情報量
I (A; B ) = H (A ) - H (A | B ) = H (B ) - H (B | A ) = I (B ; A )
AとBが互いに関係している情報量。
Aを知ることによって、間接的にBに関する情報が得られる。
同様に、Bを知ることによって、間接的にAの情報が得られる。
これらは、等しい。
25
結合エントロピー(同時エントロピー)
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だけの情報量を加えて、
関係する相互情報量を減ずる。
26
各種エントロピーの計算。
まず、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
27
次に、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
28
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
29
以上より、事象系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
30
今度は、逆に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
31
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
32
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
33
結合エントロピーを求めるためには、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
34
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
35
練習
コインゲームを考える。
「甲と乙がそれぞれコインを投げる。
表より裏が強いとする。」
このゲームを次の2つの事象系としてとらえる。
事象系 (勝負):
「甲の勝負けを表す事象系」
事象系 (裏表):
「甲の出したコインの裏表を表す事象系」
次の各種エントロピーを求めよ。
H (勝負), H (裏表), H (勝負 | 裏表), H (裏表 | 勝負), I (勝負; 裏表)
36
部分的な情報源
サイコロを投げて出た目に従って、以下の2つの情報源を考える。
ìï 1 , 2 , 3 , 4 , 5 , 6 ü
ïï
ïï
ï
B = í1
ý
1
1
1
1
1
ïï
ïï
,
,
,
,
,
ïî 6
6
6
6
6
6 ïþ
ìï 偶数 , 奇数ü
ïï
ïï
ï
D = í1
1 ý
ïï
ïï
,
ïîï 2
2 ïþ
ï
37
6
1
H (B ) = å
log 6 = log 6 ; 2.58[bit / 記号]
i= 1 6
2
1
H (D ) = å log 2 = log 2 = 1[bit / 記号]
i= 1 2
1
1
1
H (B | 偶数) = 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 (B | 奇数) = 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 (B | D ) = log 3 + log 3 = log 3 ; 1.58[bit / 記号 ]
2
2
I (B ; D ) = H (B ) - H (B | D ) = 1[bit / 記号]
Dのエントロピーと等しい。
38
I (D ; B ) = H (D ) - H ( D | B )
\ H (D | B ) = H (D ) - I (D; B ) = 0
Bを条件とすれば、Dに関する残された情報が無いこ
とを意味する。すなわち、サイコロの目がわかれば、
偶数か奇数かもわかる。
H (D | 1) = -1442
1log1
- 042log
443144
44403 = 0
奇数
偶数
M
H (D | 6) = -144
042log
- 1log1
444031442
443 = 0
奇数
\ H (D | B ) =
å
aÎ B
偶数
P (a )H (D | a ) = 0
39
練習
試行T「トランプから1枚カードを引く」
この試行Tを次の2つの事象系としてとらえる。
事象系 (数):
「引いたカードの数」
事象系 (絵札):
「引いたカードが絵札かどうか」
次の各種エントロピーを求めよ。
H (数), H (絵札), H (数 | 絵札), H ( 絵札 | 数), I ( 数; 絵札)
40
独立な情報源
サイコロを投げて得られる情報源と、コインを投げて得られる情報源
を考える。
ìï 1 , 2 , 3 , 4 , 5 , 6 ü
ïï
ïï
ï
B = í1
1
1
1
1
1ý
ïï
ïï
,
,
,
,
,
ïî 6
6
6
6
6
6 ïþ
ìï 表 , 裏ü
ïï
ïï
ï
E = í1
1 ý
ïï
ïï
,
ïîï 2
2 ïþ
ï
41
6
1
H (B ) = å
log 6 = log 6 ; 2.58[bit / 記号]
i= 1 6
2
1
H (E ) = å log 2 = log 2 = 1[bit / 記号]
i= 1 2
6
1
H (B | 表) = å
log 6 = log 6
i= 1 6
6
1
H (B | 裏) = å
log 6 = log 6
i= 1 6
1
1
H (B | E ) = log 6 + log 6 = log 6
2
2
I (B ; E ) = H (B ) - H (B | E ) = 0[bit / 記号]
コインの試行からは、サイコロに関する情報
が得られないことを意味する。
42
I (E ; B ) = H (E ) - H ( E | B )
H (E | B ) = H (E ) - I (E ; B ) = log 2 = 1[bit / 記号]
Bを条件としても、Eに関する平均情報量に変化がな
い。
43
練習
試行T「トランプから1枚カードを引く」
この試行Tを次の2つの事象系としてとらえる。
事象系 (数):
「引いたカードの数」
事象系 (マーク):
「引いたカードがマーク」
次の各種エントロピーを求めよ。
H (数), H (マーク), H (数| マーク), H (マーク | 数), I ( 数; マーク)
44