Microsoft PowerPoint - 2.ppt [互換モード]

Transcription

1 前 回 の 練 習 問 題 無 記 憶 非 定 常 な 情 報 源 を一 つ 例 示 せよ 時 刻 t に t 枚 のコインを 投 げるとき, 表 が 出 る 枚 数 以 下 のマルコフ 情 報 源 について, 状 態 の 定 常 確 率 分 布 を 求 めよ 通 報 A, Bの の 定 常 確 率 を 求 めよ A/.4 A/.5 B/.6 B/.2 B/.5 2 A/.8 w, w, w 2 =.,.7,.2 A =.7 B =.3

2 前 回 の 補 足 :マルコフ 情 報 源 が 既 約 であること 既 約 irreducibleマルコフ 情 報 源 任 意 の 状 態 から 任 意 の 状 態 に 遷 移 可 能 なマルコフ 情 報 源 厳 密 には... 時 刻 t の 状 態 を 変 数 X t で 表 現 するとき, 任 意 の 時 刻 i, j i < j および 任 意 の 状 態 s i, s j に 対 し,X j = s j X i = s i > であること 無 限 個 の 状 態 を 持 つマルコフ 連 鎖 では, 既 約 であっても, X j = s j X i = s i となるケースもある 収 束 一 致

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

4 記 憶 のない 情 報 源 のエントロピー 以 下 の 通 報 発 生 確 率 を 持 つ, 記 憶 のない 定 常 情 報 源 S を 考 える a a... 通 報 2 a M... 確 率 p p 2 p M 情 報 源 S の 一 次 エントロピー first-order entropy: H M S p i log 2 p i ビット, bit 例 : i この 項 は 非 負 エントロピーは 常 に 以 上 コイン 投 げのエントロピー: 表, 裏 とも 確 率 /2...M = 2, p =p 2 =.5 H S.5log.5.5log.5 log/ 2 ビット 4

5 エントロピーの 計 算 例 例 2:サイコロの 目...コイン 投 げより, 結 果 予 想 は 難 しいはず 通 報 確 率 /6 /6 /6 /6 /6 /6 H S log 6 6 log log ビット 例 3:イカサマ 賭 博 のサイコロ 通 報 確 率 H S.9 log.9.2log log.2.7 ビット 一 個 の 指 標 で, 予 測 の 難 しさの 大 小 関 係 を 定 義 可 能 5

6 予 想 の 難 しさとエントロピー: 二 元 情 報 源 の 場 合 通 報 が またはの, 記 憶 のない 二 元 情 報 源 S を 考 える, の 発 生 確 率 が p, p のとき, H S p log p plog p ビット この 値 をHp と 表 記 する 二 元 エントロピー 関 数 p=.5のとき,. Hp は 最 大 値 を 取 る Hp p が, に 近 づくとき, Hp は に 近 づく 予 想 のしやすさとエントロピーの.5. p 間 には, 相 関 関 係 がある 6

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

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

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

10 記 憶 のない 情 報 源 の 拡 大 とエントロピー S:, をそれぞれ 確 率 8.8, 2で.2 で 発 生 する 記 憶 のない 情 報 源 S H S=.8log.8 8l 8 2l.2log.2 2= S H S 2 =.64log.64.6log.6.6log.6.4log.44log 4 = H 2 S = H S 2 /2 =.44/2 =.72 この 情 報 源 では, 任 意 の n に 対 して H S n =.72n となる H n S = HS = 極 限 エントロピー= 一 次 エントロピー

11 記 憶 のない 情 報 源 の 拡 大 とエントロピ 記 憶 のない 情 報 源 の 拡 大 とエントロピー 定 理 : 任 意 の 無 記 憶 な 定 常 情 報 源 S に 対 し H S n =nh S 定 理 : 任 意 の 無 記 憶 な 定 常 情 報 源 S に 対 し,H S = nh S. 証 明 :n = 2の 場 合 を 考 える log 2 S H 無 記 憶 だから log, log, S H M M 無 記 憶 だから, = log log log log log log 確 率 の 2 g g S H S H S H 確 率 の 総 和 は 系 : 任 意 の 無 記 憶 な 定 常 情 報 源 S に 対 し,H S = H S.

