情報理論：楫 勇一（かじ ゆういち） 情報理論： C. E. Shannon によって創始された理論体系 情報伝達の効率と限界を議論する手段を与える Claude E. Shannon 1916-2001 デジタル情報処理・通信の発達と二人三脚で発展してきた 離散数学を多用，デジタルシステムと高い親和性 画像・音声情報処理，通信・ネットワークの基礎を与える 必ずしも電子計算機やデジタル通信を意識した理論ではない 人工知能，学習理論方面への応用も

情報伝達のモデル 観測対象において，なんらかのイベント e が発生する 発生したイベントが，通信路に入力される 通信路の出力 e’ から，発生イベント e を推測する e’ を知ることで，発生イベントに関する知識の量は増える 知識量を増加させたものが「情報」である （次回以降，もっと厳密に議論を行う） e ? 観測 対象 e 通信路 e’

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

このモデルの約束事 観測対象の統計的性質は既知であるとする 発生するイベントの種類，発生確率はわかっている 実際にどのイベントが発生するかは，事前に特定できない 例：コイン投げ...２つのイベント「表」「裏」が等確率で発生 通信路は，かならずしも正確でない 「入力＝出力」の保証はないケースも多い 誤り，近似... 入出力の統計的性質は既知であるとする 19.2 19.0 18.8 18.6 18.4 18.2 18.0 19 18 0.9 表 表 0.1 0.1 裏 裏 0.9

情報伝達における課題 小さなデータ量で，発生イベントを正確に伝えたい どこまでデータ量を削減できる？ 多少不正確でも良ければ，データ量を減らせるか？ 信頼性の低い通信路でも，情報を正確に送りたい 誤りの影響を軽減するには？ 性能改善の限界は？ 情報を，できるだけ伝えないようにしたい 上記はすべて，情報理論がターゲットとする課題

本講義の概要 第一部：情報の量を計る 情報を計量可能にし，工学的な議論を可能にする 第二部：情報をコンパクトに表現する 情報に含まれるムダを削り，情報を圧縮する 第三部：情報を正確に伝える 通信途中で発生する誤りを検出し，訂正する 第四部：情報を不正者から隠す いわゆる暗号技術の基礎について学ぶ

講義計画 火２ ６ １３ ２０ ２７ ３ １１ １８ ２５ １ 木１ ８ １５ ２２ ２９ ６ １３ ２０ ２７ ３ ４月 ５月 ６月 ６月３日...試験 講義日程の中間付近で，レポート出題予定 講義資料...http://narayama.naist.jp/~kaji/lecture/

第一部：情報の量を計る 目標：情報を計量可能にし，工学的な議論を可能にする 良い自動車を作りたい: 燃費の良い車を... 距離や燃料を正確に計ることが必要 スピードが出る車を...距離や時間を正確に計ることが必要 正確な計量ができなければ，精度の高い議論はできない 良い情報システムを作るには，情報を正確に計ることが必要 ⇒ 第一部の具体目標...情報量の概念を導入すること

情報源と通報 情報伝達モデル：「観測対象」で「イベントが発生」 イベントを文字，文字列で表現する...通報（message）と呼ぶ 「観測対象」と「イベントを通報に変換する仕組み」をあわせて 情報源（information source）と呼ぶ 観測 対象 e 抽象的な 「イベント」 変換 通報 注意点： 何を情報源と考えるかは，問題により異なってくる 観測対象は多種多様 （⇒ 次スライド） 情報源は，情報を発生しているのではない（通報 ≠ 情報）

観測対象の分類 連続時間 (continuous-time) vs. 離散時間 (discrete-time) 連続時間：時間的に途切れることなく，イベントが発生し続ける 離散時間：決まった時刻に，イベントが一個ずつ発生 アナログ (analog) vs. デジタル (digital) アナログ：イベントは非可算（連続集合となる） デジタル：イベントは可算（離散集合となる） ４タイプ：{連続時間，離散時間} × {アナログ，デジタル} ⇒ 情報源の中の変換器で違いを吸収可能：標本化，量子化

標本化と量子化 標本化 (sampling)： 連続時間イベントを，離散時間イベントに近似する技法 特定の時刻に発生したイベントを抜き出す 量子化 (quantization)： アナログイベントを，デジタルイベントに近似する技法 既定の代表値でもっとも近いものに置換える

本講義における「情報源」 離散時間・デジタル的な振舞いをする情報源だけ考えれば良い 情報源は，1, 2, ....の各時刻に通報を一個発生する 通報は，離散集合M の要素のどれか 通報は| M |種類...| M |元(| M |-ary) 情報源という 観測対象に関する約束より... 同一の情報源でも，試行のたびに異なる通報を発生する 通報の確率分布が事前にわかっている

