のくやし

前回の復習
𝑋: タイガースの試合結果，𝑃𝑋 𝑤 = 𝑃𝑋 𝑑 = 𝑃𝑋 𝑙 = 1/3
𝑌: 阪神ファンの友人のtweet
𝑋
𝑤
𝑑
𝑙
𝑌
やったー
くやしー
くやしー
p.13 のように同時確率の表を書き，周辺確率も求めよ
p.34 に示した3つの異なる方法で，相互情報量 𝐼(𝑋; 𝑌)を求めよ
（ページ番号は前回スライドのもの）
1
相互情報量
相互情報量の計算法は３通りある
1. 𝐼 𝑋; 𝑌 = 𝐻1 𝑋 + 𝐻1 𝑌 − 𝐻1 (𝑋, 𝑌)
2. 𝐼 𝑋; 𝑌 = 𝐻1 𝑋 − 𝐻1 𝑋|𝑌
3. 𝐼 𝑋; 𝑌 = 𝐻1 𝑌 − 𝐻1 𝑌|𝑋
全部同じ値になるが，計算の手間が違う，かも
𝐻1(𝑋, 𝑌)
𝐻1(𝑋)
𝐻1(𝑋|𝑌)
𝐻1(𝑌)
𝐻1(𝑌|𝑋)
𝐼(𝑋; 𝑌) = 𝐼(𝑌; 𝑋)
2
練習問題：手順１による𝐼(𝑋: 𝑌)の計算
𝑋 𝑌 や
1/3
𝑤
0
𝑑
0
𝑙
1/3
いくつかの基本的なエントロピーを計算
はじめに，同時確率と周辺確率を
計算する
𝐻1 𝑋, 𝑌
𝐻1 𝑋 =
𝐻1 𝑌 =
1
1
1
1
1
1
= − log 2 − log 2 − log 2
3
3
3
3
3
3
1
1
1
1
1
1
− log 2 − log 2 − log 2 =
3
3
3
3
3
3
1
1
2
2
− log 2 − log 2 = 0.918 bit
3
3
3
3
く
0
1/3
1/3
2/3
1/3
1/3
1/3
= 1.585 bit
1.585 bit
𝐼 𝑋; 𝑌 = 𝐻1 𝑋 + 𝐻1 𝑌 − 𝐻1 𝑋, 𝑌 = 0.918 bit
3
練習問題：手順２による𝐼(𝑋: 𝑌)の計算
𝑋
𝐻1 (𝑋|𝑌)を求める
𝑌 = 「やったー」のとき
𝑃𝑋|𝑌 𝑤 や = 1, 𝑃𝑋|𝑌 𝑑 や = 𝑃𝑋|𝑌 𝑙 や = 0
𝑌
𝑤
𝑑
𝑙
𝐻1 𝑋 𝑌 = や = −1 log 2 1 − 0 log 2 0 − 0 log 2 0 = 0
や
1/3
0
0
1/3
く
0
1/3
1/3
2/3
1/3
1/3
1/3
𝑌 = 「くやしー」のとき
𝑃𝑋|𝑌 𝑤 く = 0, 𝑃𝑋|𝑌 𝑑 く = 𝑃𝑋|𝑌 𝑙 く = 1/2
1
2
1
2
1
2
1
2
𝐻1 𝑋 𝑌 = く = −0 log 2 0 − 0 log 2 − log 2 = 1
𝐻1 𝑋 𝑌 = 𝑃𝑌 や 𝐻1 (𝑋|𝑌 = や) + 𝑃𝑌 く 𝐻1 (𝑋|𝑌 = く)
1
3
2
3
= × 0 + × 1 = 0.667 bit
𝐼 𝑋; 𝑌 = 𝐻 𝑋 − 𝐻 𝑋 𝑌 = 1.585 − 0.667 = 0.918 bit
4
練習問題：手順３による𝐼(𝑋: 𝑌)の計算
𝐻1 (𝑌|𝑋)を求める
𝑋 = 𝑤のとき：
𝑃𝑌|𝑋 や 𝑤 = 1, 𝑃𝑌|𝑋 く 𝑤 = 0
...𝐻1 𝑌 𝑋 = 𝑤 = 0
𝑋 = 𝑑のとき：
𝑋
𝑌
𝑤
𝑑
𝑙
や
1/3
0
0
1/3
く
0
1/3
1/3
2/3
1/3
1/3
1/3
𝑃𝑌|𝑋 や 𝑑 = 0, 𝑃𝑌|𝑋 く 𝑑 = 1
...𝐻1 𝑌 𝑋 = 𝑑 = 0
𝑋 = 𝑙 のとき：
𝑃𝑌|𝑋 や 𝑙 = 0, 𝑃𝑌|𝑋 く 𝑙 = 1
...𝐻1 𝑌 𝑋 = 𝑙 = 0
𝐻1 𝑌 𝑋 = 0 bit
𝐼 𝑋; 𝑌 = 𝐻 𝑌 − 𝐻 𝑌 𝑋 = 0.918 − 0 = 0.918 bit
5
本日の講義
通信路容量
情報源について
マルコフ情報源
情報源の拡大とエントロピー
Andrey Markov
1856-1922
レポート課題 / report assignment
http://isw3.naist.jp/~kaji/lecture/
6
相互情報量と通信
情報通信に近い例で，相互情報量を考える
通信路 C
入力 𝑋＝{1, 2, 3, 4, 5, 6} 𝑋
出力 𝑌＝{𝐿, 𝑀, 𝐻}
1
2
3
4
5
6
𝐿
𝑀
𝑌
𝐻
この通信路 C を使ってサイコロの目を伝達する
... 伝達される情報量𝐼(𝑋; 𝑌)は？
7
手順１による計算
𝑌
𝑋
1
2
3
4
5
6
𝐿
𝑀
𝐻 𝑃𝑋 (𝑥)
1
1 1
1
1
1
1/6 0
0
1/6 𝐻 𝑋, 𝑌 = − log 2 − log 2 … − log 2 = 2.585
6
6 6
6
6
6
1/6 0
0
1/6
0 1/6 0
1/6 𝐻 𝑋 = − 1 log 1 − 1 log 1 … − 1 log 1 = 2.585
2
2
2
6
6 6
6
6
6
0 1/6 0
1/6
1
1 1
1 1
1
0
0 1/6 1/6
𝐻 𝑌 = − log 2 − log 2 − log 2 = 1.585
0
0 1/6 1/6
3
3 3
3 3
3
𝑃𝑌 (𝑦) 1/3 1/3 1/3
𝐻1(𝑋, 𝑌)
𝐻1(𝑋)
𝐻1(𝑌)
𝐼(𝑋; 𝑌)
この例では𝐻 𝑋, 𝑌 = 𝐻(𝑋)なので...
𝐼 𝑋; 𝑌 = 𝐻 𝑋 + 𝐻 𝑌 − 𝐻 𝑋, 𝑌 = 𝐻 𝑌 = 1.585 bit
8
相互情報量の意味付け
通信路の入力と出力の相互情報量
＝ その通信路が，どれだけ正確に情報を伝えるか
𝐻1(𝑋, 𝑌)
𝐻1(𝑋)
𝐻(𝑋|𝑌)
𝐻1(𝑌)
𝐼(𝑋; 𝑌)
𝐻 𝑋 = 2.585
𝐻 𝑋 𝑌 = 𝐻 𝑋, 𝑌 − 𝐻 𝑌 = 1.000
通信路の入力のエントロピーは 2.585 bit
通信路の出力を知っても，1.000 bit 分エントロピーが残る
通信路は，1.585 bit 分の情報しか伝達できていない
9
入力を取り替える
先ほどと同じ通信路 C
入力 𝑋＝{1, 2, 3, 4, 5, 6}
𝑋
出力 𝑌＝{𝐿, 𝑀, 𝐻}
1
2
3
4
5
6
𝐿
𝑀
𝑌
𝐻
同じ通信路 C を使って，公正でないサイコロの目を伝達する
𝑃𝑋 1 = 0.9
𝑃𝑋 2 = ⋯ = 𝑃𝑋 6 = 0.02
10
手順１による計算
𝑌
𝑋
1
2
3
4
5
6
𝐿
𝑀
𝐻 𝑃𝑋 (𝑥)
0.9 0
0
0.9 𝐻 𝑋, 𝑌 = −0.9 log 0.9 − 0.02 log 0.02 … = 0.701
0.02 0
0
0.02
0 0.02 0
0.02 𝐻 𝑋 = −0.9 log 0.9 − 0.02 log 0.02 … = 0.701
0 0.02 0
0.02
0
0 0.02 0.02 𝐻 𝑌 = −0.92 log 0.92 − 0.04 log 0.04 … = 0.482
0
0 0.02 0.02
𝑃𝑌 (𝑦) 0.92 0.04 0.04
𝐻1(𝑋, 𝑌)
𝐻1(𝑋)
𝐻1(𝑌)
𝐼(𝑋; 𝑌)
この例でも𝐻 𝑋, 𝑌 = 𝐻(𝑋)なので...
𝐼 𝑋; 𝑌 = 𝐻 𝑋 + 𝐻 𝑌 − 𝐻 𝑋, 𝑌 = 𝐻 𝑌 = 0.482 bit
11
相互情報量と入力の関係
同じ通信路でも，入力が変わると相互情報量も変わる
C
𝐼 𝑋; 𝑌 = 1.585 bit
C
𝐼 𝑋; 𝑌 = 0.482 bit
通信路には，得意な入力，不得意な入力がある
通信路の性能
＝最も得意な入力につないだ時の相互情報量
＝（入力の確率分布を動かしたときの）相互情報量の最大値
＝通信路容量（講義の最終回に続く... ）
12
情報源のお話
エントロピー，相互情報量の話は，ここでいったん小休止
通信路に接続する入力（＝情報源）について議論する
情報源の諸性質
マルコフ情報源
13
本講義で扱う情報源
情報源は，1単位時間に1個の記号を出力する
（離散時間情報源）
出力記号は有限集合の中から確率的に選ばれる
（デジタル情報源）
現実世界では，上記条件を満たさない情報源も多数存在...
連続時間 / アナログ情報源
標本化・量子化等の操作により，離散時間の
デジタル情報源として近似できる場合が多い
14
記法について
𝑆 を離散時間デジタル情報源とする
𝑋𝑡 : 時刻 𝑡 (=1, 2, ...) に出力される記号を表す確率変数
𝐷 𝑋1 = ⋯ = 𝐷 𝑋𝑡 = ⋯ = 𝑀（実現値の集合）
集合𝑀が𝑘個の要素を持つとき... 𝑘 元情報源
例: 𝑆 = サイコロ
𝑀={
}
𝑋𝑡 の値は，確率的に定まる
𝑋2 =
𝑋8 =
15
情報源の基本性質１：無記憶性
情報源が無記憶 ⇔
′
任意の 𝑡, 𝑎1 … 𝑎𝑡−1 , 𝑎1′ … 𝑎𝑡−1
, 𝑎𝑡 に対し
𝑃𝑋𝑡 |𝑋1 …𝑋𝑡−1 𝑎𝑡 𝑎1 … 𝑎𝑡−1 = 𝑃𝑋𝑡 |𝑋1 …𝑋𝑡−1 𝑎𝑡 𝑎′1 … 𝑎′𝑡−1
過去の出力は，将来出力される記号の確率分布に影響しない
情報源が無記憶なら，𝑃𝑋𝑡 |𝑋1 …𝑋𝑡−1 𝑎𝑡 𝑎1 … 𝑎𝑡−1 = 𝑃𝑋𝑡 (𝑎𝑡 )
（条件付き確率＝周辺確率）
無記憶でない情報源 ＝ 記憶のある情報源
自然言語が代表例： 𝑃𝑋𝑡 |𝑋𝑡−1 𝑢 𝑞 ≫ 𝑃𝑋𝑡 |𝑋𝑡−1 𝑢 𝑢
16
情報源の基本性質２：定常性
情報源は定常 ⇔
任意の 𝑛, 𝑡, 𝑎1 … 𝑎𝑛 に対し
𝑃𝑋1 …𝑋𝑛 (𝑎1 … 𝑎𝑛 ) = 𝑃𝑋𝑡 …𝑋𝑡+𝑛−1 (𝑎1 … 𝑎𝑛 )
出力される記号の確率分布は，いつでも同じ
𝑛 = 1の場合を考えると，𝑃𝑋1 𝑎 = ⋯ = 𝑃𝑋𝑡 𝑎 = ⋯ = 𝑃𝑋 (𝑎)
... １個の確率変数 𝑋 で，全ての確率変数を代表できる
定常でない情報源 ＝ 非定常情報源
天気...「雪の降る確率」は季節に依存
17
情報源の基本性質２+：エルゴード性
定常情報源がエルゴード的 ⇔
「情報源から出力される一続きの記号列」
の中に含まれる記号 𝑎 の割合
サイコロ投げはエルゴード的
1個のサイコロを100回投げると，100/6回は 1が出る
喫煙記録は非エルゴード的
1人の成人の100日間の喫煙日数 ≠ 成人喫煙率
【定理】
無記憶な定常情報源は，必ずエルゴード的
記憶のある定常情報源には，エルゴード的でないものも存在
18
無記憶
非定常
アナログ
記憶のある
デジタル
情報源の性質：まとめ
定常
離散時間
エルゴード的
連続時間
19
定常無記憶情報源
定常で無記憶な情報源
サイコロ，コイン投げ，etc.
エルゴード的となることが保証されている
𝑃𝑋1 …𝑋𝑛 𝑎1 … 𝑎𝑛 = 𝑛𝑖=1 𝑃𝑋 𝑎𝑖
⇒ 理論的に取り扱いが容易
...本講義でも，定常無記憶情報源に的を絞って議論する
が，
定常無記憶情報源に専念する前に，
記憶のある情報源について簡単に紹介する
20
（狭義の）マルコフ情報源
記憶のある情報源の（比較的単純な）モデル
次に出力される記号は，直前 𝑚 個の出力記号の
影響を受ける (𝑚 次マルコフ情報源)
𝑃𝑋𝑡 |𝑋1 …𝑋𝑡−1 𝑎𝑡 𝑎1 … 𝑎𝑡−1
= 𝑃𝑋𝑡 |𝑋𝑡−𝑚 …𝑋𝑡−1 𝑎𝑡 𝑎𝑡−𝑚 … 𝑎𝑡−1
Andrey Markov
1856-1922
𝑚 = 0  無記憶情報源と一致する
𝑚 = 1  単純マルコフ情報源，と呼ばれる
21
（一般化）マルコフ情報源
状態遷移図により定義される情報源
狭義のマルコフ情報源を真に含む
情報源は，𝜎個ある状態のどれか１つを取る
遷移辺に付与された確率に従い，状態が遷移する
状態遷移の際は，遷移辺に付与された記号が出力される
（初期状態については後述）
𝑠1
𝜎 = 3：
b / 0.5
a / 0.4
b / 0.6
a / 0.8
状態 𝑠2 のとき
a / 0.5
0.8 の確率で a を出力して 𝑠2 に
𝑠2
𝑠3
0.2 の確率で b を出力して 𝑠3 に
b / 0.2
22
正規マルコフ情報源
以下のようなマルコフ情報源は，ある意味で「不健全」
袋小路的な部分がある
周期的な動作をする
（既約でない）
正規マルコフ情報源 ... 「健全な」マルコフ情報源
任意の状態組 𝑠, 𝑠 ′ , ある程度大きな任意の整数𝑛に対し，
𝑠 から 𝑠′への 𝑛ステップの状態遷移が存在する
...十分時間をかければ，どの状態からどの状態へも遷移可能
以降の議論では，正規マルコフ情報源のみを考える
23
マルコフ情報源の初期状態
マルコフ情報源の初期状態は，確率分布により与えられる
𝑆𝑡 ...時刻 𝑡 における状態を表す確率変数
𝑆𝑡 の確率分布 ... 𝜎個の確率の組で表現可能
𝐩𝑡 = (𝑃𝑆𝑡 𝑠0 , … 𝑃𝑆𝑡 𝑠𝜎 ) ： 時刻 𝑡 の確率ベクトル
𝐩0 を指定することで，初期状態を規定する
𝑠1
a / 0.4
a / 0.8
𝑠2
b / 0.5
b / 0.6
a / 0.5
b / 0.2
𝑠3
𝐩0 = 1,0,0
...必ず𝑠1 からスタート
𝐩0 = 0,0.5,0.5
...𝑠2 か𝑠3 のどちらかが，
等確率で初期状態に
24
状態の遷移と確率ベクトル
𝐩0 = 1,0,0
時刻0では，確率1で状態𝑠1
時刻1では，
確率 0.4で状態𝑠2
確率 0.6で状態𝑠3
𝐩1 = (0,0.4,0.6)
より一般的に， 𝐩𝑡+1 = 𝐩𝑡
𝑠1
a / 0.4
a / 0.8
𝑠2
b / 0.5
b / 0.6
a / 0.5
b / 0.2
𝑠3
0 0.4 0.6
0 0.8 0.2 となる
0.5 0.5 0
遷移確率行列 𝑇：
(𝑖, 𝑗)成分は，𝑠𝑖 から𝑠𝑗 への遷移確率
25
確率ベクトルの変化
𝐩0 = 1,0,0 とした場合
𝐩0 = 0,0.5,0.5 とした場合
それぞれの確率ベクトルの変化を観察する
𝑠1
a / 0.4
a / 0.8
𝑠2
b / 0.5
b / 0.6
a / 0.5
𝑠3
b / 0.2
𝑃𝑆𝑡 𝑠1
𝑃𝑆𝑡 (𝑠2 )
𝑃𝑆𝑡 (𝑠3 )
0
1
2
3
4
5
6
7
1.00 0.00 0.30 0.04 0.15 0.08 0.11 0.09
0.00 0.40 0.62 0.66 0.69 0.69 0.70 0.70
0.00 0.60 0.08 0.30 0.16 0.23 0.19 0.21
𝑃𝑆𝑡 𝑠1
𝑃𝑆𝑡 (𝑠2 )
𝑃𝑆𝑡 (𝑠3 )
0
1
2
3
4
5
6
7
0.00 0.25 0.05 0.14 0.08 0.11 0.09 0.10
0.50 0.65 0.67 0.70 0.69 0.70 0.70 0.70
0.50 0.10 0.28 0.16 0.22 0.19 0.21 0.20
26
正規マルコフ情報源の定常分布
確率ベクトルが特定の値に収束し，ほとんど変化しなくなった
遷移関係 𝑝𝑡+1 = 𝑝𝑡 𝑇 の不動点を定常分布と呼ぶ
正規マルコフ情報源には定常分布が必ず存在し，一意に定まる
定常分布 𝐩 = 𝑝1 , … , 𝑝𝜎 は，以下の連立方程式の解
𝐩 = 𝐩𝑇
𝑝1 + ⋯ + 𝑝𝜎 = 1
前ページの例では
0 0.4 0.6
𝑝1 , 𝑝2 , 𝑝3 = (𝑝1 , 𝑝2 , 𝑝3 ) 0 0.8 0.2
0.5 0.5 0
𝑝1 + 𝑝2 + 𝑝3 = 1
𝑝1 , 𝑝2 , 𝑝3
= (0.1,0.7,0.2)
27
定常分布の計算例
0/0.9
遷移確率行列は
1/0.1
𝑠1
0.9 0.1
𝑇=
0.4 0.6
𝑠2
0/0.4
1/0.6
解くべき連立方程式は
0.9 0.1
0.4 0.6
𝑝1 + 𝑝2 = 1
𝑝1 , 𝑝2 = (𝑝1 , 𝑝2 )
解は (𝑝1 , 𝑝2 ) = (0.8,0.2)
...これが定常分布
28
定常分布の性質
𝐩を正規マルコフ情報源の定常分布とするとき...
任意の 𝐩0 に対し， lim 𝐩𝑡 = 𝐩
𝑡→∞
初期状態の違いは，十分長い時間の後には無視できる
𝐩0 = 𝐩 とすると，正規マルコフ情報源は定常情報源となる
確率的には，いつでも同じ振る舞いをする
𝑠1
a / 0.4
正規マルコフ情報源 ＋ 「𝐩0 = 𝐩」という制約
⇒ 定常マルコフ情報源
a / 0.8
𝑠2
b / 0.5
b / 0.6
a / 0.5
𝑠3
b / 0.2
29
定常マルコフ情報源の性質
𝐩0 = 𝐩を定常分布とする定常マルコフ情報源を考える
0/0.9 1/0.1
𝐩0 = 𝐩1 = ⋯ = (0.8,0.2)
𝑠1
𝑠2
常に 𝑃𝑆𝑡 𝑠1 = 0.8, 𝑃𝑆𝑡 𝑠2 = 0.2
0/0.4
1/0.6
0が出力されるのは，
𝑆𝑡 = 𝑠1 で，確率0.9の遷移が発生，または
𝑆𝑡 = 𝑠2 で，確率0.4の遷移が発生
𝑃𝑋 0 = 𝑃𝑆𝑡 𝑠1 × 0.9 + 𝑃𝑆𝑡 𝑠2 × 0.4 = 0.8
同様に
𝑃𝑋 1 = 𝑃𝑆𝑡 𝑠1 × 0.1 + 𝑃𝑆𝑡 𝑠2 × 0.6 = 0.2
30
この先の議論について
以下では...
記憶のない定常情報源
記憶のある定常情報源
の違いについて，情報理論的に議論する
情報源が出力する複数の記号に着目する必要アリ
⇒ 情報源の拡大
31
情報源の拡大
𝑆 𝑛 : 定常情報源 𝑆 の 𝑛次拡大情報源;
𝑛個の出力記号を，まとめて1個のものと解釈する
出力記号を表す確率変数 𝑋 𝑛 = 𝑋1 … 𝑋𝑛
𝐷 𝑋 𝑛 = 𝑎1 , … , 𝑎𝑛 𝑎𝑖 ∈ 𝐷(𝑋)}
𝑃𝑋 𝑛 𝑎1, … , 𝑎𝑛 =
𝑃𝑋1 𝑎1 × 𝑃𝑋2 |𝑋1 𝑎2 𝑎1 × ⋯ × 𝑃𝑋𝑛 |𝑋1 …𝑋𝑛−1 (𝑎𝑛 |𝑎1, … , 𝑎𝑛−1 )
01000101
𝑋
𝐷(𝑋) = {0, 1}
01 00 01 01 𝑋 2
𝐷(𝑋 2 ) = {00, 01, 10, 11}
32
拡大情報源のエントロピー
コイン投げの2次拡大情報源
（拡大後の）記号
確率
表表
0.25
表裏
0.25
裏表
0.25
裏裏
0.25
この2次拡大情報源の1次エントロピーは:
𝐻1 𝑋 2 = 4 × −0.25log 2 0.25 = 2 bits
記号を 2個 1組で予測するときの難しさ
1個ずつ予測するときの 2倍難しい？
もう少し詳しく議論するため，以下を定義
𝐻1 (𝑋 𝑛 )/𝑛 = 𝑋の n次エントロピー 𝐻𝑛 (𝑋)
lim 𝐻1 (𝑋 𝑛 )/𝑛
𝑛→∞
= 𝑋の （極限）エントロピー 𝐻(𝑋)
33
記憶のない場合
𝑃𝑋 (0) = 0.8, 𝑃𝑋 (1) = 0.2 である定常無記憶情報源
𝑋
0
1
0.8
0.2
𝑋 2 00
01
10
11
0.64
0.16
0.16
0.04
𝐻1(𝑋) = – 0.8log0.8 – 0.2log0.2 = 0.72
𝐻1 𝑋 2 = – 0.64log0.64– 0.16log0.16
– 0.16log0.16– 0.04log0.04 = 1.44
𝐻2(𝑋) = 𝐻1 𝑋 2 /2 = 1.44/2 = 0.72
任意の 𝑛 に対して 𝐻1 𝑋 𝑛 = 0.72𝑛 となる？
34
記憶のない場合：証明
定理: 定常無記憶情報源なら，𝐻1 𝑋 𝑛 = 𝑛𝐻1 (𝑋).
n = 2 の場合の概略
無記憶性:
𝐻1 𝑆 2 = −
=−
=−
=−
=−
𝑎0 ∈𝐷(𝑋)
𝑎0
𝑎1
𝑎0
𝑎0
𝑎0
𝑎1 ∈𝐷(𝑋)
𝑃 𝑎0 , 𝑎1 log 2 𝑃 𝑎0 , 𝑎1
𝑃(𝑎0, 𝑎1) = 𝑃(𝑎0)𝑃(𝑎1)
𝑃 𝑎0 𝑃 𝑎1 log 2 𝑃 𝑎0 𝑃 𝑎1
𝑎1
𝑃 𝑎0 𝑃 𝑎1 log 2 𝑃 𝑎0 −
𝑃 𝑎0 log 2 𝑃 𝑎0
𝑃 𝑎0 log 2 𝑃 𝑎0 −
𝑎1
𝑃 𝑎1 −
𝑎1
𝑎0
𝑎1
𝑎1
𝑃 𝑎0 𝑃 𝑎1 log 2 𝑃 𝑎1
𝑃 𝑎1 log 2 𝑃 1
𝑃 𝑎1 log 2 𝑃 1
𝑎0
𝑃 𝑎0
𝑃(𝑎0)の総和は 1
= 𝐻1 𝑋 + 𝐻1 𝑋 = 2𝐻1 (𝑋)
系: 定常無記憶情報源なら，𝐻 𝑋 = 𝐻1 (𝑋)
35
記憶のある情報源（マルコフ情報源）の場合
0/0.9
1/0.1
𝑠1
𝑠2
0/0.4
0
1
00
01
10
11
定常分布: 𝐩 = (0.8,0.2)
1/0.6
0.8·0.9 + 0.2·0.4 = 0.80
𝐻1 𝑋 = 0.722
0.8·0.1 + 0.2·0.6 = 0.20
0.8·0.9·0.9 + 0.2·0.4·0.9 = 0.72
2 = 1.2914
𝐻
𝑋
1
0.8·0.9·0.1 + 0.2·0.4·0.1 = 0.08
2
𝐻
𝑋
1
0.8·0.1·0.4 + 0.2·0.6·0.4 = 0.08
𝐻2 𝑋 =
= 0.6457
2
0.8·0.1·0.6 + 0.2·0.6·0.6 = 0.12
2個同時に予測する難しさ
< 1個ずつ予測する難しさ × 2
36
マルコフ情報源のエントロピー
マルコフ情報源では H1(X) > H2(X) > ....
Hn(X)
定理:（証明略）
n次エントロピーは極限エントロピーに
H(X)
収束する
n
どのようにして 𝐻(𝑋) を計算するか:
1. 定常分布を計算
2. 状態をバラバラにし，それぞれを無記憶情報源と考える
3. 各状態のエントロピーを計算
4. 3 の結果の重み付き平均を計算
37
計算例
1/0.1
0/0.9
𝑠1
定常分布:
𝐩 = 0.8, 0.2
𝑠2
0/0.4
1/0.6
ℋ 𝑝 = −𝑝log 2 𝑝 − 1 − 𝑝 log 2 (1 − 𝑝)
0/0.9
0/0.4
𝑠1
状態𝑠1 , 𝐻 𝑋 = ℋ 0.9 = 0.469
状態𝑠2 , 𝐻 𝑋 = ℋ 0.4 = 0.971
𝑠2
1/0.1
1/0.6
重み付き平均= 0.8×0.469 + 0.2×0.971= 0.5694 bit = 𝐻(𝑋)
38
マルコフ情報源の拡大について：まとめ
マルコフ情報源の場合...
n次エントロピーは，n に対して単調現象する
n次エントロピーは，極限エントロピーに収束する
（マルコフ情報源以外の，任意の有記憶情報源でも成り立つ）
マルコフ情報源では，さらに，
極限エントロピーの計算は，比較的容易
Hn(X)
H(X)
n
記憶のある情報源では，
n 記号まとめて予測することの難しさは，
1 記号ずつ予測する難しさの n 倍よりも小さい
39
本日のまとめ
相互情報量について
マルコフ情報源
A
練習問題：右図のマルコフ情報源に対し，
0/0.4 0/0.5
定常確率分布を求めよ
010 が出力される確率を求めよ
1/0.2
B
極限エントロピー 𝐻(𝑋)を求めよ
0/0.8
1/0.5
1/0.6
C
レポート課題 / report assignment
http://isw3.naist.jp/~kaji/lecture/
40