知的情報処理システム特論
第9回
二宮崇
1
今日の講義の予定

品詞解析


HMM
HMMの解析


ビタビアルゴリズム
教科書



北研二(著) 辻井潤一(編) 言語と計算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
品詞解析
PART-OF-SPEECH (POS)
TAGGING
3
品詞解析

品詞タガー
“I have a pen.”
トーカナイザー
I
have
a
pen
.
POSタガー
I
代名詞
have
動詞
a
pen
不定冠詞
名詞
.
ピリオド
4
隠れマルコフモデル
Hidden Markov Model (HMM) (1/3)
I
he
名詞
Mary
ピリオド
出力 (emission)
…
代名詞
不定
冠詞
遷移 (transition)
動詞
I
代名詞
have
動詞
a
pen
不定冠詞
名詞
.
ピリオド
5
隠れマルコフモデル
Hidden Markov Model (HMM) (2/3)
0.3
ピリオド
0.5
名詞
0.43
0.3
代名詞
0.4
動詞
0.01
0.25
出力 (emission)
0.01
…
遷移 (transition)
動詞
have
he
代名詞
不定
冠詞
I
0.3
Mary
0.01
0.1
I
a
pen
不定冠詞
名詞
.
ピリオド
6
隠れマルコフモデル
Hidden Markov Model (HMM) (3/3)
Q: 状態の有限集合
 Σ: 出力記号の有限集合
 πq: 文頭が状態qになる確率
 aq,r: 状態qから状態rへの遷移確率



Σr∈Q aq,r=1
bq,o: 状態qにおける記号oの出力確率

Σo∈Σ bq,o = 1
7
状態記号列に対する確率の例
π
a
b
名詞
代名詞
動詞
不定冠詞
ピリオド
0.2
0.4
0.1
0.3
0.0
遷移元＼遷移先
名詞
代名詞
動詞
不定冠詞
ピリオド
名詞
0.5
0.0
0.3
0.0
0.2
代名詞
0.1
0.0
0.5
0.2
0.2
動詞
0.2
0.2
0.2
0.2
0.2
不定冠詞
1.0
0.0
0.0
0.0
0.0
ピリオド
0.5
0.0
0.5
0.0
0.0
状態＼出力
a
… have
…
I
…
pen
…
.
…
名詞
0.01
… 0.0
…
0.01
…
0.1
…
0.0
…
代名詞
0.0
… 0.0
…
0.3
…
0.0
…
0.0
…
動詞
0.0
… 0.2
…
0.0
…
0.0
…
0.0
…
不定冠詞
0.2
… 0.0
…
0.0
…
0.0
…
0.0
…
ピリオド
0.0
… 0.0
…
0.0
…
0.0
…
1.0
…
I
0.3
have
0.2
0.4
0.2
動詞
代名詞
0.5
a
不定冠詞
0.2
pen
.
0.1
1.0
名詞
1.0
ピリオド
0.2
0.4*0.3*0.5*0.2*0.2*
0.2*1.0*0.1*0.2*1.0
=0.0000096
8
状態記号列の確率と
生成確率

状態と記号の列が与えられた時
状態記号列 : q1o1q2 o2  qT oT
p (q1o1q2 o2  qT oT ) = π q1 bq1 ,o1 aq1 ,q2 bq2 ,o2  aqT −1 ,qT bqT ,oT
= π q1 aq1 ,q2  aqT −1 ,qT bq1 ,o1 bq2 ,o2  bqT ,oT
T
T
t =2
t =1
= π 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
)
(生成確率)
9
品詞解析

品詞解析 (入力: o1o2…oT)
q~1q~2  q~T =
arg max
q1∈Q , q2 ∈Q ,qT ∈Q
p (q1o1q2 o2  qT oT )
10
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 )
11
HMMの教師付学習
Supervised Learning of HMMs

パラメータ推定

訓練データ (入力)
訓練データ: x1 x2  xn , y1 y2  yn
xi : 文を表す記号列(単語列)。xi = oi1oi 2 oi 3  oiTiとする。
Ti : xiの記号列長
yi : xiに対応する正解状態列(正解品詞列)。yi = qi1qi 2 qi 3  qiTiとする。

