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

人工知能特論II 第10回
二宮崇
1
今日の講義の予定
HMMの前向き後向きアルゴリズムによる
パラメータ学習
 生成モデルと識別モデル
 教科書

北研二(著) 辻井潤一(編) 言語と計算4 確率的言
語モデル東大出版会
 Christopher M. Bishop “PATTERN
RECOGNITION AND MACHINE
LEARNING” Springer, 2006

2
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 )
3
HMMのEMアルゴリズム

パラメータ更新式

π, a, b をπ’, a’, b’ に更新
n
 q
  p(q  q

i 1 q1Q ,, qTi Q
1
| o1  oTi ; )[q1  q ]
Ti
n
n
  p(qq  q


i 1 q2 Q ,, qTi Q
2
Ti
| o1  oTi ; )
n
先頭が qとなる回数の期待値
n
4
HMMのEMアルゴリズム

パラメータ更新式

π, a, b をπ’, a’, b’ に更新
 Ti

p (q1  qTi | o1  oTi ; )  [q  qt 1 ][r  qt ] 


i 1 q1Q ,, qTi Q
 t 2


n
 Ti




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
aq ,r
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 ; )C (q, r ; q1  qTi )
Ti
1
Ti
| o1  oTi ; )C (q, r ; q1  qTi )
状態qから状態 rへ遷移する回数の期待値
状態qから遷移する回数の期待値
C(q, r; q1 qT ) q1 qTの中でqから rに遷移する回数
5
HMMのEMアルゴリズム

パラメータ更新式

π, a, b をπ’, a’, b’ に更新
 Ti



p
(
q

q
|
o

o
;

)
[
q

q
][
o

o
]


1
Ti
1
Ti
t
t 

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 

o i 1 q1Q ,, qTi Q
 t 1

n
bq ,o
n
  p(q  q

i 1 q1Q ,, qTi Q
1
| o1  oTi ; )C (q, o; q1  qTi , o1  oTi )
n
  p(q  q
i 1 q1Q ,, qTi Q

Ti
1
Ti
| o1  oTi ; )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を出力する回数
6
HMMのためのEMアルゴリズム
の問題点

期待値を計算するために全ての可能な隠れ
状態を列挙すると文長に対し、指数爆発的
計算量が必要
解決策：前向き後向きアルゴリズム。隠れ状
態を列挙することなく、この期待値を計算す
る動的計画法。
7
前向きアルゴリズムと後ろ向き
アルゴリズム
8
前向きアルゴリズム (1/3)

動的計画法
α(t, q): o1 … otを出力し、otが出力される時(時刻t)に状態qである確率
 t 1

 (t , q) 

b
a
b


q1 q1 ,o1   qu 1 , qu qu ,ou 
aqt 1 ,q bq ,ot
q1Q ,, qt 1Q
 u 2

全てのt,qに対し、α(t, q)を求めれば良い
時刻
出力記号
1
o1
2
o2
3
o3
T
oT
状態1
…
状態2
…
状態3
状態4
…
…
トレリス
9
前向きアルゴリズム (2/3)
 t 1

 (t , q) 

b
a
b


q1 q1 ,o1   qu 1 , qu qu ,ou 
aqt 1 ,q bq ,ot
q1Q ,, qt 1Q
 u 2





 t 2

   
 q1 bq1 ,o1   aqu1 ,qu bqu ,ou aqt 2 ,qt 1 bqt 1 ,ot 1 aqt 1 ,q bq ,ot 

qt 1Q 
 u 2


q1Q ,,qt 2 Q 
   (t  1, qt 1 )aqt 1 ,q bq ,ot
全ての遷移確率の和
qt 1Q
o1
o2
ot-1
ot
oT
状態1
…
…
状態2
…
…
…
状態 q
…
…
…
…
…
10
前向きアルゴリズム (3/3)
α[1,q] := π[q]b[q,o1] (for all q)
for t =2 to T
for q ∈ Q
α[t, q] := Σq’∈Q {α[t-1, q’]a[q’,q]b[q, ot]}
11
後ろ向きアルゴリズム (1/3)

