Microsoft PowerPoint - 情報科学概論-10.ppt [互換モード]

情報科学概論 ２回目

情報科学概論 ２回目

「モノとしての情報」 「モノとしての情報」 「情報」を，工学の対象物として取り扱うための理論と技術 情報を測る 情報の量 情報伝達系の性能を数値として測る 情報の量，情報伝達系の性能を数値として測る 確率論をベースに，人間の直観にあった定式化を行う 情報を伝える 情報をできるだけコンパクトに表現する 情報をできるだけコンパクトに表現する 情報をできるだけ確実に伝える 1

出欠確認 課題

出欠確認・課題

情報通信以外の分野で 情報理論の技術や考え方が 情報通信以外の分野で，情報理論の技術や考え方が 利用できる分野，技術，応用，ビジネスを考えよ 出席届兼用の用紙に記入，本講義終了時に提出 知識を問うのではなく，「発想」「着眼点」を評価します． 「ナルホド」「面白い」と思わせる回答を期待しています 「ナルホド」「面白い」と思わせる回答を期待しています 情報の学生に対する注意 情報の学生に対する注意： 今回の内容は「情報理論」のサブセット 上記課題について 高いレベルの回答を期待します 2 上記課題について，高いレベルの回答を期待します http://narayama.naist.jp/~kaji/lecture/

第

部 「情報量」をどうとらえるか

良い自動車を作りたい

第一部：「情報量」をどうとらえるか

良い自動車を作りたい... 時間や距離，燃料の量などを正確に計量できないと難しい 良い「情報システム」を作りたい... 情報の量を測り 数値として表現することが必要 情報の量を測り，数値として表現することが必要 情報の「量」： 情報の「量」： 人間の直観と乖離した定義では意味がない 我々が漠然と考えている「情報量」にマッチする定義が必要 我々が漠然と考えている「情報量」にマッチする定義が必要 どういうときに「情報を得た」と考えるか？ どういうときに「情報を得た」と考えるか？ http://narayama.naist.jp/~kaji/lecture/

情報の獲得

情報の獲得

情報を得る ＝ 対象物に関する「不確かさ」が減少すること 情報を得る ＝ 対象物に関する「不確かさ」が減少すること 昨日の野球の試合結果 何も知らないと 勝敗はわからない 昨日の野球の試合結果，何も知らないと，勝敗はわからない 友人から「昨日の試合，勝てなかった」と聞いた（情報を得た） 情報を得る前：勝ち，負け，引き分けの３通り...不確かさ大 情報を得た後：負け 引き分けの２通り 不確かさ小 情報を得た後：負け，引き分けの２通り...不確かさ小 「情報量 不確かさの減少量」とするのが自然 「情報量 ＝ 不確かさの減少量」とするのが自然 「不確かさ」の定量化が先決

情報源と通報

情報源と通報

情報伝達のモデル： 情報伝達のモデル： 情報源で発生した事象を，通信路が伝達し，観測者が受信 事象を表現する具体的な「モノ」 通報と呼ぶ 事象を表現する具体的な「モノ」...通報と呼ぶ 「通報≠ 情報」である点に注意 e ? 通信路 情報源 e ? e’ e 観測者 情報源の統計的性質は既知，実際に発生する通報は未知 通信路は，正確に通報を伝達しないかもしれない 5

情報伝達の例

情報伝達の例

情報伝達の多くは 概念上 前スライドのモデルとして表現可能 情報伝達の多くは，概念上，前スライドのモデルとして表現可能 「イベント」 「通信路の出力」： 「イベント」– 「通信路の出力」： 「野球の試合結果」– 「友人からの速報メール」 「プログラムの出力」 「ファイルからの読み出しデータ」 「プログラムの出力」– 「ファイルからの読み出しデータ」 「明日の天気」– 「天気予報」 「画像デ タ」 「ＪＰＥＧ圧縮デ タ」 「画像データ」– 「ＪＰＥＧ圧縮データ」 「敵軍隊の指令文書」– 「盗聴で得た暗号文」 「イベント」「通信路」という言葉にとらわれ過ぎる必要はない 66 http://narayama.naist.jp/~kaji/lecture/

情報源の分類

情報源の分類

情報源の分類 情報源の分類 アナログ情報源vs. デジタル情報源 通報がアナログ的か デジタル的か 通報がアナログ的か，デジタル的か 記憶のある情報源vs 記憶のない情報源 記憶のある情報源vs. 記憶のない情報源 発生する通報に相関があるか，独立しているか 定常情報源vs. 非定常情報源 統計的な振舞いが 時間に対して不変か そうでないか 統計的な振舞いが，時間に対して不変か，そうでないか http://narayama.naist.jp/~kaji/lecture/

