Document

Report
人工知能特論II 第9回
二宮 崇
1
今日の講義の予定

EMアルゴリズム




EMアルゴリズムの別の導出法と理解
混合モデルのEMアルゴリズム
HMMのEMアルゴリズム
教科書



北研二(著) 辻井潤一(編) 言語と計算4 確率的言語モ
デル 東大出版会
C. D. Manning & Hinrich Schütze
“FOUNDATIONS OF STATISTICAL NATURAL
LANGUAGE PROCESSING” MIT Press, 1999
Christopher M. Bishop “PATTERN
RECOGNITION AND MACHINE LEARNING”
Springer, 2006
2
ジェンセンの不等式
ジェンセンの不等式
 凸関数 f(x) は区間 I 上の実数値関数
 p1,p2,...,pnはp1+p2+...+pn=1を満たす非負の実数
 任意のx1,x2,...,xn∈ I に対し次の不等式が成り立つ
p1 f ( x1 )  p 2 f ( x 2 )    p n f ( x n )  f ( p1 x1  p 2 x 2    p n x n )

f(x)=-log(x)、xi=qi /piとおくと

i

qi 
   log
p i log
  log   p i

qi
p
i 
 i
pi
q
i
i
0
3
EMアルゴリズムの全体像
~
  arg max l ( )

問題変形

( i 1)
 arg max Q (
(i)
[Eステップ] p(y | x ; θ)
を計算
, )

個々の問題に応じ
て決まるQ関数の
極値を解析的に求
める
[Mステップ]

( i 1)
 arg max Q (
(i)
, )

によりパラメータ更新
個々の問題によって決
まるパラメータ更新式
4
EMアルゴリズムの別の導出法と理
解
5
EMアルゴリズムの
別の導出法と理解 1/3





パラメータ: θ
入力: x
隠れ状態: y
観測データ: X={x1, x2, …, xn}
対数尤度: log pθ(X)
n
log p θ ( X )

 log
