情報理論 第5回 情報量とエントロピー

(1)

. .. . . .

情報理論

第

5

回 情報量とエントロピー

堀田 政二 工学部 情報工学科 情報理論 第 5 回 情報量とエントロピー

(2)

.

.

情報量とは

聞いて非常に驚く情報· · · 情報量が大きい(人が犬を噛む) 聞いても驚かない情報· · · 情報量が小さい(犬が人を噛む) これを数学的に表現することを考える．例えば生起確率(発生確 率) がp(a)の事象aが実際に起きたとき，これを知ることによっ て得られる情報量を I(a)∝ 1 p(a) と定義したとしよう．すなわち，情報量は生起確率に反比例する． p(a)が小さい· · · I(a)が大きい p(a)が大きい· · · I(a)が小さい 情報理論 第 5 回 情報量とエントロピー

(3)

.

自己情報量

(self information)

この定義ではp(a) = 1ならばI(a) = 0とはならない．つまり必 ず起きる事象が起きた時の驚きはI(a) = 0であるにも関わらず， この定義ではI(a)が∞に近づいてしまう．そこで右辺の対数を とったものを事象aの自己情報量と定義する． . 自己情報量 . . . .. . . . I(a) = log₂ 1

p(a) =− log2p(a)単位はbit

情報理論では，対数の底として通常2 (log₂)を用いる

(4)

.

.

自己情報量のグラフ

p(a) 0 0.5 1 1 2 3 4 5 6 7 I(a) p(a) = 1/2の時，I(a) = 1 p(a) = 1の時，I(a) = 0 情報理論 第 5 回 情報量とエントロピー

(5)

.

自己情報量の例

【例1】赤ん坊が生まれたとき，その男女比が1 : 1とする．男が 生まれる事象をboy，女が生まれる事象をgirlとすると，それぞ れの自己情報量は下記の通りになる:

I(boy) =− log₂ 1₂ = 1 bit

I(girl) =− log₂ 1₂ = 1 bit

【例2】ある試験では合格する可能性が1/8である．この，試験に 合格した場合の自己情報量は

I(合格) =− log_{2 2}13 = 3 bit

となる．一方，不合格になった時の自己情報量は

I(不合格) =− log₂ 7₈ =− log₂7 + log₂8 =−2.807 + 3 = 0.193 bit

となる．

(6)

.

.

情報量の加法性

ある事象Eは二つの事象E1とE2の積だとする．この時，事象 Eの自己情報量は

I(E) = I(E1) + I(E2)

となる．例えば，ジョーカーを除いた52枚のトランプを相手に引 いて貰い，その内容を教えてもらうことを考える．

引いたカードが♠のAであることを知ったときの情報量は

I(♠ ∩ A) = − log_{2 52}1 ∼ 5.7 bit

引いたカードが♠であることのみを知ったときの情報量は

I(♠) = − log214 = 2 bit

引いたカードがAであることのみを知ったときの情報量は

I(A) =− log_{2 13}1 ∼ 3.7 bit

したがってI(♠ ∩ A) = I(♠) + I(A)

(7)

.

対数の計算

(

復習

)

.

.

_. 1 _log ab = c⇔ b = ac (対数の定義) .

.

. 2 log ab = log₁₀b log₁₀a .

.

. 3 _log

a(xy) = loga(x) + loga(y)

.

.

. 4 log a x

y = loga(x)− loga(y)

.

.

. 5 log axy = y logax .

.

. 6 − log a 1 x = logax (式5でy =−1のとき) なお，log₂xを計算するには，式2を利用すれば良い．すなわち

log₂x = log₁₀x/ log₁₀2 = log₁₀x/0.3010∼ 3.3223 × log₁₀x

(8)

.

.

平均情報量

(average information)

情報量の平均(期待値) について考えよう．いま，ある事象系A をA ={a1, a2, ..., an}とする．これらn個の事象は互いに排反 で，その生起確率p(ai)の総和は1とする(完全事象系)．情報量 I(ai)の期待値をH(A)とすると H(A) = n ∑ i=1 p(ai)I(ai) =− n ∑ i=1

p(ai) log2p(ai)

簡単のためにp(ai)をpiと略記すると . 平均情報量 . . . .. . . . H(A) =− n ∑ i=1 pilog2pi bit 情報理論 第 5 回 情報量とエントロピー

(9)

.

平均情報量の性質

平均情報量の取りうる値は0≤ H(A) ≤ log₂n bit

事象系Aのうち，一つの事象aiの生起確率がp(ai) = 1で， その他の事象の生起確率がすべて0の時，H(A) = 0．これ は結果を聞く前から結果が既知なので驚き0． 事象系Aのすべての事象の生起確率がp(ai) = 1/nと一様の 場合は平均情報量は最大のH(A) = log₂nとなる．これはど れが起きるか全く予想できない状態． 情報理論 第 5 回 情報量とエントロピー

(10)

.

.

平均情報量の例