典型的な情報源

定常で記憶のない デジタル情報源

典型的な情報源

定常で記憶のない，デジタル情報源 通報の集合は離散集合により与えられる 発生する通報は 以前の通報とは独立して決定される 発生する通報は，以前の通報とは独立して決定される 時刻をシフトしても，通報の発生確率は変化しない サイコロの目やコイン投げの結果を想定すれば良い サイコロの目やコイン投げの結果を想定すれば良い 現実世界では 記憶のある情報源もかなり多い 現実世界では，記憶のある情報源もかなり多い 人間が使う自然言語 画像 音声等のデ タ 画像，音声等のデータ ...基本的に，本講義では（最初に少ししか）扱わない

情報源のエントロピ

情報源のエントロピー

S: 以下の通報発生確率を持つ（記憶の無い定常）情報源 S: 以下の通報発生確率を持つ（記憶の無い定常）情報源 a₁ p a₂ p a_M p ... ... 通報 確率 M 元情報源 p₁ p₂ pM 確率 情報源 S の一次エントロピー(first-order entropy): M



  M i i i p p S H 1 2 1( ) log (ビット, bit） の項は非負 例１： この項は非負 ⇒エントロピーは常に０以上 コイン投げのエントロピー：表，裏とも確率1/2...M = 2, p₁=p₂=0.5 1 ) 2 / 1 log( 5 . 0 log 5 . 0 5 . 0 log 5 . 0 ) ( 1 S     H ビット 9 ) g( g g ) ( 1

エントロピ の計算例

エントロピーの計算例

例２：サイコロの目 コイン投げより 結果予想は難しいはず 例２：サイコロの目...コイン投げより，結果予想は難しいはず 1 1/6 通報 確率 2 1/6 3 1/6 4 1/6 5 1/6 6 1/6 1/6 確率 1/6 1/6 1/6 1/6 1/6 585 . 2 6 1 log 6 1 6 1 log 6 1 6 1 log 6 1 ) ( 1 S     H ビット 6 6 6 6 6 6 例３：イカサマ賭博のサイコロ 1 0.9 通報 確率 2 0.02 3 0.02 4 0.02 5 0.02 6 0.02 701 . 0 02 . 0 log 02 . 0 ... 02 . 0 log 02 . 0 9 . 0 log 9 . 0 ) ( 1 S     H ビット 10 一個の指標で，予測の難しさの大小関係を定義可能 http://narayama.naist.jp/~kaji/lecture/

記憶のある情報源

記憶のある情報源

記憶のある情報源は多種多様 記憶のある情報源は多種多様 比較的シンプルなモデルとして，マルコフ情報源がある 0 1 0/0.9 1/0.1 状態間を遷移しながら通報発生 直観的には，「双六」のイメージ 0 1 0/0.4 1/0.6 スタート，ゴールはない 十分時間が経過した後（定常状態） 通報 確率 での振舞いを議論することが多い 上の例の場合 十分な時間が経過すると 通報/ 確率 上の例の場合，十分な時間が経過すると... 80%の確率で状態 “0”，20%の確率で状態 “1”を取っているはず （実際は，漸化式を立てて計算を行う） （実際は，漸化式を立てて計算を行う） http://narayama.naist.jp/~kaji/lecture/

マルコフ情報源のエントロピ

マルコフ情報源のエントロピー

0/0 9 1/0 1 80%の確率で状態 “0” 20%の確率で状態 “1” 0 1 0/0.9 1/0.1 0%の確率で状態 0/0.4 1/0.6 0 が発生する確率 0 8 0 9 0 2 0 4 0 80 0 が発生する確率... 0.8  0.9 + 0.2  0.4 = 0.80 1 が発生する確率... 0.8  0.1 + 0.2  0.6 = 0.20 ⇒ エントロピーは– 0 8log 0 8 – 0 2log 0 2 = 0 722 bit ⇒ エントロピ は– 0.8log 0.8 – 0.2log 0.2 = 0.722 bit

通報を「ブロック化」すると，興味深い振舞いが見られる （情報源からの通報を複数個まとめて，一個の通報とみなす）

ブロック化の例 記憶のない場合

ブロック化の例：記憶のない場合

コイン投げ２回分の通報を １ブロックにまとめる場合 コイン投げ２回分の通報を，１ブロックにまとめる場合... 通報は{表表, 表裏，裏表，裏裏} の４通り 表表 通報 表表 表裏 裏表 裏裏 1/4 通報 確率 表裏 1/4 裏表 1/4 裏裏 1/4 H (S2) l 4 2 ビ ト 結果予想は 個の場合の２倍難しい H₁(S2)=log 4 = 2 ビット...結果予想は一個の場合の２倍難しい H₁(S2)は，S の通報２個分のエントロピー 通報 個分に換算すると 2 _{ビ ト} ⇒ S の通報１個分に換算すると，H₁(S2_{)/2 = 1ビット} 記憶のない情報源では，ブロック化してもエントロピーは変化なし n 個まとめて予想する難しさ = n×（1 個だけ予想する難しさ） 13

マルコフ情報源とブロック化

マルコフ情報源とブロック化

0/0 9 1/0 1 80%の確率で状態 “0” 20%の確率で状態 “1” 0 1 0/0.9 1/0.1 0%の確率で状態 0/0.4 1/0.6 00 が発生する確率 0 8 0 9 0 9 0 2 0 4 0 9 0 72 00 が発生する確率... 0.8  0.9  0.9 + 0.2  0.4  0.9 = 0.72 01 が発生する確率... 0.8  0.9  0.1 + 0.2  0.4  0.1 = 0.08 10 が発生する確率 0 8 0 1  0 4 + 0 2  0 6  0 4 = 0 08 10 が発生する確率... 0.8  0.1  0.4 + 0.2  0.6  0.4 = 0.08 11 が発生する確率... 0.8  0.1  0.6 + 0.2  0.6  0.6 = 0.12 ⇒ エントロピーは1.2914bit...一文字あたりでは0.6457bit ブロック化しないときは0.722bit だった ⇒ブロ ク化により エントロピ が小さくな た 14 ⇒ブロック化により，エントロピーが小さくなった http://narayama.naist.jp/~kaji/lecture/

記憶のある情報源のエントロピ

一般に 記憶のある情報源では

記憶のある情報源のエントロピー

般に，記憶のある情報源では... H₁(Sn) / n（通報一個あたりのエントロピー）は，単調減少する H (Sn) / n は ある一定の値 H(S) に収束していく H₁(Sn) / n は，ある 定の値 H(S) に収束していく H₁(Sn) / n _H 1(Sn) / n < H1(S) 1( ) H(S) 1( ) 1( ) n 個まとめて予想する難しさ < n ×（1 個だけ予想する難しさ） n H(S) （ 個だけ予想する難しさ） ある程度，通報の出現パターンが「読める」 自然語だと，“qu” は高頻出，“qz” は，まず出現しない 無記憶の場合より，振舞いが予想しやすい ⇒ エントロピー小 http://narayama.naist.jp/~kaji/lecture/

第

部 折り返し地点

第一部：折り返し地点

ここまでは，「情報源の予測の難しさ」の定量化 ここからは「情報量」の定義 ここからは「情報量」の定義

通報の持つ情報量

通報の持つ情報量

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

野球の試合の例では

野球の試合の例では

メイルを受け取る前：P(勝) = 1/3 P(引) = 1/3 P(負) = 1/3 メイルを受け取る前：P(勝) = 1/3. P(引) = 1/3, P(負) = 1/3 エントロピーは 585 1 3 l 1 l 1 1 l 1 1 l 1 _{log3 1.585} 3 log 3 3 log 3 3 log 3      メイルを受け取った後：P(勝) = 1/2. P(引) = 1/2, P(負) = 0イ を受け取 後 (勝) (引) , (負) 条件付きエントロピーは 1 2 log 0 1 log 1 1 log 1 _{   }  0 log2 1 2 log 2 2 log 2   「阪神は負けなかった」というメイルに含まれる情報量： 1.585 – 1 = 0.585 ビット 18 http://narayama.naist.jp/~kaji/lecture/

情報量とエントロピ

情報量とエントロピー

離れたところにある情報源 S の出力（通報）を知りたい 離れたところにある情報源 S の出力（通報）を知りたい 通報の確率分布はわかるが，何が実際出力されたか知りたい S の出力に関し なんらかの「ヒント」を入手したとする S の出力に関し，なんらかの「ヒント」を入手したとする ヒントにより，通報の確率分布が，別の情報源 S’ の確率分布 と一致することがわかったとする と 致することがわかったとする このとき ヒント（通報）がもたらした情報量 （information) は このとき，ヒント（通報）がもたらした情報量 （information) は H(S) – H(S’) ビット http://narayama.naist.jp/~kaji/lecture/