n
pθ (x i ) 
i 1
  q (y
i
| x i ) log p θ ( x i )
i  1 y i Y ( x i )
n

  q (y
i
| x i ) log p θ ( x i , y i )  log p θ ( y i | x i ) 
i
| x i ) log p θ ( x i , y i )  log q ( y i | x i )  log p θ ( y i | x i )  log q ( y i | x i ) 
i  1 y i Y ( x i )
n

  q (y
i  1 y i Y ( x i )
n


i 1
n


i 1

pθ (x i , y i )
pθ (y i | x i ) 
q
(
y
|
x
)
log

log

 i i  q (y | x )
q
(
y
|
x
)
y i Y ( x i )
i
i
i
i


n
pθ (x i , y i )
pθ (y i | x i )
q
(
y
|
x
)
log

q
(
y
|
x
)
log
 i i
  i i
q
(
y
|
x
)
q (y i | x i )
y i Y ( x i )
i  1 y i Y ( x i )
i
i
6
EMアルゴリズムの
別の導出法と理解 2/3





パラメータ: θ
入力: x
隠れ状態: y
観測データ: X={x1, x2, …, xn}
対数尤度: log pθ(X)
n
L (q, θ) 
 
q ( y i | x i ) log
i  1 y i Y ( x i )
n
KL ( q || p )   

ポイント!
前ページのように式を展開するよりも
ここに
log p θ ( x i , y i )  log p θ ( y i | x i )  log p θ ( x i )
を代入して等式が成り立つことを確認
するほうがわかりやすい
pθ ( xi , yi )
q ( yi | xi )
q ( y i | x i ) log
i  1 y i Y ( x i )
pθ ( yi | xi )
0
q ( yi | xi )
とおくと
log p θ ( X )
 L ( q , θ )  KL ( q || p )
 L (q, θ)
7
EMアルゴリズムの
別の導出法と理解 3/3

q
(  1 )
Eステップ
( y i | x i )  arg max L ( q ( y i | x i ), θ
q ( y i |x i )
( )
)  arg min KL ( q ( y i | x i ) || p θ (  ) ( y i | x i ))  p θ (  ) ( y i | x i )
q ( y i |x i )
パラメータが固定されているので、pθ(X) は変わらない
→ Lを最大化 ⇔ KLを最小化

Mステップ
θ
(  1 )
 arg max L ( q
θ
(  1 )
n
, θ )  arg max
θ
 q
(  1 )
( y i | x i ) log p θ ( x i , y i )
i 1 y i Y ( x i )
Q関数
隠れ状態の確率とパラメータを交互に動かし
て、Lを最大化
8
EMアルゴリズムによる混合モデル
のパラメータ更新
9
混合モデルのパラメータ更新式
導出

混合モデル (mixture model)
観測データx1,..,xnに対し、それらを生成する複
数の隠れ状態y1,...,ymを仮定
 いずれかの隠れ状態がλj (=p(yj) )の確率で選択
され、その隠れ状態から観測データxがp(x | yj)
の確率で生成されたと考える

m
p(x) 

m
p ( x, y j ) 
j 1

j 1
m
p( y) p(x | y j ) 

j
p ( x | y j ) j 1
m
ただし 
j
1
j 1
10
混合モデルのパラメータ更新式
導出

混合モデル (mixture model)
m
p( x) 
m

p ( x, y j ) 
j 1

j 1
m
p( y) p(x | y j ) 

j
p ( x | y j ) j 1
m
ただし 
j
1
j 1

Q関数
n
Q (  ,  ) 
m

i 1
p ( y j | x i ;  ) log p ( x i , y j ;   )
j 1
11
混合モデルのパラメータ更新式
導出

Q関数を最大化するλ’を見つける⇒ラグラ
ンジュの未定乗数法

(  1 )
 arg max Q ( 
( )
,)

n
Q (  ,  ) 
m

i 1
p ( y j | x i ;  ) log p ( x i , y j ;   )
j 1
12
ラグランジュの未定乗数法

ラグランジュの未定乗数法
arg max f ( θ )ただし g 1 ( θ )  0 ,..., g m ( θ )  0
θ

L ( θ )  f ( θ )   1 g 1 ( θ )  ...   m g m ( θ )
L
1

 0,
L
 2
 0 ,...,
L
 n
0
ラグランジュ関数
 m

L (  ,  )  Q (  ,   )      j  1 


j

1


13
混合モデルのパラメータ更新式
導出

ラグランジュ関数を偏微分
 L (  ,  )
  k
n


i 1
n


i 1
n


i 1
n


i 1
n


i 1
 log p ( x i , y j ;   ) 
 p ( y j | xi ;  )
log p ( x i , y j ;   )  p ( y j | x i ;  )


  k
  k
j 1 

m
 log p ( x i , y j ;   ) 


  p ( y j | xi ;  )

k
j 1 

m 
 p ( x i , y j ;   ) 
1


  p ( y j | x i ;  ) p ( x , y ;  )
  k

j 1 
i
j

1
p ( y k | xi ;  )
p ( x i | y k ;  )  
 k p ( x i | y k ;   )
1
p ( y k | xi ;  )
  0
 k
m
14
混合モデルのパラメータ更新式
導出
1
 k 

n

p ( y k | xi ;  )
i 1
m

j
 1であるから
j 1
p ( xi , y k )
p ( y k | xi ) 
1


p ( xi )
n
m

1
p ( y j | xi ;  ) 

j 1 i 1
p ( xi , y k )
m

j 1
p ( xi , y j )

n
 1  1より
 n
i 1
 k p ( xi | y k )
m

j
p ( xi | y j )
j 1
したがって
 k 
1
n
n

i 1
 k p ( xi | y k )
m

j
p ( xi | y j )
j 1
15
HMMの教師無し学習
EMアルゴリズムによるHMMのパラ
メータ更新
16
HMMのパラメータ更新式導出

Q関数
n
Q ( ,   )


i 1
n


p ( y i | x i ;  ) log p ( x i , y i ;   )
yi

p ( q 1  q Ti | o1  o Ti ;  ) log p ( q 1  q Ti , o1  o Ti ;  ' )
i  1 q 1  Q , , q T  Q
i
n



i  1 q 1  Q , , q T  Q
i
n



i  1 q 1  Q , , q T  Q
i
Ti
Ti


p ( q 1  q Ti | o1  o Ti ;  ) log   ' q1  a ' q t 1 , q t  b ' q t , o t 
t2
t 1


Ti
Ti

p ( q 1  q Ti | o1  o Ti ;  )  log  ' q1   log a ' q t 1 , q t   log b ' q t , o t
t2
t 1





17
HMMのパラメータ更新式導出

Q関数のラグランジュ関数
n
L ( ,   )



i  1 q 1  Q , , q T  Q
i

  1 


Ti

p ( q 1  q Ti | o1  o Ti ;  )  log  ' q1   log a ' q t 1 , q t 
t2



  q  
qQ


  q  1 
qQ



 a q , r  
r Q


qQ

Ti

t 1

log b ' q t , o t  


 q  1   b q , o 

o 

ラグランジュ乗数
ρ … 1個の変数
αq … |Q|個の変数
βq … |Q|個の変数
18
HMMのパラメータ更新式導出
 L ( ,   )
n
  q
i 1


q

p ( q 1  q Ti | o1  o Ti ;  )[ q 1  q ]    0
q q 1  Q , , q Ti  Q
n
1
 q 
1
 



p ( q 1  q Ti | o1  o Ti ;  )[ q 1  q ]
 (1)
i  1 q 1  Q , , q T  Q
i
 1より
qQ
1

n


p ( q 1  q Ti | o1  o Ti ;  )[ q 1  q ] 
q  Q i  1 q 1  Q , , q T  Q
i
n
1



p ( q 1  q T i | o1  o T i ;  )  1
i  1 q 1  Q , , q T  Q
i
したがって、
n
  
n

p ( q 1  q T i | o1  o T i ;  )   
i  1 q 1  Q , , q T  Q
i 1
i

p ( q 1  q T i , o1  o T i ;  )
q 1  Q , , q T  Q
i
p ( o1  o T i ;  )
n
 
i 1

p ( q 1  q T i , o1  o T i ;  )
q 1  Q , , q T  Q
i

p ( q 1  q T i , o1  o T i ;  )
 n
q 1  Q , , q T  Q
i
(1)に代入して、
n

 q 

p ( q 1  q Ti | o1  o Ti ;  )[ q 1  q ]
i  1 q 1  Q , , q T  Q
i
n
19
HMMのパラメータ更新式導出
 L ( ,   )
 a q , r
a q , r 
 a
q ,r
n
1

a q , r
i  1 q 1  Q , , q T  Q
i
n
1


q
i  1 q 1  Q , , q T  Q
i
 1より、

r  Q
r Q
n

q  


q

r  Q i  1 q 1  Q , , q T  Q
i
n


a q , r 
i  1 q 1  Q , , q T  Q
i
n




i  1 q 1  Q , , q T  Q
i
 (1)

 Ti
p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t 1 ][ r   q t ]   1、よって、

 t2

 Ti
p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t 1 ][ r   q t ] 。これを式

 t2
