数理言語 - 愛媛大学｜人工知能

人工知能特論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 )  p2 f ( x2 )   pn f ( xn )  f ( p1x1  p2 x2   pn xn )

f(x)=－log(x)、xi=qi /piとおくと

pi
qi 
i pi log qi   log i pi pi    log i qi  0


3
EMアルゴリズムの全体像
~
  arg maxl ( )

問題変形
[Eステップ] p(y | x ; θ)
を計算
 (i1)  arg maxQ( (i) , )

個々の問題に応じ
て決まるQ関数の
極値を解析的に求
める
[Mステップ]
 (i1)  arg maxQ( (i) , )

によりパラメータ更新
個々の問題によって決
まるパラメータ更新式
4
EMアルゴリズムの別の導出法と理
解
5
EMアルゴリズムの
別の導出法と理解 1/3





パラメータ: θ
入力: x
隠れ状態: y
観測データ: X={x1, x2, …, xn}
対数尤度: log pθ(X)
n
n
log pθ ( X )   log pθ (xi )  
i 1
n
 q(y
i 1 y i Y ( xi )
i
| xi ) log pθ (xi )

 q(y
i
| xi )log pθ (xi , y i )  log pθ (y i | xi )

 q(y
i
| xi )log pθ (xi , y i )  log q(yi | xi )  log pθ (y i | xi )  log q(y i | xi )
i 1 y i Y ( xi )
n
i 1 y i Y ( xi )
n
 pθ (xi , yi )
pθ (y i | xi ) 
q
(
y
|
x
)
log

log


i
i 
q
(
y
|
x
)
q
(
y
|
x
)
i 1 y i Y ( xi )
i
i
i
i 

n
n
p (x , y )
p (y | x )
   q(y i | xi ) log θ i i    q(y i | xi ) log θ i i
q(y i | xi ) i 1 yi Y ( xi )
q(y i | xi )
i 1 y i Y ( xi )

6
EMアルゴリズムの
別の導出法と理解 2/3





パラメータ: θ
入力: x
隠れ状態: y
観測データ: X={x1, x2, …, xn}
対数尤度: log pθ(X)
n
L(q, θ)  
 q( yi | xi ) log
i 1 yi Y ( xi )
n
KL(q || p)  
pθ ( xi , yi )
q( yi | xi )
 q( yi | xi ) log
i 1 yi Y ( xi )
ポイント!
前ページのように式を展開するよりも
ここに
log pθ (xi , yi )  log pθ (yi | xi )  log pθ (xi )
を代入して等式が成り立つことを確認
するほうがわかりやすい
pθ ( yi | xi )
0
q( yi | xi )
とおくと
log pθ ( X )  L(q, θ)  KL(q || p)
 L(q, θ)
7
EMアルゴリズムの
別の導出法と理解 3/3

Eステップ
q( 1) (yi | xi )  arg max L(q(yi | xi ), θ( ) )  arg min KL(q(yi | xi ) || pθ( ) (yi | xi ))  pθ( ) (yi | xi )
q( yi |xi )
q( yi |xi )
パラメータが固定されているので、pθ(X) は変わらない
→ Lを最大化 ⇔ KLを最小化

Mステップ
( 1)
θ
 arg max L(q
θ
( 1)
n
, θ)  arg max
θ
q 
i 1 y i Y ( xi )
( 1)
(yi | xi ) log pθ (xi , yi )
Q関数
隠れ状態の確率とパラメータを交互に動かして、
Lを最大化
8
EMアルゴリズムによる混合モデル
のパラメータ更新
9
混合モデルのパラメータ更新式
導出

混合モデル (mixture model)
観測データx1,..,xnに対し、それらを生成する複
数の隠れ状態y1,...,ymを仮定
 いずれかの隠れ状態がλj (=p(yj) )の確率で選択
され、その隠れ状態から観測データxがp(x | yj)
の確率で生成されたと考える

m
m
m
j 1
j 1
j 1
p( x)   p( x, y j )   p( y) p( x | y j )    j p( x | y j )　m
ただし　  j  1
j 1
10
混合モデルのパラメータ更新式
導出

混合モデル (mixture model)
m
m
m
j 1
j 1
j 1
p( x)   p( x, y j )   p( y) p( x | y j )    j p( x | y j )　m
ただし　  j  1
j 1

Q関数
n
m
Q(, )   p( y j | xi ; ) log p( xi , y j ; )
i 1 j 1
11
混合モデルのパラメータ更新式
導出

Q関数を最大化するλ’を見つける⇒ラグラ
ンジュの未定乗数法
( 1)  arg maxQ(( ) ,  )

n
m
Q(, )   p( y j | xi ;  ) log p( xi , y j ; )
i 1 j 1
12
ラグランジュの未定乗数法

ラグランジュの未定乗数法
arg max f (θ)ただし g1 (θ)  0,...,gm (θ)  0
θ

L(θ)  f (θ)  1 g1 (θ)  ... m gm (θ)
L
L
L
 0,
 0,...,
0
1
2
n

ラグランジュ関数
m

L(,  )  Q(, )     j 1
 j 1