小金井の8月1日の天気の生起確率が以下の通りだとする: p(晴) = 1 4, p(雨) = 1 2 p(曇) = 1 4, p(雪) = 0 この時の平均情報量を求めると H(A) = − 4 ∑ i=1 pilog2pi = −1 4log2 1 4 − 1 2log2 1 2 − 1 4log2 1 4− 0 log20 = 2 4 + 1 2+ 2 4 − 0 = 1.5 bit ただし，x→ 0のときx log₂x→ 0 情報理論 第 5 回 情報量とエントロピー

(11)

.

エントロピー

(entropy)

熱力学における分子の無秩序さを表す尺度 . 熱力学におけるエントロピー . . . .. . . . H =−K∑ k nkln nk ここで，Kはポルツマン定数，nkは気体分子のk番目のエネル ギー状態にある確率． . 情報理論におけるエントロピー . . . .. . . . H =−∑ i pilog2pi 熱力学におけるエントロピーと平均情報量は定数倍，対数の底を 除いて一致する．そのため，平均情報量を(情報) エントロピー と呼ぶことにする． 情報理論 第 5 回 情報量とエントロピー

(12)

.

.

エントロピーの例

ある日のK市の天気予報が 晴40%，曇30%，雨30%の時，エントロピーは

H =−0.4 log₂0.4− 0.3 log₂0.3− 0.3 log₂0.3 = 1.57 bit

晴100%のとき

H =−1.0 log₂1.0− 0 log₂0− 0 log₂0 = 0 bit

晴れが100%のときは結果が一つに決まっているのでエントロ ピーは0，すなわち曖昧さがない

(13)

.

最大エントロピー

(maximum entropy)

エントロピーが最大になるのはどのような場合かを考える．二つの事象からな る事象系(2元事象系)を次のように表す: A = ( a1 a2 p1 p2 ) 一行目は二つの互いに排反な事象を表し，どちらか一方の事象のみが起 きる 二行目は各事象の生起確率(p1+ p2= 1) この場合のエントロピーは H =−p1log2p1− p2log2p2 となり，p1+ p2= 1という制約条件のもとでHの最大値を求めるにはラグラ ンジュの未定乗数法を使って解けばよい: L =−p1log2p1− p2log2p2+ λ(1− p1− p2) ∂L/∂pi=− log2pi+ 1− λ = 0，∂L/∂λ = 1− p1− p2= 0の連立方程式を解

けば，log₂p1 = log2p2のときエントロピーがHmax=− log2 1

2 = 1 bitと最大

になることが分かる．

(14)

.

.

ラグランジュ未定乗数法

制約条件のもとで関数の極値を求める方法の一つ． . 問題設定 . . . .. . . . 制約条件 g(x) = 0 のもとで関数 f (x) の極値を求めよ ラグランジュ乗数 λ を用いてラグランジュ関数を導入 L = f (x)− λg(x) 制約条件のもとで関数が極値をとる点は次式を満たす： ∂ ∂xL =∇f − λ∇g = 0, ∂L ∂λ = 0 上記から d + 1 個の方程式が得られる．一方，未知数は x1,...,xd, λ の d + 1 個なので，方程式の解を求めることができる 情報理論 第 5 回 情報量とエントロピー

(15)

.

ラグランジュ未定乗数法の直感的な理解

