前回の練習問題
無記憶・非定常な情報源を一つ例示せよ
時刻 t に t 枚のコインを投げるとき,表が出る枚数
以下のマルコフ情報源について,
状態の定常確率分布を求めよ
通報 A, B の定常確率を求めよ
0
A/0.4 A/0.5
B/0.2
1
B/0.5
A/0.8
B/0.6
2
(w0, w1, w2) = (0.1, 0.7, 0.2)
P(A) = 0.7
P(B) = 0.3
1
前回の補足:マルコフ情報源が既約であること
既約(irreducible)マルコフ情報源
任意の状態から任意の状態に遷移可能なマルコフ情報源
厳密には...
時刻 t の状態を変数 Xt で表現するとき,任意の時刻 i, j (i < j)
および任意の状態 si, sj に対し,P(Xj = sj | Xi = si) > 0 であること
無限個の状態を持つマルコフ連鎖では,既約であっても,
P(Xj = sj | Xi = si) → 0 となるケースもある(収束 ≠ 一致)
1.0
0.9
0.9
0.9
0.9
0.1
0.1
0.1
0.1
0.1
2
本日の講義について
「情報量」を定義する
1. 情報源に対し,エントロピーの概念を導入
エントロピー=通報を予想する難しさの定量的指標
エントロピーが大きい ⇔ 予測することが難しい
2.
一個の通報の持つ情報量を定義
情報量=その通報がもたらすエントロピーの減少量
3.
通信路の性能指標となる相互情報量を定義
その通信路を通過する通報の情報量の加重平均
3
記憶のない情報源のエントロピー
以下の通報発生確率を持つ,記憶のない定常情報源S を考える
... a
通報 a1 a2
M
...
pM
確率 p1 p2
情報源 S の一次エントロピー (first-order entropy):
M
H1 ( S )    pi log 2 pi (ビット, bit)
i 1
この項は非負
⇒エントロピーは常に0以上
例1:
コイン投げのエントロピー:表,裏とも確率 1/2...M = 2, p1=p2=0.5
H1 ( S )  0.5 log 0.5  0.5 log 0.5   log(1/ 2)  1 ビット
4
エントロピーの計算例
例2:サイコロの目...コイン投げより,結果予想は難しいはず
通報 1 2 3 4 5 6
確率 1/6 1/6 1/6 1/6 1/6 1/6
1
1 1
1
1
1
H1 ( S )   log  log ...  log  2.585 ビット
6
6 6
6
6
6
例3:イカサマ賭博のサイコロ
2
3
4
5
6
通報 1
確率 0.9 0.02 0.02 0.02 0.02 0.02
H1 ( S )  0.9 log 0.9  0.02 log 0.02...  0.02 log 0.02  0.701 ビット
一個の指標で,予測の難しさの大小関係を定義可能
5
予想の難しさとエントロピー:二元情報源の場合
通報が0 または1の,記憶のない二元情報源 S を考える
0, 1 の発生確率が p, 1 – p のとき,
H1 ( S )   p log p  (1  p) log(1  p) ビット
この値をH(p) と表記する(二元エントロピー関数)
p=0.5のとき,
1.0
H(p) は最大値 1 を取る
p が 0, 1 に近づくとき,
H(p)
H(p) は 0 に近づく
0.5
1.0
p
予想のしやすさとエントロピーの
間には,相関関係がある
6
M元情報源の場合
天気...三元情報源
奈良の天気...晴40%, 曇50%, 雨10%とすると,H1(S)=1.361
砂漠の天気...晴90%, 曇9%, 雨1%とすると,H1(S)=0.516
もし,晴,曇,雨の確率が全部 1/3 の場合,
1 1 1 1 1 1
H1 ( S )   log  log  log  log 3  1.58
3 3 3 3 3 3
M元情報源では,M個の通報が等確率で発生するとき,
エントロピーは最大値 log M ビットとなる
エントロピーが最小値を取るのは,ある一つの通報について,
その発生確率が1となる場合
...この場合,通報は,あいまいさなく予測可能
7
拡大情報源について
ブロック化(block):
情報源からの通報を複数個まとめて,一個の通報とみなすこと
M元情報源Sの出力をn個まとめて一つのブロックを構成
⇒ S の n次拡大(n-th order extended)情報源
...通報は Mn 種類: Mn元情報源になる
拡大情報源のエントロピーは?
記憶のない情報源だと,ブロック化しても面白くない
記憶のある情報源のブロック化,が興味深い結果を示す
... 話の順番として,まずは記憶のないケースを議論
8
拡大情報源のエントロピー計算
コイン投げ2回分の通報を,1ブロックにまとめる場合...
通報は {表表, 表裏,裏表,裏裏} の4通り...22元情報源
通報 表表
確率 1/4
表裏
1/4
裏表
1/4
裏裏
1/4
H1(S2)=log 4 = 2 ビット...結果予想は一個の場合の2倍難しい
H1(S2)は,S の通報2個分のエントロピー
⇒ S の通報1個分に換算すると,H1(S2)/2 = 1ビット
H1 ( S n ) / n
lim H1 ( S n ) / n
n
Sの n次 (n-th order)エントロピー.Hn(S)と表記
Sの極限エントロピー.H(S)と表記
9
記憶のない情報源の拡大とエントロピー
S: 0, 1 をそれぞれ確率 0.8, 0.2 で発生する記憶のない情報源
S
S2
0
1
0.8
0.2
H1(S)= –0.8log0.8 – 0.2log0.2 = 0.72
00
01
10
11
0.64
0.16
0.16
0.04
H1(S2)= –0.64log0.64 – 0.16log0.16
–0.16log0.16 – 0.04log0.04 = 1.44
H2(S) = H1(S2)/2 = 1.44/2 = 0.72
この情報源では,任意の n に対して H1(Sn) = 0.72n となる
⇒ Hn(S) = H(S) = 0.72...極限エントロピー=一次エントロピー
10
記憶のない情報源の拡大とエントロピー
定理:任意の無記憶な定常情報源 S に対し,H1(Sn) = nH1(S).
証明:(n = 2の場合を考える)
H1 ( S 2 )     P ( x0 , x1 ) log P ( x0 , x1 )
無記憶だから
x0M x1M
   P ( x0 ) P ( x1 ) log P ( x0 ) P ( x1 )
