数理言語

数理言語情報論第6回
2009年11月11日
数理言語情報学研究室講師二宮崇
1
今日の講義の予定

前回までの復習



CFG (Context Free Grammar, 文脈自由文法)
PCFG (Probabilistic Context Free Grammar, 確率付
文脈自由文法)
教科書



北研二(著) 辻井潤一(編) 言語と計算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
簡単なCFGの例
CFG: 構文木
S → SUBJ VP1
S
S → SUBJ V
SUBJ → NP が
VP1 → OBJ1 V
SUBJ
OBJ1 → NP を
NP → S NP
V → 送った
V → 読んだ
NP → 香織
NP
NP → プレゼント
NP → 香織 NP1
NP → 恵 NP1
NP1 → と NP
OBJ1
が
V
を
NP
香織
S
NP → 恵
NP → 電子メール
VP1
SUBJ
NP
恵
が
NP
V
読んだ
電子メール
送った
3
PCFG
CFGの書換規則の適
用確率をパラメータ
化した文法
 構文木の確率は、適
用された書換規則の
パラメータの積
 各パラメータは
0.0≦θ≦1.0

簡単なCFGの例
パラメータ
S → SUBJ VP1
θS → SUBJ
VP1
S → SUBJ V
θS → SUBJ
V
SUBJ → NP が
θSUBJ → NP
VP1 → OBJ1 V
θVP1 → OBJ1
OBJ1 → NP を
θOBJ1 → NP を
NP → S NP
θNP → S
V → 送った
θV → 送った
V → 読んだ
θV → 読んだ
NP → 香織
θNP → 香織
NP → 恵
θNP → 恵
NP → 電子メール
θNP → 電子メール
NP → プレゼント
θNP → プレゼント
NP → 香織 NP1
θNP → 香織 NP1
NP → 恵 NP1
θNP → 恵
NP1
NP1 → と NP
θNP1 → と
NP
が
V
NP
4
構文木の確率
文 s = “香織が恵が送った電子メールを読んだ”
S
構文木 t
VP1
SUBJ
簡単なCFGの例
パラメータ
S → SUBJ VP1
θS → SUBJ
VP1
S → SUBJ V
θS → SUBJ
V
SUBJ → NP が
θSUBJ → NP
VP1 → OBJ1 V
θVP1 → OBJ1
OBJ1 → NP を
θOBJ1 → NP を
NP → S NP
θNP → S
V → 送った
θV → 送った
V → 読んだ
θV → 読んだ
NP → 香織
θNP → 香織
NP → 恵
θNP → 恵
NP → 電子メール
θNP → 電子メール
NP → プレゼント
θNP → プレゼント
NP → 香織 NP1
θNP → 香織 NP1
NP → 恵 NP1
θNP → 恵
NP1
NP1 → と NP
θNP1 → と
NP
NP
OBJ1
が
香織
NP
が
V
S
SUBJ
NP
NP
が
V
を
読んだ
NP
V
電子メール
送った
恵
P(t) = θS → SUBJ VP1 × θSUBJ → NP が × θNP → 香織 ×
θVP1 → OBJ1 V × θOBJ1 → NP を × θNP → S NP ×
θS → SUBJ V × θSUBJ → NP が × θNP → 恵×
θV → 送った× θNP → 電子メール × θV → 読んだ
5
書換規則の制約

Sからの生成



Sからの生成は2通りしかな
いので、


S→SUBJ VP1を使う場合
S→SUBJ Vを使う場合
θS → SUBJ
VP1+θS → SUBJ V = 1.0
同様にNPも

θNP → S NP + θNP → 香織 + θNP → 恵
+ θNP → 電子メール + θNP → プレゼント
+θNP → 香織 NP1 + θNP → 恵 NP1 =
1.0
簡単なCFGの例
パラメータ
S → SUBJ VP1
θS → SUBJ
VP1
S → SUBJ V
θS → SUBJ
V
SUBJ → NP が
θSUBJ → NP
VP1 → OBJ1 V
θVP1 → OBJ1
OBJ1 → NP を
θOBJ1 → NP を
NP → S NP
θNP → S
V → 送った
θV → 送った
V → 読んだ
θV → 読んだ
NP → 香織
θNP → 香織
NP → 恵
θNP → 恵
NP → 電子メール
θNP → 電子メール
NP → プレゼント
θNP → プレゼント
NP → 香織 NP1
θNP → 香織 NP1
NP → 恵 NP1
θNP → 恵
NP1
NP1 → と NP
θNP1 → と
NP
が
V
NP
6
書換規則の制約

