数理言語

数理言語情報論第7回
2007年11月19日
数理言語情報学研究室講師二宮崇
1
今日の講義の予定

前回までの復習



PCFG (Probabilistic Context Free Grammar, 確率付文脈自由
文法)
マルコフ文法
論文




Michael Collins (1997) Three generative, lexicalised models
for statistical parsing, In proc. of ACL-EACL, p.16—23
Michael Collins (1999) Head-Driven Statistical Models for
Natural Language Parsing, Ph.D thesis, University of
Pennsylvania
Michael Collins (2003) Head-Driven Statistical Models for
Natural Language Parsing, Computational Linguistics, 29(4),
589--637.
Daniel M. Bikel (2004) Intricacies of Collins’ Parsing Model,
Computational Linguistics, 30, 479—511
2
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 → と NP
θNP1 → と
が
V
NP
NP1
NP
3
構文木の確率
文 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 → と NP
θNP1 → と
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 → 読んだ
NP1
4
NP
書換規則の制約

CFG書換規則をA→ αと表したとき、(Aは
非終端記号、αは非終端記号列)すべての非
終端記号Aに対し、



A
 1.0
とする。
5
構文木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
6
構文木tの確率

C(r; t): CFG<VN, VT, P, σ>の書換規則r∈Pが
構文木t中で使われた回数
p(t )  r
C ( r ;t )
rP
7
最大確率の木を選ぶ

ある文sに対し、CFG<VN, VT, P, σ>を用い
てsを導出できる全ての構文木集合をT(s)と
したとき、
~
t  arg max p(t )
tT ( s )
8
パラメータ推定

教師付学習


正解構文木の集合（＝ツリーバンクと呼ばれ
る）が存在する場合の学習
教師無学習

正解構文木の集合が与えられない状況で、パ
ラメータの推定を行う学習
9
パラメータ推定

単純な数え上げ
教師付学習のもっとも単純な実現
 正解構文木の集合(ツリーバンクと呼ばれる)が
あれば、その中で使われているCFG書換規則
の頻度をカウントすれば各々のパラメータを
簡単に計算できる


最尤推定
教師無学習の最も有名な実現
 正解構文木がない場合や書換規則パラメータ
以外のパラメータが存在する場合に使われる

10
パラメータ推定: 単純な数え上げ

正解構文木の集合（ツリーバンク）
Treebankが与えられた時、
 A 
 C( A   ; t)
C( A   ; t)
 

tTreebank
tTreebank
11
パラメータは条件付き確率
A→αという形のCFGルールに対するパラ
メータθA→α
 パラメータの関数と明示するほうがわかり
やすいけど、その確率は親が生成された時
の条件確率

 θA→α =

p(α | A)
今後は、パラメータの形ではなくて、条件
付き確率の形式で説明していきます
12
PCFG概説
13
ツリーバンクを使った構文解析

S → NP VP
NP → DET N
NP → N
…
文法規則、辞書


人間が文法を直接定義する
のは困難
構文木の実例（ツリーバン
ク）に基づく定量的評価が
必要
文法はツリーバンクから導
出
（ツリーバンク文法）
検証・開発
ツリーバンク
コンピュータ
14
ツリーバンク



実世界の文に対して人手で構文木を付与する
明示的な文法を仮定しない
構造は開発者の言語直感とガイドラインに依存

ガイドラインはあるが、文法で定義されるような「何
が正解か」の客観的基準は存在しない
文
法？
A record date has n’t been set.
15
有名なツリーバンク

構文木や係り受け木を人手で付与したコーパス
（ツリーバンク）の登場








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]
16
Penn Treebank (1/2)
構文木が付与された最初の大規模英語ツ
リーバンク [Marcus et al. 1993]
 様々な分野の英語テキストを収録

Wall Street Journal （新聞）約5万文、100万語
 ATIS （航空券予約の会話）
 Brown （様々な分野のテキスト）
 Switchboard （電話の自由発話）

17
Penn Treebank (2/2)



