情報量とエントロピー 田浦健次朗

本日の範囲 コンピュータにおける情報の表現 ファイルとその中身 コンピュータの仕組み 通信・ネットワーク,インターネット 情報の符号化,その限界 ファイルとフォルダ コマンドライン プログラムの仕組み 通信の符号化,その限界 暗号 簡単なプログラムの作成・実行 Excelで計算・データの可視化 基礎的概念 (本講義中では)やや高度な概念 実技・実践

計算機による情報表現の基本 (人間が)計算機を通じて目にする「情報」には様 々なものがある 文字, 絵, 音, 動画, etc. 計算機はそれらすべての情報を 0/1 (bit)の列とし て表現する というよりもbitの列しか蓄積・処理できない 注:通常 8 bit 未満の単位で情報を蓄積・処理する ことはないので, 8 bitをまとめてバイト(byte)と呼 び, 「すべてをバイト列で表現する」というのが 実際に近い

用語: 符号化と復号化 符号化(encoding) (なんらかの意味のある)「情報」 → バイトの列 復号化(decoding) バイトの列 → (なんらかの意味のある)「情報」 「情報」 「情報」の符号 符号化 ○○さん こんにちは 226 151 139 226 151 ... 復号化 255 216 255 224 0 ... 212 0 124 218 26 34 58 29 ...

符号化にあたっての一般的な制約 (当然のことながら)符号から,元の情報が復元可能 でなくてはならない A → 00 B → 01 C → 000 D → 1 というわけにはいかない(0001はABなのかCDな のか?)

本日の内容 情報量と情報エントロピー 効率の良い符号化(圧縮) 情報源符号化定理

全体を通した動機付け 符号化の方法にも色々ある cf. 前回の演習 テキストファイル vs それをgzipで圧縮したもの BMPファイル vs JPEGファイル どうせ符号化するなら効率が良い(=必要なバイト 数が少ない)符号化を考えたい どのようにしたらそれが達成できるか? 限界はあるのか? 情報量やエントロピーは,それらに対する答えを 与えてくれる

準備:確率に関する用語の復習(1) 事象(event) ある確率で起こる事柄 よく使う記号: A, B, C, ... 例 サイコロを2個ふってたして10が出る 明日の天気が晴れ 画像中の(5,8)の画素が青である 文章の最初の文字が 'T' である P(A) : 事象Aが起こる確率

準備:確率に関する用語の復習(2) 確率分布(probability distribution) 起こりうる全事象とその確率の組の集合 { (A1, p1), (A2, p2), ..., (An, pn) } 注: ここおよび以降, 全事象は有限個と仮定する 事象に確率を割り当てる関数P(A)のこと,という 言い方もできる

確率分布の例(1) サイコロを2個ふって出た目の和 (2が出る, 1/36) (3が出る, 1/18) ... (12が出る, 1/36) 明日の天気 (晴, 1/2) (曇り,1/4) (雨, 1/4)

確率分布の例(2) X = 「英文中に現れる文字」 ('a', 0.03) ('b', 0.01) ...

確率変数(random variable) ある確率分布にしたがって定まる値 事象に付随する値という言い方もできる よく使う記号: X, Y, … 例: くじ引き 事象: 1等が当たる, 2等が当たる, はずれ 確率変数: 賞金(1等 → 5000円, 2等 →1000円, 3等 → 0円)

準備:確率変数の平均(期待値) X : 確率変数とし, 事象Aiに割り当てられた値をxi と書くことにする 例: サイコロの出た目に応じて賞金(出た目 1000円)がもらえる この時, その確率変数の平均(期待値)E(X)を, E(X) =  pi xi で定義する(pi= P(X = xi))

情報量:定義 確率pでおこる事象の情報量を, – log p で定義する. logの底は2とする 上式を以降 I(p)と書く

情報量  めずらしさ(ビックリ 度) いったい何が始まったのか? 「ある事象が起こった」という情報の「量」(大 雑把に言って,それが起きるということを知ること の貴重さ)を定量的に把握したい 「めずらしい」=「滅多に起こらない」=「確率 が小さい」事象ほど「情報量が多い」 情報量  めずらしさ(ビックリ 度)