13
混合モデルのパラメータ更新式
導出

ラグランジュ関数を偏微分
n m
 log p( xi , y j ; ) 
 p( y j | xi ;  )
L(,  )
  
log p( xi , y j ; )  p( y j | xi ;  )
 
k
k
k
i 1 j 1 

n m
 log p( xi , y j ; ) 

   p( y j | xi ;  )
 

k
i 1 j 1 

n m 
p( xi , y j ; ) 
1

   p( y j | xi ;  )
 
p( xi , y j ; )
k

i 1 j 1 

n
1
  p( yk | xi ;  )
p( xi | yk ; )  
k p( xi | yk ; )
i 1
n
1
  p( yk | xi ;  )    0
k
i 1
14
混合モデルのパラメータ更新式
導出
k 
j 1
k
i 1
m

n
p( y


1
j
| xi ;  )
 1であるから
m
n
p( y


1
j 1 i 1
j
| xi ;  ) 
n
1  1より   n


1
i 1
k p( xi | yk )
p( xi , yk )
p( xi , yk )
 m
 m
p( yk | xi ) 
p( xi )
 p( xi , y j )  j p( xi | y j )
j 1
j 1
したがって
1 n k p( xi | yk )
k   m
n i 1
 j p( xi | y j )
j 1
15
HMMの教師無し学習
EMアルゴリズムによるHMMのパラ
メータ更新
16
HMMのパラメータ更新式導出

Q関数
Q( , ) 

n
 p( y | x ; ) log p( x , y ; )
i 1 yi
n
i
i
i
  p(q q
i 1 q1Q,,qTi Q
1
Ti
i
| o1 oTi ; ) log p(q1 qTi , o1 oTi ; ' )
Ti
Ti


   p(q1 qTi | o1 oTi ; ) log 'q1  a'qt1 ,qt b'qt ,ot 
i 1 q1Q,,qTi Q
t 2
t 1


Ti
Ti
n


   p(q1 qTi | o1 oTi ; ) log 'q1  log a'qt1 ,qt   logb'qt ,ot 
i 1 q1Q,,qTi Q
t 2
t 1


n
17
HMMのパラメータ更新式導出

Q関数のラグランジュ関数
Ti
Ti


L( , )    p(q1 qTi | o1 oTi ; ) log 'q1  log a'qt1 ,qt   logb'qt ,ot  
i 1 q1Q,,qTi Q
t 2
t 1













  1   q    q 1   aq,r    q 1  bq ,o 
 qQ  qQ  rQ
 qQ  o 
n
ラグランジュ乗数
ρ … 1個の変数
αq … |Q|個の変数
βq … |Q|個の変数
18
HMMのパラメータ更新式導出
L( , ) n 1

 q
i 1  q
 q 
 p(q q
q1Q,,qTi Q
1
Ti
| o1 oTi ; )[q1  q]    0
1 n
  p(q qTi | o1 oTi ; )[q1  q]
  i 1 q1Q,,qTi Q 1
(1)
   1より
qQ
q
n
1
1 n
p(q1 qTi | o1 oTi ; )  1
  p(q qTi | o1 oTi ; )[q1  q]    

  qQ i 1 q1Q,,qTi Q 1
i 1 q1Q,,qTi Q
したがって、
n
  
n
 p(q q
i 1 q1Q,,qTi Q
1
| o1 oTi ; )  
Ti
 p(q q
q1Q,,qTi Q
i 1
1
Ti
, o1 oTi ; )
p(o1 oTi ; )
 p(q q
 
 p(q q
n
q1Q,,qTi Q
i 1
q1Q,,qTi Q
, o1 oTi ; )
1
Ti
1
Ti , o1 oTi ; )
 n
(1)に代入して、
n
 q 
  p(q q
i 1 q1Q,,qTi Q
1
Ti
| o1 oTi ; )[q1  q]
n
19
HMMのパラメータ更新式導出

 Ti

]
q

