依存関係を用いた漸進的構文解析の効率化
村瀬 隆久y1
y1名古屋大学工学部

松原 茂樹y2y4

外山 勝彦y3y4

y2名古屋大学言語文化部

稲垣 康善y3

y3名古屋大学大学院工学研究科

y4名古屋大学統合音響情報研究拠点 (CIAIR)

fmurase,matu,toyama,inagakig@inagaki.nuie.nagoya-u.ac.jp

1 はじめにa) 辞書引き 語 wi の範疇が A ならば，項 [wi ]A をラベルに即時応答機能を備えた対話処理システムを実現するためには，話者による入力に従って順次，解析を行う漸進的解釈手法が必要である．漸進的に解釈するためには，語の入力毎にそれまでの入力に対する解析木を随時作成する必要があり，それを実現するための手法として漸進的チャート解析法が提案されている [4]．しかし，この手法では，未入力部分の予測をもとに解析木を作成するため， 1 文単位の解析手法に比べて，作成される解析木数が増加し，さらに解析処理時間が増大するという問題が生じる．
そこで本稿では，文脈自由文法を用いた構文解析と，意味情報を用いた構文的曖昧性解消を，漸進的かつ同期的に行うことによって解析処理時間を抑える手法を提案する．本手法では，あらかじめ獲得した単語間の依存関係情報を，漸進的チャート解析における文法適用可能性に関する制約として利用することにより，意味的に不適当な解析木の作成を回避し，漸進的構文解析を効率化できる．
これまでにも，意味情報を制約として用いることによって，意味的に不適当な部分解析木を削除する構文解析手法が提案されている [2, 7]．一方，本手法では漸進的チャート解析によって，随時，それまでの入力に対する解析木を作成するため，解析木全体に対して意味情報を活用することができる．
本稿の構成は以下の通りである． 2節では，漸進的チャート解析とその効率化について述べる． 3節では，依存関係情報を用いた漸進的チャート解析法を提案する． 4節では，本手法を用いた解析実験の結果について報告する．

2 漸進的構文解析とその効率化
2.1 漸進的チャート解析
文脈自由文法に対する構文解析手法の一つである漸進的チャート解析 [4] では，解析途中の結果をチャート [3] と呼ばれるグラフで表現する．チャートの節点は，入力文の単語と単語の間に付けられた番号であり， 2 つの節点 i 1, i の間は入力文の左から i 番目の入力単語に対応する．節点間に張られる弧には，項と呼ばれる構文構造がラベルとして付けられる． X を範疇とするとき項 [?]X を未決定項と呼ぶ．特に項の中の最も左に位置する未決定項を最左未決定項と呼ぶ．未決定項を含む項をラベルとしてもつ弧を活性弧と呼び，そうでない弧を不活性弧と呼ぶ．
漸進的チャート解析では，項 [?]S をもつ弧が節点 0, 0 の間に張られたチャートを初期状態として， i 番目の語 wi が入力されたとき以下の手続きを順に実行する．

0もつ弧をチャートの節点 i01, iの間に追加する．

b) 文法規則の適用 チャートの節点 i01, i の間に張られた弧111!

111

A1 A2Anの項が [ ]A1 であり，かつ，文法規則 Aが存在するならば，項 [[ ]A1 [?]A2[?]An ]A をラベルとしてもつ弧をチャートの節点 i 1, i の間に追加する．この操作を可能な限り繰り返す．

1111110c) 項の置き換え チャートの節点 0, i 0 1 の間に張られた弧の項  の最左未決定項を [?]X とする．このときチャートの節点 i 1, i を結ぶ弧の項  の範疇が X ならば， の最左未決定項を  で置き換えた項をラベルとしてもつ弧を，チャートの節点 0, i の間に追加する．

0

漸進的チャート解析では，語が入力される毎にそれまでの入力に対する解析木を作成することができ，漸進的解釈のための構文解析手法として適している．

2.2

漸進的構文解析の効率化

漸進的構文解析の結果，一般に，複数の解析木が作成されるが，これは，その文に含まれる構文的曖昧性に起因する．
構文的曖昧性は，文中で語と語の間の依存関係，すなわち，修飾，非修飾関係が複数考えられるときに発生する [2]．図3に示した文法と辞書を用いて，英語文
Ken studied English at school yesterday.