気まぐれな友人の場合（

1）

気まぐれな友人の場合（

case 1）

右図の行動を取る友人Ｂが _勝ち 0.5 _{「勝 たよ」} 右図の行動を取る友人Ｂが 「言いたくない」と言った時の 情報量は？ 勝ち 引分 「勝ったよ」 「言いたくない」 0.5 0.5 0 5 1.0 情報量は？ 負け 0.5_0.5 「負けたよ」 P(言いたくない) = 2/3 P(勝ち，言いたくない) = 1/6 P(勝ち | 言いたくない) = 1/4 P(引分，言いたくない) = 1/3 P(引分 | 言いたくない) = 1/2 P(負け，言いたくない) = 1/6 P(負け | 言いたくない) = 1/4 「言いたくない」と言っているときのエントロピ は 「言いたくない」と言っているときのエントロピーは 5 . 1 4 1 log 4 1 2 1 log 2 1 4 1 log 4 1 _{  }  情報量は1.585 – 1.5 = 0.085ビット（友人Ａのメイル：0.585ビット）

気まぐれな友人の場合（

2）

気まぐれな友人の場合（

case 2）

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

情報量の「平均」

情報量の「平均」

友人Ｂの行動： 友人Ｂの行動： 1/6 の確率で「勝ったよ」...情報量 1.585ビット 2/3 の確率で「言いたくない」 情報量 0 085ビット 2/3 の確率で「言いたくない」...情報量 0.085ビット 1/6 の確率で「負けたよ」...情報量 1.585ビット 平均すると1 585 1/6 + 0 085  2/3 +1 585  1/6 =0 585ビット 平均すると1.585  1/6 + 0.085  2/3 +1.585  1/6 = 0.585ビット 友人Ａの行動： 2/3の確率で「負けなかった」 情報量 0 585ビット 友人Ａの行動： 勝ち 2/3の確率で「負けなかった」...情報量 0.585ビット 1/3の確率で「負けたよ」...情報量 1.585ビット 平均すると0 585 2/3 + 1 585  1/3 =0 918ビット 勝ち 引分 「負けなかった」 平均すると0.585  2/3 + 1.585  1/3 = 0.918ビット 平均すると 友人Ａのほうが 22 負け 「負けたよ」 平均すると，友人Ａのほうが_{0.333ビット多くの情報をくれる} http://narayama.naist.jp/~kaji/lecture/