P(x0, x1) = P(x0)P(x1)
x0 x1
   P ( x0 ) P ( x1 ) log P ( x0 )    P ( x0 ) P ( x1 ) log P ( x1 )
x0 x1
x0 x1
  P ( x0 ) log P ( x0 ) P ( x1 )   P ( x1 ) log P ( x1 ) P ( x0 )
x0
x1
x1
  P ( x0 ) log P ( x0 )   P ( x1 ) log P ( x1 )
x0
x1
 H1 ( S )  H1 ( S )  2 H1 ( S )
x0
確率 P(x0) の
総和は 1
系:任意の無記憶な定常情報源 S に対し,H (S) = H1(S).
11
記憶のある情報源:マルコフ情報源の場合
0/0.9
0
1/0.1
1
定常確率分布は w0 = 0.8, w1 = 0.2
0/0.4
1/0.6
各通報の定常確率:
0
1
00
01
10
11
不一致
0.8·0.9 + 0.2·0.4 = 0.80
0.8·0.1 + 0.2·0.6 = 0.20
H1(S) = 0.722
0.8·0.9·0.9 + 0.2·0.4·0.9 = 0.72
0.8·0.9·0.1 + 0.2·0.4·0.1 = 0.08
0.8·0.1·0.4 + 0.2·0.6·0.4 = 0.08
0.8·0.1·0.6 + 0.2·0.6·0.6 = 0.12
H1(S2) = 1.2914
H2(S) = H1(S2)/2 = 0.6457
1文字を2個予測するより,2文字
まとめてのほうが予測しやすい
前スライドの定理は,記憶のある情報源では成立しない
12
マルコフ情報源の極限エントロピー
極限エントロピーの計算:
情報源に記憶がなければ...一次エントロピーと一致
情報源に記憶のある場合は...一般には計算困難
⇒ マルコフ情報源であれば,別の手がある
1.
2.
3.
定常確率分布を求めておく
各状態について,その状態を記憶のない情報源と考え,
極限エントロピー(一次エントロピー)を計算する
定常確率分布より,各状態のエントロピーの加重平均を取る
13
極限エントロピーの計算例
0/0.9
1/0.1
0
極限分布は w0 = 0.8, w1 = 0.2
1
0/0.4
1/0.6
状態 0:P(0)=0.9, P(1)=0.1の情報源 ⇒ H(S) = H(0.9) = 0.469
状態 1:P(0)=0.4, P(1)=0.6の情報源 ⇒ H(S) = H(0.4) = 0.971
状態0に居る確率80%,1に居る確率20%なので,加重平均は
0.8·0.469 + 0.2·0.971 = 0.5694...これが極限エントロピー
ちなみに,H1(S) = 0.722,H2(S) = 0.6457,... 単調減少?
14
拡大マルコフ情報源と極限エントロピー
一般に,マルコフ情報源においてブロック長 n を大きくすると...
n 次エントロピーは単調に減少していく
極限エントロピーに収束する
Hn(S)
H(S)
n
記憶のある情報源:
ある程度,通報の出現パターンが「読める」
自然語だと,“qu” は高頻出,“qz” は,まず出現しない
無記憶の場合より,振舞いが予想しやすい ⇒ エントロピー小
15
情報源の記憶とエントロピー
定常確率 0.8 で 0 を,0.2 で 1 を出力する情報源を考える
1/0.1
0/0.9
0/0.8
1/0.6
0/0.4
1/0.2
記憶無し
記憶あり
0.72
一次エントロピー
0.72
0.72
極限エントロピー
0.5694
記憶のある情報源では,「ブロック化したほうが都合良い」場合も
⇒ プロセッサの条件分岐予測など
16
通報の持つ情報量
阪神タイガースの試合があったが,結果をまだ知らない
阪神が勝つ確率,負ける確率,引き分ける確率は,全部1/3
巨人ファンの友人Aからメイル:「阪神は負けなかった」
友人Aのメイルに含まれる情報の「量」は?
メイルを受け取る前:結果に関する不確かさが大きい
P(勝) = 1/3. P(引) = 1/3, P(負) = 1/3
メイルを受け取った後:結果に関する不確かさが小さくなった
P(勝) = 1/2. P(引) = 1/2, P(負) = 0
「不確かさの減少量 = 情報量」と定義したい
17
野球の試合の例では
メイルを受け取る前:P(勝) = 1/3, P(引) = 1/3, P(負) = 1/3
エントロピーは
1 1 1 1 1 1
 log  log  log  log 3  1.585
