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

PCFGのEMアルゴリズムとス
ムージング
二宮崇
1
今日の講義の予定

PCFG (Probabilistic Context Free Grammar, 確率付
文脈自由文法)



EMアルゴリズム
スムージング
教科書



北研二(著) 辻井潤一(編) 言語と計算4 確率的言語モデル
東大出版会
C. D. Manning & Hinrich Schütze “FOUNDATIONS
OF STATISTICAL NATURAL LANGUAGE
PROCESSING” MIT Press, 1999
D. Jurafsky, J. H. Martin, A. Kehler, K.V. Linden & N.
Ward “Speech and Language Processing: An
Introduction to Natural Language Processing,
Computational Linguistics, and Speech Recognition”
Prentice Hall Series in Artificial Intelligence, 2000
2
PCFGの最尤推定

次の二文を訓練データとして、パラメータ
推定


“John sees Mary with_a_telescope”
“Mary with_a_telescope runs”
r
Pr
S → NP VP
1.0
VP → VP PP
θ1
VP → V NP
θ2
VP → V
θ3
NP → NP PP
θ4
NP → John
θ5
NP → Mary
θ6
PP → with_a_telescope
1.0
V → sees
θ7
V → runs
θ8
3
PCFGの最尤推定
S
t1,1
構文木
構文木
t1,2
S
VP
NP
θ5
θ2
V
John
θ7
NP
NP
sees
VP
NP
θ4
θ6
VP
θ5
John
PP
Mary
V
θ7
sees
t2,1
NP
θ6
PP
Mary
S
NP
θ4
NP
with_a_telescope
with_a_telescope
構文木
θ2
θ1
VP
PP
θ6
ts,u: sは文ID
θ3
V
θ8
runs
Mary
with_a_telescope
uはsに対する構文木集
合の中での各々の木ID
4
PCFGの最尤推定

問題
文1に対する確率
文2に対する確率
~
θ  arg max( 2 45 6 7  1 25 6 7 )(3 4 68 )
θ
1   2  3  1
 4  5  6  1
 7  8  1
PCFGの場合この制約を満たすように最大値を
求めなければならない
制約付き極値問題⇒ラグランジュの未定乗数法
5
PCFGの最尤推定
 ラグランジュの未定乗数法
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(θ)  ( 2 45 6 7  1 25 6 7 )(3 4 68 )
 1 (1   2  3  1)  2 ( 4  5   6  1)
 3 ( 7  8  1)
6
PCFGの最尤推定

結果
 θ1=
0.081357
 θ2= 0.459321
 θ3= 0.459321
 θ4= 0.377964
 θ5= 0.207345
 θ6= 0.41469
 θ7= 0.5
 θ8= 0.5
r
Pr
S → NP VP
1.0
VP → VP PP
θ1
VP → V NP
θ2
VP → V
θ3
NP → NP PP
θ4
NP → John
θ5
NP → Mary
θ6
PP → with_a_telescope
1.0
V → sees
θ7
V → runs
θ8
7
EMアルゴリズム
最尤推定をコンピュータで行うためによく
用いられるアルゴリズム
 アルゴリズム

1.
2.
3.
4.
θ := 適当な値
[Eステップ] θを用いて各構文木の確率を計算
[Mステップ]全体の尤度がより高くなる新し
いθを求める
2.に戻る
8
EMアルゴリズム: Eステップ
θ(i): 前回求めたパラメータ
 各構文木の確率

p(t1,1; θ(i ) )   2(i ) 4(i )5(i ) 6(i ) 7(i )
p(t1, 2 ; θ )      
(i )
(i ) (i ) (i ) (i ) (i )
1
2
5
6
7
p(t2,1; θ )     
(i )
(i ) (i ) (i ) (i )
3
4
6
8
9
EMアルゴリズム: Mステップ

