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

人工知能特論II 第8回
二宮崇
1
今日の講義の予定


HMMの教師付学習
HMMの教師無し学習

EMアルゴリズムの導入

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
隠れマルコフモデル
Hidden Markov Model (HMM)
Q: 状態の有限集合
 Σ: 出力記号の有限集合
 πq: 文頭が状態qになる確率



aq,r: 状態qから状態rへの遷移確率


Σr∈Q πr=1
Σr∈Q aq,r=1
bq,o: 状態qにおける記号oの出力確率

Σo∈Σ bq,o = 1
3
状態記号列の確率と
生成確率

状態と記号の列が与えられた時
状態記号列 : q1o1q2 o2  qT oT
T
T
t 2
t 1
p (q1o1q2 o2  qT oT )   q1  aqt 1 ,qt  bqt ,ot

記号列のみが与えられた時
記号列 : o1o2  oT
p (o1o2  oT ) 

 p(q o q o  q o
1 1 2 2
q1Q , q2 Q ,qT Q
T T
)
(生成確率)
解析 (入力: o1o2…oT)
q~1q~2 q~T 
arg max
q1Q , q2 Q ,qT Q
p(q1o1q2o2 qT oT )
(この問題はビタビアルゴリズムで効率的に解ける)
4
ラグランジュの未定乗数法

ラグランジュの未定乗数法
arg max f (θ)ただし g1 (θ)  0,..., g m (θ)  0
θ

L(θ)  f (θ)  1 g1 (θ)  ...  m g m (θ)
L
L
L
 0,
 0,...,
0
1
 2
 n

L(θ) はラグランジュ関数と呼ばれる
5
学習 (パラメータ推定): HMMの
教師付学習
6
HMMの教師付学習
Supervised Learning of HMMs

パラメータ推定

訓練データ (入力)
訓練データ : x1 x2  xn , y1 y2  yn
xi : 文を表す記号列(単語列)。 xi  oi1oi 2oi 3  oiTiとする。
Ti : xiの記号列長
yi : xiに対応する正解状態列(正解品詞列)。 yi  qi1qi 2 qi 3  qiTiとする。
パラメータ (出力)
πq
… |Q|個の変数
aq,r … |Q|×|Q|個の変数
bq,o … |Q|×|Σ|個の変数

7
HMMの教師付学習
Supervised Learning of HMMs

パラメータ推定
n
 , a, b  arg max  p( xi , yi )
 , a ,b
i 1
n
 arg max  p (qi1oi1qi 2 oi 2  qiTi oiTi )
 , a ,b
i 1
n
Ti
Ti
i 1
t 2
t 1
 arg max   qi1  aqi ( t 1) ,qit  bqit ,oit
 , a ,b
8
HMMの教師付学習
Supervised Learning of HMMs

パラメータ推定
n
Ti
Ti
i 1
t 2
t 1
l ( , a, b)    qi1  aqi ( t 1) ,qit  bqit ,oit
Ti
Ti


log l ( , a, b)    log  qi1   log aqi ( t 1) ,qit   log bqit ,oit 
i 1 
t 2
t 1

n
制約付き最適化問題
arg max log l ( , a, b)
 , a ,b
s.t.

a
b
qQ
rQ
o
q
1
q ,r
 1 (for all q )
q ,o
 1 (for all q )
9
HMMの教師付学習
Supervised Learning of HMMs
ラグランジュの未定乗数法

ラグランジュ関数
L( , a, b)









 log l ( , a, b)   1    q     q 1   aq ,r     q 1   bq ,o 

 qQ  qQ  rQ
 qQ  o
Ti
Ti








   log  qi1   log aqi ( t 1) ,qit   log bqit ,oit    1    q     q 1   aq ,r     q 1   bq ,o 
i 1 
t 2
t 1


 qQ  qQ  rQ
 qQ  o
n
ラグランジュ乗数
ρ … 1個の変数
αq … |Q|個の変数
βq … |Q|個の変数
10
HMMの教師付学習
Supervised Learning of HMMs

πqを求める
アイバーソンの記法
(Iverson bracket)
L C1 (q )
 0

q
 q
ただし、 C1 (q )  i 1 qi1  q 
n
q 
C1 (q )

 q
qQ
C1(q)は訓練データ中で、文の
先頭がqになっている回数
 (1)



ところで
qQ
qQ
1 if P is true
[ P]  
0 otherwise
 q  1であるから
C1 (q )


n
1

よって、   n。これを式 (1)に代入して、
C (q)
q  1
n
11
HMMの教師付学習
Supervised Learning of HMMs