3 3 3 3 3 3
メイルを受け取った後:P(勝) = 1/2, P(引) = 1/2, P(負) = 0
条件付きエントロピーは
1
1 1
1
 log  log  0  log 2  1
2
2 2
2
「阪神は負けなかった」というメイルに含まれる情報量:
1.585 – 1 = 0.585 ビット
18
情報量とエントロピー
離れたところにある情報源 S の出力(通報)を知りたい
通報の確率分布はわかるが,実際に発生した通報は不明
S の出力に関し,なんらかの「ヒント」を入手したとする
ヒントにより,通報の確率分布が,別の情報源 S’ の確率分布
と一致することがわかったとする
このとき,ヒント(通報)がもたらした情報量 (information) は
H(S) – H(S’) ビット
19
気まぐれな友人の場合(case 1)
右図の行動を取る友人Bが
「言いたくない」と言った時の
情報量は?
P(言いたくない) = 2/3
P(勝ち,言いたくない) = 1/6
P(引分,言いたくない) = 1/3
P(負け,言いたくない) = 1/6
勝ち
引分
0.5
0.5
1.0
0.5
負け 0.5
「勝ったよ」
「言いたくない」
「負けたよ」
P(勝ち | 言いたくない) = 1/4
P(引分 | 言いたくない) = 1/2
P(負け | 言いたくない) = 1/4
「言いたくない」と言っているときのエントロピーは
1
1 1
1 1
1
 log  log  log  1.5
