Information Theory

この講義について
担当：楫勇一（かじゆういち），ソフトウェア基礎学研究室
３年前まで，全１５回の専門科目として実施
ベーシックな部分を抜き出し，全８回の基礎科目として再構成
基本的に，情報系以外の学部を卒業した学生向け
少し専門的な内容は，III期の「符号理論」にて
情報を正確に，効率よく伝えるための理論と技術を学ぶ
本講義スライド
http://isw3.naist.jp/~kaji/lecture/
1
about this class
This class is given in Japanese.
English slides are available at
http://isw3.naist.jp/~kaji/lecture/12/
but the slides are based on an previous version of this course;
15-classes
more extensive
Use them with your own risk.
Feel free to visit me @ A615.
2
情報理論
1948年の C. E. Shannon の論文からスタート
情報通信の数学的側面に着目
今日のデジタル技術に多大な影響
有線・無線の通信・放送技術
CD/DVD/HDD等のデータ記録技術
データ圧縮
Claude E. Shannon
1916-2001
暗号，言語学，バイオ情報学，ゲーム理論，...
本講義では，情報理論の基礎的な知見について学ぶ
3
講義の構成
最初の能書き＋３つの章:
能書き：講義内容全体の予告編
chapter 1: 情報を測る
chapter 2: 情報をコンパクトに表現する
chapter 3: エラーから情報を守る
4
シャノン当時の時代背景を知る
1940年代の通信技術...
電信が広い用途で一般的に使われていた
モールス符号：「トン ( ∙ )」と「ツー ( − )」の記号の組み合わせ
トン = 1 単位時間, ツー = 3 単位時間
記号と記号の間は，1単位時間の空白
英文字間は3単位，英単語間は8単位時間の空白
10101000111000101110001011101000111
00000001110100011101110111000101110111
ある意味で，「デジタル通信」が既に用いられていた
5
情報処理の自動化・機械化
通信の一部を自動化する「装置」が出現
Teletype model 14-KTR, 1940
http://www.baudot.net/teletype/M14.htm
Enigma machine
http://enigma.wikispaces.com/
機械...人間より高速で，ミスを犯さない（と思われていた）
当時の興味の方向性：限られた資源（時間，通信路）の中で...
【効率の問題】どれだけ多くの情報を伝えることができるか
【信頼性の問題】どれだけ正確に情報を伝えることができるか
6
通信のモデル
通信は，下記のようにモデル化できる
伝送路
情報源
送信機
（符号化器）
雑音源
受信機受領者
（復号器）
C.E. Shannon, A Mathematical Theory of Communication,
The Bell System Technical Journal, 27, pp. 379–423, 623–656, 1948.
通報
通信＝広い意味での情報の伝達
7
効率的であるとは
通信を効率化する＝ B のサイズを小さくする
ただし A = D （または A ≈ D）の必要あり
通信路に雑音あり(B ≠ C ), 雑音なし (B = C)の２つのケース
A
B
C
D
8
問題その１：効率性
例：天気を毎日記録したい（情報源＝天気）
通報 = {晴, 曇, 雨}
記録には “0” と “1”だけが使用可能（空白等の使用はNG）
天気
晴
曇
雨
符号語
00
01
10
0100011000
1日当たり2ビットの記号を送信することになる
送信すべきビット数を減らすことができれば，より効率的
9
良い符号はあるか？
天気
晴
曇
雨
符号 A
00
01
10
符号 B
00
01
1
符号 A...0100011000
符号 B...010001100
符号 B のほうが，よりコンパクトに情報を表現できる
符号語の長さが違っているが，正しく復号できるか?
先頭から処理すれば問題ナシ
符号 B よりも良い符号はあるか?
Yes でもあり，No でもある(→ 次ページ)
10
「平均」で考える
天気の発生確率は，一般には均等でない...
天気
晴
曇
雨
確率
0.5
0.3
0.2
符号 A 符号 B 符号 C
00
00
1
01
01
01
10
1
00
一日あたりの記録に必要なビット数は
符号 A：2.0 bit
符号 B：20.5 + 20.3 + 10.2 = 1.8 bit
符号 C：10.5 + 20.3 + 20.2 = 1.5 bit
... 「工夫次第で，効率的な符号を作ることができる」
11
最良の符号
たとえば，一日あたり，平均 0.0000000001 bit で表現できる？
...無理っぽい
「どこかに限界がある」ことは，直感的にわかる
シャノン：「どこに限界があるのかを数学的に解明したい」
→ この確率分布では，一日あたり 1.485 ビットが絶対に必要
天気
晴
曇
雨
確率
0.5
0.3
0.2
天気の情報そのものの「量」
「情報を格納する容器（符号語）のサイズは，
格納される情報の量よりも小さくできない」
12
本講義の前半部分について
能書き：講義内容全体の予告編
chapter 1: 情報を測る
情報を定量的に測るための技術に
ついて学ぶ
chapter 2: 情報をコンパクトに表現する
情報をコンパクトに表現するための
技術と限界について学ぶ
chapter 3:エラーから情報を守る
13
信頼性の高さとは
通信の信頼性を上げる＝「A = D （または A ≈ D）」を保証する
雑音の影響により，B ≠ Cとなるおそれがある
B のサイズをあまり大きくせず，A = Dとなる確率を上げたい
A
B
C
D
14
問題その２：信頼性
伝送路は，必ずしも信頼できるものではない
送信情報 ≠ 受信情報
ABCADC
ABCABC
伝送路上での誤りを根絶することは難しい
日常会話では...「符丁」の利用により問題回避
ABC
Alpha, Bravo, Charlie
あさひの「あ」
いろはの「い」
Alpha, Bravo, Charlie
ABC
15
符丁とは
送りたい通報
誤り対策のため，やむを得ず
付加する冗長な記号
＝
必要のない
余分な
符丁では，冗長な記号を故意に付加する
冗長記号により，誤りを訂正可能とする
→これと同種の機構を，0-1 データ上で実現したい
16
冗長性について
Q. どうやって 0-1 データに冗長性を付加するか？
A. パリティビットを使えばよい
パリティビットとは...
データ中の1 の個数を偶数にするための「追加ビット」
00101 → 001010 (２個の1 → ２個の 1)
11010 → 110101 (３個の1 → ４個の 1)
パリティビットを一個使うと，奇数個のビット誤りを検出可能
17
誤りを訂正するには？
パリティビットを複数使うと，誤りを訂正できる（場合もある）
例: ４ビットデータ (a0, a1, a2, a3)に対し，パリティビットを５個付加
a0
a1
p0
a2
a3
p1
q0
q1
r
符号語 =
(a0, a1, a2, a3, p0, p1, q0, q1, r)
18
誤り訂正の例
1011 を送信する...
100110011 が受信された...
1
0
1
1
0
1
○
1
1
0
0
1
0
×
0
1
1
0
1
1
○
×
○
○
符号語 = 1 0 1 1 1 0 0 1 1
１ビット誤りを訂正可能
（だが，あまりにも安直）
3ビット目が怪しい...
「送信されたのは101110011 だろう」
19
本講義の後半部分について
能書き：講義内容全体の予告編
chapter 1: 情報を測る
chapter 2: 情報をコンパクトに表現する
chapter 3:エラーから情報を守る
誤りを発見し，訂正するための技術に
ついて学ぶ
20
授業日程
火曜１限（9:20～10:50）
4/7, 14, 21, 28, 5/12, 19, 26, 6/2
5/26 は休講（補講日程調整中）
中間レポート... 4月末前後
試験... 6月 2日（最終回の講義）
講義資料（本スライド）
http://isw3.naist.jp/~kaji/lecture/
http://isw3.naist.jp/~kaji/lecture/12/
(old version in English)
21
chapter 1:
情報を測る
22
測るべき「情報」
情報とは，何かを伝えるもの．ただし...
まったく興味のないことを教わっても，「情報」とは思わない
わかりきったことを教わっても，「情報」とは思わない
情報とは...
不確実性を持つ興味対象について，その不確実さを減らすもの
Before
After
不確実さが
大きい
不確実さが
小さい
23
興味対象を，どのように表現するか
興味対象は様々
明日の天気，野球の試合結果，テストに出る問題，
友人の予定，夕食のおかず ...
現実の細部はバッサリと切り落とし，確率・統計の世界で考える
興味対象は，確率変数の値
どれくらいの確率で，どの値を取るかはわかっている
実際に発生する（発生した）値は，いまのところ不明
「サイコロの目」が典型例
24
復習：確率変数とは
確率変数 𝑋 ：中身を覗けない「箱」のようなもの
箱の中には， 𝑣1 , … 𝑣𝑀 のどれか一個が入っている
何が入っているかは，箱を開けてみないとわからない
𝑣1 , … , 𝑣𝑀 ...確率変数の実現値と呼ぶ
実現値の集合... 𝐷 𝑋 = {𝑣1 , … , 𝑣𝑀 } と書く
𝑋 = 𝑣𝑖 である確率が 𝑝𝑖 のとき
𝑃𝑋 𝑣𝑖 = 𝑝𝑖 と書く
𝑝1 + ⋯ +𝑝𝑀 = 𝑣∈𝐷 𝑋 𝑃𝑋 𝑣 = 1
25
復習：確率変数の例
「サイコロの目を，確率変数𝑋で表す」
𝑋の値は1, 2, … , 6 のどれか，全部同じ確率
𝐷 𝑋 = {1,2,3,4,5,6}
𝑃𝑋 1 = 𝑃𝑋 2 = 𝑃𝑋 3 = 𝑃𝑋 4 = 𝑃𝑋 5 = 𝑃𝑋 (6) = 1/6
「今夜のメニューを確率変数𝑋で表す」
𝐷 𝑋 = {カレー, とんかつ, ラーメン, … }
𝑃𝑋 (カレー) = 1/6, 𝑃𝑋 (とんかつ) = 1/4, ...
26
情報の伝達と確率変数
確率変数 𝑋の値を知りたい
𝑋の実現値の集合や，確率分布は既知
実際に 𝑋 が取った値は不明
𝑋の値について，なんらかの情報を得る
𝑋の確率分布が変化する
正確で完全な情報
⇒ 𝑋 の値が一意に定まる
不正確，不完全な情報
⇒ 多少の不確実さが残る
27
情報伝達の例
𝑋はサイコロの目を表す確率変数，𝑃𝑋 (1) = ⋯ = 𝑃𝑋 (6) = 1/6
1/6
不確実さ：大
1 2 3 4 5 6
① 「𝑋は 4だ」
1
② 「𝑋は 3の倍数ではない」
1/4
不確実さ：0
1 2 3 4 5 6
不確実さ：小
1 2 3 4 5 6
28
情報の「量」と不確実さ
① 「𝑋は 4だ」
② 「𝑋は 3の倍数ではない」
1
1/4
①
1 2 3 4 5 6
②
1 2 3 4 5 6
after
「情報量＝不確実さの削減量」
として定義するのが自然
before
直感的には ...
①のほうが②よりも大きな「情報量」を持つ，ように思われる
① ... 不確実さを大きく削減
② ... 不確実さを少しだけ削減
情報量
29
この後のシナリオ
最終目標：「情報」の量を測る定量的指標を導入する
step 1: 確率変数の「エントロピー」を定義
エントロピー大  不確実さ大
今日
次回
step 2: 一つのニュースが持つ情報量を定義
情報量= (BEFORE エントロピー) – (AFTER エントロピー)
step 3: 確率変数の間の相互情報量を定義
ある確率変数の値が，他の確率変数について何を語るか
𝑋
𝑌
30
エントロピーの定義
確率変数𝑋... 以下の値と確率分布を持つ
... 𝑣
𝑣
𝑣
（値は，あまり重要でない）
値 1 2
𝑀
... 𝑝
（確率値が重要）
確率 𝑝1 𝑝2
𝑀
𝑋 の（一次）エントロピー
𝑀
𝐻1 (𝑋) =
−𝑝𝑖 log 2 𝑝𝑖 =
𝑖=1
−𝑃𝑋 (𝑣) log 2 𝑃𝑋 (𝑣) (bit)
𝑣∈𝐷(𝑋)
（ただし，0log 2 0 = 0とする）
−log 2 𝑝𝑖 の平均（期待値）と考えることもできる
−log 2 𝑝𝑖 を，値𝑣𝑖 の自己エントロピーと呼ぶ場合も
31
自己エントロピーの直感的意味付け
自己エントロピー −log 2 𝑝
... 確率𝑝の出来事が起こったと
知ったときの「驚き」の量
𝑝に対して単調減少
... 滅多にないことが起こる（𝑝が小さい）と，驚きが大きい
𝑝 > 0で連続
... 同程度の確率であれば，驚きも同程度
𝑝 = 𝑞1 𝑞2 ならば，− log 𝑝 = − log 𝑞1 − log 𝑞2
... 驚きの「加法性」に対応している（次ページ）
32
驚きの加法性
トランプのカードを一枚引く
𝑁1 =「ダイヤの５だった」... 1/52の確率
𝑁2 =「ダイヤだった」... 1/4の確率
𝑁3 =「５だった」... 1/13の確率
𝑁1 を知ったときの驚き
1
− log 2
52
𝑁2 を知り，その後に
𝑁3 を知ったときの驚き
1
1
− log 2 − log 2
4
13
自己エントロピーは，我々の直感的な理解と良く対応している
33
エントロピーの定義（再）
𝑋 の（一次）エントロピー
𝑀
𝐻1 (𝑋) =
−𝑝𝑖 log 2 𝑝𝑖 (bit)
𝑖=1
確率で重み付けした，自己エントロピーの平均値
確率変数の値が与える「驚き」の平均値＝不確実さ
− log 2 𝑝
−𝑝 log 2 𝑝
34
エントロピー計算の例（１）
コインを投げて出た面を確率変数𝑋で表す
𝑋の取りうる値は「表」か「裏」の２種類
𝑃𝑋 表 = 𝑃𝑋 裏 = 1/2
𝐻1 𝑋
1
2
1
2
1
2
= − log 2 − log 2
1
2
1
2
= − log 2 = log 2 1 = 1 bit
1bit の情報は，２進数１桁で表現できる ⇒ Chapter 2
35
エントロピー計算の例（２）
２枚の異なるコインを投げる
𝑋 ∈ { 表，表，表，裏，裏，表，裏，裏 }
𝑃𝑋 (表, 表) = ⋯ = 𝑃𝑋 (裏, 裏) = 1/4
𝐻1 𝑋
1
4
1
4
1
4
1
4
1
4
1
4
1
4
= − log 2 − log 2 − log 2 − log 2
1
4
1
4
= − log 2 = log 2 22 = 2 bit
コイン１枚のときの２倍のエントロピー ...不確実さが「２倍」
36
エントロピー計算の例（３）
サイコロ投げ
𝑋の取りうる値は 1, 2, 3, 4, 5, 6
𝑃𝑋 1 = 𝑃𝑋 2 = ⋯ = 𝑃𝑋 6 = 1/6
𝐻1 𝑋
1
6
1
6
1
6
1
6
1
6
= − log 2 − log 2 ⋯ − log 2
1
6
1
6
= − log 2 = log 2 6 = 2.585 bit
コイン投げのときと同じ尺度で比較ができる
37
エントロピー計算の例（４）
公正でないサイコロ
𝑋の取りうる値は 1, 2, 3, 4, 5, 6
𝑃𝑋 1 = 0.9, 𝑃𝑋 2 = ⋯ = 𝑃𝑋 6 = 0.02
𝐻1 𝑋
= −0.9 log 2 0.9 − 0.02 log 2 0.02 ⋯ − 0.02 log 2 0.02
= 0.701 bit
コインを１枚投げるときより，不確実さが小さい
38
唯一尺度としてのエントロピー
𝐻1 𝑋 = 1
𝐻1 𝑋 = 2
𝐻1 𝑋 = 2.585
𝐻1 𝑋 = 0.701
様々な現象に対し，エントロピーを計算できる
違ったタイプの現象の「比較」ができる
エントロピーが何を意味するのか ... これから議論
39
本日のまとめ
講義概要
エントロピーの定義
復習問題（レポートではありません）
講義 webページにあるデータを使い，エントロピーを計算せよ
http://isw3.naist.jp/~kaji/lecture/
英語の文字出現頻度
株価の騰落データ
40

Download Report