aq,rを求める
L
C ( q, r )

 q  0
aq ,r
aq , r


ただし、 C (q, r )  i 1 t i 2 qi (t 1)  q qit  r 
n
aq , r 
C ( q, r )
q



ところで
a
r 'Q
q ,r '
T
C(q,r)は訓練データ中で、状
態qから状態rに遷移した回数
 (1)
rQ
aq ,r  1であるから
r 'Q
C ( q, r ' )
q
1
よって、  q  r 'Q C (q, r ' )。これを式 (1)に代入して、
aq , r 
C ( q, r )
r 'Q C (q, r ' )
12
HMMの教師付学習
Supervised Learning of HMMs

bq,oを求める
L
C ( q, o)

 q  0
bq ,o
bq ,o
ただし、 C (q, o)  i 1 t i 1 qit  q oit  o
n
b q ,o 
C ( q, o)
 q



ところで
b
o '
C(q,o)は訓練データ中で、状
態qから記号oを出力した回数
 (1)
o
o '
q ,o '
T
bq ,o  1であるから
C ( q, o' )
 q
1
よって、  q  o ' C (q, o' )。式 (1)に代入して、
bq ,o 
C ( q, o)
C ( q, o)

o' C (q, o' ) C (q)
ただし、 C (q )  i 1 t i 1 qit  q 
n
T
C(q)は訓練データ中で、状態
qが出現した回数
13
HMMの教師付学習
Supervised Learning of HMMs

パラメータ推定
C1 (q ) 先頭の状態が qになっている文の数

n
全文数
q