品詞： NN（普通名詞）, VBZ（三単現動詞）…
構文木： NP（名詞句）, VP（動詞句）…
Function tag, null element: 述語項構造を計算する
ための付加情報（詳細省略）
S
名詞句
VP
NP
限定詞
DT
NN
VP
NN VBZ RB VBN VBN
A record date has n’t been set.
普通名詞
三単現動詞
副詞
過去分詞
18
ツリーバンクから文法を抽出す
る

ツリーバンクの背後にある文法を自動抽出

潜在的な規則性を自動獲得できるはず
文法抽出
文
法？
S
VP
NP
DT
NN
VP
NN VBZ RB VBN VBN
A record date has n’t been set.
ツリーバンク
開発
19
確率CFGの自動抽出(1/2)

ツリーバンクの各分岐をCFG規則だと仮定
して抽出する [Charniak 1996; 1997] c.f. [Sekine1995]
CFG規則
S
VP
NP
DT
NN
VP
NN VBZ RB VBN VBN
S → NP VP
NP → DT NN NN
VP → VBZ RB VP
VP → VBN VBN
A record date has n’t been set.
20
確率CFGの自動抽出(2/2)


ツリーバンクでの出現頻度から確率値を推定
確率値最大の木を探索することで、構文解析の曖
昧性解消ができる
S
VP
NP
DT
NN
VP
NN VBZ RB VBN VBN
S → NP VP
NP → DT NN NN
VP → VBZ RB VP
VP → VBN VBN
0.5
0.03
0.02
0.1
A record date has n’t been set.
21
問題点（１）：文法が大きい
40,000文から約15,000のCFG規則
 CFG規則数が収束しない [Carpenter et al. 1997]
→ 抽象化・一般化しきれていない

16000
14000
12000
10000
8000
6000
4000
文法規則数
2000
0
0
10000
20000
30000
40000
22
問題点（２）：精度が低い

Charniak [1996]: 80%
S
VP
VP
PP
NP
NP
We applied the algorithm to
NN
VBD
IN
NN
We selected the approach to
NP
NP
IE
S
DT
VP
NN
NP
IE
NP
PP
NP
VP → VP PP
NP → NP PP
同じ品詞列でも、単語によって
構文木の形が変わる
23
ツリーバンク文法の改良
(1) 文法が大きい
CFG規則の自動圧縮 [Krotov et al. 1998; 1999]
 CFG規則の確率モデル化 [Magerman 1995; Collins 1997;

Charniak 2000]
(2) 精度が低い

非終端記号の細分化 [Magerman 1995; Collins 1996; 1997;
Johnson 1998; Charniak 2000]
24
CFG規則の確率モデル化

Markov Grammar: CFG規則を確率的に生
成する [Collins 1997; Charniak 2000]
p(NP → DT NN NN | NP)
= p(NN | NP) p(NN | NN, NP) p(DT | NN, NN, NP)
原理的には、全てのCFG規則をもつ PCFG
 Penn Treebank から抽出したそのままの
PCFG より高精度を達成する

25
非終端記号の細分化(1/2)

語彙化: Head percolation table (Magerman
1995) を用いて、非終端記号に head word を
付与 applied
S
Head percolation table
親の記号主辞になる子の記号
VPapplied
VPapplied
NPalgorithm
NPWe
NN
VBD
DT
NN
IN
We applied the algorithm to
PPto
NPIE
S
VP, …
VP
VP, VBD, VBZ, …
NN
NP
NN, …
IE
PP
IN, …
Charniak [1996]: 80% vs. Magerman [1995]: 86%

（参考）語彙化の意味 [Gildea 2001; Bikel 2004]
26
非終端記号の細分化(2/2)


非終端記号だけでは構造を決める情報が少ない
（例）親の非終端記号で細分化 [Johnson 1998]
S
S
NP
V

NP
VP-S
V-VP
NP-VP
主語のNPと目的語のNPが区別できる



NP-S
VP
主語は代名詞が出やすい
目的語は長くなりやすい
その他、様々な周辺情報で細分化 [Charniak 2000; Klein
et al. 2003]
27
マルコフ文法
28
マルコフ文法

