確率木接合文法に基づく漸進的構文解析
加藤 芳秀†

松原 茂樹††

稲垣 康善†††† 名古屋大学大学院国際開発研究科〒 464-8601 名古屋市千種区不老町†† 名古屋大学情報連携基盤センター〒 464-8601 名古屋市千種区不老町††† 愛知県立大学情報科学部〒 480-1198 愛知県愛知郡長久手町
E-Mail: yosihide@gsid.nagoya-u.ac.jp

概要

本稿では，漸進的構文解析により生成された部分構文木の妥当性を逐次的に評価する手法を提案す

る．本手法は，単語が入力されるたびに，それ以前の段階で生成されたすべての部分構文木についてその妥当性を確率木接合文法に基づき評価する．評価値は，単語入力のたびに更新され，それが閾値を超えた段階で，その部分構文木を出力する．構文解析実験により，提案手法が，高カバー率，高精度な漸進的構
文解析の実現に有効であることを確認した．

Incremental Parsing based on
Probabilistic Tree Adjoining Grammar
Yoshihide Kato†

Shigeki Matsubara††

Yasuyoshi Inagaki†††† Graduate School of International Development, Nagoya University†† Information Technology Center, Nagoya University

Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japan††† Faculty of Information Science and Technology, Aichi Prefectural University

1522-3 Ibaragabasama, Kumabari, Nagakute-cho, Aichi-gun, 480-1198 Japan
E-Mail: yosihide@gsid.nagoya-u.ac.jp
Abstract This paper proposes a method for evaluating the validity of partial parse trees constructed inincremental parsing. Our method is based on probabilistic tree adjoining grammar, and it incrementally
evaluates the validity for each partial parse tree on a word-by-word basis. In our method, incremental
parser returns partial parse trees at the point where the validity for the partial parse tree becomes greaterthan a threshold. Experimental results demonstrate that incremental evaluation of partial parse trees
realizes a broad-coverage accurate incremental parser.

1

はじめに

漸進的構文解析とは，自然言語文をその単語の出現順序に従って順次解析し，文の入力途中の段階でその構文構造を捉える枠組である．同時通訳システ
ムやリアルタイム字幕生成システムなどの実時間音
声言語処理システムの実現に必要不可欠な要素技術の一つである [1, 2, 3]．
これまでに，漸進的構文解析手法がいくつか提案されている [4, 5, 6, 7, 8]．これらの手法では，単語が入力されるたびに，それまでに入力された文の断片に対する部分構文木の候補を生成できる．しかし，漸進的構文解析に特有な局所的曖昧性の問題をこれ
らの手法は全く扱っていない．局所的曖昧性とは，文の断片に対する構文構造の曖昧性であり，その断片
Initial trees:
α1 S
α2 VP
α3
α4 VP
VP
の情報のみでは解消できないが，後続の入力の情報がある程度わかれば解消できる曖昧性のことである．
VB
NP
VP
VB NP
VB NP ADJP
漸進的構文解析を実時間音声言語処理システムの一
found
found
PRP
found
つの言語処理モジュールとして組み込んだ場合，局I
所的曖昧性の解消は，システム全体の性能に影響を
α5 NP
α7 NN α8 NP
α6 NP
α9 NP
与えるため重要である．
dime
DT NN
DT JJ NNDT NN DT JJ NN
一方，局所的曖昧性の問題に対して，Marcus は
a
a
the
the
単語を数単語先読みすることにより，妥当な部分構
文木を決定的に生成する手法を提案している [9]．まα10 NNた，Kato らは，漸進的構文解析の出力タイミングを
wood
遅らせ，生成された部分構文木の候補の中から，妥Auxiliary trees:
当な部分構文木が決定されてからそれを出力する手
VP
β1 NP
β2
法を提案している [10]．しかしながら，これらの手
NP* PPVP* PP法によりカバー率の高い漸進的構文解析が実現でき
IN
NP
IN
NP
るとは言い難い．Marcus の手法では，先読み規則をin
in
人手で作成しているが，カバー率の高い規則を得ることができるかどうかは明らかではない．Kato らの手法は，文脈自由文法をベースに可能なすべての部
分構文木を生成することを前提としているため，大図 1: 漸進的構文解析のための木接合文法
規模な文法を扱うことは難しい．
そこで本稿では，部分構文木の妥当性を逐次的に 2.1 漸進的構文解析のための木接合文法
評価する漸進的構文解析手法を提案する．提案手法
木接合文法は初期木 (initial tree) と補助木 (auxilでは，確率木接合文法を大規模構文木コーパスから抽出し，これをベースに漸進的構文解析を実現する． iary tree) の集合からなる．初期木と補助木をあわせまた，Kato らの手法のように，文法上可能なすべて て基本木 (elementary tree) と呼ぶ．補助木には，足の部分構文木を生成するのではなく，ビームサーチ (foot) と呼ばれる特別な節点があり，*でマークされにより確率の低い部分構文木を枝刈りする．これに ている．漸進的な解析処理を実現するために，提案
より，カバー率の高い漸進的構文解析の実現が期待 手法では，基本木の形を次のように制限する．まず，できる．局所的曖昧性を解消するために，本手法で 最左展開木を定義する．
は，単語が入力されるたびに，それ以前の段階で生 定義 1 (最左展開木) 最左展開木は，次の 1. か 2. の成されたすべての部分構文木についてその妥当性を いずれかである．
評価する．評価値は，単語が入力されるたびに，そ1. t を終端記号，X を非終端記号とする．このとの単語の情報を反映した値に更新され，それがあらき，[t]X は最左展開木である．
かじめ定めた閾値を超えた段階で，その部分構文木を出力する．これにより部分構文木の出力タイミン
2. σ を最左展開木とし，X, X1 , . . ., Xk を非終端
グは，単語の入力タイミングに対して遅れるものの，記号とする．このとき，[σX1 . . . Xk ]X は最左展
局所的曖昧性が解消できるため，精度の高い漸進的開木である．
2
構文解析の実現が期待できる．
本稿の構成は以下の通りである．次の 2 節では，確 基本木の形を次のように制限する．
率木接合文法に基づく漸進的構文解析を提案する．3
節では，漸進的構文解析において生成される部分構
文木の妥当性について論じる．4 節では，部分構文木の妥当性を漸進的に評価する手法を提案する．5 節
では，提案手法の実験による評価について報告する．