それにしてもなぜ–log pなのか? 珍しさを数値化したいなら1/pだけでもいい それどころか任意のpの減少関数でよいのでは? 要請したい性質: 加法性 二つの独立な事象AとBが「両方」おきたという 事象の情報量は,A, Bそれぞれの情報量の和であっ てほしい (AかつB)の情報量 = Aの情報量 + Bの情報量 つまりI(pq) = I(p) + I(q)

情報量の定義の心(まとめ) I(p)が満たすべき性質 pに関して単調減少, 微分可能 I(pq) = I(p) + I(q) これとIの微分可能性を仮定するとI(p) = k log pが 導かれる(k : 定数) 定数kは重要ではないがあとはとりあえず I(1/2) = 1 としておくことで, k = – 1

Xのエントロピー H(X) = i – pi log pi エントロピー:定義 確率変数Xのエントロピーを,「Xの事象の情報量 の平均」と定義する(実際, Xの「平均情報量」と も言う). つまり Xのエントロピー H(X) = i – pi log pi

エントロピーが大きい分布とは?

エントロピーと符号長 動機付け: 英語のテキストファイルをファイルに 格納する(符号化する)ことを考える 通常用いられる符号化(ASCII符号化; テキストフ ァイルで用いられる)では, 1文字に等しく8 bitを 割り当てる しかし, 例えば英語の文章には, スペースが多い, 'e'や'a'がよく現れる, などの特徴(偏り)がある これを利用した, 「もっとよい符号化」はないも のか?

基本アイデア よく現れる文字には短い符号を,滅多に現れない 文字には長い符号を割り当てる これで「平均」符号長はもっと短くできるので はないか?

問題の定式化と仮定 ある「確率分布」がわかっているとする 文字はその一定の確率分布からひかれる 複数回ひいた場合も各回独立とする (independently and identically distributed; i.i.d) 注:現実はそうでない場合もある(英語で'q'の次は ほぼ確実に'u'など) 問題: 一文字あたりの平均符号長を最小化せよ

直感 よくでてくる(確率が大きい)文字 → 短い符号 滅多にでない(確率が小さい)文字 → 長い符号

制約: なぜいくらでも短い符号は作れないのか? 復号化可能であるための条件(クラフトの不等式) 文字aiに符号長liを割り当てた(i = 1, ..., n)とき, 1 2 𝑙 1 +...+ 1 2 𝑙 𝑛 ≤1

情報源符号化定理 限界 平均符号長  H(X) 朗報 平均符号長 < H(X) + 1なる符号化は作成可能 どうやって? 大雑把には,確率pの文字に対し,符号 長 –log p (その文字の情報量分のビット数)を割り 当てる

ハフマン符号化 情報源符号化定理で言うところの効率を持つ符 号の実際の作り方 入力: n個の記号S1, S2, ..., Snが現れる確率p1, p2, ..., pn 出力: 各記号に割り当てる符号(0/1の列) S1 0.6 S2 0.08 S3 0.07 S4 0.13 S5 0.1

ハフマン符号化のやり方 ハフマン符号の「木」を作る(符号はそこから自動 的に定まる) 初期状態: 各記号に対応する「親の無い」点を作る 以下を, 親のない点が一つになるまで繰り返す: 親のない点の中で確率最小のもの二つをとり, 両者 の親を作る(その親の確率は二つ点の確率の和とす る) 各点の子供への枝の一つに符号0, もう一つに1を割 り当て, 各記号(木の葉)には,木の根からそこへ至る 枝に付いている符号の列を割り当てる

S1 0.6 S2 0.08 S3 0.07 S4 0.13 S5 0.1 S23 0.15 S1 0.6 S2 0.08 S3 0.07 S4 0.13 S5 0.1 S23 0.15 S45 0.23 S1 0.6 S2 0.08 S3 0.07 S4 0.13 S5 0.1

S2345 0.38 S23 0.15 S45 0.23 S1 0.62 S2 0.08 S3 0.07 S4 0.13 S5 0.1 S12345 1.0 S2345 0.38 ハフマン符号木 S23 0.15 S45 0.23 S1 0.62 S2 0.08 S3 0.07 S4 0.13 S5 0.1

S12345 1.0 1 S2345 0.38 1 S23 0.15 S45 0.23 1 1 S1 0.62 S2 0.08 S3 0.07 S4 0.13 S5 0.1 100 110 101 111 ハフマン符号