CFG規則を確率的に生成する [Collins 1997;
Charniak 2000]
p(NP → DT NN NN | NP)
= p(NN | NP) p(NN | NN, NP) p(DT | NN, NN, NP)
原理的には、全てのCFG規則をもつ PCFG
 Penn Treebank から抽出したそのままの
PCFG より高精度を達成する
 State-of-the-artの性能のパーザーの基本的
な仕組

29
何故マルコフ文法を講義で扱うの
か？

現在の（おおよそ）最高性能のパーザー
(Charniak&Johnson2005)の基礎


Charniak(2000)のパーザーの出力をエントロ
ピー最大化法を用いてreranking
Charniakパーザーもマルコフ文法の一種
モデル
精度(LF)
collins1999
88.19%
charniak2000
89.55%
charniak&johnson2005
91.02%
30
マルコフ過程: シャノンゲーム

Nana eats an ????

次に何が来るのか予測
バイグラム
C (an apple)
P(apple| an) 
C (an)
C (eats an apple)
P(apple| eats an) 
C (eats an)
トライグラム
31
マルコフ過程: 確率モデル

条件付き確率は
p( B | A) 

p( A, B)
p( A)
だから、
p( A, B)  p( A) p( B | A)

つまり、
p( A1 )  p( A1 )
p( A1 , A2 )  p( A1 ) p( A2 | A1 )
p( A1 , A2 , A3 )  p( A1 , A2 ) p( A3 | A1 , A2 )  p( A1 ) p( A2 | A1 ) p( A3 | A1 , A2 )
p( A1 ,, An )  p( A1 ) p( A2 | A1 ) p( A3 | A1 , A2 )  p( An | A1 , An 1 )
32
マルコフ過程: 確率モデル
単語列の確率モデル
p(w1,, wn )  p(w1 ) p(w2 | w1 ) p(w3 | w1, w2 ) p(w4 | w1, w2 , w3 ) p(wn | w1,wn1 )


単語列のNグラムモデル(N-1次のマルコフ過程)

直前のN-1個の単語列の影響のみ受ける
p(wn | w1,wn1 )  p(wn | wn N 1,wn1 )

ユニグラム(0次のマルコフ過程)
p(wn | w1 ,wn1 )  p(wn )

バイグラム(1次のマルコフ過程)
p(wn | w1 ,wn1 )  p(wn | wn1 )

トライグラム(2次のマルコフ過程)
p(wn | w1 ,wn1 )  p(wn | wn2 , wn1 )
33
高次のマルコフ過程の問題

高い次数のマルコフ過程
より精度が高いことが期待できる
 訓練データに出現しなかった単語列に対して
は推定ができない(ゼロ頻度問題、データス
パースネス)
 次数が高いほどデータスパースになってしま
う

34
スムージング

線形補間法(linear interporation)

Nグラムの確率値を低次のMグラム(M<N)の確
率値と線形に補間する方法
~
p(wn | wn N 1,, wn1 )  p(wn | wn N 1 ,, wn1 )  (1   ) p(wn | wn N 2 ,, wn1 )

トライグラムの場合
~
p ( wn | wn2 , wn1 )  1 p( wn | wn2 , wn1 )  2 p( wn | wn1 )  3 p( wn )
ただし
1  2  3  1
35
スムージング

補間係数λを推定

ヘルドアウト補間法(held-out interpolation)
訓練データとヘルドアウトデータにわける
 訓練データでNグラムを学習
 ヘルドアウトデータで補間係数を学習
 補間係数はEMアルゴリズムで最尤推定


トライグラムの場合
1 p( wn | wn 2 , wn 1 )
1 |Dh |
1 

| Dh | n 1 1 p( wn | wn  2 , wn 1 )  2 p( wn | wn 1 )  3 p( wn )
~
2 p( wn | wn 1 )
1 |Dh |
2 

| Dh | n 1 1 p( wn | wn  2 , wn 1 )  2 p( wn | wn 1 )  3 p( wn )
~
3 p( wn )
1 |Dh |
3 

