1. No category

知的情報処理システム特論
第10回
二宮 崇
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
系列ラベリングのためのHMM
HMM FOR SEQUENTIAL
LABELING
3
品詞解析

品詞タガー
“I have a pen.”
トーカナイザー
I
have
a
pen
.
POSタガー
I
代名詞
have
動詞
a
pen
不定冠詞
名詞
.
ピリオド
4
隠れマルコフモデル
Hidden Markov Model (HMM)
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
不定冠詞
名詞
.
ピリオド
5
隠れマルコフモデル
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
6
状態記号列の確率と
生成確率

状態と記号の列が与えられた時
状態記号列 : 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
)
(生成確率)
7
学習 (パラメータ推定): 最尤推定
8
パラメータ推定: 最尤推定

最尤推定
文の集合を観測したとき、その文の集合がそ
こに出現したのは、その文の集合が最も確率
が高かったから、と考えるやり方
 コインの例：表がでる確率θが未知のコインが
ある。100回投げたところ、62回表がでた。す
ると、その確率はθ62(1－θ)38となる。この確率
はθ=0.62で最大となるので、θは0.62であった
のだろう、と考えるのが最尤推定の考え方で
ある。

9
最尤推定

最尤推定

観測値 x1,...,xn が与えられた時、それぞれが独
立に出現したと考えると、その確率はパラ
メータθの関数になる
n
p ( x1 ,..., xn ) = ∏ p ( xi ;θ ) = l (θ )
i =1
このl(θ)を尤度(likelihood)もしくは尤度関数
(likelihood function)と呼ぶ
 尤度関数を最大化するθを求める

~
θ = arg max l (θ )
θ
10
最尤推定

最大を求めるために尤度関数の極値を求め
る
∂
∂θ

l (θ ) = 0
コインの例を解析的に解いてみよう

l(θ) = θ62(1－θ)38
11
最尤推定

対数尤度(log likelihood)を使うと計算が楽
になる
~
θ = arg max l (θ ) = arg max log l (θ )
θ

θ
コインの例で解いてみよう

log l(θ) = log( θ62(1－θ)38 )
12
最尤推定

正規分布の最尤推定
正規分布N(μ, σ2)から抽出された標本をx1,...,xn
とする
2
n
 尤度


−
(
)
µ
x
1
2
i

l (µ ,σ ) = ∏
i =1

exp −
2π σ

2σ
2


対数尤度
n
 ( xi − µ ) 2 
1
+ ∑ −
log l ( µ , σ ) = ∑ log

2
2
σ
2
π
σ
i =1
i =1 

n
( xi − µ ) 2
= −n log( 2π σ ) − ∑
2σ 2
i =1
n
2
13
ラグランジュの未定乗数法

ラグランジュの未定乗数法
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(θ) はラグランジュ関数と呼ばれる
14
学習 (パラメータ推定): HMMの
教師付学習
15
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とする。
パラメータ (出力)
πq
… |Q|個の変数
aq,r … |Q|×|Q|個の変数
bq,o … |Q|×|Σ|個の変数

16
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
17
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 
t =2
i =1 
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 )
18
HMMの教師付学習
Supervised Learning of HMMs

ラグランジュの未定乗数法
ラグランジュ関数
L(π , a, b)









= log l (π , a, b) − ρ 1 − ∑ π q  − ∑ α q 1 − ∑ aq ,r  − ∑ β q 1 − ∑ bq ,o 

 q∈Q  o∈Σ
 q∈Q  q∈Q  r∈Q
Ti
Ti
n








= ∑  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  o∈Σ
 q∈Q  q∈Q  r∈Q
ラグランジュ乗数
ρ … 1個の変数
αq … |Q|個の変数
βq … |Q|個の変数
19
HMMの教師付学習
Supervised Learning of HMMs

πqを求める
アイバーソンの記法
(Iverson bracket)
∂L C1 ( q)
=
+ρ =0
πq
∂π q
ただし、C1 ( q) = ∑i =1 [qi1 = q ]
n
πq =
C1 (q)
−ρ
 (1)
ところで∑q∈Q π q = 1であるから
∑π q
q∈Q
∑
=
q∈Q
C1 (q)
−ρ
=
1 if P is true
[ P] = 
0 otherwise
C1(q)は訓練データ中で、文の
先頭がqになっている回数
n
=1
−ρ
よって、ρ = −n。これを式 (1)に代入して、
C (q)
πq = 1
n
20
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
T
 (1)
C(q,r)は訓練データ中で、状
態qから状態rに遷移した回数
ところで∑r∈Q aq ,r = 1であるから
∑a
r '∈Q
q ,r '
∑
=
r '∈Q
C ( q, r ' )
−αq
=1
よって、α q = −∑r '∈Q C (q, r ' )。これを式 (1)に代入して、
aq , r =
C ( q, r )
∑r '∈Q C (q, r ' )
21
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
T
 (1)
C(q,o)は訓練データ中で、状
態qから記号oを出力した回数
ところで∑o∈Σ bq ,o = 1であるから
∑b
o '∈Σ
q ,o '
∑
=
o '∈Σ
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が出現した回数
22
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
23
まとめ

HMM

学習
 最尤推定
 教師付き学習

資料
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/iips/
24