CFG書換規則をA→ αと表したとき、(Aは
非終端記号、αは非終端記号列)すべての非
終端記号Aに対し、



A
 1.0
とする。
7
PCFGで行うべきポイント

構文木tの確率を計算する
最も確率の高いtを選択する
 文sの生成確率を計算する


PCFGのパラメータθを求める
8
構文木tの確率を計算
S
構文木 t
CFG G
パラメータ
S → NP VP
θS → NP
NP → N PP
θNP → N
N → N PP N
θN → N
VP → NP VP
θVP → NP
VP → V
θVP → V
0.7
PP → が
θPP → が
0.5
PP → を
θPP → を
0.3
PP → と
θPP → と
0.2
N → 太郎
θN → 太郎
0.3
N → 花子
θN → 花子
0.2
N → 映画
θN → 映画
0.4
V → 褒める
θV → 褒める
0.3
V → 見る
θV → 見る
0.7
値
VP
1.0
PP
1.0
PP N
0.1
VP
0.3
VP
NP
N
PP
VP
NP
V
太郎
が
PP
N
褒める
N
花子
PP
N
と
映画
を
p(t) = θS → NP VP × θNP → N PP × θN → 太郎 ×
θPP → が × θVP → NP VP × θNP → N PP ×
θN → N PP N × θN → 花子 × θPP → と×
θN → 映画 × θPP → を × θVP → V × θV → 褒める
= 1.0×1.0×0.3×0.5×0.3×1.0×
0.1×0.2×0.2×0.4×0.3×0.7×0.3
= 0.000004536
9
構文木tの確率

C(r; t): CFG<VN, VT, P, σ>の書換規則r∈Pが
構文木t中で使われた回数
p(t )  r
C ( r ;t )
rP
10
構文木集合Tの中から最も確率の高い木
を選ぶ)

”太郎が花子と映画を褒める”に対する構文木は次の二種類しかない
構文木 t1
構文木 t2
S
VP
NP
N
太郎
N
が
N
花子
PP
N
と
映画
VP
NP
VP
NP
PP
S
PP
V
を
褒める
N
太郎
NP
PP
が
N
花子
VP
と
VP
NP
PP
N
PP
V
褒める
映画
を
p(t1) = θS → NP VP × θNP → N PP2 × θN → 太郎 × p(t2) = θS → NP VP × θNP → N PP3 × θN → 太郎 ×
θPP → が × θVP → NP VP × θN → N PP N ×
θPP → が × θVP → NP VP2 × θN → 花子 ×
θN → 花子 × θPP → と× θN → 映画 ×
θPP → と × θN → 映画 × θPP → を ×
θPP → を × θVP → V × θV → 褒める
θVP → V × θV → 褒める
= 1.0×1.02×0.3×0.5×0.3×0.1×0.2×0.2× = 1.0×1.03×0.3×0.5×0.32×0.2×0.2×
0.4×0.3×0.7×0.3
0.3×0.7×0.3
11
= 0.000004536
= 0.000013608
最大確率の木を選ぶ

ある文sに対し、CFG<VN, VT, P, σ>を用い
てsを導出できる全ての構文木集合をT(s)と
したとき、
~
t  arg max p(t )
tT ( s )
12
文の生成確率

ある文sに対し、sを導出する全ての構文木
集合をT(s)としたとき、
p( s ) 
 p(t )
0.0  p(s)  1.0
tT ( s )

PCFGによって生成されうる全ての構文木
集合をTとしたとき、
 p(t )  1.0
tT
13
パラメータ推定

教師付学習


正解構文木の集合（＝ツリーバンクと呼ばれ
る）が存在する場合の学習
教師無学習

正解構文木の集合が与えられない状況で、パ
ラメータの推定を行う学習
14
パラメータ推定

単純な数え上げ
教師付学習のもっとも単純な実現
 正解構文木の集合(ツリーバンクと呼ばれる)が
あれば、その中で使われているCFG書換規則
の頻度をカウントすれば各々のパラメータを
簡単に計算できる