書換規則の適用回数
r
Pr
C(r; t11)
C(r; t12)
C(r; t21)
C’(r; t11)
C’(r; t12)
C’(r; t21)
S → NP VP
1.0
1
1
1
?
?
1
VP → VP PP
θ1
0
1
0
?
?
0
VP → V NP
θ2
1
1
0
?
?
0
VP → V
θ3
0
0
1
?
?
1
NP → NP PP
θ4
1
0
1
?
?
1
NP → John
θ5
1
1
0
?
?
0
NP → Mary
θ6
1
p(t11 )1
C ' (r; t111.0
) 1
C (r0; t11 )
PP →
1
p(t11 )  p(t12 )
with_a_telescope
?
?
1
?
?
0
V → sees
θ7
1
1
0
?
?
0
V → runs
θ8
0
0
1
?
?
1
1
10
EMアルゴリズム: Mステップ

各構文木ごとの書換規則の適用回数の期待
値
C ' ( r ; t s ,u ) 
p(t s ,u )
 p(t
s ,v
)
C ( r ; t s ,u )
v

更新パラメータ

( i 1)
A
C ( A   )

 C( A   )

11
EMアルゴリズムの心
構文木
t11
S
構文木
John
S
VP
NP
θ5
t12
θ2
V
θ7
sees
VP
NP
NP
NP
θ6
θ4
VP
θ5
John
PP
V
θ7
sees
Mary
t21
NP
θ6
PP
Mary
with_a_telescope
with_a_telescope
構文木
θ2
θ1
S
・新しいパラメータは単純な数え上げと同様に書換規則の適
NP
VP
用頻度から求まる
θ3
θ4
・ただし、曖昧性のある文に対しては、書換規則の適用頻度
V
NP
PP
θ8
の期待値として数え上げる
θ6
runs
Mary
・構文木の確率は現在のパラメータから求まる
with_a_telescope
12
EMアルゴリズム: まとめ
1.
2.
θ(0) := 適当な値
[Eステップ] θ(i)を用いて各構文木の確率を計
算
p(t )   (r )
( i ) C ( r ;t )
rP
3.
[Mステップ] θ(i+1)を求める

( i 1)
A
C ( A   )

 C( A   )

4.
C ' ( r ; t s ,u ) 
p(t s ,u )
 p(t
s ,v
)
C ( r ; t s ,u )
v
2.に戻る
13
EMアルゴリズム(一般) 1/2
パラメータ: θ
 入力: x
 隠れ状態: z
 データ: S={x(1), x(2), …, x(n)}
 対数尤度: LS(θ)


p (x, z ) 


LS (θ)   S [log pθ (x)]   S log  pθ (x, z )   S log  q(z | x) θ

q
(
z
|
x
)
z
z





pθ (x, z ) 
  S  q(z | x) log
 F ( q , θ)

q ( z | x) 
 z
(Jensenの不等式)
 S [ f (x)] 
1
f (x (i ) )

n i
14
EMアルゴリズム(一般) 2/2

Eステップ
q (t 1) (z | x)  arg max F (q, θ(t ) )  arg min KL(q(z | x) || pθ( t ) (z | x))  pθ( t ) (z | x)
q ( z|x )

θ
q ( z|x )
Mステップ
( t 1)
 arg max F (q
θ
( t 1)

q() 
KL(q || p)  q log

p
(

)




( t 1)
, θ)  arg max S  q (z | x) log pθ (x, z)
θ
z

隠れ状態の確率とパラメータを交互に動かして、
Fを最大化
15
EMアルゴリズム: 局所解
極値を求めているので最適解とは限らない
 良い解が得られるかどうかは初期値に依存
している

色々な初期値を試す
 他の頻度情報を使って初期値を設定

16
EMアルゴリズム:結果
i
θ1
θ2
θ3
θ4
θ5
θ6
θ7
θ8
1
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
2
0.2
0.4
0.4
0.333333
0.222222
0.444444
0.5
0.5
3
0.157895
0.421053
0.421053
0.351351
0.216216
0.432432
0.5
0.5
4
0.13422
0.43289
0.43289
0.360334
0.213222
0.426444
0.5
0.5
5
0.119484
0.440258
0.440258
0.365563
0.211479
0.422958
0.5
0.5
6
0.109661
0.44517
0.44517
0.368908
0.210364
0.420728
0.5
0.5
.......
53
0.081358
0.459321
0.459321
0.377964
0.207345
0.414691
0.5
0.5
54
0.081358
0.459321
0.459321
0.377964
0.207345
0.41469
0.5
0.5
55
0.081358
0.459321
0.459321
0.377964
0.207345
0.41469
0.5
0.5
56
0.081357
0.459321
0.459321
0.377964
0.207345
0.41469
0.5
0.5
57
0.081357
0.459321
0.459321
0.377964
0.207345
0.41469
0.5
0.5
17
r
おまけ: 解析的に求めるのが難
しいPCFGの例
“太郎が花子と映画を褒める”

