物理フラクチュオマティクス論
Physical Fluctuomatics
第4回 最尤推定とEMアルゴリズム
4th Maximum likelihood estimation and EM algorithm
東北大学 大学院情報科学研究科 応用情報科学専攻
田中 和之(Kazuyuki Tanaka)
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
1 May, 2008
物理フラクチュオマティクス論(東北大)
1
今回の講義の講義ノート
田中和之著:
確率モデルによる画像処理技術入門,
森北出版,第4章,2006.
1 May, 2008
物理フラクチュオマティクス論(東北大)
2
ベイズの公式による確率的推論の例(1)
A 教授はたいへん謹厳でこわい人で,機嫌の悪いときが 3/4 を占め,
機嫌のよい期間はわずかの 1/4 にすぎない.
教授には美人の秘書がいるが,よく観察してみると,教授の機嫌の
よいときは,8 回のうち 7 回までは彼女も機嫌がよく,悪いのは 8
回中 1 回にすぎない.
教授の機嫌の悪いときで,彼女の機嫌のよいときは 4 回に 1 回で
ある.
秘書の機嫌からベイズの公式を使って教授の機嫌を確率的に推論
することができる.
甘利俊一:情報理論 (ダイヤモンド社,1970) より
1 May, 2008
物理フラクチュオマティクス論(東北大)
3
ベイズの公式による確率的推論の例(2)
教授は機嫌の悪いときが 3/4 を占め,機嫌のよい期間はわずかの
1/4 にすぎない.
1
Pr教授機嫌良い  
4
3
Pr教授機嫌悪い  
4
教授の機嫌のよいときは,8 回のうち 7 回までは彼女も機嫌がよく,
悪いのは 8 回中 1 回にすぎない.
7
Pr秘書機嫌良い 教授機嫌良い  
8
教授の機嫌の悪いときで,彼女の機嫌のよいときは 4 回に 1 回である.


Pr 秘書機嫌良い 教授機嫌悪い 
1 May, 2008
物理フラクチュオマティクス論(東北大)
1
4
4
ベイズの公式による確率的推論の例(3)
P r秘書機嫌良し


 P r秘書機嫌良し 教授機嫌悪い P r教授機嫌悪い 
 P r 秘書機嫌良し 教授機嫌良し P r教授機嫌良し
7 1 1 3 13
    
8 4 4 4 32
1


Pr 教授機嫌良い 
Pr教授機嫌悪い  
4


Pr 秘書機嫌良い 教授機嫌悪い 
1 May, 2008

3
4

1
7
Pr 秘書機嫌良い 教授機嫌良い 
4
8
物理フラクチュオマティクス論(東北大)
5
ベイズの公式による確率的推論の例(4)

P r 教授機嫌良し 秘書機嫌良し

7 1
P r 秘書機嫌良し 教授機嫌良し P r教授機嫌良し 8  4 7



13
P r秘書機嫌良し
13
32




7
Pr 秘書機嫌良い 教授機嫌良い 
8
Pr教授機嫌良い  
1
4
13
Pr秘書機嫌良い  
32
1 May, 2008
物理フラクチュオマティクス論(東北大)
6
統計的学習理論とデータ
観察により得られたデータから確率を求めた例
教授の機嫌のよいときは,8 回のうち 7 回までは秘書も機嫌がよく,
悪いのは 8 回中 1 回にすぎない.
7
Pr秘書機嫌良い 教授機嫌良い  
8
すべての命題に対してデータが完全かつ十分に得られている場合
標本平均,標本分散などから確率を決定することができる.
「教授の機嫌の悪いときで,彼女の機嫌のよいとき」の
データが分からなかったらどうしよう?
不完全データ
1 May, 2008
物理フラクチュオマティクス論(東北大)
7
統計的学習理論とモデル選択
データから確率モデルの確率を推定する操作
モデル選択
統計的学習理論における確率モデルのモデル選択の代表例
最尤推定に基づく定式化
更なる
拡張
不完全データにも対応
EMアルゴリズムによるアルゴリズム化
確率伝搬法,マルコフ連鎖モンテカルロ法に
よるアルゴルズムの実装
赤池情報量基準(AIC),赤池ベイズ情報量基準(ABIC) etc.
1 May, 2008
物理フラクチュオマティクス論(東北大)
8
最尤推定
データ
パラメータ
 ,
 g0 


  g1 
g 
 


g 
 N 1 

ˆ ,ˆ   arg max Pg , 
 , 
N 1

Pg  ,    
 1
2
g i    
exp 
2
2
 2

i  0 2
 Pg  ,  
0

極値条件  
   ˆ , ˆ
 Pg  ,  
0





   ˆ , ˆ
標本平均
1 May, 2008
1
平均μと標準偏差σが与えられたと

きの確率密度関数をデータ g が与
えられたときの平均μと分散σ2に対
する尤もらしさを表す関数(尤度関
数)とみなす.
1 N 1
1 N 1
2
2
ˆ
ˆ




g


ˆ 
g
 i
 i
N i 0
N i 0
物理フラクチュオマティクス論(東北大)
標本分散
9
最尤推定
データ



 
f 