• すべての初期木は，最左展開木である．
• すべての補助木は，次の形をした木である．ただし，X, X1 , . . ., Xk を非終端記号とし，σ を
最左展開木とする．
[X ∗ σX1 . . . Xk ]X

図 1 に上記の制限を満たした木接合文法の例を示す．
これらの基本木は，代入 (substitution)，及び接合(adjunction) と呼ばれる 2 つの操作により結合され，解析
部分構文木 (partial pase tree) を構成する．以下で
本節では，木接合文法 (tree adjoining grammar, は，非終端記号をラベルにもつ節点を非終端節点と，
TAG) [11] に基づく漸進的構文解析手法を提案する． 非終端記号をラベルにもつ葉を非終端葉と呼ぶ．

2

木接合文法に基づく漸進的構文表 1: “I found a dime in the wood.” に対する漸進的構文解析の処理過程
word
I
found

a

dime
in
the

wood

#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

partial parse trees[[[I]prp ]np vp]s[[[I]prp ]np [[f ound]vb np]vp ]s[[[I]prp ]np [[f ound]vb np adjp]vp ]s[[[I]prp ]np [[f ound]vb ]vp ]s[[[I]prp ]np [[f ound]vb [[a]dt nn]np ]vp ]s[[[I]prp ]np [[f ound]vb [[a]dt jj nn]np ]vp ]s[[[I]prp ]np [[f ound]vb [[a]dt nn]np adjp]vp ]s[[[I]prp ]np [[f ound]vb [[a]dt jj nn]np adjp]vp ]s[[[I]prp ]np [[f ound]vb [[a]dt [dime]nn ]np ]vp ]s[[[I]prp ]np [[f ound]vb [[a]dt [dime]nn ]np adjp]vp ]s[[[I]prp ]np [[[f ound]vb [[a]dt [dime]nn ]np ]vp [[in]in np]pp ]vp ]s[[[I]prp ]np [[f ound]vb [[[a]dt [dime]nn ]np [[in]in np]pp ]np ]vp ]s[[[I]prp ]np [[[f ound]vb [[a]dt [dime]nn ]np ]vp [[in]in [[the]dt nn]np ]pp ]vp ]s[[[I]prp ]np [[[f ound]vb [[a]dt [dime]nn ]np ]vp [[in]in [[the]dt jj nn]np ]pp ]vp ]s[[[I]prp ]np [[f ound]vb [[[a]dt [dime]nn ]np [[in]in [[the]dt nn]np ]pp ]np ]vp ]s[[[I]prp ]np [[f ound]vb [[[a]dt [dime]nn ]np [[in]in [[the]dt jj nn]np ]pp ]np ]vp ]s[[[I]prp ]np [[[f ound]vb [[a]dt [dime]nn ]np ]vp [[in]in [[the]dt [wood]nn ]np ]pp ]vp ]s[[[I]prp ]np [[f ound]vb [[[a]dt [dime]nn ]np [[in]in [[the]dt [wood]nn ]np ]pp ]np ]vp ]s