情報源と確率 コイン投げを行い，表（H）か裏（T）かを通報とする情報源： 時刻 1 2 3 4 5 6 7 8 ... 時刻 1 2 3 4 5 6 7 8 ... 試行１ H T T H T H T H ... 試行２ T T H T H T H H ... 試行３ H H T H T T H T ... 試行によって，通報の発生系列は異なる 時刻 t に発生する通報を，確率変数 Xt によりあらわす 時刻 t で通報 a が発生する確率 P(Xt = a) を，PXt(a) と書く 結合（同時）確率 P(Xt1=a1, Xt2=a2) を PXt1, Xt2(a1, a2) と書く 条件付確率 P(Xt2=a2| Xt1=a1) を PXt2|Xt1(a2 | a1) と書く

情報源の分類 コイン投げの結果...非常に単純な「無記憶」「定常」情報源 発生する通報は，それ以前に発生した通報と無関係 どの時刻でも，通報の発生確率は変わらない 世の中には，もっと複雑な情報源もある...２種類の分類法 分類法１：記憶があるか，記憶がないか 分類法２：定常か，定常でないか

記憶のない情報源 情報源に記憶がない（memoryless）： ある時刻の通報が，それ以前の通報とは無関係に選ばれる ⇒ 確率 PXt|X1,...,Xt–1(at | a1,..., at–1) の値が a1, ..., at–1に依存しない ⇒ 定数 PXt (at) が存在し，PXt|X1,...,Xt–1(at | a1,..., at–1) = PXt (at) コイン投げは，記憶のない情報源である M = {H, T} 任意の t, 任意の a1, ..., at–1M，任意のatM に対し， PXt|X1,...,Xt–1(at | a1,..., at–1) = PXt (at) = 1/2

記憶のない情報源と記憶のある情報源 記憶のない情報源では， ⇒ 確率分布の計算が容易 ⇒ シンプルで扱いやすい情報源である 記憶のない情報源以外の情報源⇒記憶のある情報源 現実世界の多くの情報源は，「記憶のある」情報源 例：英文では，文字 q の次は u の出現確率が著しく高い 確率分布の計算も困難で，扱いにくい情報源 通報に相関がある分，圧縮できる余地が大きい ⇒ 第二部での議論

