CFG フィルタリングを用いた高効率な LTAG パーザの構築
大内田賢太 † 吉永直樹 † 辻井潤一 ‡∗† 東京大学大学院情報理工学系研究科コンピュータ科学専攻‡ 東京大学大学院情報学環 * CREST, 科学技術振興機構{oouchida, yoshinag, tsujii}@is.s.u-tokyo.ac.jp

1

はじめに

α1:

Sធว

VP

β1:

本研究では、CFG フィルタリング [1, 2, 3, 4, 5, 6, 7]
NPVP
VVP *ઍ౉を用いた LTAG[8] パーザの実現への第一段階とし䊐䉾䊃䊉䊷䊄
α2:
canVて、LTAG から CFG への近似手法を提案する。
NPrun
LTAG や HPSG[9] のような語彙化文法の枠組み
N
では、CFG などの単純な文法枠組みに比べ、文にI項構造などの豊かな意味表現を与えることができる
ため、近年、高度な自然言語処理アプリケーションで利用されることが期待されている [10, 11]。しか図 1: Elementary tree と、代入、接合操作しながら、語彙化文法の枠組みでは、構文的な制約や意味的な制約などの情報を単語の語彙項目に押し本稿で提案した近似手法の有効性を確かめるため込めるため、木構造や素性構造などの複雑なデータ構造を必要とし、またそのデータ構造を扱う構文解 に、宮尾ら [13] による手法により、Penn Treebank
コーパス [14] から自動的に獲得された LTAG を使析の速度が問題になる。
CFG への近似の実験を行った。
い、
この問題に対し、語彙化文法に対する構文解析の高速化手法として、CFG フィルタリング [1, 2, 3,4, 5, 6, 7] が提案されている。CFG フィルタリン 2 背景
グでは、与えられた語彙化文法から近似的な CFG
2.1 Lexicalized Tree-Adjoining Grammarを抽出し、得られた CFG で構文解析の探索空間を(LTAG)絞ることで高効率な構文解析を実現する。しかしながら、HPSG に対する CFG フィルタリング [7] が LTAG では、語彙項目が elementary tree と呼ば大規模な文法を用いた際にも高速化が得られている れる木構造で表現される。文を解析する時は、代入一方で、LTAG に対する既存の CFG フィルタリン と接合と呼ばれる文法規則により elementary tree
グ [1, 3, 5] は、大規模文法を用いた実験結果が今 を組み合わせることで、構文木を導出する。図 1 は、のところ報告されていない。一方、吉永ら [12] は、 “I”, “run”, “can” に対する elementary tree α1 , α2 ,LTAG を HPSG スタイルの文法に変換し、得られ β1 とそれらに対する代入および接合操作を示してた文法に対して HPSG の CFG フィルタリングを いる。
代入は、木構造の葉ノードを、その葉ノードと同適用することで、大規模な LTAG 文法に対して高速化を達成している。さらに、LTAG に対する既 じラベルを根ノードに持つ他の木構造で置き換える
存の CFG フィルタリングよりも、LTAG を変換し 操作である。図 1 では、α1 の ラベル NP の葉ノーた HPSG に対する CFG フィルタリングの方がよ ド を、同じラベル NP の根ノードを持つ α2 により置き換えている。
り効果的であることも示している。
接合は、木構造の中間ノードを、その中間ノード
我々の提案する LTAG からの CFG への近似手法
では、吉永らにより示された基本的なアイデアに と同じラベルを根ノードと葉ノードに持つ他の木構
従って、まず LTAG の語彙項目に、LTAG の文法 造で置き換える操作である。図 1 では α1 のラベル規則である代入と接合をオフラインで適用するこ VP の中間ノードを、根ノードと一つの葉ノードがとにより、構文解析中に生成され得る部分構文木を 同じラベル VP を持つ β1 で置き換えている。この数え上げる。この際に、CFG を越える記述力を持 ような、根ノードと同じラベルを持ち、接合のときつ接合の適用回数を制限することで、有限サイズの に使われる特別な葉ノードのことをフットノードとCFG に近似することを可能とする。次に、それら 呼ぶ。
本研究では、代入と接合を CFG の文法規則に変の部分構文木間の導出関係を CFG の規則とすることで、与えられた LTAG から CFG を獲得する。 換することで、LTAG から CFG を抽出する。CFG䊐䉞䊦䉺䊥䊮䉫䈭䈚䊐䉞䊦䉺䊥䊮䉫䈅䉍౉ജᢥ౉ജᢥCFG䈮䉋䉎᭴ᢥ⸃ᨆ䋨1䊐䉢䊷䉵⋡䋩