前向きアルゴリズムを逆方向に適用



文末から文頭に向かって実行
向きが逆になることを除けば前向きアルゴリズムと
まったく同じ
β(t, q) :時刻tに状態qから始める状態遷移によって
ot+1…oTまで出力する確率
 (t , q) 

qt 1Q ,, qT Q
T
aq ,qt 1 bqt 1 ,ot 1
a
u t  2
b
qu 1 , qu qu ,ou
12
後ろ向きアルゴリズム (2/3)
 (t , q) 

qt 1Q ,, qT Q
T
aq ,qt 1 bqt 1 ,ot 1
a
u t  2
b
qu 1 , qu qu ,ou
T



  aq ,qt 1 bqt 1 ,ot 1
aqt 1 ,qt 2 bqt 2 ,ot 2  aqu1 ,qu bqu ,ou 

qt 1Q 
qt  2 Q ,, qn Q 
u t  3

  aq ,qt 1 bqt 1 ,ot 1  (t  1, qt 1 )
qt 1Q
o1
全ての遷移確率の和
o2
ot
ot+1
oT
状態1
…
…
状態2
…
…
…
状態 q
…
…
…
…
…
13
後ろ向きアルゴリズム (3/3)
β[T,q] := 1 (for all q)
for t := T-1 to 1
for q ∈ Q
β[t, q] := Σq’∈Q {a[q, q’]b[q’, ot+1]β[t+1, q’]}
14
前向き後ろ向きアルゴリズムの
導出
15
前向き後ろ向きアルゴリズム: 生成確率

生成確率
p (o1  oTi ) 
 p(q o  q
q1Q ,, qTi Q
1 1
o )    (Ti , q )
Ti Ti
qQ
16
前向き後ろ向きアルゴリズム: π’
 q
1 n
   p (q1  qTi | o1  oTi ; )[q1  q ]
n i 1 q1Q ,,qTi Q
Ti
Ti
1 n
1
 
 q bq ,o1 aq ,q2 bq2 ,o2  aqt 1 ,qt  bqt ,ot

n i 1 p (o1  oTi ; ) q2 Q ,,qTi Q
t 3
t 3
1 n
1
 
 q bq ,o1  (1, q)
n i 1 p (o1  oTi ; )
1 n  (1, q )  (1, q )
 
