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
© Copyright 2024 ExpyDoc