代入 σ を部分構文木とし，その最も左に位置する非終端葉を η とする．η のラベルを X とする．このとき，η を，根のラベルが X である初期木 αで置き換える．α を代入する操作を sα と書き，
σ に sα を適用した結果を sα (σ) と書く．
接合 木 σ を非終端節点 η で分割し，その節点と同じラベルを根にもつ補助木 β を挿入する．β を接合する操作を aβ と書き，σ に aβ を適用した
結果を aβ (σ) と書く．

a)

(Xp=X1)Xp

Xp

X1* X2 X3 ... Xk...

X1 X2 X3 ... Xk
...
b)

Xp
X1 X2

c)

(Xp≠X1)X3 ... Xk
...

X

Xp

Xp
X1 X2 X3 ... Xk
...

X

X2

p
p
句構造規則に基づく漸進的構文解析では，文法が左...
X1 X2 X3 ... Xk
X1 X2 X3Xk
X3 ... Xk
再帰規則を含む場合，解析が無限ループに陥ってし...
まうが，接合操作を用いて左再帰構造を処理することにより，この問題を回避できる [12]．
提案手法では，i 番目の単語 wi が入力されたとき，
図 2: 構文木分割による基本木抽出
w1 · · · wi−1 に対する部分構文木に対して，wi に対する基本木を代入・接合することにより，w1 · · · wi−1 wiに対する部分構文木を生成する．
2.2 構文木コーパスからの文法抽出例として，図 1 の木接合文法を用いて，次の文を
カバー率の高い木接合文法を構築する方法の一つ
漸進的構文解析する場合を考える．
として，文献 [13, 14, 15] の手法のように，構文木
I found a dime in the wood.
(1)
コーパス中の構文木を分割し，基本木を抽出するこ
表 1 は文 (1) に対する部分構文木生成の過程を示し とが考えられる．本節では，2.1 節で述べたような基ている．単語 “found” が入力されたとき，“I” に対 本木を構文木コーパスから抽出する方法を提案する．
本手法では，次のようにして，コーパス中の構文
する部分構文木#2 に対して図 1 の初期木 α2 , α3 , α4木を分割する（図2 参照．
）．
を代入することにより部分構文木#3, #4 および #5がそれぞれ生成される．単語 “in” が入力されたとき，
a) 左端に位置する節点 η1 がその親 ηp と同じ記号‘I found a dime” に対する部分構文木#10 に対してをラベルにもつならば，η1 と ηp で構文木を分β1 と β2 を接合することにより，部分構文木#12 と割し，上側の木と下側の木を結合する．中間の#13 が生成される．この例が示すように，木接合文
木の η1 は足節点である．
法に基づき，単語入力ごとに，それまでに入力された文の断片に対する部分構文木の候補を生成する漸b) 左から 2 番目に位置する節点 η2 に対して，そ進的構文解析が実現できる．
の左の節点 η1 と，その親 ηp が同じ記号をラベ...

ルに持たないならば，η2 で構文木を分割する．

c) 左から 3 番目以降に位置する節点で構文木を分割する．
例えば，図 1 の初期木 α1 , α2 , α5 , α7 , α8 , α10 及び，補助木 β2 が表 1 の構文木#18 から抽出される．
提案する基本木抽出手法は，文献 [13, 14, 15] の手法と似ているが，分割する節点の選び方に違いがある．文献 [13, 14, 15] の手法では，統語範疇の主辞情報を用いて，主辞以外の節点で構文木を分割するのに対して，提案手法では，左再帰節点と左端に位置
しない節点で構文木を分割する．本提案手法により抽出された基本木は，単語単位で左から順に結合することができるのに対して，従来の手法で得られる
基本木は，このような性質を持っていない1 .

2.3

...
...
X1 ... Xss