(1)を漸進的チャート法に従って解析すると，語 \at" が入力された時点で，図 1，図 2に示す 2 つの解析木が生成される．図1の解析木は \at" が \studied" に構造上依存することを，
図 2の解析木は \at" が \English" に構造上依存することをそれぞれ表している．しかし，意味的には一般に， \at" は\studied" に依存し得るが， \English" に依存することはないと考えられる．よって，図 2の解析木は，構文的には適当であるが，意味的には不適当であるといえる．
作成された解析木において，その中の語と語の間の依存関係が常に成り立つとは限らない．正しくない依存関係を含む
ような，つまり，意味的に不適当な解析木の作成を回避することにより解析を効率化できる．

3

依存関係情報を用いた漸進的チャート解析

前節で述べたように，漸進的構文解析を効率化するために，意味情報を用いた構文的曖昧性解消を早い段階で行うことによって，作成される解析木の数を削減する方法が考えられる．本節では，単語間の依存関係情報を，漸進的チャート

S

文法

VPNPVPron

PPN

P

Adv

N

Ken studied English at ?

?

→ NP VP

Pron

→ Ken

NP

→ PronN→ English / schoolNP→ N PPV→ studied

PP→PN

P→ at

VP

→ V NP Adv

Adv→ yesterday

VP→ V N PP Adv

図 1: 英語文 (1) の解析木 1

図 3: 構文解析のための文法と辞書 (1)

S
2.

VP

NPVPron3.

AdvNP?

図 2: 英語文 (1) の解析木 2

解析における文法適用可能性に関する制約として用いることによって不適当な解析木の作成を回避する手法について述べる．本手法では，解析木全体に対して，構造上定まる語と語の間の依存関係を決定し，それらが意味的に適当であるかどうかを，あらかじめ獲得した単語間の正しい依存関係情報を用いることによって調べる．意味的に不適当であればその解析木を削除する．
以下， 3.1節では，解析木から構造上成り立つべき依存関係を決定する方法について述べ， 3.2節では，構造上の依存関係と意味的に正しい依存関係情報を用いて解析木を削除する手法について述べる．

3.1 文法と項への制約
本手法で用いる文法は文脈自由文法であり，各文法規則の右辺の範疇列の中には，記号 が付与された範疇がただ一つ存在するものとする．以下では，そのような範疇を主辞と呼ぶ．また，右辺の主辞でない範疇を補語と呼ぶ．それらの間には，補語が主辞に依存するという依存関係を定めることができる．
また，文法規則

3X! Y1 1 1 1 Z 3 1 1 1 Yn

(2)の適用により，項1 1 1 Y1 1 1 1 1 1 1 Z 3 1 1 1 1 1 1 Yn Xが作られるとき， 1 1 1 Z を項の主辞項と呼ぶ．
[[]

[[]]

[]]

(3)

(3)

定義 1 (語彙的主辞) 語彙的主辞は，次の 1. 〜 3. のいずれかである．
1.

未決定項 [?]X の語彙的主辞は \?" である．

i = [1 1 1]Ai (i = 1; : : : ; n) とする．文法規則! A1 1 1 1 A3i 1 1 1 An が存在し， が項[ 1 1 1 1 i 1 1 1 n ]A であるとき，の語彙的主辞は主辞項 i の語彙的主辞である．
AN

PPP N
Ken studied English at ?

辞書

S

wi を語， X を範疇とする．このとき，項 [wi ]Xの語彙的主辞は wi である．

語彙的主辞は，その項の中心的意味を担う語であり，すべての項は語彙的主辞を持つ．
あらかじめ主辞と補語が定められた文法規則を用いて作成された解析木では，構成要素間の依存関係を求めることができる．また，各構成要素には語彙的主辞が存在する．
構成要素間の依存関係は，語彙的主辞間においても成立するため，語彙的主辞間の依存関係が構造上定まる．すなわ
ち，文法規則 (2) の適用によって作られた項 (3) において，[]Yj (1jn) の語彙的主辞は []Z の語彙的主辞に依存する．

111

3.2 

111

依存関係情報を用いた漸進的チャート解析

