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

人工知能特論II 第12回
二宮崇
1
今日の講義の予定

系列ラベリングのための確率的識別モデル(Linear-chain
CRF)



解析 (ビタビアルゴリズム)
学習 (前向き後ろ向きアルゴリズム)
教科書




高村大也 (著), 奥村学 (監修) 言語処理のための機械学習入
門 (自然言語処理シリーズ), コロナ社, 2010
Yusuke Miyao (2006) From Linguistic Theory to Syntactic
Analysis: Corpus-Oriented Grammar Development and
Feature Forest Model, Ph.D Thesis, University of Tokyo
Jun’ichi Kazama (2004) Improving Maximum Entropy
Natural Language Processing by Uncertainty-aware
Extensions and Unsupervised Learning, Ph.D. Thesis,
University of Tokyo
Cristopher M. Bishop “PATTERN RECOGNITION AND
MACHINE LEARNING” Springer, 2006
2
系列ラベリングのための確率的識別モデル
LINEAR-CHAIN CRF
3
系列ラベリングのための確率的識別モデル
Linear-chain CRF

CRF (Conditional Random Fields, 条件付確率場)





最大エントロピーモデルの一種
出力yは入力xに対する条件付確率
出力yが無向グラフ(yをノードに分解できる)
素性を各ノードの近傍で定義
Linear-chain CRF


ノードが線形につながったCRF (系列ラベリングのためのCRF)
例えば、品詞解析の場合、入力xが文で、出力yが単語-品詞列となる。
単語と品詞のペアがノードになる。素性を各ノードの近傍で定義する。
I
代名詞
have
動詞
a
pen
不定冠詞
名詞
.
ピリオド
x =“I have a pen.”
y=“I-代名詞 have-動詞 a-不定冠詞 pen-名詞 .-ピリオド”
に対しp(y|x)を求める
4
Linear-chain CRF: 素性テンプレート

素性テンプレート



どのような素性を採用するか表記したもの
訓練データに対し素性テンプレートを適用し、実際に出現した
値だけを素性として採用
素性テンプレートの例




i番目のノードをciとする
i番目の品詞をpiとする
i番目の単語をwiとする
HMMと同様の素性の場合



各ノードciに対し、pi-1pi
各ノードciに対し、wipi
[最大で品詞数×品詞数の次元ができうる]
[最大で単語数×品詞数の次元ができうる]
他にもいろんな組合せの素性を追加できる


各ノードciに対し、 wi-1wipi
各ノードciに対し、 pi-2pi-1pi
5
Linear-chain CRF: 素性テンプレートと素性

素性テンプレートの例

HMMと同様の素性の場合


各ノードciに対し、pi-1pi
各ノードciに対し、wipi
w1
w2
w3
w4
w5
w6
x
a
pen
is
a
pen
.
y
不定冠詞
名詞
動詞
不定冠詞
名詞
p1
p2
p4
p5
p3
ピリオド
p6
pi-1piから生成される素性
wipiから生成される素性
不定冠詞-名詞
a-不定冠詞
名詞-動詞
pen-名詞
動詞-不定冠詞
is-動詞
名詞-ピリオド
.-ピリオド
6
Linear-chain CRF: 全体の素性ベクトルと局所的素
性ベクトルの関係

各素性関数の値は1文中に各素性が発火(出
現)した回数
f j ( x, y )   f j (c )
c
x
a
pen
is
y
不定冠詞
名詞
動詞
a
pen
不定冠詞
名詞
pen-名詞
不定冠詞-名詞
名詞-動詞
.
ピリオド
is-動詞
a-不定冠詞
素性ベクトル(…, 0, 2, 0, …, 0, 1, 0, …, 0, 2, 0, …, 0, 1, 0, …, 0, 2, 0, …)
7
Linear-chain CRF: 全体のスコアと局所的なスコアの関係

全体のスコア=各ノードcに対するスコアの積
p ( y | x;  ) 

 1

 1

 1


1
exp   j f j ( x, y )   exp   j  f j (c)   exp   j f j (c)    exp   j f j (c) 
Z
c
 j
 Z
 j
 Z
 c j
 Z c
 j

e 1 2 2 0 3 3 4 1 5 1
文全体の素性ベクトル: (2,0,3,1,1)
掛算
e
1 1 2 0  3 1 4 1 5 0
e
1 0  2 0  3 1 4 0  5 0
e 1 1 2 0 3 1 4 0 5 1
(1,0,1,1,0)
(0,0,1,0,0)
(1,0,1,0,1)
w1
w2
w3
p1
p2
p3
8
Linear-chain CRF: スコアの分解と
HMMとの対応

単語-品詞列の確率
p ( y | x;  ) 