パラメータ (出力)
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
12
推論(INFERENCE)
解析(ANALYSIS)
タグ付け(TAGGING)
復号化(DECODING)
13
解析

解析 (入力: o1o2…oT)
q~1q~2  q~T =
arg max
q1∈Q , q2 ∈Q ,qT ∈Q
p (q1o1q2 o2  qT oT )
しかし、計算量はO(|Q|T)!
14
効率的な品詞解析: ビタビアルゴリズム

動的計画法
δ(t, q): 時刻t(otが出力される時)に状態qとなる状態列の中で最大確率となる列
の確率
maxq∈ Q δ(T, q)を求めれば良い
2
時刻 1
o2
出力記号 o1
3
o3
T
oT
状態1
…
状態2
…
状態3
…
状態4
…
トレリス
15
効率的な品詞解析: ビタビアルゴリズム
δ (t , q) =
max
q1∈Q ,, qt −1∈Q
p (q1o1  qt −1ot −1 )aqt −1 ,q bq ,ot
{
}
p (q1o1  qt − 2 ot − 2 )aqt −2 ,qt −1 bqt −1 ,ot −1 aqt −1 ,q bq ,ot 
= max  max
qt −1∈Q q1∈Q ,, qt −2 ∈Q

= max δ (t − 1, qt −1 )aqt −1 ,q bq ,ot
qt −1∈Q
o1
最大確率で遷移したパス
をバックポインタで保存
o2
ot-1
ot
oT
状態1
…
…
状態2
…
…
…
状態 q
…
…
…
…
…
16
効率的な品詞解析: ビタビアルゴリズム

動的計画法
δ(t, q): 時刻t(otが出力される時)に状態qとなる状態列の中で最大確率となる列の確率
左から右に向かって
全てのδ(t,q)を計算
時刻
出力記号
状態1
1
o1
2
o2
3
o3
T
oT
δ(1,状態1)=π状態1b状態1,o1
…
状態2
δ(1,状態2)=π
状態2b状態2,o1
…
状態3
δ(1,状態3)=π
…
状態3b状態3,o1
状態4
δ(1,状態4)=π
状態4b状態4,o1
…
17
効率的な品詞解析: ビタビアルゴリズム

動的計画法
δ(t, q): 時刻t(otが出力される時)に状態qとなる状態列の中で最大確率となる列の確率
左から右に向かって
全てのδ(t,q)を計算
最大確率で遷移したパス
をバックポインタで保存
時刻
出力記号
状態1
状態2
状態3
状態4
1
o1
2
o2
3
o3
T
oT
δ(2,状態1)=
max { …
δ(1,状態1)a状態1,状態1b状態1,o2,
…
δ(1,状態2)a
状態2,状態1b状態1,o2,
δ(1,状態3)a状態3,状態1b状態1,o2,
…
δ(1,状態4)a状態4,状態1b状態1,o2
}
…
18
効率的な品詞解析: ビタビアルゴリズム

動的計画法
δ(t, q): 時刻t(otが出力される時)に状態qとなる状態列の中で最大確率となる列の確率
左から右に向かって
全てのδ(t,q)を計算
時刻
出力記号
状態1
状態2
状態3
状態4
1
o1
2
o2
3
o3
T
oT
δ(2,状態2)=
…
max {
b
,
δ(1,状態1)a
… 状態1,状態2 状態2,o2
δ(1,状態2)a状態2,状態2b状態2,o2,
δ(1,状態3)a
… 状態3,状態2b状態2,o2,
δ(1,状態4)a状態4,状態2b状態2,o2
}
…
19
効率的な品詞解析: ビタビアルゴリズム

最後にバックポインタを辿ることで最大確
率となる状態列が得られる
o1
o2
oT-2
状態1
…
状態2
…
状態 3
…
状態 4
…
oT-1
oT
20
効率的な品詞解析: ビタビアルゴリズム
δ[1,q] := π[q]b[q, o1] (for all q)
for t =2 to T
for q ∈ Q
δ[t, q] := maxq’∈Q {δ[t-1, q’]a[q’,q]b[q, ot]}
bp[t,q] := argmaxq’∈Q {δ[t-1, q’]a[q’,q]b[q, ot]}
21
まとめ

品詞解析
HMM
 HMMの解析

 ビタビアルゴリズム

資料
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/iips/
22