前回の練習問題 無記憶・非定常な情報源を一つ例示せよ 時刻 t に t 枚のコインを投げるとき，表が出る枚数 以下のマルコフ情報源について，

Presentation on theme: "前回の練習問題 無記憶・非定常な情報源を一つ例示せよ 時刻 t に t 枚のコインを投げるとき，表が出る枚数 以下のマルコフ情報源について，"— Presentation transcript:

1 前回の練習問題 無記憶・非定常な情報源を一つ例示せよ 時刻 t に t 枚のコインを投げるとき，表が出る枚数 以下のマルコフ情報源について，
状態の定常確率分布を求めよ 通報 A, B の定常確率を求めよ 1 2 A/0.4 A/0.5 B/0.6 A/0.8 B/0.5 B/0.2 (w0, w1, w2) = (0.1, 0.7, 0.2) P(A) = 0.7 P(B) = 0.3

2 前回の補足：マルコフ情報源が既約であること
既約（irreducible）マルコフ情報源 任意の状態から任意の状態に遷移可能なマルコフ情報源 厳密には... 時刻 t の状態を変数 Xt で表現するとき，任意の時刻 i, j (i < j) および任意の状態 si, sj に対し，P(Xj = sj | Xi = si) > 0 であること 無限個の状態を持つマルコフ連鎖では，既約であっても， P(Xj = sj | Xi = si) → 0 となるケースもある（収束 ≠ 一致） 1.0 0.1 0.9

3 本日の講義について 「情報量」を定義する 情報源に対し，エントロピーの概念を導入 エントロピー＝通報を予想する難しさの定量的指標
エントロピーが大きい ⇔ 予測することが難しい 一個の通報の持つ情報量を定義 情報量＝その通報がもたらすエントロピーの減少量 通信路の性能指標となる相互情報量を定義 その通信路を通過する通報の情報量の加重平均

4 記憶のない情報源のエントロピー 以下の通報発生確率を持つ，記憶のない定常情報源S を考える ... 通報 確率 a1 p1 a2 p2 aM
pM 情報源 S の一次エントロピー (first-order entropy): (ビット, bit） この項は非負 ⇒エントロピーは常に０以上 例１： コイン投げのエントロピー：表，裏とも確率 1/2...M = 2, p1=p2=0.5 ビット

5 エントロピーの計算例 例２：サイコロの目...コイン投げより，結果予想は難しいはず 1 1/6 通報 確率 2 3 4 5 6 ビット
例３：イカサマ賭博のサイコロ 1 0.9 通報 確率 2 0.02 3 4 5 6 ビット 一個の指標で，予測の難しさの大小関係を定義可能

6 予想の難しさとエントロピー：二元情報源の場合
通報が0 または1の，記憶のない二元情報源 S を考える 0, 1 の発生確率が p, 1 – p のとき， ビット この値をH(p) と表記する（二元エントロピー関数） p=0.5のとき， H(p) は最大値 1 を取る p が 0, 1 に近づくとき， H(p) は 0 に近づく p H(p) 1.0 0.5 予想のしやすさとエントロピーの 間には，相関関係がある

7 M元情報源の場合 天気...三元情報源 奈良の天気...晴40%, 曇50%, 雨10%とすると，H1(S)=1.361
もし，晴，曇，雨の確率が全部 1/3 の場合， M元情報源では，M個の通報が等確率で発生するとき， エントロピーは最大値 log M ビットとなる エントロピーが最小値を取るのは，ある一つの通報について， その発生確率が1となる場合 ...この場合，通報は，あいまいさなく予測可能

8 拡大情報源について ブロック化（block）： 情報源からの通報を複数個まとめて，一個の通報とみなすこと
M元情報源Sの出力をn個まとめて一つのブロックを構成 ⇒ S の n次拡大（n-th order extended）情報源 ...通報は Mn 種類： Mn元情報源になる 拡大情報源のエントロピーは？ 記憶のない情報源だと，ブロック化しても面白くない 記憶のある情報源のブロック化，が興味深い結果を示す ... 話の順番として，まずは記憶のないケースを議論

9 拡大情報源のエントロピー計算 コイン投げ２回分の通報を，１ブロックにまとめる場合...
通報は {表表, 表裏，裏表，裏裏} の４通り...22元情報源 通報 確率 表表 1/4 表裏 1/4 裏表 1/4 裏裏 1/4 H1(S2)=log 4 = 2 ビット...結果予想は一個の場合の２倍難しい H1(S2)は，S の通報２個分のエントロピー ⇒ S の通報１個分に換算すると，H1(S2)/2 = 1ビット Sの n次 （n-th order）エントロピー．Hn(S)と表記 Sの極限エントロピー．H(S)と表記

10 記憶のない情報源の拡大とエントロピー S: 0, 1 をそれぞれ確率 0.8, 0.2 で発生する記憶のない情報源 1 0.8 0.2 S
1 0.8 0.2 S H1(S)= –0.8log0.8 – 0.2log0.2 = 0.72 S2 00 01 10 11 0.64 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) = 極限エントロピー＝一次エントロピー