1
1


exp   j f j ( x, y )  
exp

f
(
c
)


j j


Z ( x,  )
 j
 Z ( x,  ) c
 j

品詞列集合全体のスコアの和 (前向きア
ルゴリズムで計算)

解析: ビタビアルゴリズムの適用


HMMの遷移確率と出
力確率に対応
遷移確率と出力確率 ⇔ ノードのスコア exp j  j f j (c)
学習: 前向き後向きアルゴリズムの適用

遷移回数と出力回数 ⇔ 素性値(素性の発火回数)
9
1次のLinear-chain CRF


ラベル集合をQ、入力をx、出力をq1q2…qTとする。
Linear-chain CRF


exp  j f j (qt 1 , qt , x, t )

t 1
 j

T




Z x    exp  j f j (qt 1 , qt , x, t )
q1Q ,, qT Q t 1
 j

1
p (q1q2  qT | x) 
Zx
T
ただし、Zx は分配関数、λj は fj に対する重み、q0 = DUMMY(ダミーの
ラベル)とし、素性関数 f の引数は次のように定義される。
f (時刻 t －1 のラベル, 時刻 t のラベル, 入力, 時刻)

入力(第三引数)と時刻(第四引数)を与えることによって、入力の情報
を素性として用いることができる

例えば、品詞解析の場合、ラベルが品詞であり、入力が単語列となり、
時刻tやその前後における単語を素性として用いることができる。
10
LINEAR-CHAIN CRFの解析
11
Linear-chain CRFの解析



入力x
ラベル集合Q
Linear-chain CRFの解析


ˆq1qˆ 2  qˆT  arg max p (q1q2  qT | x)  arg max  exp  j f j (qt 1 , qt , x, t )
q1q2 qT
q1q2 qT
t 1
 j

T
(Zx は定数であるため、必要ない)
12
Linear-chain CRFの解析: ビタビアルゴリズム

動的計画法
δ(t, q): 時刻tにラベルqとなるラベル列の中で最大のスコア
maxq∈Q δ(T, q)を求めれば良い
時刻
1
2
3
T
ラベル1
…
ラベル2
…
…
ラベル3
…
ラベル4
トレリス
13
Linear-chain CRFの解析: ビタビアルゴリズム
 t 1  j  j f j ( qu1 ,qu , x ,u )   j  j f j ( qt 1 ,q , x ,t )
 (t , q)  max   e
e
q1Q ,, qt 1Q
 u 1

 t 2  j  j f j ( qu1 ,qu , x ,u )   j  j f j ( qt2 ,qt 1 , x ,t 1)  j  j f j ( qt1 ,q , x ,t )
 max max   e
e
e
qt 1Q q1Q ,, qt 2 Q
 u 1

最大スコアで遷移したパ
 j  j f j ( qt 1 ,q , x ,t )
 max (t  1, qt 1 )e
スをバックポインタで保存
qt 1Q
時刻
1
2
t-1
t
T
ラベル1
…
…
ラベル2
…
…
…
ラベル q
…
…
…
…
…
14
Linear-chain CRF:解析(ビタビアルゴリズム)


入力x
Linear-chain CRFの解析


max p (q1q2  qT | x)  max  exp  j f j (qt 1 , qt , x, t )  max  (T , q )
q1q2 qT
q1q2 qT
q
t 1
 j

T
Linear-chain CRFのビタビアルゴリズム
HMMとの対応
for q∈Q
𝜋 𝑞 𝑏[𝑞, 𝑜1 ]
δ[1, q] := exp{Σjλjfj(DUMMY,q,x,1)}
for t =2 to T
𝑎[𝑞 ′ , 𝑞] 𝑏[𝑞, 𝑜𝑡 ]
for q∈Q
δ[t, q] := maxq’ ∈Q δ[t - 1,q’]exp{Σjλjfj(q’, q, x, t)}
bp[t, q] := argmaxq’ ∈Q δ[t - 1,q’]exp{Σjλjfj(q’, q, x, t)}

15
LINEAR-CHAIN CRFの学習
16
Linear-chain CRFの学習

学習 (パラメータ推定)

訓練データの対数尤度(=目的関数)に対する勾配を0にする
N
L( ) N
  f j ( xi , yi )    p( y | xi ;  ) f j ( xi , y)
 j
i 1
i 1 yY ( xi )


問題点



目的関数とその勾配が計算できれば勾配法でパラメータが求ま
る。
素性関数の期待値の計算: 「ある文xに対する全ての可能なラベ
ル列集合Y(x)に対する確率」を計算しないといけない
文長n、ラベル数lに対し、可能なラベル列はlnある。全て展開す
るのはほぼ不可能
解決策