相互情報量

相互情報量

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

相互情報量の意味

相互情報量の意味

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

相互情報量の計算例（１）

相互情報量の計算例（１）

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

相互情報量の計算例（２）

相互情報量の計算例（２）

晴 雨 Y P(X) ×100 X 45₁₅ 60 12 28 40 晴 雨 P(Y)×100 57 43 天気予報が当たる確率＝P （晴 晴）＋ P （雨 雨）=0 73 60 40 P(Y)×100 天気予報が当たる確率 P_X,Y（晴，晴）＋P_X,Y（雨，雨） 0.73 この予報と友人Ａのメイル どちらが「高性能」？ この予報と友人Ａのメイル，どちらが「高性能」？ 天気のエントロピー： 986 0 43 0 l 43 0 57 0 l 57 0 ) (X H ビット 26 986 . 0 43 . 0 log 43 . 0 57 . 0 log 57 . 0 ) (X    H ビット http://narayama.naist.jp/~kaji/lecture/

相互情報量の計算例（３）

相互情報量の計算例（３）

天気予報Yが晴のとき： 天気予報Yが晴のとき： 本当に晴れる確率は0.45/0.60 = 0.75，雨の確率は0.25 「晴」という予報を聞いた後の条件付エントロピーは 「晴」という予報を聞いた後の条件付エントロピ は H(X | 晴) = – 0.75log0.75 – 0.25log0.25 = 0.811 ビット 「晴」という天気予報の持つ情報量は0 986 0 811 = 0 175 「晴」という天気予報の持つ情報量は0.986 – 0.811 = 0.175 天気予報Yが雨のとき： 本当に雨の確率は0 28/0 40 0 70 晴の確率は0 30 本当に雨の確率は0.28/0.40 = 0.70，晴の確率は0.30 「雨」という予報を聞いた後の条件付エントロピーは H(X | 雨) 0 30l 0 30 0 70l 0 70 0 881 ビット H(X | 雨) = – 0.30log0.30 – 0.70log0.70 = 0.881 ビット 「雨」という天気予報の持つ情報量は0.986 – 0.881 = 0.105 加重平均をとると0 60 0 175 + 0 40 0 105 0 147 ビ ト 加重平均をとると0.60·0.175 + 0.40·0.105 = 0.147 ビット http://narayama.naist.jp/~kaji/lecture/

相互情報量と当たる確率

相互情報量と当たる確率

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

第

部のまとめ

第一部のまとめ

エントロピーの概念を導入 エントロピ の概念を導入 予測の難しさを定量化したもの 情報量，相互情報量を定義 エントロピーの減少量として定式化 エントロピーの減少量として定式化 システムの評価には，相互情報量の概念が有用 29

休憩

休憩

30 http://narayama.naist.jp/~kaji/lecture/

第二部 情報の表現方法を考える

第二部：情報の表現方法を考える

情報は 実体を持たない抽象的なもの 情報は，実体を持たない抽象的なもの 情報の容器である「通報」に，具体的表現を与える必要がある 通報の表現方法 かなり大きな自由度がある 通報の表現方法...かなり大きな自由度がある ⇒ 「良い」表現方法と「良くない」表現方法がある 「良い」表現方法とは？ 情報の蓄積を考えると できるだけコンパクトであること 情報の蓄積を考えると...できるだけコンパクトであること 情報の伝達を考えると...できるだけ誤りに強いこと 相反する二つの方向性の間で，バランスを取ることが大切 技術としては それぞれ独立したものとして扱うことが得策 技術としては，それぞれ独立したものとして扱うことが得策 http://narayama.naist.jp/~kaji/lecture/

第二部前半 情報のコンパクトな表現について

第二部前半：情報のコンパクトな表現について

３種類の通報 A B C を 0 と 1 だけを用いて符号化する ３種類の通報 A, B, C を，0 と 1 だけを用いて符号化する A 0 符号化すると B と C が区別できなくなる 符号語 通報 （ただし，区切り記号は使わない） A B C 0 1 1 符号化すると，B と C が区別できなくなる （一意に復号できない） ⇒ すべてを1 ビットで表現することは不可能 C 1 ⇒ すべてを1 ビットで表現することは不可能 A 00 10 一意性は保証されるが，一工夫足りない... B C 10 11 A B 0 10 符号語の長さが揃っていないが... 情報をコンパクトには表現できる C 11

様々な符号化法

様々な符号化法

A 0 いまのところベストの符号化法 A B C 0 10 11 いまのところベストの符号化法 C 11 A 00 11 上の例と似ているが，一意性が保証されない B → 11 B C 11 1 B → 11 CC → 11 意性は保証されるが 取り扱いが面倒 A B 00 10 一意性は保証されるが，取り扱いが面倒 10000000 → BAAA 1000000 → CAAA C 1 1000000 → CAAA 最後の一文字を見るまで，復号を行えない 33 最初の方式は，一意的で，即時に復号処理ができる

様々な符号化法（続）

様々な符号化法（続）

A 0 いまのところベストの符号化法 C_{1 A} B C 0 10 11 いまのところベストの符号化法 C₁ C 11 A B 11 10 本質的に，上と同じ？ C₂ B C 10 0 通報の出現確率に偏りがある場合を考える 通報の出現確率に偏りがある場合を考える P(A) = 0 5 C1 ：一通報を表現する符号長の平均は ビ ト P(A) = 0.5 P(B) = 0.4 P(C) = 0.1 0.5 ×1 + 0.4×2 + 0.1×2 = 1.5ビット C₂：一通報を表現する符号長の平均は 0 5 ×2 + 0 4×2 + 0 1×1 = 1 9ビット 34 P(C) 0.1 _{0.5 ×2 + 0.4×2 + 0.1×1 = 1.9ビット} C₁のほうが C₂よりもコンパクトな表現 http://narayama.naist.jp/~kaji/lecture/

符号に求められる性質

符号に求められる性質

良い符号の三条件： 良い符号の三条件： 一意に復号可能であること 瞬時に復号可能であること 瞬時に復号可能であること 平均符号長ができるだけ短いこと 理論的に最適な解法が知られている ⇒ハフマン符号化 http://narayama.naist.jp/~kaji/lecture/

ハフマン符号

ハフマン符号

1 各通報に対して節点を準備し その発生確率を付与する 1.各通報に対して節点を準備し，その発生確率を付与する 節点はそれぞれ，大きさ１の木であると考える 2.木の中で発生確率最小のものを２つ選出し，以下を行う 1 ２つの木の根節点を子とするような 新しい根節点を作る 1.２つの木の根節点を子とするような，新しい根節点を作る 2.新しい根節点と古い根節点を結ぶ枝に，0, 1 をラベル付け 3 新しい根節点に ２つの木の発生確率の和を与える 3.新しい根節点に，２つの木の発生確率の和を与える すべての節点がつながるまで 2 の操作を繰り返す 3.すべての節点がつながるまで，2 の操作を繰り返す

ハフマン符号化法

ハフマン符号化法

A B C D 記号 A 0.60 B 0.25 C 0.10 D 0.05 記号 確率 0 15 0.60 0.25 0.10 0.05 0.15 0.60 0.25 0.10 0.05 A B C D A B C D 0.40 1.00 0.60 0.25 0.10 0.05 0.60 0.25 0.10 0.05 37 0.60 A 0.10 C 0.05 D 0.25 B 0.60 A 0.10 C 0.05 D 0.25 B

練習問題

練習問題

確率 符号語 確率 符号語 A B 確率 0.2 0.1 符号語 A B 確率 0.3 0.2 符号語 C D 0.3 0.3 C D 0.2 0.1 E 0.1 E F 0.1 0.1 38 等長符号の場合と比べ，平均符号長が小さくなっている http://narayama.naist.jp/~kaji/lecture/

ハフマン符号とブロック化

ハフマン符号とブロック化

ハフマン符号： ハフマン符号： 得られる符号は，一意かつ瞬時に復号可能 通報一個を符号語一個に符号化する方式としては 通報 個を符号語 個に符号化する方式としては， 最も効率が良い（最もコンパクト，平均符号長が小さい） 複数の通報を一まとめにして（ブロック化して）符号化すれば， さらに効率が良くなることが知られている さらに効率が良くなることが知られている http://narayama.naist.jp/~kaji/lecture/

ブロックハフマン符号

ブロックハフマン符号

２つの通報をまとめて（ブロック化して）符号化する ２つの通報をまとめて（ブロック化して）符号化する A 0 6 0 記号 確率 符号語 AA 0 36 0 記号 確率 符号語 A B C 0.6 0.3 0.1 0 10 11 AA AB AC 0.36 0.18 0.06 0 100 1100 BA BB BC 0.18 0.09 0 03 101 1110 11110 平均符号長1.4 ビット BC CA CB 0.03 0.06 0 03 11110 1101 111110 CB CC 0.03 0.01 111110 111111 平均符号長2.67 ビット 平均符号長 .67 ビット ⇒一記号あたり1.335 ビット

ブロック化と性能の限界

ブロック化と性能の限界

一般に ブロック長を大きくすると 通報一記号あたりの般に，ブロック長を大きくすると，通報 記号あたりの 平均符号長は減少する どこまで減少するか？ 対象となっている情報源のエントロピーに漸近する 対象となっている情報源のエントロピーに漸近する 平均符号長 平均符号長 （一記号あたり） ブ エントロピー 41 ブロック長

情報源符号化定理

情報源符号化定理

平均符号長 （一記号あたり） ハフマン符号よりも良い方法を 工夫すれば，エントロピーの壁を 乗り越えられる？ エントロピー 乗り越えられる？ ブロック長 エントロピー 任意の符号について，平均符号長は必ず L H₁(S) となる データ圧縮における「越えられない壁」 デ タ圧縮における「越えられない壁」 平均符号長がL < H₁(S) + 1となる符号を構成できる ハフマン符号は 理論限界を達成する符号化方式 42 ハフマン符号は，理論限界を達成する符号化方式 http://narayama.naist.jp/~kaji/lecture/

ユニバ サル符号化 非可逆符号化

ユニバーサル符号化，非可逆符号化

ハフマン符号化 情報源記号の確率分布が 事前に必要 ハフマン符号化...情報源記号の確率分布が，事前に必要 確率分布が（正確には）わからないケースも多い ⇒ユニバーサル符号化法 ⇒ユニバ サル符号化法 どのような情報源に対しても，そこそこ良い性能を発揮 LZ77法 (lha gzip zoo zip etc )

LZ77法 (lha, gzip, zoo, zip etc.) LZ78法 (compress, stuffit etc.)

LZW法 (GIF TIFF 等の画像フォ マット) LZW法 (GIF, TIFF 等の画像フォーマット) 音声や画像等の情報 音声や画像等の情報... 細部まで正確に再現できなくても，実害なし 再現性を 部犠牲にして 高い圧縮率を⇒非可逆符号化 再現性を一部犠牲にして，高い圧縮率を⇒非可逆符号化 http://narayama.naist.jp/~kaji/lecture/

第二部 折り返し地点

第二部：折り返し地点

ここまでは，「情報をコンパクトに表現する」おはなし ここからは「誤 た情報を訂正する」おはなし ここからは「誤った情報を訂正する」おはなし

通信路符号化

通信路符号化

偶発的に発生する誤りから 情報を保護したい 偶発的に発生する誤りから，情報を保護したい 通信路において発生するノイズから情報を守る CD ROM が傷ついても 中のデータは読めるようにする CD-ROM が傷ついても，中のデ タは読めるようにする 基本的な考え方： 基本的な考え方： 誤りを検出し，訂正するための「余分な情報」を追加する 45

パリティ検査符号

パリティ検査符号

パリティ記号の付加： パリティ記号の付加： ０と１で表現されたひとまとまりのデータの中に， １が偶数個あれば０を １が偶数個あれば０を １が奇数個あれば１を データの最後にくっつける操作 データの最後にくっつける操作 パリティ記号の付加されたデータは， 偶数個の１を含む（偶パリティ符号） 01001 010010 偶数個の１を含む（偶パリティ符号） １の個数が奇数個 ⇒ 誤りの影響を受けている 01001 01011 010010 010111 ⇒ 誤りの影響を受けている サ バ用メ リ等 利用され る 101001 誤りを含む 46 サーバ用メモリ等で利用されている http://narayama.naist.jp/~kaji/lecture/

誤りの検出から訂正へ

誤りの検出から訂正へ

偶パリティ符号そのものには 誤り訂正能力がない 偶パリティ符号そのものには，誤り訂正能力がない 偶パリティ符号を組み合わせれば，誤り訂正可能に 例：４ビットの情報を保護したい ４ビットを長方形状に並べる ４ビットを長方形状に並べる 水平方向，垂直方向にパリティ記号（５ビット）を付加 0 1 1 保護したい ４ビ ト パリティ記号 ５ビ ト (9 4) 符号 0111 011110101 1 1 0 1 0 1 ４ビット ５ビット (9, 4) 符号 長さ９ビット 内４ビットが本来の情報 1 0 1 符号化率4/9 http://narayama.naist.jp/~kaji/lecture/

誤り訂正の原理

誤り訂正の原理

前出の(9 4) 符号 ⇒ どの行・列とも １は偶数個のはず 前出の(9,4) 符号 ⇒ どの行 列とも，１は偶数個のはず １ビットの誤りが発生すると… 誤りを含む行 列だけ １が奇数個になる 誤りを含む行，列だけ，１が奇数個になる 受信者は，誤りの発生位置を特定することが可能 誤りは 異常のある行・列の交点に存在するはず 誤りは，異常のある行・列の交点に存在するはず 0 1 1 0 1 1 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 正常（誤り無し） 1 0 1 異常（誤りあり） 正常（誤り無し） 異常（誤りあり）

般的な線形符号へ

一般的な線形符号へ

前出の(9 4) 符号 ⇒ 行単位 列単位でパリティ記号を計算 前出の(9,4) 符号 ⇒ 行単位，列単位でパリティ記号を計算 二次元的な行，列にこだわる必要はない 斜めにたどる 途中で曲げる スポット的に拾うetc 斜めにたどる，途中で曲げる，スポット的に拾うetc… データビットの任意の組合せからパリティ記号を計算可能 組み合わせ方により 符号の性能が変化する 組み合わせ方により，符号の性能が変化する 線形符号： データビットの部分集合から パリティ記号を定義する符号 いかにして良い組み合わせ方を探すか 49 ⇒ 符号設計者の腕の見せ所

ハミング符号

ハミング符号

代表的な線形符号 代表的な線形符号 符号語中に発生する１ビットの誤りを訂正可能 非常に効率が良い（完全符号） 非常に効率が良い（完全符号） 0 1 0111 0111100 0 1 1 1 1 ₀0 0111 0111100 (7,4)符号 効率4/7 0 1 1 _{0111 011110101} 効率 /7 1 1 0 0111 011110101 (9,4)符号 効率4/9 50 1 0 1 効率4/9 （どちらも，より大規模の符号も構成可能） http://narayama.naist.jp/~kaji/lecture/

生成行列

生成行列

線形符号 線形符号 データビットの部分集合から，パリティ記号を定義 パリティ記号は いくつかのデータビットの和となる パリティ記号は，いくつかのデ タビットの和となる p₃ x₁ x₂ p1 = x2 +x3+ x4 p₁ p3 p₂ x3 x4 _p 3 = x1+ x2 +x3 p2 = x1 +x3+ x4 （+は排他的論理和） ( ) ( ) 1000011 0100101 p₃ x₁x₂x₃x₄p₁p₂ ( )=(x₁x₂x₃x₄) 0100101 0010111 0001110 生成行列 符号化操作 ＝ データビットと生成行列の掛け算 http://narayama.naist.jp/~kaji/lecture/

検査行列

検査行列

p = x + x +x x + x +x +p = 0 p = x +x + x p₁= x₂+ x₃ +x₄ p2= x1 + x3 +x4 p = 0 x +x + x p₁ = 0 x₂+ x₃ +x₄ p2 = 0 x1 + x3 +x4 + + + p₃= x₁ +x₂+ x₃ x₁ +x₂+ x₃ +p₃= 0 検査行列 0111100 x₁ x_{2 0} 符号語を検査行列にかけると 0111100 1011010 1110001 2 x₃ p₁ x₄ 0 0 0 = 符号語を検査行列にかけると ゼロベクトルになる ゼロベクトルにならなければ 1110001 p₃ p₂ 0 ゼロベクトルにならなければ， 誤りが含まれる 誤り検出 ＝ 受信語と検査行列の掛け算およびゼロテスト

線形符号の特徴

線形符号の特徴

符号化 誤りの検出 訂正とも 行列演算により実行可能 符号化，誤りの検出，訂正とも，行列演算により実行可能 行列演算 ⇒ 単純な組合せ回路だけで実現可能 ⇒ 高速に動作させるのに有利 ⇒ 高速に動作させるのに有利 規模の大きな線形符号 規模の大きな線形符号 巨大な行列に対する演算が必要となる 組合せ回路の面積増大 ⇒ 遅延 消費電力 設計困難 組合せ回路の面積増大 ⇒ 遅延，消費電力，設計困難 スケーラビリティが悪い もっと扱いやすい線形符号は？ 53

巡回符号

巡回符号

符号化 復号を シフトレジスタで実現できる線形符号 符号化，復号を，シフトレジスタで実現できる線形符号 一般の線形符号に比べ般の線形符号に比べ，実装面で有利実装面で有利 シフトレジスタ利用による配線の簡単化 符号化処理と復号処理で 回路の一部共有化が可能 符号化処理と復号処理で，回路の一部共有化が可能 代表的な巡回符号： 代表的な巡回符号： BCH符号 R d S l 符号 Reed-Solomon符号： 多元符号（バイト単位での取り扱い等も容易） CD DVD等でも採用 54 CD, DVD等でも採用 http://narayama.naist.jp/~kaji/lecture/

畳込み符号

符号化装置を 有限状態機械として実現する方式

畳込み符号

符号化装置を，有限状態機械として実現する方式 最尤復号が 比較的効率よく行える（ビタビアルゴリズム） 最尤復号が，比較的効率よく行える（ビタビアルゴリズム） 統計的に，最も信頼度の高い復号法 軟判定復号の実現も容易 復号精度を上げる技術 復号精度を上げる技術 受信値の信頼度を，０と１の二値でなく，より多段階で表現 多くの通信方式にて，畳込み符号が実際に用いられている http://narayama.naist.jp/~kaji/lecture/

誤り訂正符号の応用

誤り訂正符号の応用

二次元バーコード 二次元バ コ ド コード面の汚損による誤りが起こりうる Reed Solomon 符号の利用により 耐性向上 Reed-Solomon 符号の利用により，耐性向上 地上波デジタル放送 地上波デジタル放送 畳込み符号とReed-Solomon 符号の二重符号化を利用 数独パズル 周辺の制約条件から 欠落情報を復元 周辺の制約条件から，欠落情報を復元 情報理論応用ではないが，共通点が多い

本日のまとめ

本日のまとめ

第一部：情報を測る 第 部：情報を測る 情報の量，情報伝達系の性能を数値として測る 確率論をベースに 人間の直観にあった定式化を行う 確率論をベ スに，人間の直観にあった定式化を行う 第二部：情報を伝える 情報をできるだけコンパクトに表現する 情報をできるだけコンパクトに表現する 情報をできるだけ確実に伝える 「情報理論」の簡単な概論 デジタル情報システムの重要な基盤 デジタル情報システムの重要な基盤 コンピュータ関係以外への貢献も Cl d E Sh 57 Claude E. Shannon 1916-2001

出欠確認 課題

出欠確認・課題

情報・通信以外の分野で 情報理論の技術や考え方が 情報 通信以外の分野で，情報理論の技術や考え方が 利用できる分野，技術を考えよ 58