4
4 2
2 4
4
情報量は1.585 – 1.5 = 0.085ビット(友人Aのメイル:0.585ビット)
20
気まぐれな友人の場合(case 2)
友人Bが「勝ったよ」と言った
ときの情報量は?
P(勝ったよ) = 1/6
P(勝ち,勝ったよ) = 1/6
P(勝ち | 勝ったよ) = 1
P(引分 | 勝ったよ) = 0
P(負け | 勝ったよ) = 0
勝ち
引分
0.5
0.5
1.0
0.5
負け 0.5
「勝ったよ」
「言いたくない」
「負けたよ」
エントロピーは0になる
(結果を正確に知ることができる)
情報量は1.585 – 0 = 1.585ビット(友人Aのメイル:0.585ビット)
(p.17 の)友人Aと,この友人B,どちらが「頼りになる」友人か?
... 個々の通報の情報量だけを見ていたのではわからない
21
情報量の「平均」
友人Bの行動:
1/6 の確率で「勝ったよ」...情報量 1.585ビット
2/3 の確率で「言いたくない」...情報量 0.085ビット
1/6 の確率で「負けたよ」...情報量 1.585ビット
平均すると 1.585  1/6 + 0.085  2/3 +1.585  1/6 = 0.585ビット
友人Aの行動: 2/3の確率で「負けなかった」...情報量 0.585ビット
1/3の確率で「負けたよ」...情報量 1.585ビット
勝ち
平均すると 0.585  2/3 + 1.585  1/3 = 0.918ビット
引分
負け
「負けなかった」
「負けたよ」
平均すると,友人Aのほうが
0.333ビット多くの情報をくれる
22
相互情報量
友人A,友人Bは,異なる特性を持った通信路と考えられる
「負けなかった」
「言いたくない」
通信路の入力確率変数を X,出力確率変数を Y とする
X
Y
X と Y の相互情報量 I(X; Y):
Yの各値が持つ(X に関する)情報量の加重平均
前ページでは「試合結果と友人の振舞いの相互情報量」を計算
23
相互情報量の意味
相互情報量:
その通信路が,どれだけの情報を伝達しているかの指標
システムとして通信路を実現することを考えると,個々の
通報の情報量より,相互情報量にこそ着目すべき
同じ通信路でも,入力分布が変わると,相互情報量も変わる
同じ友人Aでも...
勝ち,引分,負けが 1/3のチーム...相互情報量は0.918ビット
勝ち,負けが1/2のチーム...相互情報量は 1 ビット
相互情報量の取り得る最大値 ⇒ 通信路容量という(第三部)
24
相互情報量の計算例(1)
天気予報:天気についての情報を与える,やや不正確な通信路
例:100日間の実際の天気 (X) と天気予報 (Y) の統計:
Y
晴
X
雨
P(Y)×100
晴
45
15
60
雨
12
28
40
P(X) ×100
57
43
X
現実
Y
予報
実際の天気が晴だったのは57日,PX(晴)=0.57
予報が晴といったのは60日,PY(雨)=0.60
天気 X, 予報 Y とも晴だったのは45日,PX,Y(晴,晴)=0.45
25
相互情報量の計算例(2)
Y
晴
X
雨
P(Y)×100
晴
45
15
60
雨
12
28
40
P(X) ×100
57
43
天気予報が当たる確率=PX,Y(晴,晴)+ PX,Y(雨,雨)=0.73
この予報と友人Aのメイル,どちらが「高性能」?
天気のエントロピー:
H ( X )  0.57 log 0.57  0.43 log 0.43  0.986
ビット
26
相互情報量の計算例(3)
天気予報Yが晴のとき:
本当に晴れる確率は 0.45/0.60 = 0.75,雨の確率は0.25
「晴」という予報を聞いた後の条件付エントロピーは
H(X | 晴) = – 0.75log0.75 – 0.25log0.25 = 0.811 ビット
「晴」という天気予報の持つ情報量は 0.986 – 0.811 = 0.175
天気予報Yが雨のとき:
本当に雨の確率は 0.28/0.40 = 0.70,晴の確率は0.30
「雨」という予報を聞いた後の条件付エントロピーは
H(X | 雨) = – 0.30log0.30 – 0.70log0.70 = 0.881 ビット
「雨」という天気予報の持つ情報量は 0.986 – 0.881 = 0.105
加重平均をとると 0.60·0.175 + 0.40·0.105 = 0.147 ビット
27
相互情報量と当たる確率
A社:
まぁまぁ当たる予報
晴
X
雨
P(Y)×100
B社:
絶対はずれる予報
晴
X
雨
P(Y)×100
Y
晴
45
15
60
雨
12
28
40
P(X) ×100
57
43
雨
57
0
57
P(X) ×100
57
43
73%
0.147ビット
Y
晴
0
43
43
0%
0.986ビット
情報の「量」は,B社予報のほうが大きい
28
本日のまとめ
エントロピーの概念を導入
予測の難しさを定量化したもの
1次,n次,極限エントロピー
無記憶情報源では,上の三者は同一
記憶のある情報源では,n → 大のときエントロピー→小
情報量,相互情報量を定義
エントロピーの減少量として定式化
システムの評価には,相互情報量の概念が有用
29
練習問題
12ページの例において,3次,4次のエントロピーを求めよ.
可能であれば,n 次エントロピーを計算するプログラムを書け.
以下を示せ
I(X; Y) = H(X) – H(X | Y)
ただし H ( X | Y )   P( y ) H ( X | Y  y )
y
(条件付きエントロピーの加重平均)
I(X; Y) = I(Y; X)
I(X; Y) = H(X) + H(Y) – H(X, Y)
ただし H(X, Y) は X と Y の結合エントロピー
(X と Y をまとめて一個の確率変数と考える)
30
ダウンロード

PowerPoint