(1)に代入して、

 Ti
p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t 1 ][ r  q t ] 

 t2
r  Q i  1 q 1  Q , , q T  Q
i

 Ti
p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t 1 ][ r  q t ] 

 t2
n
1

 Ti
p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t 1 ][ r  q t ]    q  0

 t2

 Ti
p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t 1 ][ r   q t ] 

 t2
20
HMMのパラメータ更新式導出
 L ( ,   )

 b q , o
b q , o 
b q , o
i

i  1 q 1  Q , , q T  Q
i
 1より、

o  
o 
n
 q 

i  1 q 1  Q , , q T  Q

 q
q ,o

n
1
 b
n
1

 q

o   i  1 q 1  Q , , q T  Q
i
n

b q , o 

i  1 q 1  Q , , q T  Q
i
n




i  1 q 1  Q , , q T  Q
i
 (1)
 Ti

p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t ][ o   o t ]   1、よって
 t 1

 Ti

p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t ][ o   o t ] 、(1)に代入すると、
 t 1

 Ti

p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t ][ o  o t ] 
 t 1

o   i  1 q 1  Q , , q T  Q
i
 Ti

p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t ][ o  o t ] 
 t 1

n
1
 Ti

p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t ][ o  o t ]    q  0
 t 1

 Ti



p ( q 1  q Ti | o1  o Ti ;  )   [ q  q t ][ o  o t ] 
 t 1

21
HMMのEMアルゴリズム
1.
2.
3.
4.
π(0) := 適当な値; a(0) := 適当な値; b(0) := 適
当な値
[Eステップ]全ての可能な状態列に対し、
π(j),a(j),b(j)を用いて各々の状態列の確率を計
算。文に対する各状態列の相対確率を計
算。
[Mステップ] π( j+1),a( j+1), b( j+1)を求める
2.に戻る
22
HMMのEMアルゴリズム
[Eステップ] π(j), a(j),b(j)を用いて各状態列の確
率を計算。文xに対する各状態列の相対確
率を計算。
T
p ( q 1 o1  q T o T ; 
( j)
)   q1
( j)