0 = ) (x g . const ) (x = f g ∇ f ∇ 二変数の場合の例 制約条件 g(x) = 0 と f (x) の等高線の法線ベクトルが極値で平行 ∇f = λ∇g 情報理論 第 5 回 情報量とエントロピー

(16)

.

.

n

次元事象系の場合の最大エントロピー

2元事象系を一般化したn次元事象系における最大エントロピーを考える． A = ( a1 a2 · · · an p1 p2 · · · pn ) この場合のエントロピーは H =− n ∑ i=1 pilog2pi 2元事象系の場合と同様にしてラグランジュの未定乗数法を使って解けばよい: L =− n ∑ i=1 pilog2pi+ λ ( 1− n ∑ i=1 pi ) ∂L/∂pi=− log2pi+ 1− λ = 0，∂L/∂λ = 1− ∑n i=1pi= 0の連立方程式を解 けば，p1= p2=· · · = pnのときエントロピーがHmax=− log2 1 n bitと最大 になることが分かる． 情報理論 第 5 回 情報量とエントロピー

(17)

.

最大エントロピーの例

以下の例はいずれも各事象の生起確率が等確率と仮定する． サイコロを一回振る時の最大エントロピー Hmax=− 6 ∑ i=1 1 6log2 1 6 = log26 = 2.585 bit 英数字 (A∼Zと空白，計27文字) の最大エントロピー Hmax=− 27 ∑ i=1 1 27log2 1 27 = log227 = 4.755 bit 常用漢字 (1945文字) の最大エントロピー Hmax=− 1945_∑ i=1 1 1945log2 1 1945 = log21945 = 10.925 bit 情報理論 第 5 回 情報量とエントロピー

(18)

.

.

エントロピー関数

(entropy function)

2元事象系のエントロピー H =−p1log2p1− p2log2p2 において，p1 = p，p2= 1− pと置くと H(p) = −p log2p− (1 − p) log2(1− p) となる．この関数H(p)をエントロピー関数と呼ぶ． H(p) p 情報理論 第 5 回 情報量とエントロピー

(19)

.

エントロピー関数の利用法

ある試験を受けて，合格する確率がA君は0.6 (不合格の確率 0.4)，B君は0.9 (不合格の確率0.1) の場合，それぞれのエントロ ピーは H(A君) =H(0.6) = H(0.4) ∼ 0.971 bit H(B君) =H(0.9) = H(0.1) ∼ 0.496 bit B君の方が合格する可能性が高いので，曖昧さ，不確実さはA君 より少なくなる 情報理論 第 5 回 情報量とエントロピー

(20)

.

.

結合エントロピー

(joint entropy)

二つの事象系を考える: A = ( a1 a2 p(a1) p(a2) ) B = ( b1 b2 p(b1) p(b2) ) 二つの事象系AとBが同時に起きる事象を結合事象系と呼び， A⊗ B，または単にABと表す: AB = ( (a1, b1) (a1, b2) (a2, b1) (a2, b2) p11 p12 p21 p22 ) ただし，(ai, bj) = ai∩ bj，pij = p(ai∩ bj)とする．このときAB の平均情報量 H(AB) =−∑ i ∑ j pijlog2pij を結合エントロピーと呼ぶ． 情報理論 第 5 回 情報量とエントロピー

(21)

.

条件付きエントロピー

(conditional entropy)

結合エントロピーH(AB)を変形すると H(AB) = − ∑ i ∑ j

p(ai∩ bj) log2p(ai∩ bj)

= − ∑

i

∑

j

p(ai)p(bj|ai) log2p(ai)p(bj|ai)

= − ∑

i

∑

j

p(ai)p(bj|ai){log2p(ai) + log2p(bj|ai)}

= − ∑

i

∑

j

p(ai)p(bj|ai) log2p(ai)

− ∑ i ∑ j p(ai)p(bj|ai) log2p(bj|ai) = − ∑ i

p(ai) log2p(ai)

∑ j p(bj|ai) − ∑ i p(ai) ∑ j p(bj|ai) log2p(bj|ai) ∑ jp(bj|ai) = 1であるため，第1項はH(A)である． 情報理論 第 5 回 情報量とエントロピー

(22)

.

.

条件付きエントロピーの続き

一方，第2項の∑_jp(bj|ai) log2p(bj|ai)は条件aiのもとでのbj のエントロピーである．したがって，第2項全体はそのaiに関す る平均値であることからH(B|A)を意味している．すなわち， H(B|A) = −∑ i p(ai) ∑ j p(bj|ai) log2p(bj|ai) このH(B|A)を条件付きエントロピーと呼ぶ．

以上から，H(AB)はH(AB) = H(A) + H(B|A)と書けることが 分かる．同様にしてH(AB) = H(B) + H(A|B)も示すことがで きることからH(AB) = H(BA)である．

(23)

.

シャノンの基本不等式 (Shannon’s fundamental inequality) 条件付きエントロピーに関して次の関係が成り立つ: . シャノンの基本不等式 . . . .. . . .

H(A|B) ≤ H(A), H(B|A) ≤ H(B)

上式は，情報を得る前よりも，情報を得た後の方がエントロピー は小さい(曖昧さが減少する) ことを意味している．例えば

A: 雨が降るという事象

B: 台風が接近しているという事象

とするとBを知ればAが起きるであろうことは，より確実に予想 可能になる．この不等式とH(AB) = H(A) + H(B|A)から

H(AB) = H(A) + H(B|A) ≤ H(A) + H(B)

なる関係が導かれる．等号が成り立つ場合はAとBが独立の時．

(24)

.

.

シャノンの基本不等式の続き

不等式

H(AB) = H(A) + H(B|A) ≤ H(A) + H(B)

において，等号が成り立つ場合はAとBが独立の時．例えば

A: 犬が子供を産むという事象

B: 台風が接近しているという事象

の場合には，AとBの事象は互いに独立なので等号が成り立つ． これまでの議論をまとめると

0≤ H(A|B) ≤ H(A) ≤ H(AB)

なる関係が成り立つ．

(25)

.

各種エントロピーの関係

H(AB) H(A|B) H(B|A) H(A) H(B)

H(AB) = H(A) + H(B|A) = H(B) + H(A|B)

(26)

.

.

問題

【5.1】ある都市のある日の天気予報が，晴45%，曇35%， 雨12%，雪8%のとき，エントロピーHを小数第2位まで求 めよ． 【5.2】平仮名48文字の生起確率がすべて等しいと仮定した 場合の平均情報量を小数第3位まで求めよ． 【5.3】A君が3年後に大学を卒業できる確率は75%，A君の 父が3年後に会社で重役になれる確率を30%とする．このと き，二つの事象の結合エントロピーを求めよ． 情報理論 第 5 回 情報量とエントロピー