最尤推定
教師無学習の最も有名な実現
 正解構文木がない場合や書換規則パラメータ
以外のパラメータが存在する場合に使われる

15
パラメータ推定: 単純な数え上げ

正解構文木の集合（ツリーバンク）
Treebankが与えられた時、
 A 
 C( A   ; t)
C( A   ; t)
 

tTreebank
tTreebank
16
有名なツリーバンク

構文木や係り受け木を人手で付与したコーパス
（ツリーバンク）の登場








Penn Treebank [Marcus et al. 1993]
SUSANNE [Sampson 1995]
TIGER Treebank [Brants et al. 2002]
Prague Dependency Treebank [Hajic 1998]
Verbmobil [Hinrichs et al. 2000]
EDRコーパス [EDR 1995]
京都大学テキストコーパス [黒橋ら 1997]
日本語話し言葉コーパス [前川ら 2000]
17
パラメータ推定: 最尤推定
文の集合を観測したとき、その文の集合が
そこに出現したのは、その文の集合が最も
確率が高かったから、と考えるやり方
 コインの例：表がでる確率θが未知のコイ
ンがある。100回投げたところ、62回表が
でた。すると、その確率はθ62(1－θ)38とな
る。この確率はθ=0.62で最大となるので、θ
は0.62であったのだろう、と考えるのが最
尤推定の考え方である。

18
最尤推定

最尤推定

観測値 x1,...,xn が与えられた時、それぞれが独
立に出現したと考えると、その確率はパラ
メータθの関数になる
n
p( x1 ,..., xn )   p( xi ; )  l ( )
i 1
このl(θ)を尤度(likelihood)もしくは尤度関数
(likelihood function)と呼ぶ
 尤度関数を最大化するθを求める

~
  arg maxl ( )

19
最尤推定

最大を求めるために尤度関数の極値を求め
る



l ( )  0
コインの例を解析的に解いてみよう

l(θ) = θ62(1－θ)38
20
最尤推定

対数尤度(log likelihood)を使うと計算が楽
になる
~
  arg maxl ( )  arg maxlogl ( )



コインの例で解いてみよう

log l(θ) = log( θ62(1－θ)38 )
21
最尤推定

正規分布の最尤推定
正規分布N(μ, σ2)から抽出された標本をx1,...,xn
とする
n
 尤度
 ( xi   ) 2 
1
2

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
22
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
23
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
24
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の場合この制約を満たすように最大値を求
めなければならない
制約付き極値問題⇒ラグランジュの未定乗数法
25
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)
26
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
27
EMアルゴリズム
最尤推定をコンピュータで行うためによく
用いられるアルゴリズム
 アルゴリズム

1.
2.
3.
4.
θ := 適当な値
[Eステップ] θを用いて各構文木の確率を計算
[Mステップ]全体の尤度がより高くなる新し
いθを求める
2.に戻る
28
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
29
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
30
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   )

31
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
32
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.に戻る
33
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
34
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を
最大化
35
EMアルゴリズム: 局所解
極値を求めているので最適解とは限らない
 良い解が得られるかどうかは初期値に依存
している

色々な初期値を試す
 他の頻度情報を使って初期値を設定

36
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
37
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
褒める
38
頻度のディスカウンティング

ゼロ頻度問題
ある単語がたまたま訓練コーパス中に出現し
なかったら、その単語に対するパラメータは0
になってしまう
 その単語が出現するテストコーパスの構文木
の確率は0になってしまう!


対策: 出現回数を補正
39
加算法 (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)、あるいはジェフリース・パークス法を呼
ばれる
40
ヘルドアウト推定法

訓練データを二分割



訓練データ
ヘルドアウトデータ(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
41
削除推定法(deleted estimation)

ヘルドアウト推定法のクロスバリデーショ
ン版

訓練データとヘルドアウトデータの役割をさ
らに交換すれば2倍データが増える
42
グッド・チューリング推定法
(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
43
各種推定法による比較

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
44
まとめ

PCFG
構文木の確率
 曖昧性のある文に対し、最大確率の木を選ぶ
 パラメータの推定

 単純な数え上げ
 最尤推定とEMアルゴリズム

ディスカウンティング
次回は、11/18(水) 16:30～マルコフ文法
 講義資料


http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH21w/cl/
45

Download Report