12 記 憶 のある 情 報 源 :マルコフ 情 報 源 の 場 合 /.9 /. /.4 /.6 各 通 報 の 定 常 確 率 : = =.2 定 常 確 率 分 布 は w =.8, w =.2 H S =.722 不 一 致 = =.8 H S 2 = =.8 H 2 S = H S 2 /2 = =.2 文 字 を2 個 予 測 するより,2 文 字 まとめてのほうが 予 測 しやすい 前 スライドの 定 理 は, 記 憶 のある 情 報 源 では 成 立 しない 2

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

14 極 限 エントロピーの 計 算 例 /.9 /. 極 限 分 布 は w =.8, w =.2 /.4 /.6 状 態 :=.9, =.の 情 報 源 HS = H.9 =.469 状 態 :=.4, =.6の 情 報 源 HS = H.4 =.97 状 態 に 居 る 確 率 8%,に 居 る 確 率 2%なので, 加 重 平 均 は = これが 極 限 エントロピー ちなみに,HH S =.722,H H 2 S =.6457,... 単 調 減 少? 4

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

16 情 報 源 の 記 憶 とエントロピー 定 常 確 率 8で.8 で を,.2 2でで を 出 力 する 情 報 源 を 考 える /.8 /.9 /. /.4 /.6 /.2 記 憶 無 し 記 憶 あり.72 一 次 エントロピー 極 限 エントロピー.5694 記 憶 のある 情 報 源 では, ブロック 化 したほうが 都 合 良 い 場 合 も プロセッサの 条 件 分 岐 予 測 など 6

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

18 野 球 の 試 合 の 例 では メイルを 受 け 取 る 前 : 勝 =/3 /3, 引 = /3, 負 = /3 エントロピーは log log log log3.585 メイルを 受 け 取 った 後 : 勝 = /2, 引 = /2, 負 = 条 件 付 きエントロピーは log log log 阪 神 は 負 けなかった というメイルに 含 まれる 情 報 量 :.585 =.585 ビット 8

19 情 報 量 とエントロピー 離 れたところにある 情 報 源 S の 出 力 通 報 を 知 りたい 通 報 の 確 率 分 布 はわかるが, 実 際 に 発 生 した 通 報 は 不 明 S の 出 力 に 関 し,なんらかの ヒント を 入 手 したとする ヒントにより, 通 報 の 確 率 分 布 が, 別 の 情 報 源 S の 確 率 分 布 と 一 致 することがわかったとする このとき,ヒント 通 報 がもたらした 情 報 量 information は HS HS ビット 9

20 気 まぐれな 友 人 の 場 合 case 右 図 の 行 動 を 取 る 友 人 Bが 勝 ち 勝 ったよ 言 いたくない と 言 った 時 の.5. 引 分 言 いたくない 情 報 量 は? 5.5 負 け.5 負 けたよ 言 いたくない = 2/3 勝 ち, 言 いたくない = /6 勝 ち 言 いたくない = /4 引 分, 言 いたくない = /3 引 分 言 いたくない = /2 負 け, 言 いたくない = /6 負 け 言 いたくない = /4.5 言 いたくない と 言 っているときのエントロピーは log log log 情 報 量 は =.85ビット 友 人 Aのメイル:.585ビット 2

21 気 まぐれな 友 人 の 場 合 case 2 友 人 Bが 勝 ったよ と 言 った 勝 ち 勝 ったよ ときの 情 報 量 は?.5. 引 分 言 いたくない 勝 ったよ =/6 5.5 勝 ち, 勝 ったよ = /6 負 け 負 けたよ 勝 ち 勝 ったよ = 引 分 勝 ったよ = エントロピーはになる 負 け 勝 ったよ = 結 果 を 正 確 に 知 ることができる 情 報 量 は.585 =.585ビット 友 人 Aのメイル:.585ビット.5.5 p.7 の 友 人 Aと,この 友 人 B,どちらが 頼 りになる 友 人 か?... 個 々の 通 報 の 情 報 量 だけを 見 ていたのではわからない 2

