パワーポイント2007(推奨)

数理言語情報論第10回
2009年12月9日
数理言語情報学研究室講師二宮崇
1
今日の講義の予定

品詞解析 (系列ラベリング)

解析 (ビタビアルゴリズム)
パラメータ推定 (前向き後向きアルゴリズム)

内側外側アルゴリズム



構文解析の教師無し学習
教科書



北研二(著) 辻井潤一(編) 言語と計算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
EMアルゴリズム(一般) 1/3





パラメータ: θ
入力: x
隠れ状態: y
観測データ: X={x1, x2, …, xn}
対数尤度: log pθ(X)
n
n
log pθ ( X )   log pθ (x i )  
i 1
n
 q(y
i 1 y i Y ( x i )
i
| x i ) log pθ (x i )

 q(y
i
| x i )log pθ (x i , y i )  log pθ (y i | x i )

 q(y
i
| x i )log pθ (x i , y i )  log q (y i | x i )  log pθ (y i | x i )  log q (y i | x i )
i 1 y i Y ( x i )
n
i 1 y i Y ( x i )

pθ (x i , y i )
pθ (y i | x i ) 
q
(
y
|
x
)
log

log


i
i 
q
(
y
|
x
)
q
(
y
|
x
)
i 1 y i Y ( x i )
i
i
i
i 

n
n
p (x , y )
p (y | x )
   q (y i | x i ) log θ i i    q(y i | x i ) log θ i i
q (y i | x i ) i 1 y i Y ( xi )
q(y i | x i )
i 1 y i Y ( x i )
n

3
EMアルゴリズム(一般) 2/3





パラメータ: θ
入力: x
隠れ状態: y
観測データ: X={x1, x2, …, xn}
対数尤度: log pθ(X)
n
L ( q , θ)  
 q( yi | xi ) log
i 1 yi Y ( xi )
n
KL(q || p)  
pθ ( xi , yi )
q( yi | xi )
 q( yi | xi ) log
i 1 yi Y ( xi )
ポイント!
前ページのように式を展開するよりも
ここに
log pθ (xi , y i )  log pθ (y i | xi )  log pθ (xi )
を代入して等式が成り立つことを確認
するほうがわかりやすい
pθ ( yi | xi )
0
q( yi | xi )
とおくと
log pθ ( X )  L(q, θ)  KL(q || p)
 L ( q , θ)
4
EMアルゴリズム(一般) 3/3

Eステップ
q (t 1) (y i | xi )  arg max L(q(y i | xi ), θ(t ) )  arg min KL(q(y i | xi ) || pθ( t ) (y i | xi ))  pθ( t ) (y i | xi )
q ( y i |x i )
q ( y i |x i )
パラメータが固定されているので、pθ(X) は変わらない
→ Lを最大化 ⇔ KLを最小化

Mステップ
θ
( t 1)
 arg max L(q
θ
( t 1)
n
, θ)  arg max 
θ
q
i 1 y i Y ( x i )
( t 1)
(y i | xi ) log pθ (xi , y i )
Q関数
隠れ状態の確率とパラメータを交互に動かして、
Lを最大化
5
品詞解析 (系列ラベリング )
POS TAGGING
(SEQUENTIAL LABELING)
6
品詞解析

品詞タガー
“I have a pen.”
トーカナイザー
I
have
a
pen
.
POSタガー
I
代名詞
have
動詞
a
pen
不定冠詞
名詞
.
ピリオド
7
隠れマルコフモデル (1/3)
I
he
名詞
出力 (emission)
Mary
ピリオド
…
代名詞
不定
冠詞
遷移 (transition)
動詞
I
文頭
代名詞
have
動詞
a
pen
不定冠詞
名詞
.
ピリオド
8
隠れマルコフモデル (2/3)
0.3
ピリオド
0.5
名詞
0.01
0.1
he
0.25
出力 (emission)
0.01
…
代名詞
遷移 (transition)
動詞
have
0.3
Mary
0.43
不定
冠詞
I
I
a
pen
不定冠詞
名詞
.
0.3
文頭
代名詞
動詞
0.01
ピリオド
9
隠れマルコフモデル (3/3)
Q: 状態の有限集合
 Σ: 出力記号の有限集合
 q0: 初期状態
 a(i, j): 状態iから状態jへの遷移確率