Xg

...

Xp
Xs

...

X ... Xkα’

図 3: テンプレートの代入確率

P (sα0 | σ, η) = P (sα0 | X, Xp , Xg , Xs , Xss )(6)

データスパースネスの問題に対処するため，低次の言語モデルを用いて次のようにスムージングする．

確率木接合文法P (sα0 | X, Xp , Xg , Xs , Xss )本節では確率木接合文法について述べる．本手法= λ1 PM L (sα0 | X, Xp , Xg , Xs , Xss )では，基本木を部分構文木に代入・接合する事象に確+λ2 PM L (sα0 | X, Xp , Xs , Xss )率を割り当てる．この確率をコーパス中のデータか+(1 − λ1 − λ2 )PM L (sα0 | X, Xp , Xs )ら直接推定できればよいが，データスパースネスの問題が生じ，現実的でないので，本手法では，Chiangの手法 [14] のように，基本木が生成される過程を２ ここで，PM L はコーパスから最尤推定により計算さつのステップにわける，すなわち，まず，基本木か れた確率を表す．λ1 と λ2 は補間係数である．
ら単語を除いたテンプレート (template) を生成し， テンプレート β 0 を部分構文木 σ の節点 η に接合
次に単語を生成する．代入操作 sα（接合操作 aβ ）が する確率は，代入確率と同じように定義する．
部分構文木 σ の節点 η に適用される確率を，次のように分解する．
P (aβ 0 | σ, η) = PM L (aβ 0 | X, Xp , Xg , Xs )(7)
P (sα | σ, η) = P (sα0 | σ, η)P (wα | sα0 , σ, η)(2)P (aβ | σ, η) = P (aβ 0 | σ, η)P (wβ | aβ 0 , σ, η)(3)α0 は α のテンプレート，wα は α の単語である．βについても同様である．ここで，単語が生成される確率がその品詞のみに依存すると仮定する．すなわ
ち，単語の生成確率を次のように定義する．
P (wα | sα0 , σ, η) = P (wα | tα )(4)P (wβ | aβ 0 , σ, η) = P (wβ | tβ )(5)tα , tβ は，それぞれ，単語 wα , wβ の品詞である．
次にテンプレートを代入，接合する確率について考える．本手法では，テンプレート α0 を部分構文木
σ の節点 η に代入する確率が，η のラベル X ，η の親のラベル Xp ，η の祖父のラベル Xg ，η の左隣の節点のラベル Xs ，η の 2 つ左の節点のラベル Xss に依存すると仮定する（図 3 参照）．テンプレートの代入確率は次のようになる．

接合操作が節点 η に適用されない確率は次のように計算する．

P (nilX | X, Xp , Xg , Xs )X
= 1−
P (aβ 0 | X, Xp , Xg , Xs )(8)

β 0 ∈A

nilX は X をラベルにもつ節点に接合操作が適用されないことを表す．A は補助木のテンプレートの集合である．
部分構文木の生起確率は，その生成に必要な操作の確率の積として計算する．

2.4

解析戦略

効率的な解析処理を実現するために，本手法では，

1 例 え ば ，構 文 木#18 を 分 割 す る 場 合 を 考 え る ．名 詞 句[[a]dt [dime]nn ]np の主辞は，nn である．したがって，従来の 解析戦略としてビームサーチを採用する．i 番目の手法では，dt でラベル付けされた節点で分割され，“a” に対す 単語 wi が入力された時点で生成された w1 · · · wi にる初期木として [a]dt が得られる．しかし，この初期木 [a]dt は，対する部分構文木のそれぞれについて，その生起確“I found” に対する部分構文木と結合できない．この木を代入できる節点は，“dime” に対する初期木 [dt[dime]nn ]np に存在し， 率を計算し，上位 N 個（N は固定）の部分構文木を残し，その他の部分構文木は削除する．
“I found” に対する部分構文木には存在しないからである．

I
#1

found
#2

#3

a

in

dime
#6

#10

the
#12

#7
#4

#8

I

#18

#1

found
#3

#2

#15
#11

#13

#9
#5

wood
#14

#16

a

in

dime
#6

#10

the
#12

#7
#4

#19

#8

subsumption relation

#18

#15
#11

#9

#17

wood
#14

#5

#13

#16

#19

#17
subsumption relation
valid partial parse tree

図 4: 部分構文木間の包含関係
図 5: 妥当な部分構文木