S 5.ε

S 9.ε

NP5.1 VP5.2

NP 9.1 VP 9.2

VP5.2

CFG䈮䉋䉎
᭴ᢥᧁ

V 5.2.1 NP5.2.2

CFG rules
SNP VP
5.ε9.ε

5.1
9.1

5.2
9.2

VNP

VP9.2

VP
5.2

5.2.1

V 9.2.1 S*9.2.2

VPV9.2

9.2.1

5.2.2

S9.2.2ਈ䈋䉌䉏䈢⺆ᒵൻᢥᴺ䈮䉋䉎᭴ᢥ⸃ᨆ䋨2䊐䉢䊷䉵⋡䋩ᦨ⚳⊛䈭᭴ᢥᧁ

図 3: LTAG から CFG を抽出する既存手法
sign

SYNSEM …

図 2: CFG フィルタリングᢥᴺⷙೣsignに変換するとき、代入は CFG の文法規則と等価な記述力なので問題はないが、接合は CFG の文法規則以上の記述力を持つため、接合をいかに扱うかが問題になる。

2.2

SYNSEM …

Yᢥᴺⷙೣsign

CFG フィルタリング

CFG フィルタリング [1, 2, 4] とは、与えられた文法から CFG を抽出し、その CFG を使って、元の文法で得られるはずの構文木を効率的に絞り込む手法である。CFG フィルタリングでは、まず、与えられた文法からオフラインで CFG を抽出する (以下 CFG 近似と呼ぶ)。抽出された CFG は、構文木を過剰生成してもかまわないが、元の文法によって作られる構文木を全て含まなければならない。得られた CFG により、元の文法で得られるはずの構文木が満たすべき必要条件を効率的に計算することができる。
CFG フィルタリングを用いた構文解析は、2 つのフェーズで行われる (図 2)。1 フェーズ目では、オフラインで抽出された CFG を用いて構文解析を行う。このとき得られた構文木は、元の文法の制約の元では生成されない構文木を含みうる。2 フェーズ
目では、元の文法の制約を全て使って CFG 文法で得られた構文木を調べ、過剰に生成された構文木を除く。
CFG フィルタリングの性能は、CFG の近似の良さに依存する [12]。CFG が与えられた文法に対する良い近似となっていれば、過剰生成する構文木の数は抑えられ、フェーズ２でチェックする構文木の数も抑えられる。従って、いかに元の文法によって与えられた文法的制約を近似の CFG に保存するかが問題となる。
LTAG の既存の CFG フィルタリング [1, 3, 5] では、LTAG の elementary tree を各段ごとに切り離し、それをそのまま CFG 規則として用いている（図 3）。このようにして得られた CFG は、elementary tree に記述された多段の構文的制約が捉えられていないため、フェーズ２でそれらの構文的制約をチェックをしなければならない。
一方、吉永らは、LTAG を一旦等価な HPSG に変換し、得られた HPSG 文法に HPSG の CFG 近sign

SYNSEM …

SYNSEM …

X

sign

SYNSEM …

C

sign

SYNSEM …

C 㸢 YBsign

SYNSEM …

sign

SYNSEM …

B

sign

SYNSEM …

B 㸢 XAsign

SYNSEM …

sign

SYNSEM …

A

図 4: HPSG から CFG を抽出する既存手法
似手法 [6, 7] を適用することで LTAG から CFG を獲得している。HPSG を CFG に近似する手法の概要は、次の通りである。まず、素性構造で記述された語彙項目に対して文法規則を順次適用し、文法が生成しうる全ての素性構造 (HPSG の場合 sign) を列挙する。次に、この数え上げられた sign に非終端記号を割り当て、sign 間の文法規則で結ばれた導出関係を CFG の規則とする (図 4)。
吉永ら [12] はさらに、LTAG から変換されたHPSG にどのように CFG 近似の手法が適用されるかを考察することで、LTAG に対する新しい CFG近似の方法について言及している。

3

LTAG の CFG への近似アルゴリズム