定常情報源 定常（stationary）情報源： 時刻をシフトしても，通報の確率分布が変わらない情報源 ⇒ 任意の i に対して PX1,...,Xt (a1,..., at) = PXi,...,Xi+t–1 (a1,..., at) ⇒ t = 1 のときを考えると，PX1(a1) = PXi(a1)...定常確率 P(a1) 通報の発生確率は，どの時刻でも変化しない コイン投げは定常情報源 定常でない情報源の例... 電話での発声： 「もしもし」から始まることが多い：PX1(も） > PX2(も) 時刻 1 2 3 4 5 6 7 8 ... 試行１ H T T H T H T H ... 試行２ T T H T H T H H ... 試行３ H H T H T T H T ... :

小休止：ここまでのまとめ 情報源の分類 連続時間アナログ的 離散時間アナログ的 連続時間デジタル的 離散時間デジタル的 無記憶 有記憶 定常 標本化 連続時間アナログ的 離散時間アナログ的 量子化 量子化 標本化 連続時間デジタル的 離散時間デジタル的 無記憶 有記憶 定常 非定常 コイン投げ 自然言語 有記憶・定常な情報源 無記憶・非定常な情報源 どのようなものがあるか？

マルコフ情報源 第二部以降の議論...記憶のない定常情報源が中心となる 実用上は，記憶のある情報源も重要 記憶のある情報源の一例として，マルコフ情報源について紹介 m 重マルコフ (m-th order Markov) 情報源： 通報の発生確率が，直前m個より前の通報には依存しない 任意の時刻 i, m より大きな任意の n に対し， PXi|Xi–1, ..., Xi–n(ai | ai–1, ..., ai–n) = PXi|Xi–1, ..., Xi–m(ai | ai–1, ..., ai–m) 記憶のない情報源 ＝ 0 重マルコフ情報源

マルコフ情報源の例 P(0) = q, P(1) = 1 – q である，無記憶定常情報源 S を使って... S Xi R 1ビット記憶素子 Xi は排他的論理和 直前の通報 Xi–1= 0 なら，R = 0 となっているはず... S の出力が 0 なら，Xi = 0 ⇒ PXi|Xi–1(0 | 0) = q S の出力が 1 なら，Xi = 1 ⇒ PXi|Xi–1(1 | 0) = 1 – q 直前の通報 Xi–1= 1 なら，R = 1 となっているはず... S の出力が 1 なら，Xi = 0 ⇒ PXi|Xi–1(0 | 1) = 1 – q S の出力が 0 なら，Xi = 1 ⇒ PXi|Xi–1(1 | 1) = q この情報源は，１重マルコフ情報源（単純マルコフ情報源）

マルコフ情報源と状態図 n 元 m 重マルコフ情報源 直前 m 個の通報により，次の通報が決定 各状態について，通報の発生確率が定義される 通報の発生にともなって，状態の遷移が起こる Xi / 確率 1 1 / 1–q 0 / 1–q 0 / q 1 / q P(0) = q P(1) = 1–q P(0) = 1–q P(1) = q 1 前ページの情報源の状態図 少し違う書き方

状態図による情報源定義 マルコフ情報源...必ず状態図として表現できる 状態図は必ず，なんらかのマルコフ情報源と対応するか？ ⇒ 対応しないこともある マルコフ情報源は，状態図により表現される情報源の 真の部分クラスである ただし...あまり厳密に議論する必要なし，というケースも多い 状態図により表現される情報源： （一般化（generalized））マルコフ情報源と呼ぶことも

マルコフ情報源の分類 既約（irreducible）マルコフ情報源 任意の状態から任意の状態に遷移可能なマルコフ情報源 1 2 1 2 左は既約でないマルコフ情報源 状態 1 からは，状態 0 や 2 に遷移できない 正規（regular）マルコフ情報源 どの状態からスタートしても，十分な時間が経過した後には， 状態確率分布が同じ値に収束する既約マルコフ情報源

正規マルコフ情報源の例 1 0/0.9 1/0.1 0/0.8 1/0.2 状態 0 から状態 1 へは遷移しにくい 1 0/0.9 1/0.1 0/0.8 1/0.2 状態 0 から状態 1 へは遷移しにくい 状態 1 から状態 0 へは遷移しやすい 初期状態が 0 でも 1 でも，十分な時間 経過後は状態 0 に居る確率が高い？ 時刻 0に居る確率 1に居る確率 1 1.0 0.0 2 0.9 0.1 3 0.89 0.11 4 0.889 0.111 ... 状態 0 からスタート これらの確率は， 同じ値に収束する 時刻 0に居る確率 1に居る確率 1 0.0 1.0 2 0.8 0.2 3 0.88 0.12 4 0.888 0.112 ... 状態 1 からスタート 定常確率分布 （stationary prob. dist.）

定常確率分布の計算法 時刻 t で状態 0 に居る確率：t 時刻 t で状態 1 に居る確率：t 収束時には，以下の式が成り立つ 1 0/0.9 1/0.1 0/0.8 1/0.2 t, t が,  に収束する場合， t+1=t=, t+1=t=とし，  = 0.9 + 0.8  = 0.1 + 0.2 += 1 この連立方程式を解いて， =8/9, =1/9

より一般的な場合の計算法 確率分布ベクトルを w = (w0, ..., wn–1)とする （n は状態数，wi は，状態 i に居る確率，w0 + ... + wn–1= 1） 状態遷移行列を =(pi,j)とする （ i 行 j 列目の要素 pi,jは，状態 i から状態 j への遷移確率） 定常確率分布は，w = w，Σwi=1の解として与えられる 1 2 0.3 0.4 0.6 1.0 (w0 w1 w2)=(w0 w1 w2) 0.3 0.3 0.4 0.4 0.0 0.6 0.0 1.0 0.0 w0 + w1 + w2 = 1.0 これを解いて w0 = 40/168, w1 = 70/168, w2 = 58/168 （遷移確率のみ表示）

正規マルコフ情報源 正規マルコフ情報源： 十分な時間経過後は，定常情報源とみなすことができる 1 0/0.9 1/0.1 0/0.8 1 0/0.9 1/0.1 0/0.8 1/0.2 定常確率分布は，w0 = 8/9, w1 = 1/9 0 の定常確率 P(0) = 0.9w0 + 0.8w1 = 0.889 1 の定常確率 P(1) = 0.1w0 + 0.2w1 = 0.111 以上の議論を踏まえ，「記憶」が情報量に影響することを示す ⇒ 次回講義

本日のまとめ 様々なタイプの情報源があることを紹介した 自分が扱おうとしている対象がどれに相当するのか， 「対象を知る」ことが非常に大切 記憶のある情報源は，一般には複雑で扱いが難しい マルコフ情報源等，適切なモデルにより近似を 次回の講義では...情報「量」を導入する

練習問題 無記憶・非定常な情報源を一つ例示せよ 以下のマルコフ情報源について， 状態の定常確率分布を求めよ 通報 A, B の定常確率を求めよ 1 2 A/0.4 A/0.5 B/0.6 A/0.8 B/0.5 B/0.2 宿題，レポート課題ではありません 解答例は次回講義冒頭で

情報基礎学講座（関研）講座紹介 本日・明日の４限（15:10--），B507の部屋にて その他の日時も，随時受付中 メイルで連絡 kaji@is.naist.jp まで連絡 オフィスB505まで直接訪問 講義資料...http://narayama.naist.jp/~kaji/lecture/