n i 1   (Ti , q ' )
q 'Q
17
前向き後ろ向きアルゴリズム: π’
1 n
1
1 n  (1, q )  (1, q )
 q  
 q bq ,o1  (1, q)  
n i 1 p (o1  oTi ; )
n i 1   (Ti , q ' )
q 'Q
後向き確率
o1
oT
o2
…
状態 q
…
…
…
18
前向き後ろ向きアルゴリズム: a’
 Ti

aq ,rの分子部分   
p (q1  qTi | o1  oTi ; )  [q  qt 1 ][r  qt ] 
i 1 q1Q ,, qTi Q
 t 2

n
n

i 1
n

i 1
n

i 1
n

i 1
n

i 1
n

i 1
n

i 1
n

i 1
Ti
Ti
 Ti

1
 q1  aqu1 ,qu  bqu ,ou   [q  qt 1 ][r  qt ] 

p (o1  oTi ; ) q1Q ,,qTi Q u  2
u 1
 t 2

Ti
Ti
Ti
1
   q  aq ,q  bq ,o [q  qt 1 ][r  qt ]
p (o1  oTi ; ) t  2 q1Q ,,qTi Q 1 u  2 u1 u u 1 u u
Ti
 Ti

 t 2

1


b
a
b
a
b
a
b
a
b
a
b


  q q ,o  q ,q q ,o q ,q q ,o q ,q q ,o q ,q q ,o  q ,q q ,o [q  qt 1 ][r  qt ]
p (o1  oTi ; ) t  2 q1Q ,,qTi Q 1 1 1  u  2 u1 u u u  t 2 t 1 t 1 t 1 t 1 t t t t t 1 t 1 t 1  u t  2 u1 u u u 
Ti
 Ti

 t 2

1
 q1 bq1 ,o1   aqu1 ,qu bqu ,ou aqt 2 ,q bq ,ot 1 aq ,r br ,ot ar ,qt 1 bqt 1 ,ot 1   aqu1 ,qu bqu ,ou 



p (o1  oTi ; ) t  2 q1Q ,,qt 2 Q qt 1Q ,,qTi Q
 u 2

 u t  2

Ti
 Ti

 t 2

1



b
a
b
a
b
a
b
a
b
a
b


  q q ,o  q ,q q ,o q ,q q,ot1 q,r r ,ot q Q
r , qt 1 qt 1 ,ot 1   qu 1 , qu qu ,ou 
p (o1  oTi ; ) t  2 q1Q ,,qt 2 Q 1 1 1  u  2 u1 u u u  t 2
,

,
q

Q
u

t

2


t 1
Ti
Ti
 t 2

1
 q1 bq1 ,o1   aqu1 ,qu bqu ,ou aqt 2 ,q bq ,ot 1 aq ,r br ,ot  (t , r )


p (o1  oTi ; ) t  2 q1Q ,,qt 2 Q
 u 2

Ti
 t 2

1
aq ,r br ,ot  (t , r )   q1 bq1 ,o1   aqu1 ,qu bqu ,ou aqt 2 ,q bq ,ot 1

p (o1  oTi ; ) t  2
q1Q ,, qt 2 Q
 u 2

Ti
1
  (t  1, q)aq,r br ,ot  (t , r )
p (o1  oTi ; ) t  2
19
前向き後ろ向きアルゴリズム: a’
γ(t,q,r): 記号列o1…oTに対し、時刻t－1から時刻tに状態qから
状態rに遷移する確率
 (t  1, q)aq ,r br ,ot  (t , r )
 (t , q, r ) 
  (T , q' )
q 'Q
前向き確率
後向き確率
o1
o2
ot-1
oT
ot
…
…
状態 q
…
…
…
状態 r
…
…
…
…
…
20
前向き後ろ向きアルゴリズム: a’
 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


n
 Ti



p (q1  qTi | o1  oTi ; )  [q  qt 1 ][r  qt ] 


r Q i 1 q1Q ,, qTi Q
 t 2

n
aq ,r
n

Ti
  (t , q, r )
i 1 t  2
n Ti
  (t , q, r )
r Q i 1 t  2
21
前向き後ろ向きアルゴリズム: b’
 Ti

bq ,oの分子部分   
p (q1  qTi | o1  oTi ; )  [q  qt ][o  ot ] 
i 1 q1Q ,, qTi Q
 t 1

n
n

i 1
n

i 1
n

i 1
n

i 1
n

i 1
n

i 1
n

i 1
Ti
Ti
Ti
1
   q  aq ,q  bq ,o [q  qt ][o  ot ]
p (o1  oTi ; ) t 1 q1Q ,,qTi Q 1 u  2 u1 u u 1 u u
Ti
 Ti

 t 1

1


b
a
b
a
b
a
b
a
b


  q q ,o  q ,q q ,o q ,q q ,o q ,q q ,o  q ,q q ,o [q  qt ][o  ot ]
p (o1  oTi ; ) t 1 q1Q ,,qTi Q 1 1 1  u  2 u1 u u u  t 1 t t t t t 1 t 1 t 1  t u  2 t 1 t t t 
Ti
 Ti

 t 1

1



b
a
b
a
b
a
b
a
b





q1 q1 ,o1   qu 1 , qu qu ,ou  qt 1 , q q ,ot q , qt 1 qt 1 ,ot 1   qt 1 , qt qt ,ot [o  ot ]
p (o1  oTi ; ) t 1 q1Q ,,qt 1Q qt 1Q ,,qTi Q
 u 2

 t u  2

Ti
 Ti

 t 1

1



b
a
b
a
b
[
o

o
]
a
b
a
b


  q q ,o  q ,q q ,o q ,q q,ot

t
q , qt 1 qt 1 ,ot 1   qt 1 , qt qt ,ot 
p (o1  oTi ; ) t 1 q1Q ,,qt 1Q 1 1 1  u  2 u1 u u u  t 1
qt 1Q ,, qTi Q
 t u  2

Ti
 t 1

1
 q1 bq1 ,o1   aqu1 ,qu bqu ,ou aqt 1 ,q bq ,ot [o  ot ] (t , q)


p (o1  oTi ; ) t 1 q1Q ,,qt 1Q
 u 2

Ti
 t 1

1
[
o

o
]

(
t
,
q
)

b
a
b



t
q1 q1 ,o1   qu 1 , qu qu ,ou 
aqt 1 ,q bq ,ot
p (o1  oTi ; ) t 1
q1Q ,, qt 1Q
 u 2

Ti
1
 [o  ot ] (t , q) (t , q)
p (o1  oTi ; ) t 1
22
前向き後ろ向きアルゴリズム: b’
γ(t,q): 記号列o1…oTに対し、時刻tに状態qに滞在する確率
 (t , q)  (t , q)
 (t , q) 
 (T , q' )
q 'Q
前向き確率
後向き確率
o1
o2
ot
oT
ot+1
…
…
…
状態 q
…
…
…
…
…
…
…
23
前向き後ろ向きアルゴリズム: b’
 Ti

p (q1  qTi | o1  oTi ; )  [q  qt ][o  ot ] 


i 1 q1Q ,, qTi Q
 t 1


T
n
 i




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
bq ,o
Ti
n

 [o  o ] (t , q)
t
i 1 t 1
n Ti
 [o  o ] (t , q)
t
o i 1 t 1
n

Ti
 [o  o ] (t , q)
i 1 t 1
n
t
Ti
  (t , q)
i 1 t 1
ちなみに、
1 n  (1, q )  (1, q ) 1
 q  
  (1, q )
n i 1   (Ti , q ' )
n
q 'Q
24
前向き後向きアルゴリズム
まとめ(1/2)
α(t, q): o1 … otを出力し、otが出力される時(時刻t)に状態qである確率
 t 1

 (t , q) 

b
a
b


q1 q1 ,o1   qu 1 , qu qu ,ou 
aqt 1 ,q bq ,ot
q1Q ,, qt 1Q
 u 2

   (t  1, qt 1 )aqt 1 ,q bq ,ot
qt 1Q
β(t, q) :時刻tに状態qから始める状態遷移によってot+1…oTまで出力する確率
 (t , q) 


qt 1Q ,, qT Q
a
qt 1Q
 (t , q) 
 (t , q)  (t , q)
 (T , q' )
q 'Q
T
b
aq ,qt 1 bqt 1 ,ot 1
q , qt 1 qt 1 ,ot 1
a
u t  2
b
qu 1 , qu qu ,ou
 (t  1, qt 1 )
 (t  1, q)aq,r br ,o  (t , r )
 (t , q, r ) 
 (T , q' )
t
q 'Q
25
前向き後向きアルゴリズム
まとめ(2/2)
あるパラメータπ,a,bが与えられているとする
 αを求める(前向きアルゴリズム)
 βを求める(後向きアルゴリズム)


それぞれ動的計画法。計算量はO(T) ※ビタビアルゴリズムも計算量は
O(T)。ビタビアルゴリズムのおよそ3倍の計算量。
次のようにπ, a, bを更新する
 'q
1
1 n
 (先頭が qとなる回数の期待値 )    (1, q )
n
n i 1
n
a 'q , r
状態qから状態 rへ遷移する回数の期待値


状態qから遷移する回数の期待値
Ti
  (t , q, r )
i 1 t  2
n Ti
  (t , q, r )
r Q i 1 t  2
n Ti
b'q ,o
状態qに滞在し記号 oを出力する回数の期待値


状態qに滞在する回数の期待値
 [o  o ] (t , q)
i 1 t 1
n
t
Ti
  (t , q)
i 1 t 1
26
Generative Model and Discriminative Model
生成モデルと識別モデル
27
生成モデルから識別モデルへ

生成モデル

HMM
状態遷移による生成
 状態遷移の確率は一つ前の状態のみに依存
 任意の文sと状態列qに対する同時確率p(s,q)を計算でき
る


PCFG
CFGによる生成のステップ（書換規則の適用 A → B C）
の確率をp(B C| A)とする
 CFGによる生成の過程の確率を、独立な事象の(条件付
き)確率の積とする
 任意の文sと構文木tに対する同時確率p(s, t)を計算でき
る

28
生成モデルの改良の先に

構文木の分岐の外の情報を条件部に導入
PCFG: p(BC|A, hw) [Ahw→BhwC] (hw: 主辞)
 HMM: p(qj|qj-1, qj-2)


素性（特徴）という考え方
条件部をどんどんリッチにして線形補間をとれ
ばよいのでは？→構文木のノードxの確率
p(x)=p(x|x周辺の状況)
29
生成モデルの問題点

生成モデルの問題点

独立性の仮定
PCFGでは、各構文木ノードは独立な(条件付き）試行に
より生成されていると仮定している
 例えば、(S (NP John) (VP eats (NP apples)))という構文
木は、以下の独立な（条件付き）事象に分解されている






SからNP VPを生成
NPからJohnを生成
VPからeats NPを生成
NPからapplesを生成
結果、上記のNPの文脈(S→NP VP)から導出されたNPか
(VP→eats NP)から導出されたNPかわからなくなってい
る→主語のNPなのか目的語のNPなのかわからない。
30
生成モデルの問題点

生成モデル
~
t  arg max p(t | s; )  arg max p( s, t; )
t

t
しかし、
p(s, t; )  p(t | s; ) p(s; )
であるからp (s;θ) が計算できてしまう分、冗
長なモデルになっている。間接的に分類問題
を解いている。
 独立性を仮定した事象に分解しないと同時確
率を計算することができない
31
識別モデル

識別モデル
直接
~
t  arg max p(t | s; )
t
を解く
 独立な事象を仮定しない
 「条件部の確率」をモデルにいれない
32
生成モデルと識別モデル
(イメージ)
生成モデル
識別モデル
GOOD
BAD
生成モデルと識別モデル
（イメージ２）

生成モデル
絵を描いて全体像の比較

識別モデル
それぞれの特徴を比較




鼻の位置
耳の形
体の大きさ
舌の表面
34
識別するための訓練

教師付学習

良い例と悪い例を与えて、どこに注目すれば
より良く識別出来るのか学習
good examples
bad examples
35
識別モデル
p(t | s )
素性ベクトル
(特徴ベクトル)
(0,0,1,0)
t1
s = “A blue eye girl with white hair and skin walked”
(1,0,1,0)
(1,1,1,0)
t2
t3
(0,0,1,1)
t4
(1,0,0,0)
…
tn
文法Gによりsから導出出来る全ての構文木集合
p(t3|s) はt1,t2,t3,..,tnからt3を選択する確率
生成モデルと識別モデル
生成モデル
識別モデル
p( x, y2 )
p( x, y1 )
1.0
p ( y2 | x)
p( y1 | x)
どちらが優秀なのか？
Tom Minka (2005) Discriminative models, not
discriminative training, MSR-TR-2005-144, 1 p.
xを入力(文)、yを出力(構文木)としたときのパラメー
タ推定
 生成モデル
p( x, y; )  p( x | y; ) p( y; )

識別モデル
p( y | x; )

θ = θ’
一般モデル
p( x, y; , )  p( y | x; ) p( x; )
38
まとめ

HMMの前向き後向きアルゴリズム

前向き後向きアルゴリズム

動的計画法


隠れ状態を全て並べあげることなく、トレリス上で期待値を計算
できる



計算量はO(T) ※ビタビアルゴリズムも計算量はO(T)。ビタビアルゴリズ
ムのおよそ3倍の計算量。
ある状態からある状態への遷移回数の期待値
ある状態からある記号を出力する回数の期待値
生成モデルと識別モデル
今までの講義資料
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/ai2/

39

Download Report