Σj∈Q a(i, j)=1
 a(q0, i): 文頭が状態iになる確率


b(i, o): 状態iにおける記号oの出力確率

Σo∈Σ b(i,o) = 1
10
状態と記号の列の確率
生成確率と解析

状態と記号の列が与えられた時
状態と記号の列 : s0 s1o1s2 o2  sn on (ただし s0  q0 )
p( s1o1s2 o2  sn on )  a( s0 , s1 )b( s1 , o1 )a( s1 , s2 )b( s2 , o2 )  a( sn 1 , sn )b( sn , on )
 a( s0 , s1 )a( s1 , s2 )  a( sn 1 , sn )b( s1 , o1 )b( s2 , o2 ) b( sn , on )
n
n
i 1
i 1
  a( si 1 , si ) b( si , oi )

記号列のみが与えられた時
記号列 : o1o2  on
p (o1o2  on ) 
q~1q~2  q~n 
 p(q o q o  q o )
1 1 2 2
q1Q , q2 Q ,qn Q
arg max
q1Q , q2 Q ,qn Q
a, b  arg max
a ,b
n n
p (q1o1q2 o2  qn on )
 p(q o q o  q o )
1 1 2 2
q1Q , q2 Q ,qn Q
n n
(生成確率)
(品詞解析)
(パラメータ推定)
計算量がO(|Q|n )
11
効率的な品詞解析: ビタビアルゴリズム (1/4)

動的計画法
δ(t, q): 時刻t(otが出力される時)に状態qとなる状態列の中で最大確率となる列
の確率
maxq∈ Q δ(n, q)を求めれば良い
2
時刻 1
o2
出力記号 o1
3
o3
n
on
状態1
…
状態2
…
…
状態3
…
状態4
トレリス
12
効率的な品詞解析: ビタビアルゴリズム (2/4)
 (t , q) 
max
q1Q ,, qt 1Q
p(q1o1  qt 1ot 1 )a(qt 1 , q)b(q, ot )
 max  max p(q1o1  qt  2 ot  2 )a(qt  2 , qt 1 )b(qt 1 , ot 1 )a(qt 1 , q)b(q, ot )
qt 1Q q1Q ,, qt 2 Q

 max  (t  1, qt 1 )a(qt 1 , q)b(q, ot )
qt 1Q
最大確率で遷移したパス
をバックポインタで保存
o1
o2
ot-1
ot
on
状態1
…
…
状態2
…
…
…
状態 q
…
…
…
…
…
13
効率的な品詞解析: ビタビアルゴリズム (3/4)

最後にバックポインタを辿ることで最大確
率となる状態列が得られる
o1
o2
on-2
状態1
…
状態2
…
状態 3
…
状態 4
…
on-2
on
14
効率的な品詞解析: ビタビアルゴリズム (4/4)
δ[1,q] := a(q0, q) (for all q)
for t =2 to n
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)}
15
パラメータ推定

パラメータ推定
記号列 : o1o2  on
arg max p(o1o2  on )  arg max
a ,b
a ,b
 p(q o q o  q o )
1 1 2 2
q1Q , q2 Q ,qn Q
n n
前向きアルゴリズム
 後向きアルゴリズム
 前向き後向きアルゴリズムによる推定

16
前向きアルゴリズム (1/3)

動的計画法
α(t, q): o1 … otを出力し、otが出力される時(時刻t)に状態qである確率
Σq∈ Q α(n, q)を求めれば良い
時刻
出力記号
1
o1
2
o2
3
o3
n
on
状態1
…
状態2
…
…
状態3
…
状態4
トレリス
17
前向きアルゴリズム (2/3)
 (t , q) 
 p(q o  q
q1Q ,, qt 1Q
1 1
o )a(qt 1 , q)b(q, ot )
t 1 t 1


    p(q1o1  qt  2 ot  2 )a(qt  2 , qt 1 )b(qt 1 , ot 1 )a(qt 1 , q)b(q, ot )