t2
p ( q 1  q T | o1  o T ;  ) 
T
a q t 1 , q t  b q t , o t
( j)
p ( q 1 o1  q T o T ;  )
p ( o1  o T ;  )
( j)
t 1

p ( q 1 o1  q T o T ;  )

p ( q '1 o1  q 'T o T ;  )
q '1  Q , q 'T  Q
23
HMMのEMアルゴリズム
[Mステップ] π( j+1)を求める
n


( j 1)
q


p ( q 1  q T i | o1  o T i ; 
( j)
)[ q 1  q ]
i  1 q 1  Q , , q T  Q
i
n
n



p ( qq 2  q Ti | o1  o Ti ; 
( j)
)
i  1 q 2  Q , , q T  Q
i
n

先頭が q となる回数の期待値
n
24
HMMのEMアルゴリズム
[Mステップ] a( j+1)を求める
n

( j 1)
a q ,r


i  1 q 1  Q , , q T  Q
p ( q 1  q T i | o1  o T i ; 
( j)
i
n


r  Q i  1 q 1  Q , , q T  Q
p ( q 1  q T i | o1  o T i ; 
( j)
i
n



p ( q 1  q T i | o1  o T i ; 
( j)
i  1 q 1  Q , , q T  Q
 Ti

)   [ q  q t 1 ][ r  q t ] 
 t2

 Ti

)   [ q  q t 1 ][ r   q t ] 
 t2

) C ( q , r ; q 1  q Ti )
i
n


p ( q 1  q T i | o1  o T i ; 
r  Q i  1 q 1  Q , , q T  Q
( j)
) C ( q , r ; q 1  q Ti )
i

状態 q から状態
r へ遷移する回数の期待
状態 q から遷移する回数の期
C ( q , r ; q1  q T )
値
待値
q 1  q T の中で q から r に遷移する回数
25
HMMのEMアルゴリズム
[Mステップ] b( j+1)を求める
n

( j 1)
bq ,o

i  1 q 1  Q , , q T  Q

p ( q 1  q T i | o1  o T i ; 
( j)
i
n


o   i  1 q 1  Q , , q T  Q
p ( q 1  q T i | o1  o T i ; 
( j)
i
n



p ( q 1  q T i | o1  o T i ; 
i  1 q 1  Q , , q T  Q
( j)
 Ti

)   [ q  q t ][ o  o t ] 
 t 1

 Ti

)   [ q  q t ][ o   o t ] 
 t 1

) C ( q , o ; q 1  q T i , o1  o T i )
i
n


p ( q 1  q T i | o1  o T i ; 
( j)
i  1 q 1  Q , , q T  Q
) C ( q ; q1  q Ti )
i

C ( q ; q1  q T )
状態 q に滞在し記号
o を出力する回数の期待
状態 q に滞在する回数の期待
値
値
q 1  q T の中で q が出現した回数
C ( q , o ; q 1  q T , o1  o T )
q 1  q T o1  o T の中で q から o を出力する回数
26
状態遷移回数の期待値の例


q, rの2つの状態があるとする (例えば、名詞、動詞)
o1o2o3o4に対する状態列を列挙
状態 q から状態


r へ遷移する回数の期待
値
p ( q 1  q T | o1  o T )  ( q 1 q 2  q T における
q から r への遷移回数
q 1  Q , , q T  Q
qからrに遷移する回数の期待値:
(0.02+0.008+0.02+0.001+0.03*2+0.02+0.08+
0.085+0.024+0.011+0.098)/0.626
=0.476/0.626=0.7603
状態列
q1 q2 q3 q4
qqqq
qqqr
qqrq
qqrr
) qrqq
qrqr
qrrq
qrrr
rqqq
rqqr
rqrq
rqrr
rrqq
rrqr
rrrq
rrrr
確率
p(q1o1q2o2
q3 o 3 q4 o 4 )
0.03
0.02
0.008
0.02
0.001
0.03
0.02
0.08
0.082
0.085
0.024
0.011
0.009
0.098
0.053
0.055
27
HMMのためのEMアルゴリズム
の問題点

期待値を計算するために全ての可能な隠れ
状態を列挙すると文長に対し、指数爆発的
計算量が必要
解決策:前向き後向きアルゴリズム。隠れ状
態を列挙することなく、この期待値を計算す
る動的計画法。
28
まとめ

EMアルゴリズム
別の導出法と理解
 混合モデルのEMアルゴリズム
 HMMのEMアルゴリズム


資料

http://aiweb.cs.ehime-u.ac.jp/~ninomiya/ai2/
29

similar documents