3

部分構文木の妥当性

本節では，部分構文木の妥当性に関していくつか定義を与える．部分構文木の妥当性について述べる
準備として，部分構文木間の包含関係を定義する．
定義 2 (包含関係) σ と τ を部分構文木とする．ある初期木 α に対して，sα (σ) = τ ，あるいは，ある補助木 β に対して，aβ (σ) = τ のいずれかが成り立つならば，σ ¤ τ である．¤∗ を ¤ の反射推移閉包とする．σ ¤∗ τ ならば，σ は τ を包含するという． 2σ が τ を包含するとは，σ に対して代入や接合をいくつか適用すると τ が得られることを意味する．図4 に，文 (1) に対して生成される部分構文木の間の包含関係を示す．
文の断片に対する部分構文木が構文的関係を正しく捉えているならば，その部分構文木は，文全体に対する正解構文木を包含している．そのような部分
構文木を妥当な部分構文木と呼び，次のように定義する．

構文木の妥当性を次のように定義する．
Pτ ∈Sub(σ,w1 ···wj ) P (τ )V (σ | w1 · · · wj ) = Pτ ∈T (w1 ···wj ) P (τ )(9)

ここで，σ は文の断片 w1 · · · wi (i ≤ j) に対する部分
構文木であり，T (w1 · · · wj ) は文の断片 w1 · · · wj に対して漸進的構文解析が生成した部分構文木の集合である．また，Sub(σ, w1 · · · wj ) は T (w1 · · · wj ) の部分集合で，σ に包含されるものの集合である．式(9) は入力が w1 · · · wj までわかった段階での σ の妥
当性を表現している．σ が入力文に対して妥当であるのは，σ に包含される w1 · · · wj に対する部分構文
木のいずれかが妥当な場合である．式 (9) は，生成された部分構文木のうちのそのような部分構文木の割合を表している．

4.1

部分構文木の出力

局所的曖昧性を解消するため，提案手法では，部
定義 3 (妥当な部分構文木) σ を部分構文木とし，分構文木の妥当性が閾値を超えた段階で，それを出
w1 · · · wn を入力文とする．σ が w1 · · · wn に対する力する．
正解構文木を包含するならば，σ は w1 · · · wn に対し
j 番目の単語 wj が入力されたとき，つぎのようなて妥当であるという．
2
部分構文木を出力する．
例えば，#18 を文 (1) に対する正解構文木であるとargmax{σ:V (σ,w1 ···wj )≥θ} l(σ)(10)
仮定する．このとき，#3 ¤∗ #18 であるので，部分
構文木#3 は (1) に対して妥当である．一方，部分構
ここで，θ は閾値で [0, 1] の値をとる．l(σ) は σ が含
文木#4 と#5 は (1) に対して妥当ではない．図 5 に，む単語の数である．出力される部分構文木は，式 (9)文 (1) に対して妥当な部分構文木を示す．
が閾値 θ を超える部分構文木のうち，最も多くの単語を含むものである．

4

部分構文木の妥当性の評価

文の断片に対する部分構文木の妥当性は，その断片に続く入力に依存している．例えば，部分構文木#3 〜#5 の妥当性は，単語 “found” に続く入力に依存している．これは，単語入力ごとに部分構文木の妥当性が変わることを意味している．そこで，部分

4.2

解析例

文 (1) に対する解析例を考える．閾値 θ = 0.8 とする．各操作の適用確率は，表 2 のとおりとする．文 (1)に対して妥当な部分構文木である#3 がどのタイミン
グで出力されるかについて考える．単語 “found” が表 2: 操作の適用確率

operation

probability

sα 1
sα 2
sα7 , sα10
sα5 , sα8
sα4 , sα6 , sα9
sα 3

1.0
0.7
0.5
0.3
0.2
0.1

aβ1
aβ2
nilN P
nilV P

0.3
0.7
0.7
0.3

表 3: 出力される部分構文木

input word
I
found
a
dime
in
the
wood

output partial parse tree
#2
#3
#10
#12
#18

となっている．

5

実験による評価