qt 1Q q1Q ,, qt 2 Q

   (t  1, qt 1 )a(qt 1 , q)b(q, ot )
全ての遷移確率の和
qt 1Q
o1
o2
ot-1
ot
on
状態1
…
…
状態2
…
…
…
状態 q
…
…
…
…
…
18
前向きアルゴリズム (3/3)
α[1,q] := a(q0, q) (for all q)
for t =2 to n
for q ∈ Q
α[t, q] := Σq’∈Q {α[t-1, q’]a(q’,q)b(q, ot)}
19
後向きアルゴリズム (1/2)

前向きアルゴリズムを逆方向に適用



文末から文頭に向かって実行
向きが逆になることを除けば前向きアルゴリズムと
まったく同じ
β(t, q) :時刻tに状態qから始める状態遷移によって
ot+1…onまで出力する確率
 (t , q) 
 a ( q, q
qt 1Q ,, qn Q
t 1
)b(qt 1 , ot 1 ) p(qt 1ot  2 qt  2  on qn )


  a(q, qt 1 )b(qt 1 , ot 1 )  a(qt 1 , qt  2 )b(qt  2 , ot  2 ) p(qt  2 ot 3  on qn )
qt 1Q 
qt 2 Q ,, qn Q

  a(q, qt 1 )b(qt 1 , ot 1 )  (t  1, qt 1 )
qt 1Q
20
後向きアルゴリズム (2/2)
β[n,q] := 1 (for all q)
for t := n-1 to 1
for q ∈ Q
β[t, q] := Σq’∈Q {a(q, q’)b(q’, ot+1)β[t+1, q’]}
21
EMアルゴリズムによるパラメータ推定

パラメータ更新式
a ' ( q, q ' ) 
状態qから状態 q ' へ遷移する回数の期待値
状態qから遷移する回数の期待値
状態qに滞在し記号 oを出力する回数の期待値
b' ( q, o) 
状態qに滞在する回数の期待値
22
状態列を列挙した場合の期待値
状態qから状態 rへ遷移する回数の期待値

 p(q o q o  q o )  (q q  q における qから rへの遷移回数 )
q1Q ,, qn Q

1 1 2 2
n n
1 2
n
例


q, r, sの3つの状態があるとする (例えば、名詞、動詞、形容詞)
o1o2o3に対する状態列を列挙
状態列
確率
状態列
確率
状態列
確率
qqq
qqr
qqs
qrq
qrr
qrs
qsq
qsr
qss
0.03
0.02
0.008
0.02
0.001
0.03
0.02
0.08
0.07
rqq
rqr
rqs
rrq
rrr
rrs
rsq
rsr
rss
0.082
0.085
0.024
0.011
0.009
0.098
0.053
0.055
0.001
sqq
sqr
sqs
srq
srr
srs
ssq
ssr
sss
0.003
0.07
0.008
0.002
0.02
0.005
0.003
0.018
0.008
23
qからrに遷移する回数の期待値: 0.02+0.02+0.001+0.03+0.085+0.07=0.226
前向き後向きアルゴリズム (1/2)
あるパラメータa,bが与えられているとする
 αを求める(前向きアルゴリズム)
 βを求める(後向きアルゴリズム)
γ(t,q,r): 記号列o1…onに対し、時刻tに状態qから状態rに遷移する確率
 次のようにa,bを更新する
n
状態qから状態 q ' へ遷移する回数の期待値
a ' ( q, q ' ) 

