...

のくやし

by user

on
Category: Documents
0

views

Report

Comments

Transcript

のくやし
前回の復習
: タイガースの試合結果,  =   =   = 1/3
: 阪神ファンの友人のtweet





やったー
くやしー
くやしー
p.13 のように同時確率の表を書き,周辺確率も求めよ
p.34 に示した3つの異なる方法で,相互情報量 (; )を求めよ
(ページ番号は前回スライドのもの)
1
相互情報量
相互情報量の計算法は3通りある
1.  ;  = 1  + 1  − 1 (, )
2.  ;  = 1  − 1 |
3.  ;  = 1  − 1 |
全部同じ値になるが,計算の手間が違う,かも
1(, )
1()
1(|)
1()
1(|)
(; ) = (; )
2
練習問題:手順1による(: )の計算
  や
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
練習問題:手順2による(: )の計算

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
練習問題:手順3による(: )の計算
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による計算


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による計算


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   ≫  |−1  
16
情報源の基本性質2:定常性
情報源は定常 ⇔
任意の , , 1 …  に対し
1 … (1 …  ) =  …+−1 (1 …  )
出力される記号の確率分布は,いつでも同じ
 = 1の場合を考えると,1  = ⋯ =   = ⋯ =  ()
... 1個の確率変数  で,全ての確率変数を代表できる
定常でない情報源 = 非定常情報源
天気...「雪の降る確率」は季節に依存
17
情報源の基本性質2+:エルゴード性
定常情報源がエルゴード的 ⇔
「情報源から出力される一続きの記号列」
の中に含まれる記号  の割合
サイコロ投げはエルゴード的
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つを取る
遷移辺に付与された確率に従い,状態が遷移する
状態遷移の際は,遷移辺に付与された記号が出力される
(初期状態については後述)
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  = 21 ()
系: 定常無記憶情報源なら,  = 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
Fly UP