f N 1 
f0
f1

極値条件


 g0 


  g1 
g 
 


g 
 N 1 
 
 
 Pg  ,  
0





  ˆ , ˆ
 , 

 

 
P f , g  ,  P g f , P f 


N 1

P g f ,  
i 0
 1
2
exp  2 gi  f i  
 2

2 2
1
 
N 1


  
P f  
exp  f i 2 
2
 2 
i 0
 Pg  ,  
0





  ˆ , ˆ
1
 1 N 1 2 
    fi 
N

 i 0

1 May, 2008

 
ˆ ,ˆ   arg max P f , g  , 
パラメータ
N 1
1
2
2
   gi  f i 
N i 1
物理フラクチュオマティクス論(東北大)
10

f
最尤推定
が分からなかったらどうしよう

ˆ  arg max Pg  
データ
ハイパパラメータ



 
f 



不完全





f N 1 
f0
f1

データ
パラメータ

ベイズの公式


f


N 1

P g f ,  
 ˆ
i 0
 1
2
exp  2 gi  f i  
 2

2 2
1

 N 1
P f 
0
i 0
1
 1 
exp  fi 2 
2
 2 


まずP f は完全に
1
ˆ  1   gi2
N i 1


f
2

 
P g f , P f

P f g, 

Pg  
1 May, 2008



N 1
不完全
データ

周辺尤度
極値条件  Pg   1,  


 


 
Pg    
P f ,g  
P g f , P f


 g0 


  g1 
g 
 


g 
 N 1 
わかっている場合
を考えよう.


 
ˆ

f   f P f g , ̂ df
物理フラクチュオマティクス論(東北大)
11
信号処理の確率モデル
観測信号  原信号 白色ガウス雑音
雑音
gi
fi
i
i
通信路
原信号
観測信号
尤度
事前確率













事後確率


 Pr観測信号 | 原信号 Pr原信号 
Pr原信号 観測信号  
Pr観測信号 

ベイズの公式
1 May, 2008
周辺尤度
物理フラクチュオマティクス論(東北大)
12
原信号の事前確率
 

P f 
1
Z Prior
 1
2
exp     f i  f j  
 2 ijB

画像データの場合
1次元信号データの場合
Ω:すべてのノード
(画素)の集合
1 May, 2008
B:すべての最近接
ノード(画素)対の集合
物理フラクチュオマティクス論(東北大)
13
データ生成過程
加法的白色ガウス雑音 (Additive White Gaussian Noise)


 
P g f ,  
i
 1
2
exp  2  f i  gi  
 2

2 2
1

gi  fi ~ N 0, 2
1 May, 2008
物理フラクチュオマティクス論(東北大)

14
信号処理の確率モデル
パラメータ


 
f 




不完全
データ





f N 1 
f0
f1

データ
 g0 


  g1 
g 
 


g 
 N 1 

gi
fi
i
ハイパパラメータ
i



P g f ,  
i
 

1
 1
2


P f 
exp


f

f
  2 i j 
Z prior ijB
fˆi  




f i P f g ,  ,  df


 
 

 
P g f , P f 

P f g, , 


 
 P g f , P f  df

事後確率
1 May, 2008
 1
2
exp  2 gi  f i  
 2

2 2
1
物理フラクチュオマティクス論(東北大)

15
信号処理の最尤推定
パラメータ



 
f 



不完全
データ





f N 1 
f0
f1

ハイパパラメータ

データ
 g0 


  g1 
g 
 


g 
 N 1 

ˆ , ˆ   arg max Pg  ,  
 , 

 



 
Pg  ,     P g f ,  P f  df
周辺尤度
極値条件
 Pg  ,  
 Pg  ,  
 0, 
0






 ˆ , ˆ

 ˆ , ˆ
1 May, 2008
物理フラクチュオマティクス論(東北大)
16
最尤推定とEMアルゴリズム
パラメータ

不完全
データ




 

f 



f 
 N 1 
f0
f1


データ
 g0 


  g1 
g 
 


g 
 N 1 
ハイパパラメータ
E Step : CalculateQ ,   (t ), (t ) 
M Step : Update
α(t  1),σ (t  1)
 arg maxQ ,   (t ), (t ) 
( , )
EM アルゴリズムが収束すれば
周辺尤度の極値条件の解になる.
1 May, 2008

 



 
Pg  ,     P g f ,  P f  df
周辺尤度
Q関数
Q ,   ,  

 

  P f g ,  ,   ln P f , g  ,  df

 

 Q  ,   ,  
0





   , 
 Q  ,   ,  
0




   , 
 Pg  ,  
 Pg  ,  

0
,
0









 ˆ , ˆ

 ˆ , ˆ
物理フラクチュオマティクス論(東北大)
極値条件
17
1次元信号のモデル選択
EM Algorithm
Original Signal
200
fi
100
0.04
0
Degraded Signal
200
0
127
i
255
i
255
0.03
α(t)
0.02
gi
  40