p(t1) = θ3θ4θ5θ6θ7θ8θ9θ10θ11θ12
p(t2) = θ42θ5θ6θ7θ8θ9θ10θ11θ12
θ3+θ9+θ10+θ11=1, θ4+θ5=1, θ6+θ7+θ8=1, θ12+θ13=1
構文木
S
t1
VP
NP
N
太郎
N
が
N
花子
PP
N
と
映画
VP
NP
VP
NP
PP
S
t2
構文木
PP
V
を
褒める
N
太郎
が
N
花子
S → NP VP
θ1
NP → N PP
θ2
N → N PP N
θ3
VP → NP VP
θ4
VP → V
θ5
PP → が
θ6
PP → を
θ7
PP → と
θ8
N → 太郎
θ9
N → 花子
θ10
N → 映画
θ11
V → 褒める
θ12
V → 見る
θ13
VP
NP
PP
Pr
と
VP
NP
PP
N
PP
映画
を
V
褒める
18
頻度のディスカウンティング

ゼロ頻度問題
ある単語がたまたま訓練コーパス中に出現し
なかったら、その単語に対するパラメータは0
になってしまう
 その単語が出現するテストコーパスの構文木
の確率は0になってしまう!


対策: 出現回数を補正
19
加算法 (additive method)

ラプラス法
頻度に1を加える
C ( w1  wn )  1
p( w1  wn ) 
N V
N: 訓練データ中に出現した単語の総数
V: 出現確率の合計を1にするための定数(n単語列の異なり
総数に等しい)


一般の方法(リッドストーン法とも呼ばれる)


頻度に小さな値(δ)を加える
C ( w1  wn )  
p( w1  wn ) 
N  V
δ=1/2の時、予期尤度推定法(expected likelihood
estimation)、あるいはジェフリース・パークス法を呼
ばれる
20
ヘルドアウト推定法

訓練データを二分割



訓練データ
ヘルドアウトデータ(Chをヘルドアウトデータ中の
出現回数とする)
訓練データでの出現回数をヘルドアウトデー
タでの出現回数で置き換える
Nr 
Cr 
1
w1wn :C ( w1wn )  r
h
C
 (w1  wn )
w1wn :C ( w1wn )  r
Cr
p( w1  wn ) 
(ただし、 r  C ( w1  wn ))
Nr N
21
削除推定法(deleted estimation)

ヘルドアウト推定法のクロスバリデーショ
ン版

訓練データとヘルドアウトデータの役割をさ
らに交換すれば2倍データが増える
22
グッド・チューリング推定法
(Good-Turing estimation)

出現回数の補正値として次のr*を用いる
Nr 

出現確率
1
w1wn :C ( w1wn )  r
N r 1
r*  ( r  1)
Nr
 r*
 N
p ( w1  wn )   N
 1
 N 0 N
C ( w1  wn )  0
C ( w1  wn )  0
23
各種推定法による比較

APコーパス中の2単語組の出現回数の推定
最尤推定
ラプラス法
ヘルドアウト削除推定法
法
グッド・チューリ
ング法
0
0.000137
0.0000270
0.0000374
0.0000270
1
0.000274
0.448
0.396
0.446
2
0.000411
1.25
1.24
1.26
3
0.000548
2.24
2.23
2.24
4
0.000685
3.23
3.22
3.24
5
0.000822
4.21
4.22
4.22
6
0.000959
5.23
5.20
5.19
7
0.001096
6.21
6.21
6.21
8
0.001233
7.21
7.18
7.24
9
0.001370
8.26
8.18
8.25
24
まとめ

PCFGとEMアルゴリズム
EMアルゴリズム
 ディスカウンティング

25

Download Report