吉永ら [12] の LTAG の CFG 近似の基本的なアイデアは、2.2 で説明した HPSG の CFG 近似と同様に、「構文解析時に可能な部分構造を数え上げる」というものである。彼らは、LTAG の語彙項目のelementary tree に逐次的に代入・接合を適用することで、可能な部分構文木を数え上げる。文法規則をelementary tree に逐次的に適用する既存の方式としては、例えば head corner traversal [13] が提案されている。head corner traversal では、elementarytree に対し、主辞から根ノードにいたる一意なボトムアップのパスをまず定義する。次に、パス上のノードを順に辿って、適用可能な文法規則を適用していく (図 5)。このとき、生成される部分構文木について、着目しているノードより「下の」部分木は既に文法適用を行った部分、「上の」部分木は、これから文法適用を行う部分であることに注意されα1:
NP

α2:

β1:

S

NP

4
1NP

3S

3VP

I

J

S

VP
V2V

VP*2VP
Vcan1NPS

1think NPrun

Vὐ✢䈪␜䈜䊌䉴䈱㗅䈮䇮ᢥᴺⷙೣ䈱ㆡ↪น⢻ᕈ䈏䉼䉢䉾䉪䈘䉏䉎 䇯thinkS

図 5: head-corner traversalNPVNP
S*think

SNP

SH
VPISNPV
thinkGJ㸢H IVPVrun

図 7: CFG 抽出:接合FSNPVPVrun

以下で、これらの CFG 規則が LTAG のどの文法規則に対応しているかをみていき、実際に LTAG を有限サイズの CFG に近似する際に問題となるケースについて考察する。

ESNPVPVrun

E

まず、図 6 で上の G → A F は、LTAG の代入に対応する CFG 規則である。代入が行われる時、親V
VP *Vの活性部分木が子供の活性部分木よりも小さくなる
このことから新しく生成される活性部分木の数が有C
A
α2:
B
β1:
限であることが分かる。活性部分木の数が有限なら
SNP
α1:
VP
NP
VP
ば、割り当てる非終端記号も有限になる。つまり、
V
VP *V
代入のみを文法規則を用いる LTAG であれば、有限の CFG に変換することができる。
また、F → E 、D → B 、E → C のように、代入や接合を行わない場合も存在する。代入の場合
図 6: LTAG から CFG の抽出手法と同様、親の活性部分木が小さくなるので、有限のCFG に変換することができる。
たい。構文解析に必要となる情報は、着目している
図 6 で中ほどの E → D E は、LTAG の接合にノードより「上の」部分木に全て含まれる。本論文 対応する CFG 規則である。代入の場合と同様に、
ではこの部分木を活性部分木 と呼ぶ。吉永らのア 活性部分木に非終端記号を割り当てる。このようイデアでは、このようにして得られる活性部分木を に、フットノードが木構造の深さ 1 段目にある活性CFG の非終端記号と考え、活性部分木間の導出関 部分木の接合の時は、生成される活性部分木のサイ係を CFG 規則とすることで CFG を獲得する。
ズは増大しない。しかし、図 7 の例のように接合す
図 6 は図 1 の文法に対し、head-corner traversal る活性部分木のフットノードの深さが木構造の 2 段に従い、文法適用を行った例である。このとき、網 目以下の位置にあるとき、親の活性部分木が複数の掛けの部分が活性部分木である。この活性部分木に 活性部分木の組み合わせになる。これにより、活性対し、図 6 中の A〜G の様に非終端記号を割り当 部分木のサイズが増えるため、部分活性木が無限に生成されうる。
てる。
次に、CFG の文法規則を抽出する。図 6 を例に、 本手法では、活性部分木ごとに、何度このような代入・接合を CFG の文法規則として抽出すると、 活性部分木のサイズが増える接合を適用して得られたのかを記録しておき、閾値以上適用して得られた以下のように表せる。
活性部分木には、全て同じ非終端記号 “*” を割り当
G→ AFてることとする。これにより、活性部分木の最大のF → E深さを制限することができるので、得られる CFGE→ DEのサイズも有限に抑えることができる。また、得らD→ B
れた CFG が元の文法で得られるはずの構文木を全E→ C
VPSDNPVP

canruncanrunI表 1: WSJ section 23 から抽出された LTAG
単語数
非終端記号の数
elementary tree の数

1,56960466

表 2: LTAG から抽出された CFG
終端記号数
非終端記号数CFG 規則数