提案手法の性能を評価するために，構文解析実験を行った．提案する漸進的構文解析を GNU Common Lisp で実装した．文法は，Penn Treebank[16]の WSJ コーパスのセクション 2-21 から抽出した（構文木は，Klein らの手法 [17] に従っていくつかの情報を付与している．さらに，Roark の手法 [18] に従って構文木を変換している．
）．補間係数の λ1 ，λ2 は，EM アルゴリズムにより推定し，学習データとしてセクション 24 を用いた．ビームサーチの幅は 500 である，すなわち漸進的構文解析の過程で，確率値が上位 500 位以内の部分構文木だけを残し，それ以外は削除して解析を進めた．
セクション 23 の文に対して，ラベル正解率とラベ
ル再現率はそれぞれ 83.1%，81.4%であった．実験の対象として，セクション 23 の文のうち，漸進的構
文解析の最終的な解析結果が正解構文木と一致した
417 文を用いた．これらの文の平均文長は 13.5 単語である．閾値が，0.5, 0.6, 0.7, 0.8, 0.9 及び 1.0 に場合について，解析精度と遅延を測定した．
遅延は次のように定義する．s = w1 · · · wn を入力
文とし，oj (s) を，j 番目の単語 wj が入力されたときに出力された部分構文木とする．j 番目の単語が入力されたときの遅延を次のように定義する．

D(j, s) = j − l(oj (s))(11)

最大遅延 Dmax (s) と平均遅延を次のように定義する．