状態qから遷移する回数の期待値
  (t , q, q' )
t 1
n
   (t , q, q' ' )
 (t , q, q' ' )


状態qに滞在し記号 oを出力する回数の期待値
t 1 q ''Q
b' ( q, o)

状態qに滞在する回数の期待値

t:ot  o q ''Q
n
   (t , q, q' ' )
t 1 q ''Q
24
前向き後向きアルゴリズム (2/2)
γ(t,q,r): 記号列o1…onに対し、時刻tに状態qか
ら状態rに遷移する確率
 (t , q)a(q, r )b(ot 1 )  (t  1, r )
 (t , q, r ) 
 (n, q' )
q 'Q
前向き確率
o1
o2
ot
後向き確率
ot+1
on
…
…
状態 q
…
…
…
状態 r
…
…
…
…
…
25
内側外側アルゴリズム
INSIDE OUTSIDE
ALGORITHM
26
PCFGのEMアルゴリズム
1.
2.
θ(0) := 適当な値
[Eステップ] θ(i)を用いて各構文木の確率を計
算。文sに対する各構文木の相対確率を計算。
p (t )   ( r ) C ( r ;t )
(i )
p(t | s) 
rP
3.
[Mステップ] θ(i+1)を求める
 A(i1) 
p(t )
 p(u)
uT ( s )
  p(t | s)C ( A   ; s, t )
   p(t | s)C ( A   ; s, t )
sText tT ( s )
sText tT ( s )
4.
2.に戻る
27
PCFGのEMアルゴリズム

[Eステップ]各構文木の文sに対する確率



仮のパラメータθ(i)を用いてフルパーズした結果の各々の構文木の確率を計算。
文sに対するそれぞれの構文木の相対確率p(t|s)を計算
[Mステップ]パラメータ更新


書換規則の適用回数の期待値を計算
単純な数え上げと同じ方法でパラメータを求める
s1
parse
p(t|s1)=p(t)/Z1 =
s2
0.1
0.3
0.6
Zi 
parse
p(t|s2)=p(t)/Z 2=
s3
C’(r;t) = 0.6×C(r; t)
1.0
 p(t )
tT ( si )
parse
p(t|s3)=p(t)/Z3 =
0.21
0.16
0.51
0.05
0.07
...
...
...
28
PCFGに対するEMアルゴリズム
の問題点

s
構文木が多すぎて現実的な時間で各構文木
の相対確率を計算できない！(文長に対し
て指数爆発的に増加。簡単に数百億ぐらい
になる。)
parse
...
p(t)/Z =
0.21
0.06
0.001
0.05
0.07
数百億続く！
29
内側外側アルゴリズム


畳みこまれた構文木集合に対して効率的にEMア
ルゴリズムを実行する手法
アイデア
CKYアルゴリズムでフルパーズした後のCKY
テーブルから構文木を展開することなく各書
換規則の適用回数の期待値が計算できればよ
い
 バイナリールールを仮定し、内側確率と外側
確率を動的計画法で効率的に計算
 内側確率と外側確率から書換規則の適用回数
の期待値が計算

30
内側確率

内側確率 β(i,j,A)

非終端記号Aから単語列wi+1,...,wjを導出する確
率(=単語列wi+1,...,wjを構文解析してルート(根)
がAとなる構文木集合の確率の和)
A
w1,...,wi wi+1, ..................,wj wj+1,...,wn
31
内側確率の計算

Si,jをビタビアルゴリズムと同様に計算

ただし、ファクタリングの際にmaxをとっていたのをsumに
する
Si,j: <X, p>の集合 (X: 非終端記号, p: 部分木の確率)
 Si,jの求め方
sumをmaxにする
for k = i+1 to j-1
とビタビアルゴリ
forall <B, pX>∈ Si,k
ズムになる
forall <C, pY>∈ Sk,j
forall A ∈ G(B, C)
if( <A, p> exists in Si,j )
p := p + pX×pY×θZ→X Y
else
Si,j := Si,j ∪ <A, pX×pY×θZ→X Y>

32
外側確率

外側確率α(i,j,B)

S(開始記号)からw1...wiBwj+1...wnを導出する確
率
S
B
w1,...,wi wi+1, ..................,wj wj+1,...,wn
33
外側確率計算のアイデア

バイナリールールなので、次の2通りとAC
の組み合わせからα(i,j,B)が計算できる
A→B C: Aの外側確率×Cの内側確率×θA→B
 A→C B :Aの外側確率×Cの内側確率×θA→C

S
S
A
B
w1..wi
C
B
A
C
wi+1 ..wj wj+1 ..wk wk+1..wn
C
w1..wk wk+1 ..wi
B
wi+1 ..wj wj+1..wn
外側確率の計算

α(i,j,B)の計算
 (i, j, B) 

n
A BC
A ,C

A ,C
ACB
 (i, k , A) ( j, k , C ) 
k  j 1
0
 (k , j, A) (k , i, C )
k i 1
35
外側確率の計算

α(i,j,X)の計算の順番
S0,6
スタート
S0,5
S0,4
S0,3
S0,2
S0,1
0
w1
S1,5
S1,4
S1,3
S1,2
1
w2
S1,6
S2,5
S2,4
S2,3
2
S2,6
w3
S3,6
S3,5
S3,4
3
w4
S4,6
S4,5
4
w5
S5,6
5
w6
6
36
外側確率計算アルゴリズム
フルパージングと内側確率計算後を仮定
for all 0 ≦i < j ≦n, X∈VN
Ai,j → Bi,k Ck,j in Si,jはフル
パージングの際にSi,j中の
α(i,j,X) := 0
非終端記号Aを生成するに
α(0,n,S) := 1.0
到った履歴
for l = n – 1 to 1
・書換規則がA→B C
・BはSi,kの中の要素
for i = 0 to n － l
・CはSk,jの中の要素
j := i + l
forall Ai,j → Bi,k Ck,j in Si,j
α(i, k, B):=α(i, k, B)+α(i,j,A)×β(k,j,C)×θA→ B C
α(k, j, C):=α(k, j, C)+α(i,j,A)×β(i,k,B)×θA→B C
37
書換規則の適用回数の期待値
内側確率と外側確率を使って書換規則の適
用回数の期待値を計算
 Ai,j→Bi,k Ck,jの適用回数の期待値= Ai,j→Bi,k
Ck,j の出現した構文木の確率の和

s
Ai,j
Ai,j
Ai,j
Bi,k Ck,j
Bi,k Ck,j
Bi,k Ck,j
parse
p(t)/Z =
0.21
0.16
...
0.07
38
書換規則の適用回数の期待値

Ai,j→Bi,k Ck,jの適用回数の期待値
=1/Z×(Ai,j→Bi,k Ck,j の出現した構文木の確率の和)
=1/Z×(Bi,kの内側確率×Ck,jの内側確率×θA→B C×Ai,jの外側確率)
S
A
B
w1..wi
C
wi+1 ..wk wk+1 ..wj wj+1..wn
39
書換規則の適用回数の期待値
p ( Ai , j  Bi ,k Ck , j
1
| s) 
 A BC (i, j , A)  (i, k , B)  (k , j , C )
p( s)
j 1
n 1 n
1
C ( A  BC ; s ) 
 A BC     (i, j , A)  (i, k , B)  (k , j , C )
p(s)
i  0 j i  2 k i 1
p ( s )   (0, n, S )
40
内側外側アルゴリズム
1.
2.
3.
θ(0) := 適当な値
[Eステップ] θ(i)を用いて内側確率と外側確率を計算。
[Mステップ] 書換規則の適用回数の期待値を計算。
θ(i+1)を求める
j 1
n 1 n
1
C ' ( A  BC ; s) 
 A BC     (i, j, A)  (i, k , B)  (k , j, C )
 (0, n, S )
i  0 j i  2 k i 1
)
 A(i1BC

 C( A  BC ; s)
  C( A  BC ; s)
sText
sText B ,C
4.
2.に戻る
41
まとめ

品詞解析 (系列ラベリング)

解析 (ビタビアルゴリズム)
パラメータ推定 (前向き後向きアルゴリズム)

内側外側アルゴリズム

http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH21w/cl/




構文解析の教師無し学習
次回は、12/16(水) 16:30～確率的HPSG (単一化ア
ルゴリズム、フルパージングアルゴリズム、確率
的HPSG)
講義資料
42

Download Report