aq , r
C ( q, r )
qから rに遷移した回数


 C (q, r ' ) qから任意の rに遷移した回数
r 'Q
bq ,o
C ( q, o)
C (q, o) qから oを出力した回数



qの出現回数
 C ( q, o' ) C ( q )
o '
ただし、 C1 (q )  i 1 qi1  q 
n


C (q, r )  i 1 t i 2 qi (t 1)  q qit  r 
n
T
C (q, o)  i 1 t i 1 qit  q oit  o
n
T
C (q )  i 1 t i 1 qit  q 
n
T
14
HMMの教師無し学習: EMアルゴリ
ズムの導入
15
HMMの教師無し学習
Unsupervised Learning of HMMs

パラメータ推定

訓練データ (入力)
訓練データ : x1 x2  xn
xi : 文を表す記号列(単語列)。 xi  oi1oi 2 oi 3  oiTiとする。
Ti : xiの記号列長

パラメータ (出力)
n
 , a, b  arg max p ( xi )
 , a ,b
i 1
n
 arg max p (oi1oi 2  oiTi )
 , a ,b
i 1
n
 arg max
 , a ,b
 p(q o q o
1 i1 2 i 2
i 1 q1Q , q2 Q ,qTi Q
 qTi oiTi )
16
HMMの教師無し学習
Unsupervised Learning of HMMs

EMアルゴリズムによる教師無し学習
不完全データ（欠損や曖昧性のあるデータ）
に対する有名な学習法
 EMアルゴリズム＋前向き後向きアルゴリズム

17
EMアルゴリズム
18
EMアルゴリズムの問題設定 (1/2)


実際に観測されたデータx1,...,xNが存在
それぞれのデータxiは隠れ状態yi1,...,yiTのいずれかから生成され
たと仮定


隠れ状態の集合はデータ毎に変わっても良い
(機械学習一般には隠れ状態集合は固定であることが多い)
パラメータ集合θによりp(x, y)が計算される
x1
y11
y12
y13
p(x1, y11) p(x1, y12) p(x1, y13)
x2
y21
p(x2, y21)
x3
y31
y32
y33
y34
y35
p(x3, y31) p(x3, y32) p(x3, y33)p(x3, y34) p(x3, y35)
..
..
..
19
EMアルゴリズムの問題設定 (2/2)

パラメータ推定


訓練データ (入力)
訓練データ: x1 x2  xn
Y ( x) : xに対する隠れ状態集合
パラメータ (出力)
~

n
 arg max p( xi ; )

i 1
n
 p ( x , y;  )
 arg max

i 1 yY ( xi )
n
 arg max log 

i
 p ( x , y;  )
i 1 yY ( xi )
n
l ( )  log 
i
~
p
(
x
,
y
;

)
とおくと

 arg maxl ( )
 i
i 1 yY ( xi )

20
EMアルゴリズムの全体像
~
  arg maxl ( )

問題変形
[Eステップ] p(y | x ; θ)
を計算
 ( 1)  arg maxQ( ( ) , )

個々の問題に応じ
て決まるQ関数の
極値を解析的に求
める
[Mステップ]
 ( 1)  arg maxQ( ( ) , )

によりパラメータ更新
個々の問題によって決
まるパラメータ更新式
21
Q関数の導出 (1)

問題: 実際に観測されたデータx1,...,xnが存在して、それに
対して、対数尤度を最大化するパラメータを求める
n
~
  arg maxl ( )  arg max  log p( xi ; )



i 1
問題チェンジ: パラメータをθからθ’にした時の対数尤度
の差を最大化することを繰り返せば極大値が求まる
n
arg max  log p( xi ; )  log p( xi ; )

i 1
argmaxを求めているが、ようは正の値になればより尤度の高いパラ
メータが得られることに注意
22
Q関数の導出 (2)

個々の事象の対数尤度の差
p ( xi ; )
p ( xi ; )
 log
p ( y | xi ; )

p ( xi ; )
p ( xi ; ) y
p ( xi ; )
  p ( y | xi ; ) log
p ( xi ; )
y
 p ( xi , y; ) p ( y | xi ; ) 
  p ( y | xi ; ) log 

y
 p ( xi , y; ) p ( y | xi ; ) 
p ( xi , y; )
p ( y | xi ; )
  p ( y | xi ; ) log
  p ( y | xi ; ) log
p ( xi , y; )
p ( y | xi ; )
y
y
log p ( xi ; )  log p ( xi ; )  log
ジェンセンの不等式より、常に≧0
23
Q関数の導出 (3)

個々の事象の対数尤度の差
p( xi , y; )
p ( y | xi ; )
  p ( y | xi ; ) log
p ( xi , y; )
p ( y | xi ; )
y
y
p ( xi , y; )
  p( y | xi ; ) log
p ( xi , y; )
y
  p ( y | xi ; ) log p ( xi , y; )   p( y | xi ; ) log p( xi , y; )
log p ( xi ; )  log p ( xi ; )   p ( y | xi ; ) log
y
y
ここをQ関数とみなす
Q( , )   p( y | xi ; ) log p( xi , y; )
y
すると、ここは、
Q( , )
24
Q関数の導出 (4)

まとめ

対数尤度の差は次のようにおける
log p( xi ; )  log p( xi ; )  Q( , ' )  Q( , )
ただし Q( , ) 
 p( y | x ; ) log p( x , y; )
i
i
y

より良いパラメータθ’を見つけるためには、




Q(θ, θ’)－Q(θ, θ)≧0となれば良いが、
効率を考えると、対数尤度の差が最大になるほうが良い
Q(θ, θ)はθ’に関わりなく一定なので、対数尤度の最大化するには、
Q(θ, θ’)を最大化すれば良い
θ’ = θとおくと(古いパラメータと同じにすると)Q関数の差は0にな
る⇒argmaxをとれば、常にQ(θ, θ’)-Q(θ, θ) ≧0
25
EMアルゴリズム: Q関数の最大
化

次のパラメータ更新を繰り返すアルゴリズ
ム
 ( 1)  arg maxQ( ( ) , )

ただし、
Q( , )   p( y | xi ; ) log p( xi , y; )
y
全ての観測データx1, x2, ..., xnに対しては、
n
Q( , )   p( y | xi ; ) log p( xi , y; )
i 1
y
とすればよい
しかし、まだ問題は解けていない！
argmax Qをどうやって求めるか？？
26
休憩: Q関数の直感的な意味 (1)

Q関数 Q( , )   p( y | xi ; ) log p( xi , y; )
y

(古いパラメータθで計算した隠れ状態の条件付き確
率)× (新しいパラメータθ’によるxiとyの同時確率の
対数)≒ xiとyの同時確率の対数の期待値
xi
p( y1 | xi ; )
y1
log p( xi , y1; )
p( y2 | xi ; )
y2
log p( xi , y2 ; )
...
p( y3 | xi ; )
y3
log p( xi , y3 ; )
27
休憩: Q関数の直感的な意味 (2)

そもそもなぜ直接θを最大化しないのか？
n
l ( )  log  p ( xi , y; )
i 1
y
n
  log  p ( xi , y; )
i 1
 ????
y
⇒パラメータ更新式にすれば、実はこのsumをlogの外
にだすことができるのであった
28
休憩: ジェンセンの不等式
ジェンセンの不等式
 凸関数 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 q   log i pi p    log i qi  0
i
i 

29
まとめ
HMMの教師付学習
 HMMの教師無し学習



EMアルゴリズム


EMアルゴリズムの導入
Q関数の導出
資料
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/ai2/
30

Download Report