本手法では，解析木から定まる構造上の依存関係が，あらかじめ獲得した単語間の意味的な依存関係情報と適合するかどうかを，漸進的チャート解析における項の置き換え操作の時点で調べることにより，解析木を削除する．
漸進的チャート解析では，項の置き換え操作によって解析木を作り上げていくため，置き換え操作の実行可能性に対して条件を追加することにより，不適当な解析木の作成を回避することができる．例えば，図 4において，項 の最左未決定項 を項  で置き換えたとすると，図 5が示す依存関係が構造上成り立つことになる (項 i の語彙的主辞を w i ，置き換えられた項  の語彙的主辞を w とする．)．よって，この依存関係が意味的に成り立つかどうかを，置き換え操作前に調べることにより，項の置き換え可能性を判断できる．図4では，項の最左未決定項 が主辞項であるため，語彙的主辞 w i (1 i m) が語彙的主辞 w に構造上依存することが，意味的に成り立つかを調べる．また図 6において，項の最左未決定項 を項  で置き換えたとすると，図 7が示す依存関係が構造上成り立つことになる．図 6では，項 の最左未決定項 が主辞項 n より右に位置するため，語彙的主辞 w が語彙的主辞 w n に構造上依存することが，意味的に成り立つかを調べる．
すなわち 2.1節の c) で述べた置き換え操作に対して以下の追加条件を加え，それを満たすならば c) を実行し，解析木を作る．

 

項α項αX

X
項の置き換え項の置き換え項δY1YmZ*Y1ZYm

Y*n…

…

…

?
項βm 項γ項β1項β1項βmZ…

項δ
Z?
項βn 項γ

図 4: 置き換え操作 1

図 6: 置き換え操作 2wβ1 … wβm wδ

wβ1 … wβm… wβn… wδ

図 5: 構造上の依存関係 1

図 7: 構造上の依存関係 2

追加条件  の語彙的主辞が \?" である．または，あらかじめ獲得した語と語の間の正しい依存関係情報を用いて，wb
以下のいずれかのケースを満たす．ただし， waで wa が wb に依存することを表すこととする．また の最左未決定項 [?]X を  とし，項N 3 [?]PP ]において， 最左未決定項 [?]PP は主辞
項 [English]N 3 の右に位置するため，追加条件の中のケース 1) により，項 [English]N 3 の語彙的主辞 \English" と，
項 [[at]P 3 [?]N ]PP の語彙的主辞 \at" の依存関係について調べる．このとき，あらかじめ獲得した単語間の依存関係情報から， \at" は \English" に意味的に依存しないと判断されるなら， (a) と (b) の間で項の置き換え操作を行わないので，図 2の解析木を生成しない．

)

1 1 1 l01  l+1 1 1 1 n A  lの主辞項を h h  n とする．さらに，項の列f 1 1 1 1 l01  l+1 1 1 1 n g  l
=[ 1(1]((==)))

を L とする．

 h  l 0 であるとき， ケース 1) L において， 1の語彙的主辞 w と，間に依存関係情報 w

1h の語彙的主辞 w h とのw h がある．

)

ケース 2) L において， h = l であるとき，  の語彙的主辞 w と， i の語彙的主辞 w i (i = 1; : : : ; l1) との間に依存関係情報 w iw (i = 1; : : : ; l1) があるならば，  :=  とし，項の列 L00)

f 1 1 1 1 l01  l+1 1 1 1 n g (=l)

に対して，追加条件を満たす．
ケース 3) L において， l + 1 h  n である．

3.3 解析例
英語文 (1) に対する解析例は以下の通りである．なお，ここでは，図 9に示した文法と辞書を用いる．図 8に示す
ように，語 \at" が入力された時点で， (a) と (b) の間で項の置き換えを行うと， \at" が \English" に依存するという構造上の依存関係が成り立つことになる．このとき，項[[English]

4

実験

本稿で提案した手法の有効性を評価するために，それをワークステーション (メモリ 512MB， CPU248MHz) 上に， GNU Common Lisp 2.2.2 を用いて実装し，解析実験を行った．実験では，文献 [6] に収録された辞書 (438 語)，文法 (224 規則, 非終端記号数 93)，及び，英語
文 40 文 (平均語数 12.2 語) を用いた．各文における単語間の正しい依存関係は，あらかじめ人手で付与した．実験では， 1 単語入力毎の，生成された解析木数，及び，解析処理時間について，従来の漸進的チャート法と依存関係を用いた漸進的チャート法との間で比較した．
UltraSparcII