11 記憶のない情報源の拡大とエントロピー 定理：任意の無記憶な定常情報源 S に対し，H1(Sn) = nH1(S)．
無記憶だから P(x0, x1) = P(x0)P(x1) 確率 P(x0) の 総和は 1 系：任意の無記憶な定常情報源 S に対し，H (S) = H1(S).

12 記憶のある情報源：マルコフ情報源の場合 1 0/0.9 1/0.1 0/0.4 1/0.6
1 0/0.9 1/0.1 0/0.4 1/0.6 定常確率分布は w0 = 0.8, w1 = 0.2 各通報の定常確率： 不一致 0.8· ·0.4 = 0.80 H1(S) = 0.722 1 0.8· ·0.6 = 0.20 00 0.8·0.9· ·0.4·0.9 = 0.72 01 0.8·0.9· ·0.4·0.1 = 0.08 H1(S2) = H2(S) = H1(S2)/2 = 10 0.8·0.1· ·0.6·0.4 = 0.08 11 0.8·0.1· ·0.6·0.6 = 0.12 １文字を２個予測するより，２文字 まとめてのほうが予測しやすい 前スライドの定理は，記憶のある情報源では成立しない

13 マルコフ情報源の極限エントロピー 極限エントロピーの計算： 情報源に記憶がなければ...一次エントロピーと一致
情報源に記憶のある場合は...一般には計算困難 ⇒ マルコフ情報源であれば，別の手がある 定常確率分布を求めておく 各状態について，その状態を記憶のない情報源と考え， 極限エントロピー（一次エントロピー）を計算する 定常確率分布より，各状態のエントロピーの加重平均を取る

14 極限エントロピーの計算例 1 0/0.9 1/0.1 0/0.4 1/0.6 極限分布は w0 = 0.8, w1 = 0.2
1 0/0.9 1/0.1 0/0.4 1/0.6 極限分布は w0 = 0.8, w1 = 0.2 状態 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.971 = これが極限エントロピー ちなみに，H1(S) = 0.722，H2(S) = ，... 単調減少？

15 拡大マルコフ情報源と極限エントロピー 一般に，マルコフ情報源においてブロック長 n を大きくすると...
極限エントロピーに収束する n Hn(S) H(S) 記憶のある情報源： ある程度，通報の出現パターンが「読める」 自然語だと，“qu” は高頻出，“qz” は，まず出現しない 無記憶の場合より，振舞いが予想しやすい ⇒ エントロピー小

16 情報源の記憶とエントロピー 定常確率 0.8 で 0 を，0.2 で 1 を出力する情報源を考える 0/0.8 1/0.2 0/0.9
1/0.1 1/0.6 0/0.4 記憶無し 記憶あり 一次エントロピー 0.72 極限エントロピー 0.5694 記憶のある情報源では，「ブロック化したほうが都合良い」場合も ⇒ プロセッサの条件分岐予測など

17 通報の持つ情報量 阪神タイガースの試合があったが，結果をまだ知らない 阪神が勝つ確率，負ける確率，引き分ける確率は，全部1/3
巨人ファンの友人Ａからメイル：「阪神は負けなかった」 友人Ａのメイルに含まれる情報の「量」は？ メイルを受け取る前：結果に関する不確かさが大きい P(勝) = 1/3. P(引) = 1/3, P(負) = 1/3 メイルを受け取った後：結果に関する不確かさが小さくなった P(勝) = 1/2. P(引) = 1/2, P(負) = 0 「不確かさの減少量 ＝ 情報量」と定義したい

18 野球の試合の例では メイルを受け取る前：P(勝) = 1/3, P(引) = 1/3, P(負) = 1/3 エントロピーは
条件付きエントロピーは 「阪神は負けなかった」というメイルに含まれる情報量： 1.585 – 1 = ビット

19 情報量とエントロピー 離れたところにある情報源 S の出力（通報）を知りたい 通報の確率分布はわかるが，実際に発生した通報は不明
このとき，ヒント（通報）がもたらした情報量 （information) は H(S) – H(S’) ビット

20 気まぐれな友人の場合（case 1） 右図の行動を取る友人Ｂが 「言いたくない」と言った時の 情報量は？ 勝ち 引分 負け 「勝ったよ」
「負けたよ」 0.5 1.0 P(言いたくない) = 2/3 P(勝ち，言いたくない) = 1/6 P(勝ち | 言いたくない) = 1/4 P(引分，言いたくない) = 1/3 P(引分 | 言いたくない) = 1/2 P(負け，言いたくない) = 1/6 P(負け | 言いたくない) = 1/4 「言いたくない」と言っているときのエントロピーは 情報量は1.585 – 1.5 = 0.085ビット（友人Ａのメイル：0.585ビット）