r
][
q

q
[
)

;
o

o
|
q

q
(
p


t 
t 1
Ti
1
Ti
1
  q  0

i 1 q1Q,,qTi Q

 t 2

 Ti
1 n

]
q

r
][
q

q
[
)

;
o

o
|
q

q
(
p
aq ,r 
 
t 
t 1
Ti
1
Ti
 (1)

  q i 1 q1Q,,qTi Q 1

 t 2

 Ti
1 n



 1、よって、
]
q

r
][
q

q
[
)

;
o

o
|
q

q
(
p
より、
1

a





t 
t 1
Ti
1
Ti
1
q ,r


r Q   q i 1 q1Q,,qTi Q
rQ

 t 2
n

 Ti
 q     p(q1 qTi | o1 oTi ; ) [q  qt 1 ][r  qt ]。これを式 (1)に代入して、
r Q i 1 q1Q,,qTi Q

 t 2
n

 Ti

]
q

r
][
q

q
[
)

;
o

o
|
q

q
(
p


t 
t 1
Ti
1
Ti
1


t 2
i 1 q1Q,,qTi Q


aq ,r 
n

 Ti


]
q

r
][
q

q
[
)

;
o

o
|
q

q
(
p



t 
t 1
Ti
1
Ti
1


r Q i 1 q1Q,,qTi Q

 t 2
L( , ) 1

aq ,r
aq ,r
n
20
HMMのパラメータ更新式導出
 Ti

L( , ) 1 n


p
(
q

q
|
o

o
;

)
[
q

q
][
o

o
]
 q  0



1
Ti
1
Ti
t
t 


bq ,o
bq ,o i 1 q1Q,,qTi Q
 t 1

 Ti


bq ,o 
p
(
q

q
|
o

o
;

)
[
q

q
][
o

o
]
(1)



1
Ti
1
Ti
t
t 


 q i 1 q1Q,,qTi Q
 t 1

 Ti

1 n



b

1
より、
p
(
q

q
|
o

o
;

)
[
q

q
][
o

o
]
 1、よって





q ,o
1
Ti
1
Ti
t
t 


o
o   q i 1 q1Q,,qTi Q
 t 1

n
 Ti

 q    p(q1 qTi | o1 oTi ; ) [q  qt ][o  ot ]、(1)に代入すると、
o i 1 q1Q,,qTi Q
 t 1

n
 Ti


p
(
q

q
|
o

o
;

)
[
q

q
][
o

o
]


1
Ti
1
Ti
t
t 


i 1 q1Q,,qTi Q
t 1


bq ,o 
n
 Ti



p(q1 qTi | o1 oTi ; ) [q  qt ][o  ot ]


o i 1 q1Q,,qTi Q
 t 1

1
n
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
T
t 2
t 1
p(q1o1 qT oT ; ( j ) )   q(1j )  aq( tj)1 ,qt bq(tj,)ot
p(q1o1 qT oT ; )
p(q1 qT | o1 oT ; ) 

p(o1 oT ; )
p(q1o1 qT oT ; )
 p(q'1 o1 q'T oT ; )
q '1Q,q 'T Q
23
HMMのEMアルゴリズム
[Mステップ] π( j+1)を求める
n

( j 1)
q


i 1 q1Q,,qTi Q
n
n

( j)

;
o

o
|
q

q
(
p
 1 Ti 1 Ti )[q1  q]

( j)

;
o

o
|
q

qq
(
p
 2 Ti 1 Ti )
i 1 q2Q,,qTi Q
n
先頭がqとなる回数の期待値

n
24
HMMのEMアルゴリズム
[Mステップ] a( j+1)を求める
 Ti


p
(
q

q
|
o

o
;

)
[
q

q
][
r

q
]


1
Ti
1
Ti
t 1
t 


i 1 q1Q,,qTi Q
 t 2


Ti
n

( j) 


p
(
q

q
|
o

o
;

)
[
q

q
][
r

q
]



1
Ti
1
Ti
t 1
t 


r Q i 1 q1Q,,qTi Q
 t 2

n
( j)
aq( ,jr1)
n

  p(q q
i 1 q1Q,,qTi Q
1
n
  p(q q
r Q i 1 q1Q,,qTi Q

| o1 oTi ; ( j ) )C(q, r; q1 qTi )
Ti
1
Ti
| o1 oTi ; ( j ) )C(q, r; q1 qTi )
状態qから状態 rへ遷移する回数の期待値
状態qから遷移する回数の期待値
C(q, r; q1 qT ) q1 qTの中でqから rに遷移する回数
25
HMMのEMアルゴリズム
[Mステップ] b( j+1)を求める
 Ti


p
(
q

q
|
o

o
;

)
[
q

q
][
o

o
]


1
Ti
1
Ti
t
t 


i 1 q1Q,,qTi Q
 t 1


Ti
n

( j) 


p
(
q

q
|
o

o
;

)
[
q

q
][
o

o
]



1
Ti
1
Ti
t
t 


o i 1 q1Q,,qTi Q
 t 1

n
( j)
bq( ,jo1)
n

  p(q q
i 1 q1Q,,qTi Q
1
| o1 oTi ; ( j ) )C(q, o; q1 qTi , o1 oTi )
n
  p(q q
i 1 q1Q,,qTi Q

Ti
1
Ti
| o1 oTi ; ( j ) )C(q; q1 qTi )
状態qに滞在し記号oを出力する回数の期待値
状態qに滞在する回数の期待値
C(q; q1 qT ) q1 qTの中でqが出現した回数
C(q, o; q1 qT , o1 oT ) q1 qT o1 oTの中でqから oを出力する回数
26
状態遷移回数の期待値の例


q, rの2つの状態があるとする (例えば、名詞、動詞)
o1o2o3o4に対する状態列を列挙
状態qから状態rへ遷移する回数の期待値

 p(q q
q1Q,,qT Q
1
T
| o1 oT )  (q1q2 qTにおける qから rへの遷移回数)
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
確率
p(q1o1q2o2
q3 o 3 q4 o 4 )
qqqq
qqqr
qqrq
qqrr
qrqq
qrqr
qrrq
qrrr
rqqq
rqqr
rqrq
rqrr
rrqq
rrqr
rrrq
rrrr
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

Download Report