3,001
1,31819,1555まとめ本論文では、CFG フィルタリングを用いた LTAGパーザの実現するため、LTAG から CFG への近似手法を提案した。吉永ら [12] の手法に基づき、構文解析時に可能な部分構造を数え上げるという近似手法を、活性部分木のサイズが増える接合の回数を制限するという制約を取り入れることで実現した。
今後の課題として、まず、制限が必要であると思
われる XTAG 英文法などの人手で書かれた文法のCFG への近似実験があげられる。また、LTAG パー
ザに CFG フィルタリングを実装し、本手法によって得られた CFG による CFG フィルタリングの有効性を検証したい。

参考文献て生成することを保証するために、非終端記号 “*”に対して、全ての非終端記号 X において、* → X *あるいは * → * X となる CFG の規則を作る。得られる CFG は、この規則によって、過剰生成する可能性があるが、与えられた文法が出力する全ての構文木を出力することが保証される。
このように、適用する文法規則の回数を制限することで語彙化文法を CFG に変換する手法は Kiefer
ら [6] により HPSG の枠組で提案されている。我々の LTAG に対する近似手法は、LTAG の文法規則の性質に着目し、実際に問題となるケースに限って適用回数を制限しており、単純に文法規則自体の適用回数を制限するよりも良い近似を得ることができると思われる。

4

実験[1] K. Harbusch. An eﬃcient parsing algorithm forTree Adjoining Grammars. In Proc. of the 28thACL, pages 284–291, 1990.
[2] J. T. Maxwell III and R. M. Kaplan. The interface between phrasal and functional constraints.
Computational Linguistics, 19(4):571–590, 1993.
[3] P. Poller. Incremental parsing with LD/TLPTAGs. Computational Intelligence, 10(4):549–562,
November 1994.
[4] K. Torisawa and J. Tsujii. Computing phrasalsigns in HPSG prior to parsing. In Proc. of the16th COLING, pages 949–955, 1996.
[5] P. Poller and T. Becker. Two-step TAG parsing revisited. In Proc. of TAG+4, pages 143–146, 1998.
[6] B. Kiefer and H.-U. Krieger. A context-free
approximation of Head-Driven Phrase StructureGrammar. In Proc. of the sixth IWPT, pages 135–146, 2000.
[7] K. Torisawa, K. Nishida, Y. Miyao, and J. Tsujii. An HPSG parser with CFG ﬁltering. Natural
Language Engineering, 6(1):63–80, 2000.

本論文で提案した CFG の近似手法の有効性を確か[8] Y. Schabes, A. Abeillé, and A. K. Joshi. Parsing
めるために、コーパスから獲得した LTAG に CFG
strategies with ‘lexicalized’ grammars: applicationの近似手法適用し、得られる CFG の性質を調べる。
to Tree Adjoining Grammars. In Proc. of the 12thCOLING, pages 578–583, 1988.
我々は、本稿で提案した CFG への近似手法を実装し、宮尾ら [14] の文法抽出プログラムを使用し、 [9] C. Pollard and I. A. Sag. Head-Driven Phrase
Structure Grammar. CSLI Publications, 1994.
Penn Treebank Wall Street Journal (WSJ) の section 23 から抽出した LTAG(表 1) に適用した。今 [10] Deep Thought Project.
http://www.project-deepthought.net/.
回のコーパスから自動獲得した LTAG 文法では、活性部分木のサイズを増やす接合回数を制限すること [11] Kototoi Project.
http://www-tsujii.is.s.u-tokyo.ac.jp/kototoi/.
無しに、LTAG を CFG に近似することに成功した。これは、吉永らの HPSG 経由の CFG コンパイ [12] N. Yoshinaga, T. Kentaro, and J. Tsujii. Comparison between CFG ﬁltering techniques for LTAG
ルの [12] の実験結果と一致する。
and HPSG. In Proc. of the 41st ACL companion
表 2 に近似の結果得られた CFG のスペックを示
volume, pages 185–188, 2003.
す。近似にかかった時間は、約 30 分である。単純に[13] G. van Noord. Head corner parsing for TAG.
elementary tree の各段を切り離すことで CFG を得
Computational Intelligence, 10(4):525–534, 1994.
る既存の手法の場合、得られる CFG の非終端記号
Y. Miyao, T. Ninomiya, and J. Tsujii. Lexicalizedの数は元の LTAG の非終端記号と同じ 60 個となる [14] grammaracquisition. In Proc. of the 10th EACL
ことを考えると、我々の手法で得られる CFG はよcompanion volume, pages 127–130, 2003.
り深い制約を考慮していると言えるだろう。