100
0
0
Estimated Signal
127
0.01
200
fˆi
0
100
0
1 May, 2008
0
127
i
255
α(0)=0.0001, σ(0)=100
物理フラクチュオマティクス論(東北大)
18
ノイズ除去のモデル選択
原画像
  40
劣化画像
MSE
327
推定画像
ˆ
0.000611
ˆ
36.30
EMアルゴリズムと
確率伝搬法
α(0)=0.0001
σ(0)=100
MSE 
1 May, 2008

1
 fi  fˆi
|  | i

2
MSE
ˆ
ˆ
260
0.000574
34.00
物理フラクチュオマティクス論(東北大)
19
ガウス混合モデル
  (0) 


   (1) 
 




  ( K  1) 


 a0 


  a 
a  1 



a 
 N 1 
 a0 


  a1 
a 
 


a 
 N 1 
  (1) 
  (1) 




   (2)     (2) 
 
,  
 
 




  (K ) 
 ( K ) 






N
  
P f a,  ,  
i 1
1 May, 2008
N

Pa     ai 
i 1


 
f 



K
  k   1
k 1





f N 1 
f0
f1


1
2
 f i   ai  
exp 
2
2  ai 
 2 ai 

1
物理フラクチュオマティクス論(東北大)
20
ガウス混合モデルのベイズ推定
事後確率
パラメータ


不完全
データ
 a0 


  a1 
a 
 


a 
 N 1 

    
P a f ,  ,  ,
   
P f a ,  ,  Pa  
   

 P f a,  , Pa  
データ






 
f 




ベイズの公式





f N 1 
f0
f1



a



N

Pa     ai 
i 1
ハイパパラメータ


N
  
P f a,  ,  
i 1
1 May, 2008

1
2

 f i   ai  
exp 
2
2  ai 
 2 ai 

1
物理フラクチュオマティクス論(東北大)
21
ガウス混合モデルのEMアルゴリズム
パラメータ


不完全
データ
 a0 


  a1 
a 
 


a 
 N 1 




周辺尤度

データ


 
f 








f N 1 
f0
f1


 
P f μ,σ,
    
  P f a,μ,σ P a γ 

a
N

K
 
i 1 k 1

 1  64,  2  127,
 3  192,  4  192,
 1   2
  3   4  10
  f i   k 2 
 k 

exp 
2
2 k  
2  k 

ˆ ˆ ˆ
  


 ,  ,   arg max P f  ,  ,  


ハイパパラメータ
    
   
   
Q , ,   , ,    Pa f ,  , , ln Pa, f  , ,  
  
 ,  ,

a
EM アルゴリズム
(t  1),  (t  1),σ(t  1)  arg (max
   Q ,  ,   (t ),  (t ), (t ) 
 ,  , )
1 May, 2008
物理フラクチュオマティクス論(東北大)
22
ガウス混合モデルの数値実験

  
P f a,  , 

Pa γ 

観測データ
 1  64,  2  127,
 3  192,  4  192,
 1   2   3   4  10
ˆ 1  63.4, ˆ 2   91.6,
ˆ 3  127.5, ˆ 4   191.5,
ˆ 1  7.5, ˆ 2   7.5
ˆ 3  7.5, ˆ 4   7.6
ˆ 1  0.20, ˆ 2   0.16
ˆ 3  0.53, ˆ 4   0.11


 
周辺確率
P f μ,σ,
    
  P f a,μ,σ P a γ 
推定結果


a
N
K
 
i 1 k 1


  f i   k 2 
 k 

exp 
2



2

k
2  k 



   

P f a ,  ,  P a   事後確率
   
   
P a f ,  ,  , 
 P f a,  ,  Pa  



a
1 May, 2008
観測データの
ヒストグラム
物理フラクチュオマティクス論(東北大)


23
ガウス混合モデルの数値実験

a

  
P f a,  , 


f
 1  64,  2  127,
 3  192,  4  192,
 1   2   3   4  20
Gauss Mixture Model



1 
Pa γ  
    ai   exp  ai ,a j
Z PR γ   i
 ijB
ポッツモデル
1 May, 2008
+Potts Model





+EM Algorithm
+Belief Propagation

â
物理フラクチュオマティクス論(東北大)
24
ガウス混合モデルによる
領域分割の数値実験
観測画像
ヒストグラム
 1  12.7,  1  2.7,  1  0.1831
 2   42.2,  2   18.0,  2  0.0711
 3  130.6,  3  23.6,  3  0.3375
 4   168.4,  4  11.7,  4  0.3982
 5  224.8,  5  14.4,  5  0.0101
1 May, 2008
Gauss Mixture
Gauss Mixture
Model
Model and
物理フラクチュオマティクス論(東北大)
Potts Model
Belief
Propagation
25
統計的学習理論による移動体検出
a
Segmentation
a b
b
bc
Detection
AND
Segmentation
c
Gauss Mixture Model and Potts Model with Belief Propagation
1 May, 2008
物理フラクチュオマティクス論(東北大)
26
まとめ
最尤推定とEMアルゴリズム
ガウス混合モデル
項目応答理論
1 May, 2008
物理フラクチュオマティクス論(東北大)
27
ダウンロード

PPT