前向き後ろ向きアルゴリズム
畳み込まれたデータ構造を展開することなく素性関数の期待値
を計算
17
Linear-chain CRFの学習: 目的関数




訓練データ D={(x1, y1), (x2, y2), …, (xN, yN)}
各 yi を yi=qi1qi2…qiTiとする。
目的関数: 訓練データに対するLinear-chain CRFの
対数尤度
パラメータλに対する目的関数 L(λ)
 N

L( )  log  p ( yi | xi ;  ) 
 i 1

Ti
N


1

  log
exp   j f j (qi (t 1) , qit , xi , t ) 

Z ( xi ,  ) t 1
i 1
 j

Ti
N
N
i 1
i 1 t 1
  log Z ( xi ,  )    j f j (qi (t 1) , qit , xi , t )
j
18
Linear-chain CRFの学習: 目的関数の勾配 (1/2)

L( )
 j
目的関数 L(λ) に対するパラメータ λ の勾配


N
Ti

i 1 t 1
N Ti
Z ( xi ,  )
1
f j (qi (t 1) , qit , xi , t )  
 j
i 1 Z ( xi ,  )
 f
i 1 t 1
N
N
j
(qi (t 1) , qit , xi , t )
Ti
 Ti

1

f j (qt1 , qt, xi , t ) exp  j f j (qu 1 , qu , xi , u )


i 1 Z ( xi ,  ) q1Q ,, qT i Q t 1
 u 1 j


N
Ti
 f
i 1 t 1
N
j
(qi (t 1) , qit , xi , t )  

i 1 q1Q ,, qT i Q
Ti
p (q1  qTi | xi ) f j (qt1 , qt, xi , t )
t 1
素性関数の合計の期
待値となっている
19
Linear-chain CRFの学習: 目的関数の勾配 (2/2)

L( )
 j
目的関数 L(λ) に対するパラメータ λ の勾配
(前のスライドの続き)



N
Ti
N
 f
j
(qi (t 1) , qit , xi , t )  
 f
j
(qi (t 1) , qit , xi , t )  

f j (qt1 , qt, xi , t )
 f
j
(qi (t 1) , qit , xi , t )  
f
(qt1 , qt, xi , t ) p (qt1qt | xi )
i 1 t 1
N Ti
i 1 t 1
N Ti
i 1 t 1

Ti
i 1 q1Q ,, qT i Q
N Ti
p (q1  qTi | xi ) f j (qt1 , qt, xi , t )
i 1 t 1 qt1Q , qtQ
N Ti
j
i 1 t 1 qt1Q , qtQ
t 1
 p ( q  q
1
Ti
q1Q ,, qt2 Q , qt1Q ,, qT i Q
| xi )
qt-1 qt の周辺確率を効率的に
求められればよい
20
Linear-chain CRFの学習: 前向きアルゴリズム (1/3)

動的計画法
α(t, q): 時刻tにラベルqであるスコアの合計
 t 1  j  j f j ( qu1 ,qu , x ,u )   j  j f j ( qt 1 ,q , x ,t )
 (t , q) 
  e
e

q1Q ,, qt 1Q  u 1

全てのt,qに対し、α(t, q)を求めれば良い
時刻
1
2
3
T
ラベル1
…
ラベル2
…
ラベル3
ラベル4
…
…
トレリス
21
Linear-chain CRFの学習: 前向きアルゴリズム (2/3)
 t 1  j  j f j ( qu1 ,qu , x ,u )   j  j f j ( qt 1 ,q , x ,t )
 (t , q) 
  e
e

q1Q ,, qt 1Q  u 1

 t  2  j  j f j ( qu1 ,qu , x ,u )   j  j f j ( qt 2 ,qt 1 , x ,t 1)  j  j f j ( qt 1 ,q , x ,t )
 
e
  e
e

qt 1Q q1Q ,, qt 2 Q  u 1

 j  j f j ( qt 1 ,q , x ,t )
   (t  1, qt 1 )e
全てのスコアの和
qt 1Q
時刻
1
2
t-1
t
T
ラベル1
…
…
ラベル2
…
…
…
ラベル q
…
…
…
…
…
22
Linear-chain CRFの学習: 前向きアルゴリズム (3/3)
Linear-chain CRFの前向きアルゴリズム
for q∈Q
α[1, q] := exp{Σjλjfj(DUMMY,q,x,1)}
for t =2 to T
for q∈Q
α[t, q] := Σq’ ∈Q α[t - 1,q’]exp{Σjλjfj(q’, q, x, t)}



入力xとパラメータλが与えられているとする
分配関数 Zx を効率的に求めることもできる
⇒ 目的関数を効率的に求めることができる！
23
Linear-chain CRFの学習: 後ろ向きアルゴリズム (1/3)