従来手法に対して本手法が作成する解析木数の比を図 10に示す．図 10から，文が長くなると，作成された解析木数の割合は小さくなることがわかる．これは，長い文では，構文的曖昧性が大きくなり，そのため意味的に不適当な解析木が多く作成されるからであり，それに対して本手法の効果が現れている．
一方，従来手法に対する本手法の解析処理時間の比を図に示す．本手法では，語と語の間の依存関係のチェックに時間を要するため，削除される解析木数の割合が小さいときには，両手法の解析処理時間はそれほど変わらないものの，解析木数の割合が大きくなると，本手法の効果は大きくなる．
11

1(a)

V*

Pron*

NP
N*

Adv(b)?

PPP* Nat ?

PP

Ken studied English?

構造上の依存関係KenRate

0.9

VP*NPStudiedEnglishRate of Syntax Trees

S0.8
0.7
0.60.5

at0.40.3

図 8: 解析例

051015202530

Length of sentence (Words)

図 10: 作成された解析木数の比辞書

S→ NP VP*Pron→ Ken

NP→ Pron*

N→ English / school

NP→ N* PP

V→ studied

PP→ P* N

P→ atVP→ V* NP Adv

Adv→ yesterday

VP→ V* N PP Adv
図 9: 構文解析のための文法と辞書 (2)1.3

5 おわりに

1.1
1
0.9
0.8
0.7
0.6
0.50.4

本稿では，単語間の依存関係情報を利用した漸進的構文解析の効率化手法を提案した．本手法では，解析木から定まる依存関係が意味的に正しいかどうかを，あらかじめ獲得した単語間の依存関係に関する情報を用いて調べることによって，意味的に不適当な解析木の作成を回避することができる．作成される解析木数を削減することができるため，解析処理時間を抑えることができる．実験を通してその有効性を確認した．
本稿で提案した手法では，語が入力される毎に，作成された項に対して語彙的主辞を与えるため，項の語彙的主辞となる語が早い段階で入力されれば，早期に項の語彙的主辞を決定することができ，語と語の依存関係を調べることができる．そのため本手法は，英語のような主辞先行言語に対して，より有効であると考えられる．
これまでに，漸進的構文解析を効率化する手法として，構文構造に対して行っていた処理をグループ単位で行い，実行する処理量を削減することにより，解析を高速化する手法[1] や，いくつかの解析木を同一化できるようにあらかじめ文脈自由文法を変換することによって，作成される解析木数を抑える手法 [5] などが提案されている．それらの手法を本手法に導入することにより，一層の効率化が期待できる．

Rate

1.2

Rate of Processing Time

文法051015202530

Length of sentence (Words)

図 11: 解析処理時間の比[2]

今一 修, 松本 裕治, 藤尾 正和: 統計情報と文法制約を統合した統語解析手法, 自然言語処理, Vol.5, No.3,pp.67-83 (1998).

[3] Kay, M: Algorithm Schemata and Data Structures
in Syntactic Processing,

12

Technical Report CSL-80-, Xerox PARC (1980).

[4] Matsubara, S., Asai, S., Toyama, K. and Inagaki,Y.: Chart-based Parsing and Transfer in Incremen-Proc. of 4th Natural Language Processing Paci c Rim Symposium
tal Spoken Language Translation,,

pp.521-524 (1997).
[5]松原 茂樹, 村瀬 隆久, 加藤 芳秀, 外山 勝彦, 稲垣 康善:
文脈自由文法の変換に基づく漸進的構文解析の効率化,
電気関係学会東海支部連合大会 pp.635(1999).

[6] Tomita, M: Ecient Parsing for Natural Language:

参考文献
[1]

浅井 悟, 松原 茂樹, 外山 勝彦, 稲垣 康善: 構文構造のグループ化における漸進的チャート解析の高速化, 言語処理学会第 5 回年次大会 pp.88-91(1999).

A Fast Algorithm for Practical Systems (1985).
[7]渡辺 日出雄: 係り受け関係を用いた CFG 構文解析の枝刈手法, 情報処理学会第 59 回全国大会 (2) pp.345-346(1999).