22 情 報 量 の 平 均 友 人 Bの 行 動 : /6 の 確 率 で 勝 ったよ... 情 報 量.585ビット 2/3 の 確 率 で 言 いたくない... 情 報 量.85ビット85ビット /6 の 確 率 で 負 けたよ... 情 報 量.585ビット 平 均 すると.585 / / /6 =.585ビット 友 人 Aの 行 動 : 2/3の 確 率 で 負 けなかった... 情 報 量.585ビット 勝 ち /3の 確 率 で 負 けたよ... 情 報 量.585ビット 平 均 すると.585 2/ /3 =.98ビット 引 分 負 け 負 けなかった 負 けたよ 平 均 すると, 友 人 Aのほうが.333ビット 多 くの 情 報 をくれる 22

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

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

25 相 互 情 報 量 の 計 算 例 天 気 予 報 : 天 気 についての 情 報 を 与 える,やや 不 正 確 な 通 信 路 例 : 日 間 の 実 際 の 天 気 X と 天 気 予 報 Y の 統 計 : 晴 X 雨 Y Y 晴 雨 X X 現 実 Y 予 報 実 際 の 天 気 が 晴 だったのは57 日, X 晴 =.57 予 報 が 晴 といったのは6 日, Y 雨 =.6 天 気 X, 予 報 Y とも 晴 だったのは45 日, X,Y 晴, 晴 =.45 25

26 相 互 情 報 量 の 計 算 例 2 晴 X 雨 Y Y 晴 雨 X 天 気 予 報 が 当 たる 確 率 = X,Y 晴, 晴 + X,Y 雨, 雨 =.73 この 予 報 と 友 人 Aのメイル,どちらが 高 性 能? 天 気 のエントロピー: H X X.57log.57.43log ビット 26

27 相 互 情 報 量 の 計 算 例 3 天 気 予 報 Yが 晴 のとき: 本 当 に 晴 れる 確 率 は.45/.6 =.75, 雨 の 確 率 は.25 晴 という 予 報 を 聞 いた 後 の 条 件 付 エントロピーは HX 晴 =.75log.75.25log.25 =.8 ビット 晴 という 天 気 予 報 の 持 つ 情 報 量 は =.75 天 気 予 報 Yが 雨 のとき: 本 当 に 雨 の 確 率 は.28/.4 =.7, 晴 の 確 率 は.3 雨 という 予 報 を 聞 いた 後 の 条 件 付 エントロピーは HX 雨 =.3log.3.7log.7 =.88 ビット 雨 という 天 気 予 報 の 持 つ 情 報 量 は =.5 加 重 平 均 をとると =.47 ビット 27

28 相 互 情 報 量 と 当 たる 確 率 A 社 : まぁまぁ 当 たる 予 報 晴 X 雨 Y B 社 : 絶 対 はずれる 予 報 晴 X 雨 Y Y 晴 雨 Y 晴 雨 X %.47ビット X %.986ビット 情 報 の 量 は,B 社 予 報 のほうが 大 きい 28

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

30 練 習 問 題 2ページの 例 において,3 次,4 次 のエントロピーを 求 めよ. 可 能 であれば,n 次 エントロピーを 計 算 するプログラムを 書 け. 以 下 を 示 せ IX; Y = HX HX Y ただし H X Y y H X Y y IX; Y = IY; X IX; Y =HX +HY HX, Y y 条 件 付 きエントロピーの 加 重 平 均 ただし HX, Y は X と Y の 結 合 エントロピー X と Y をまとめて 一 個 の 確 率 変 数 と 考 える 3