21 気まぐれな友人の場合（case 2） 友人Ｂが「勝ったよ」と言った ときの情報量は？ 勝ち 引分 負け 「勝ったよ」 「言いたくない」
「負けたよ」 0.5 1.0 P(勝ったよ) = 1/6 P(勝ち，勝ったよ) = 1/6 P(勝ち | 勝ったよ) = 1 P(引分 | 勝ったよ) = 0 エントロピーは０になる （結果を正確に知ることができる） P(負け | 勝ったよ) = 0 情報量は1.585 – 0 = 1.585ビット（友人Ａのメイル：0.585ビット） （p.17 の）友人Ａと，この友人Ｂ，どちらが「頼りになる」友人か？ ... 個々の通報の情報量だけを見ていたのではわからない

22 情報量の「平均」 友人Ｂの行動： 1/6 の確率で「勝ったよ」...情報量 1.585ビット
2/3 の確率で「言いたくない」...情報量 0.085ビット 1/6 の確率で「負けたよ」...情報量 1.585ビット 平均すると  1/  2/  1/6 = 0.585ビット 友人Ａの行動： 2/3の確率で「負けなかった」...情報量 0.585ビット 1/3の確率で「負けたよ」...情報量 1.585ビット 平均すると  2/  1/3 = 0.918ビット 勝ち 引分 負け 「負けなかった」 「負けたよ」 平均すると，友人Ａのほうが 0.333ビット多くの情報をくれる

23 相互情報量 友人Ａ，友人Ｂは，異なる特性を持った通信路と考えられる 通信路の入力確率変数を X，出力確率変数を Y とする
「負けなかった」 「言いたくない」 通信路の入力確率変数を X，出力確率変数を Y とする X と Y の相互情報量 I(X; Y)： Yの各値が持つ（X に関する）情報量の加重平均 前ページでは「試合結果と友人の振舞いの相互情報量」を計算 X Y

24 相互情報量の意味 相互情報量： その通信路が，どれだけの情報を伝達しているかの指標 システムとして通信路を実現することを考えると，個々の
通報の情報量より，相互情報量にこそ着目すべき 同じ通信路でも，入力分布が変わると，相互情報量も変わる 同じ友人Ａでも... 勝ち，引分，負けが 1/3のチーム...相互情報量は0.918ビット 勝ち，負けが1/2のチーム...相互情報量は 1 ビット 相互情報量の取り得る最大値 ⇒ 通信路容量という（第三部）

25 相互情報量の計算例（１） 天気予報：天気についての情報を与える，やや不正確な通信路
例：100日間の実際の天気 (X) と天気予報 (Y) の統計： X 晴 45 15 60 雨 12 28 40 P(Y)×100 Y P(X) ×100 57 43 X Y 現実 予報 実際の天気が晴だったのは57日，PX(晴)=0.57 予報が晴といったのは60日，PY（雨）=0.60 天気 X, 予報 Y とも晴だったのは45日，PX,Y(晴，晴）=0.45

26 相互情報量の計算例（２） X 晴 45 15 60 雨 12 28 40 P(Y)×100 Y P(X) ×100 57 43
天気予報が当たる確率＝PX,Y（晴，晴）＋ PX,Y（雨，雨）=0.73 この予報と友人Ａのメイル，どちらが「高性能」？ 天気のエントロピー： ビット

27 相互情報量の計算例（３） 天気予報Yが晴のとき： 本当に晴れる確率は 0.45/0.60 = 0.75，雨の確率は0.25
「晴」という予報を聞いた後の条件付エントロピーは H(X | 晴) = – 0.75log0.75 – 0.25log0.25 = ビット 「晴」という天気予報の持つ情報量は – = 0.175 天気予報Yが雨のとき： 本当に雨の確率は 0.28/0.40 = 0.70，晴の確率は0.30 「雨」という予報を聞いた後の条件付エントロピーは H(X | 雨) = – 0.30log0.30 – 0.70log0.70 = ビット 「雨」という天気予報の持つ情報量は – = 0.105 加重平均をとると 0.60· ·0.105 = ビット

28 相互情報量と当たる確率 X 晴 45 15 60 雨 12 28 40 P(Y)×100 Y P(X) ×100 57 43 A社：
まぁまぁ当たる予報 73% 0.147ビット X 晴 43 雨 57 P(Y)×100 Y P(X) ×100 B社： 絶対はずれる予報 0% 0.986ビット 情報の「量」は，Ｂ社予報のほうが大きい

29 本日のまとめ エントロピーの概念を導入 予測の難しさを定量化したもの １次，n次，極限エントロピー 無記憶情報源では，上の三者は同一
情報量，相互情報量を定義 エントロピーの減少量として定式化 システムの評価には，相互情報量の概念が有用

30 練習問題 １２ページの例において，３次，４次のエントロピーを求めよ．可能であれば，n 次エントロピーを計算するプログラムを書け． 以下を示せ
I(X; Y) = H(X) – H(X | Y) ただし I(X; Y) = I(Y; X) I(X; Y) = H(X) + H(Y) – H(X, Y) ただし H(X, Y) は X と Y の結合エントロピー （X と Y をまとめて一個の確率変数と考える） （条件付きエントロピーの加重平均）