| Dh | n 1 1 p( wn | wn 2 , wn 1 )  2 p( wn | wn 1 )  3 p( wn )
~
36
スムージング

削除補間法(deleted interporation)







データをm個に分割(L1, L2, ..., Lm)
L2,...LmをNグラムの訓練データ、L1を補間係数推定
のためのヘルドアウトデータとしてヘルドアウト推
定法で学習
同様にL1, L3, ..., LmでNグラム、L2で補間係数を学
習
…
これを繰り返して、L1,...Lm-1でNグラム、Lmで補間
係数を学習
以上のようにして求めた補間係数の平均をとる
|Li|=1の時、リーヴィング・ワン・アウト法と呼
ばれる（リーブ・ワン・アウトともいう）
37
COLLINS MODEL 1
38
ツリーバンクの変形

語彙化
Head percolation table
親の記号主辞になる子の記号
TOP
S
S(bought, VBD)
NP(week, NN)
NP(IBM, NNP)
VP, …
VP
VP, VBD, VBZ, …
NP
NN, …
PP
IN, …
VP(bought, VBD)
NNP(IBM, NNP)
JJ(Last, JJ)
VBD(bought, VBD)NP(Lotus, NNP)
NN(week, NN)
Last
IBM
NNP(Lotus, NNP)
bought
week
Lotus
39
語彙化

構文木ノードが非終端記号から(非終端記
号＋主辞語＋主辞品詞)の組になった
pure CFGの構文木ノード: NP
 語彙化 CFGの構文木ノード: NP(IBM, NNP)


書換規則も語彙化されたノードで表現
pure CFG: S → NP NP VP
 語彙化CFG: S(bought, VBD) → NP(week, NN)
NP(IBM, NNP) VP(bought, VBD)

40
語彙化CFGの書換規則

書換規則

M(h) → Ln(ln)...L1(l1)H(h)R1(r1)...Rm(rm)
H: head-child
 M: 親
 L: 主辞の左側の修飾句
 R: 主辞の右側の修飾句
 h: 主辞語と主辞品詞のペア
 li: Liの主辞語と主辞品詞のペア
 ri: Riの主辞語と主辞品詞のペア


書換規則の確率
p( Ln1 (ln1 ),...,L1 (l1 ), H (h), R1 (r1 ),...,Rm1 (rm1 ) | M , h)
41
書換規則のマルコフ化

書換規則の確率
p( Ln 1 (ln 1 ),...,L1 (l1 ), H (h), R1 (r1 ),...,Rm 1 (rm 1 ) | M , h) 
ph ( H | M , h ) 
n 1
 p ( L (l ) | L (l ),...,L
l
i
i
1
1
i 1
(li 1 ), M , h, H ) 
i 1
n 1
 p ( R (r ) | L (l ),...,L
r
i
i
1
1
n 1
(ln 1 ), R1 (r1 ),...,Ri 1 (ri 1 ), M , h, H )
i 1
ただし
Ln 1 (ln 1 )  STOP, Rm 1 (rm 1 )  STOP
42
書換規則のマルコフ化

書換規則の確率

0次のマルコフ過程 (c.f. charniak(2000)は3次の
マルコフ文法)
pl ( Li (li ) | L1 (l1 ),...,Li 1 (li 1 ), M , h, H )  pl ( Li (li ) | M , h, H )
pr ( Ri (ri ) | L1 (l1 ),...,Ln1 (ln1 ), R1 (r1 ),...,Ri 1 (ri 1 ), M , h, H )  pr ( Ri (ri ) | M , h, H )