前向きアルゴリズムを逆方向に適用



文末から文頭に向かって実行
向きが逆になることを除けば前向きアルゴリズムと
まったく同じ
β(t, q) :時刻tにラベルqとなっているとき、時刻
t+1から文末までのスコアの合計
 (t , q) 

qt 1Q ,, qT Q
e
 j  j f j ( q ,qt 1 , x ,t 1)
T
e
 j  j f j ( qu1 ,qu , x ,u )
u t  2
24
Linear-chain CRFの学習: 後ろ向きアルゴリズム (2/3)

 (t , q) 
e
qt 1Q ,, qT Q




 j  j f j ( q ,qt 1 , x ,t 1)
e
 j  j f j ( qu1 ,qu , x ,u )
u t  2
 j  j f j ( q ,qt 1 , x ,t 1)  j  j f j ( qt 1 ,qt 2 , x ,t  2 ) T  j  j f j ( qu1 ,qu , x ,u )
e
e
e
qt 1Q qt  2 Q ,, qT Q
 j f j ( q , qt 1 , x ,t 1)
e
T
j
qt 1Q
u t  3
 (t  1, qt 1 )
全てのスコアの和
時刻
1
2
t
t+1
T
ラベル1
…
…
ラベル2
…
…
…
ラベル q
…
…
…
…
…
25
Linear-chain CRFの学習: 後ろ向きアルゴリズム (3/3)
後ろ向きアルゴリズム
for q∈Q
β[T, q] := 1
for t = T － 1 to 1
for q ∈ Q
β[t, q] := Σq’∈Q β[t + 1, q’]exp{Σjλjfj(q, q’, x, t + 1)}

26
Linear-chain CRF
学習(前向き後ろ向きアルゴリズム)

qt-1 qt の周辺確率
p (qt1qt | xi ) 








 p ( q  q
q1Q ,, qt2 Q qt1Q ,, qT i Q
1
Ti
| xi )
Ti
1
 j  j f j ( qu 1 ,qu , xi ,u )
e

 
Z ( xi ,  ) q1Q ,,qt2 Q qt1Q ,,qTi Q u 1
 t 1  j  j f j ( qu 1 ,qu , xi ,u )   j  j f j ( qt1 ,qt , xi ,t )  Ti  j  j f j ( qu 1 ,qu , xi ,u ) 
1
  e

  e
e


Z ( xi ,  ) q1Q ,,qt2 Q qt1Q ,,qTi Q  u 1

 u t 1

 Ti  j  j f j ( qu 1 ,qu , xi ,u ) 
 t 1  j  j f j ( qu 1 ,qu , xi ,u ) 
1
 j  j f j ( qt1 ,qt , xi ,t )
  e

e
  e
 

Z ( xi ,  )
q1Q ,, qt2 Q  u 1
qt1Q ,,qTi Q  u t 1

 t 1  j  j f j ( qu 1 ,qu , xi ,u ) 
1
 j  j f j ( qt1 ,qt , xi ,t )
e
  e
  (t , qt )

Z ( xi ,  )
q1Q ,, qt2 Q  u 1

t

1

1
  j f j ( qt1 ,qt , xi ,t )
  j f j ( qu 1 ,qu , xi ,u ) 
e j
 (t , qt )    e j

Z ( xi ,  )
q1Q ,, qt2 Q  u 1

1
  j f j ( qt1 ,qt , xi ,t )
e j
 (t , qt ) (t  1, qt1 )
Z ( xi ,  )
1
 j  j f j ( qt1 ,qt , xi ,t )

 (t  1, qt 1 )e
 (t , qt )
Z ( xi ,  )
27
Linear-chain CRF
学習(前向き後ろ向きアルゴリズム)

前向き後ろ向きアルゴリズムによる目的関数L(λ)に対するパラメータλの勾配
L( )
 j


N
Ti
N
Ti
 f
j
(qi (t 1) , qit , xi , t )  
 f
j
(qi (t 1) , qit , xi , t )
i 1 t 1
N Ti
i 1 t 1
N Ti
f
j
i 1 t 1 qt1Q , qtQ
(qt1 , qt, xi , t ) p (qt1qt | xi )
 f ( qt1 , qt , xi ,t )
1

j j j
    f j (qt1 , qt, xi , t )
 (t  1, qt1 )e
 (t , qt )
Z ( xi ,  )
i 1 t 1 qt1Q qtQ
28
まとめ

系列ラベリングのための確率的識別モデル
Linear-chain CRF
 解析 (ビタビアルゴリズム)
 学習 (前向き後ろ向きアルゴリズム)

今までの講義資料
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/ai2/
29

Download Report