Dmax (s) = max D(j, s)
(12)
1≤j≤n
入力されたとき，部分構文木#3 〜#5 が生成される．
すなわち，T (I found) = {#3, #4, #5} である．図n1X4 に示すように，Sub(#3, I found) = {#3} である．
Dave (s) =D(j, s)(13)
n j=1
さらに，P (#3) = 0.7, P (#4) = 0.1，P (#5) = 0.2
である．したがって，V (#3, I found) = 0.7/(0.7 +
解析精度は，出力された部分構文木のうちの妥当
0.1 + 0.2) = 0.7 である．V (#3, I found) < θ である なものの割合と定める．
ので，部分構文木#3 はこの時点では出力されない． さらに，ベースラインとして，遅延が常に 0 である
単に，候補として保持しておくだけである．
解析，すなわち，確率が最も大きい部分構文木を出
次の単語 “a” が入力されたとき，部分構文木#6 力する方法についても，解析精度と遅延を測定した．
〜#9 が生成される．P (#6) = 0.21, P (#7) =表 4 に解析精度と遅延を示し，図 6 にそれらの間
0.14, P (#8) = 0.03，P (#9) = 0.02 であり， の関係を示す．
Sub(#3, I found a) = {#6, #7} である．したがこの実験結果は，精度と遅延の間のトレードオフって，V (#3, I found a) = (0.21 + 0.14)/(0.21 + の関係を示している．ベースラインと比較して，出0.14 + 0.03 + 0.02) = 0.875 で あ る の で ， 力は遅れるものの，解析精度は大幅に向上している．
V (#3, I found a) ≥ θ であり，部分構文木#3 はこ θ = 1 のとき，出力される部分構文木の妥当性は保の時点で出力される．
障され，この場合， 加藤らの手法 [10] と似た手法と
表 3 に，各単語入力に対して出力される部分構文 みなすことができる．この場合と比較すると，θ < 1
木を示す．
のとき，大きく遅延が減少している．
この例が示すように，提案する漸進的構文解析でこの実験結果は必ずしも，提案手法が最善のもの
は，部分構文木の出力を遅らせる．一方で，この例 であることを示すわけではないが，高い解析精度とにおいて出力された部分構文木はすべて妥当なもの 低い遅延の解析をある程度達成できていると言える．

表 4: 解析精度と遅延
precision(%) DmaxDave

θ = 0.5

100.0
99.3
96.8
95.3
92.3
88.6

13.2
10.2
8.9
7.7
6.6
5.4

7.2
4.9
3.9
3.2
2.6
1.9

baseline

74.3

0.0

0.0

θ = 1.0
θ = 0.9
θ = 0.8
θ = 0.7
θ = 0.6

delay(number of word)

14
12
10
8
6
4
2
0

3
Dmax
Dave
baseline

3
×
2
3
×

2
75

70

80

85

90

3
3
3
×
3
×
×
×
×
95

100

precision(%)

図 6: 解析精度と遅延の関係

6

おわりに

本稿では，漸進的構文解析において生成された部
分構文木の妥当性を評価する手法を提案した．この手法は，確率木接合文法に基づいている．単語が入力されるたびに，各部分構文木に対してその妥当性を随時計算し，妥当性が閾値を超えた段階でそれを出力する．本手法では，出力すべき部分構文木の決定を遅らせる．
提案手法を評価するために，Penn Treebank を用いた構文解析実験を実施した．この実験により，提案手法が漸進的構文解析の精度向上に有効であることが確認できた．
実験結果は，解析精度と遅延のトレードオフを示している．漸進的構文解析の性能を総合的に評価するために，遅延と解析精度の両者を総合的に評価する尺度が必要であるが，これについては今後検討し
たい．

参考文献
[1] J. Allen, G. Ferguson, and A. Stent, “An Architecture for More Realistic Conversational

Systems,” Proceedings of International Conference of Intelligent User Interfaces, pp.1–8,
2001.
[2] Y. Inagaki and S. Matsubara, “Models for
Incremental Interpretation of Natural Language,” Proceedings of the 2nd Symposium on
Natural Language Processing, pp.51–60, 1995.
[3] D. Milward and R. Cooper, “Incremental Interpretation: Applications, Theory, and Relationship to Dynamic Semantics,” Proceedingsof the 15th International Conference on Computational Linguistics, pp.748–754, 1994.
[4] F. Costa, V. Lombardo, P. Frasconi, andS. G., “Wide Coverage Incremental Parsing by
Learning Attachment Preferences,” Proceedings of the 7th Congress of the Italian Association for Artificial Intelligence, pp.297–307,
2001.
[5] N.J. Haddock, “Incremental Interpretation
and Combinatory Categorial Grammar,” Proceedings of the 10th International Joint Conference on Artificial Intelligence, pp.661–663,
1987.
[6] S. Matsubara, S. Asai, K. Toyama, and Y. Inagaki, “Chart-based Parsing and Transfer in
Incremental Spoken Language Translation,”
Proceedings of the 4th Natural Language Processing Pacific Rim Symposium, pp.521–524,
1997.
[7] D. Milward, “Incremental Interpretation of
Categorial Grammar,” Proceedings of the 7th
Conference of European Chapter of the Association for Computational Linguistics, pp.119–
126, 1995.
[8] B. Roark, “Probabilistic Top-Down Parsing
and Language Modeling,” Computational Linguistics, vol.27, no.2, pp.249–276, 2001.
[9] M. Marcus, A Theory of Syntactic Recognition
for Natural Language, MIT Press, Cambrige,
MA, 1980.
[10] Y. Kato, S. Matsubara, K. Toyama, and Y. Inagaki, “Spoken Language Parsing based on
Incremental Disambiguation,” Proceedings of
the 6th International Conference on Spoken
Language Processing, pp.999–1002, 2000.
[11] A.K. Joshi, “Tree Adjoining Grammar: How
Much Context-Sensitivity is required to provide reasonable structural descriptions?,” inNatural Language Parsing, ed. D.R. Dowty,
L. Karttunen, and A. Zwicky, pp.206–
250, Cambridge University Press, Cambridge,
1985.
[12] V. Lombardo and P. Sturt, “Incremental Processing and Infinite Local Ambiguity,” Proceedings of the 19th Annual Conference of the
Cognitive Science Siciety, pp.448–453, 1997.
[13] J. Chen and K. Vijay-Shanker, “AutomatedExtraction of TAGs from the Penn Treebank,”
Proceedings of the 6th International Workshop
on Parsing Technologies, pp.65–76, 2000.
[14] D. Chiang, “Statistical Parsing with an Automatically Extracted Tree Adjoining Grammar,” in Data-Oriented Parsing, ed. R. Bod,
R. Scha, and K. Sima’an, pp.299–316, CSLI
Publications, Stanford, 2003.
[15] F. Xia, “Extracting Tree Adjoining Grammars
from Bracketed corpora,” Proceedings of the
5th Natural Language Processing Pacific Rim
Symposium, pp.398–403, 1999.
[16] M.P. Marcus, B. Santorini, and M.A.
Marcinkiewicz, “Building a Large Annotated
Corpus of English: the Penn Treebank,” Computational Linguistics, vol.19, no.2, pp.310–
330, 1993.
[17] D. Klein and C.D. Manning, “Accurate Unlexicalized Parsing,” Proceedings of the 41th
Annual Meeting of the Ass0ciation for Computational Linguistics, pp.423–430, 2003.
[18] B. Roark, “Robust Garden Path Parsing,”
Natural Language Engineering, vol.10, no.1,
pp.1–24, 2004.