つまり、、、
p( Ln1 (ln1 ),...,L1 (l1 ), H (h), R1 (r1 ),...,Rm1 (rm1 ) | M , h) 
n 1
n 1
i 1
i 1
ph ( H | M , h)   pl ( Li (li ) | M , h, H )  pr ( Ri (ri ) | M , h, H )
（語彙化と）書換規則の確率の定義が変わるだけで、その他はpure
PCFGと同じであることに注意！
43
書換規則のマルコフ化: 例
S(bought) → NP(week) NP(IBM) VP(bought)
 p(NP(week)NP(IBM)VP(bought)|S(bought)=
ph(VP|S, bought)×
pl(NP(IBM)|S, VP, bought)×
pl(NP(week)|S, VP, bought)×
pl(STOP|S, VP, bought)×
pr(STOP|S, VP, bought)

44
Distance関数の追加
 マルコフ化の際にDistance関数を追加
pl ( Li (li ) | L1 (l1 ),...,Li 1 (li 1 ), M , h, H )  pl ( Li (li ) | M , h, H , l (i 1))
pr ( Ri (ri ) | L1 (l1 ),...,Ln1 (ln1 ), R1 (r1 ),...,Ri 1 (ri 1 ), M , h, H ) 
pr ( Ri (ri ) | M , h, H ,  r (i  1))

書換規則の確率
p( Ln 1 (ln 1 ),...,L1 (l1 ), H (h), R1 (r1 ),...,Rm1 (rm1 ) | M , h) 
n 1
ph ( H | M , h)   pl ( Li (li ) | M , h, H ,  l (i  1)) 
i 1
n 1
 p ( R (r ) | M , h, H , 
r
i 1
i
i
r
(i  1))
45
Distance関数の中身

Distance関数が指す部分木
M(h)
L1(l1)
H(h)
R1(r1)
...
Ri-1(ri-1) Ri(ri)
...
Rm(rm)
δ(i-1)はこ
の木のこと
46
Distance関数の中身
求めようとする構文木ノードの条件付き確
率p(Ri(ri)|...)の一つ手前のノードRi-1(ri-1)の
下に広がる部分構文木が対象
 Distance関数の返す値

R1かL1である？
 部分構文木の下に動詞を含むか否か？

47
COLLINS MODEL 2
48
ツリーバンクの変形

語彙化+補語(句)/修飾語(句)の区別
TOP
S(bought, VBD)
NP-C(IBM, NNP)
VP(bought, VBD)
NP(week, NN)
NNP(IBM, NNP)
JJ(Last, JJ) NN(week, NN)
NP-C(Lotus, NNP)
VB(bought, VBD)
IBM
NNP(Lotus, NNP)
Last
week
bought
Lotus
49
ツリーバンクの変形

補語(complements)/修飾語(adjuncts)の区別

次の条件を満たす非終端記号は全て補語
(complements)

非終端記号は次のうちのいずれかである
(1)
(2)
(3)

非終端記号は次のうちのいずれかのsemantic tagを
もっていてはいけない


親がSであるNP, SBAR, S
親がVPであるNP, SBAR, S
親がSBARであるS
ADV, VOC, BNF, DIR, EXT, LOC, NMR, TMP, CLR or PRP
それに加えて、前置詞句の主辞の後にすぐに続
く兄弟ノードは補語である
50
下位範疇化フレーム: 問題


補語や修飾語の区別をつけても、文法的に誤った
構文と正しい構文の確率に差がつかない
(例1)
不正解
S
NP-C
VP
NP-C
NP-C
NP
was
Dreyfus
正解
S
VP
NP
was
ADJP
the best fund
Dreyfus
low
ADJP
the best fund
low
51
下位範疇化フレーム: 問題


補語や修飾語の区別をつけても、文法的に誤った
構文と正しい構文の確率に差がつかない
(例2)
S
不正解
S
正解
VP
VP
NP-C
NP-C
NP-C
was
NP-C
VP-C
was
NP
VP
The issue
The issue
a bill
NP-C
NP-C
a bill
funding
funding
Congress
Congress
52
下位範疇化フレーム

解決策

下位範疇化フレーム(subcat frame)を導入
 補語として取る非終端記号の多重集合(multi
set)
 HPSGで出てきたVALの下のSUBJやCOMPSやSPR
53
書換規則の確率モデル

LC(左側の下位範疇化フレーム)とRC(右側の下
位範疇化フレーム)の導入
p ( Ln 1 (ln 1 ),...,L1 (l1 ), H (h), R1 ( r1 ),...,Rm 1 (rm 1 ) | M , h) 
ph ( H | M , h)  plc ( LC | M , H , h)  prc ( RC | M , H , h) 
n 1
 p ( L (l ) | M , h, H ,  (i  1), LC ) 
l
i
i
l
i 1
n 1
 p ( R ( r ) | M , h, H , 
r
i
i
r
(i  1), RC)
i 1

例


RC={NP-C, NP-C}, LC={NP-C}
plc({NP-C, NP-C}|S, VP, bouht}やprc({NP-C, VPC}|VP, VB, was)は低い
54
下位範疇化フレーム
下位範疇化フレームは補語をひとつとる度
に消費される（減っていく）
 下位範疇化フレームに要素が残っている間
はSTOPに対する確率は0
 下位範疇化フレームに要素が無い場合は、
補語をとる確率は0

55
下位範疇化フレーム: 例

S(bought) → NP(week) NP-C(IBM) VP(bought)の
確率
ph(VP|S, bought)×
plc({NP-C}|S, VP, bought)×
prc({}|S, VP, bought)×
pl(NP-C(IBM)|S, VP, bought, {NP-C})×
pl(NP(week)|S, VP, bought, {})×
pl(STOP|S, VP, bought, {})×
pr(STOP|S, VP, bought, {})
56
Collins Model 3

痕跡(Trace)とwh-移動
ex.1 The store (SBAR which TRACE bought
Brooks Brothers)
 ex.2 The store (SBAR which Marks bought
TRACE)
 ex.3 The store (SBAR which Marks bought
Brooks Brothers from TRACE)

57
Collins Model 3

例
NP(store)
SBAR(that)(+gap)
boughtがTRACE
をとった後の下位
範疇化フレームは
空: {}
NP(store)
WHNP(that)
S(bought)(+gap)
The store
WDT
NP-C(Marks)
VP(bought)(+gap)
that
Marks
boughtの下位範
疇化フレーム:
{NP-C}
VBD
bought
TRACE
NP(week)
last week
58
主辞品詞

スムージング
主辞語
plとpr
pl ( Li ( lti , lwi ) | M , h, H ,  l (i  1), LC ) 
pl1 ( Li (lti ) | M , h, H ,  l (i  1), LC ) 
pl 2 (lwi | M , h, H ,  l (i  1), LC )
pr ( Ri ( rti , rwi ) | M , h, H ,  r (i  1), RC) 
pr ( Ri (rti ) | M , h, H ,  r (i  1), RC) 
pr (rwi | M , h, H ,  r (i  1), RC)

削除補間法(deleted interporation)
back-off
level
ph(H|...)
plc(LC|...)
prc(RC|...)
pl1(Li(lti)|...)
pr1(Ri(rti)|...)
pl2(lwi|...)
pr2(rwi|...)
1
M,w,t
M,H,w,t
M,H,w,t,δ,LC
Li,lti,M,H,w,t,δ,LC
2
M,t
M,H,t
M,H,t,δ,LC
Li,lti,M,H,t,δ,LC
3
M
M,H
M,H,δ,LC
Li,lti
4
-
-
-
lti
59
性能評価

PARSEVALという基準で評価




構文木ノードの位置（左端の位置と右端の位置）と非終端
記号ラベル
Labeled Precision (LP)=(パーザーが正解したラベル
数)/(パーザーが出力したラベル数)
Labeled Recall (LR) = (パーザーが正解したラベル数)/(ツ
リーバンク中のラベル数)
Labeled F-Score(F1-Score) = labeled precisionとlabeled
recallの調和平均=2*LP*LR/(LP+LR)
model
LP
LR
LF
Magerman95
84.3%
84.0%
84.1%
Collins96
85.7%
85.3%
85.5%
Model 1
87.6%
86.8%
87.2%
Model 2
88.1%
87.5%
87.8%
Model 3
88.1%
87.5%
87.8%
60
まとめ


PCFG概要
マルコフ文法







マルコフ過程
スムージング
Collins Model 1
Collins Model 2
Collins Model 3
次回は、11/26(月) 16:30～構文解析(decoding)
講義資料

http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH19w/
61

Download Report