文脈自由文法の有限オートマトン近似に基づく漸進的構文解析の高速化
湊 恵一y

加藤 芳秀yy名古屋大学大学院工学研究科

松原 茂樹z

稲垣 康善yz名古屋大学情報連携基盤センター

fminato,yosihide,matu,inagakig@inagaki.nuie.nagoya-u.ac.jp

1 はじめに→(2)

S0

実時間音声言語処理システムでは，ユーザの発話をそ
S0S
Sの出現と共に順次理解する必要がある．そのような処理
(7)
S
(6)
?
SVP
を実現するためには，発話の断片が入力されるごとに，
(5)
(1)
VP
VP
PP VP
順次，解析処理を実行する，漸進的な構文解析が必要で
S
adv S
PP?
(4)
(10)
ある [1, 2, 3, 4]．漸進的構文解析手法としてこれまでに，
PPNP p(9)?
(3) NPVP(8)
漸進的チャート解析が提案されている [3]．漸進的チャーNPnVPv
advnpvト解析では，単語が入力されるたびに，それまでに入力(adv)(n)(p)(v)された文の断片に対する構文木を生成する．これにより，文全体が入力されていなくても，その時点までの構文構
図 1: 漸進的チャート解析の解析過程
造を明らかにすることができる．
しかし，この手法は，解析処理時間についてはこれまp / p]
であまり考慮されておらず，現状の方式で，ユーザの発adv / [[ adv
話を実時間で処理することは必ずしも容易ではない．
n/[ [[[n]v/[v]] ] ]]
そこで本稿では，発話を同時進行的に処理する構文解
析の実現を目的として，漸進的構文解析のための有限状
図 2: 漸進的構文解析に用いる FST の例
態変換器 (Finite State Transducer; FST)[5] の構成手法，および，それを用いた構文木生成手法を提案する． する漸進的チャート解析の過程を図 1に示す．図中の番号
漸進的チャート解析では，単語が入力されるたびに文法 は，処理の順序を示しており，実線矢印は規則の適用を，規則を組み合わせて構文木を生成するが，このような構 点線矢印は構文木の結合を表す．例えば，品詞1 が n であ文木をあらかじめ作成し， FST に記述しておくことによ る単語「予約」に対しては，図のように， \NPn" かり，構文木を即時に出力でき，高速に漸進的構文解析を ら \SVP" までの 4 つの文法規則を順に適用すること実行できる．
により (処理 (3) 〜 (6))，その単語に対する構文木を作る．
本手法では，文脈自由文法 (Context Free Grammar; そして，「今日」の品詞である adv に対する構文木と結CFG) を近似変換して FST を構成する．したがって，構合することにより (処理 (7))，「今日 / 予約」に対する構成した FST で解析可能な文の集合は，もとの CFG で解 文木を生成する．しかし，この手法では，単語が入力さ析できる文の集合のサブセットであり，より多くの文を れるたびに文法規則を組み合わせて，新たに構文木を生解析できるように， FST を構成する必要がある．そこで， 成するため，解析処理に時間がかかる．使用する文法が生成頻度の高い構文木が記述された弧は，解析において 同一であれば，同一の品詞に対して作成すべき構文木は，たどられる可能性が高いという， FST の弧と構文木の関 あらかじめ決まる．したがって，それを事前に計算して係に着目して，そのような弧を優先的に作成する．その おき，解析時に利用すれば，効率的な構文解析が可能で優先度は，構文木付きテキストコーパスから獲得した構 ある．
文木生成確率をもとに計算する．
本研究では，このような漸進的構文解析を実現するた

→→

→

今日

S0→→

予約

する

PPS

S!

を→

VP

PPNPNP

VP

VP

VP

SS

S0!

めに FST を利用する． FST は，有限状態オートマトンに出力ラベルを付加した状態遷移機械であり，状態を遷漸進的チャート解析は， CFG に基づく構文解析手法で 移するたびに，弧に割り当てられた記号を出力する [5]．
ある．新たな単語が入力されるたびに，文法規則の適用 漸進的構文解析を実現するために，弧の入力ラベルにはを繰り返すことにより，その単語に対する可能な構文木 入力単語を，出力ラベルにはその単語に対して出力すべを生成し，それをそれまでの入力に対して生成された構1 本研究では，品詞は範疇に含まれないものとし，品詞を終端記号，文木と結合することにより，漸進的に構文木を生成することができる．日本語文「今日 / 予約 / を / する」に対 範疇を非終端記号として扱っている．

2 漸進的な有限状態構文解析

(a)
S0

PPv

NPp

PP

NP

S0(b)
PP(c)
NPn!
!
!
!

PP v

PPNP pNP

PP NPNPn

図 4: CFG の例

図 3: RTN の例
S0S0

α X β11r11α X β r2222Xn-1α X βnnrnα1X1β1α2X2…

β2αn

XnβnXXn

図 6: 文法規則の適用に対応する
図 5: 文法規則の適用

一般に，この操作は無限に適用できるが，有限回の置き換えを実行すると，もとの RTN が受理する言語のサブセットを受理するようなオートマトンを構成できる．
上で述べた方法で構成したオートマトンに対して，適切な構文木を出力ラベルとして与えることにより，漸進的構文解析を実現する FST を構成できる．以下では，そのための手法について考える．
ネットワーク中の弧を，そのラベルに対応するネットワークで置き換える操作は， CFG における文法規則のトップダウンの適用とみなすことができる．すなわち，図6のようなネットワークの置き換えは，図 5のような文法規則の適用と対応している．したがって，図 6中の n を入力ラベルにもつ弧を遷移することは，入力に対して図5のような構文木を認識することに相当する．すなわち，このような構文木を， n を入力ラベルにもつ弧に対する出力ラベルとして与える．
本手法では，このように，弧のネットワークによる置き換えと文法規則のトップダウンな適用とを対応させ，FST 中の弧の出力ラベルを与える．
まず，本手法での構文木の表記法について述べる．本
手法では，括弧を用いて構文木を次のように表現する．

ネットワークの置き換え

き構文木を割り当てる．解析では，入力に従って FST 上を遷移し，出力ラベルに付与された構文木を用いて漸進的に構文木を生成する．図 2に，図 1の解析過程に対応した FST の動きを示す．入力文「今日 / 予約 / を / する」の品詞系列 \adv n p v" に対して，順次，出力した木を単に結合することにより，その時点までの入力に対する構文木が生成できる．

::: i::: n A
ここで， A は非終端記号， i  i  n は括弧で表現した構文木である．これは，根が A で，その構成要素が1 ; : :: ; i ; : : :; n である構文木を示す．なお，以下では
A 1

[]

(1)

(1)

A を左括弧付範疇, A ] を右括弧付範疇とよぶ．

[E とし，弧 e qs ; X;olXor ; qe 2 E を中の Xに対応するネットワーク
Mで置き換えることにより，X
本節では，漸進的な有限状態構文解析を実現するE に更新する．ただし，弧 e は，状態 qs から状態 qe へを構成する手法について述べる．本手法では，をX ，出力ラベル ol Xor を持つ．まと遷移し，入力ラベルに変換することによりそれを実現する．
を再oは左括弧付範疇の系列，or は右括弧付範疇の系列た，l
帰遷移ネットワークを示す．
M中の弧の集合をEとする． EX の要素はXXで表現し，ネットワークの弧を別のネットワークで項組始点の状態，ラベル，終点の状態である． iX ; fX置き換える操作を繰り返すことによりを作成する．
をMの初期状態，最終状態とし，状態q
X1 ; q2 はそれぞを近似したものであり，もとので解析
これはq6i;
q6fであるとする．
れ1X2X
で解析でき可能な文であるからといって，必ずしもE 0 feg
るわけではないが，本手法では，統計情報を用いて置き E[ f eq1; A; A; eq2 j q1; A; q2 2 EX g
換え操作の優先度を計算することにより，カバレッジのを作成する．
高い[ f qs;A; ol X A;eq2 j iX ; A; q2 2 EX g
[ f eq1; A; AX or ;qe j q1; A; fX 2 EX g
3.1 CFG から FST への変換
[ f qs;A; ol X AX or ; qe j iX ; A; fX 2 EX g
は，をネットワークで表現したものであり，置き換え操作は以下の通りである． FST の弧の集合を

3 FST の構成手法= (FST)

RTN

0

CFG

FST

CFG

(Recursive Transition Network;RTN)

3FST

CFG

()

CFG

FST=0==()(FST()

[(RTN

(CFG

受理する言語はそれと等価である． RTN では，各非終端記号に対して，それぞれ対応するネットワークが一つ存在する．ネットワーク中の非終端記号をラベルにもつ弧は，その非終端記号に対応するネットワークにより再帰的に定義される．例えば，図 3 に示す RTN は，図 4 に示す CFG を表現する． S0 ,PP,NP は非終端記号であり，n,p,v は終端記号である． S0 ,PP,NP には，ネットワーク(a),(b),(c) がそれぞれ対応する．
RTN 中の非終端記号をラベルにもつ弧を，その非終端記号に対応するネットワークで置き換える操作を繰り返すことにより，一つの有限オートマトンを構成できる．

][]())())())()(2)

置き換え操作の例を図 7に示す．図 7では， NP を入力ラベルとする弧を図 3(c) のネットワークで置き換えている．その結果， NP の代わりに，系列 \PP NP"，または \n" での遷移が可能となる．さらに，新たに作られた弧に対して出力ラベルを与える．置き換える弧の入力ラ
ベルは NP，出力ラベルは \[S0 [PP NP" であるから，式(2) では，=NP， l = [S0 [PP ， r =である．したがって，以下のように出力ラベルを与えればよい．

Xoo"をラベルに持つ弧は，弧の始点が図 3(c) の初期状態であるので， \[S0 [PP [NP PP" を与える

PP

SNP/ [ 0 [PP NPp / p PP]

うに定義する．

v / v S0]

PT(PP置き換え
PP/SNP PP[ 0 [PP [rNP]p/ p

S PP [NP n NP]

PP] v / v S0]

図 7: 置き換え操作の例

 をラベルに持つ弧は，弧の終点が図 の最終をそれぞれ与える．
状態であるので，
 をラベルに持つ弧は，弧の始点および終点がそれNP3(c)\NP NP ]"n

ぞれ図 3(c) の初期状態および最終状態であるので，\[S0 [PP [NP n NP ]" を与える．

得られた FST では，「私 (n) は (p) 行く (v)」の単語ごとの入力に対して，，\[S0 [PP [NP n NP ]"，\[S0 [PP [NP n NP ] p PP ]"\[S0 [PP [NP n NP ] p PP ] v S0 ]"が順に出力される．

3.2 統計情報を用いた置き換える弧の選択節の手法により，漸進的構文解析を実現する FST を構成できる．ここで考えなければならない問題は，ネッ
トワーク置き換え操作の適用が有限回であるために，構成された FST はもとの RTN を近似したものとなり，もとの RTN により解析できる文が必ずしも構成された FSTにより解析できるとはかぎらない点である．ネットワー
ク置き換え操作には任意性があるが，より多くの文を解析できる FST を構成する上で，優先的に置き換えを適用すべき弧とそうでない弧が存在すると考えられる．本節では，弧に対する置き換え優先度を導入し，優先度の高い弧から順に置き換え操作を実行する．
まず，どのような弧を優先して置き換えるべきかについて図 5 および図 6 を用いて考える．図 5 に示す構文木を解析時に生成するためには，それに対応する図 6 のような置き換えを実行しなければならない．図 5 に示す構
文木の生起確率が高い場合，これに対応する図 6 の置き換えを実行すれば，より多くの文を解析できる FST を構成できる．逆に，図 5 に示す構文木の生起確率が低ければ，図 6 の置き換えを実行しても，その結果得られた弧は，文の解析能力に大きく寄与しない．そこで本手法では，図 6 の n をラベルにもつ弧の置き換え優先度の計算に，図 5 の構文木の生起確率を用いる．
本手法では，文法規則 1n を順にトップダウンに適用した結果として得られる構文木の生起確率を次のよ

r ; : :: ; rii0N +1; : :: ; ri 10)(3)r;:::;r3.3 置き換え操作の制限
本手法では，優先度の高い順に弧の置き換え操作を実行する．置き換え操作の適用を繰り返すにつれて， FSTの規模も大きくなる．本手法では，使用できるメモリの容量に応じて，作成可能な弧の数に制限を設定し，それを越えない範囲で置き換え操作を繰り返す．

3.4 弧の除去
前節までに述べた FST 作成手法では，非終端記号を入力ラベルに持つ弧はそのまま FST 中に残される．しかし，このような弧は解析時に使用されることはなく，これらの弧を除去しても解析性能は変わらない．さらに，これらの弧を除去することによって，解析上，不要となる弧が生まれる．このような弧を FST から除去することにより， FST のサイズは小さくなり．その分だけ新たにネットワークの置き換えが可能となり，より多くの文を解析できるようになる．
すなわち，本手法では，以下のような弧を除去する．
弧の数が制限を超えたとき，優先度の低い弧を FSTから除去する．
2. 弧の除去の結果，成功経路を構成しなくなった弧をFST から除去する．
1.

3.1

X

(i=1

式 (3) が示すように，文法規則 i の適用確率は文脈i0N +1
i01 に依存するとする．
しかし，このようにして求めた適用確率は，データのスパースネスの問題により，信頼性の高い値であるとは言い難い．そこで，線形補間法によりスムージングした適用確率を用いることとする．

nn / [ 0[=NP

NPNP/ NPYP r j rn)

ここで，成功経路とは， FST の初期状態から最終状態までを結ぶ弧の系列である． 2. において，弧が成功経路を構成しなくなったかどうかの判定は，次の通りである．
状態 から出て状態 へ入る弧 を除去するとき， から出る弧が の他に存在しなければ， から他の状態へ出る遷移ができなくなるため， へ入る全ての弧は成功経路を構成しない．同様に， へ入る弧が の他に存在しなければ，初期状態から への経路が消滅するため，から出る全ての弧は成功経路を構成しない．

peqqqqepppe

3.5 FST 構成手順
3.1 節から 3.4 節で説明した， FST 構成の手順は以下の通りである．
1.

非終端記号を入力ラベルとする弧がなければ，置き換え操作を終了する．

2.

最も優先度が高い弧をネットワークで置き換える．

3. FST
4.の弧の数が閾値を越えていなければ， 1 へ．

最も優先度が低い弧を除去する．その結果，成功経路を構成しない弧が現れたら，連続的に除去する．
3 へ．

表 1: 本手法と漸進的チャート解析の解析結果
手法
解析時間 (秒) 文正解率 (%)
漸進的チャート解析

2.8233.4

本手法

0.0588.79080706050403020100)%(率解正4 FST を利用した構文木生成
3 節で述べた手法により作成した FST を用いて，漸進的に構文木を生成する手法は以下の通りである． FST に単語を順に入力し，状態を非決定的に遷移することにより，構文木の出力を得る．そのとき，それ以前に入力された単語列に対する出力構文木を示す記号列に，遷移した弧に記述された出力ラベルを連接して，新しい構文木を生成する．

5 解析実験
5.1 実験の概要

80.4

82.4

83.8

83.9

N=2

N=3

N=4N=562.931.4

優先度不使用 N=1(PCFG)

図 8: FST を用いた解析における正解率
また，非終端記号をラベルに持つ弧を除去する効果を調査した． N=5 のとき，弧を除去しないときの正解率は83.9% であったのに対し，除去したときは 88.7% であった．

6 おわりに実験では， ATR 音声言語データベース [8] に対して作成された構文木付きテキストコーパス2 を用いた．学習デー 本稿では， CFG から FST への近似変換手法を提案し，タとして 9,081 文をランダムに抽出し，そこから文法規 それに基づく漸進的構文解析について述べた．本手法で則とその適用確率を獲得した．使用した文法規則は 698 種 は，漸進的構文解析の途中で出力する構文木をあらかじ類であり，品詞は 337 種類，範疇は 153 種類である．ま め作成し，それを FST 上に記述する．解析では，入力にた，テストデータとして 1,874 文 (平均形態素数 9.4) を用 したがって FST 上を状態遷移することにより，漸進的にい，それに付与されている構文木を正解とした．実験で 構文木を生成する．実験の結果，高い正解率を達成可能は， Pentium4 2GHz CPU，及び， 2GB メモリを搭載 な漸進的構文解析を，話者発話に追随可能な速度で実現した Linux ワークステーションを用いた．作成可能な FST できることを確認した．の弧の数は，メモリ容量の制限から， 15,000,000 を上限として設定した．

参考文献
[1]

5.2 実験結果

加藤 芳秀，松原 茂樹，外山 勝彦，稲垣 康善， \確率文脈自由文法に基づく漸進的構文解析"，電気学会論文誌， Vol.
122-C, No.12, pp.2109-2119 (2002)

本手法の性能を評価するために，漸進的チャート解析[2] 加藤 芳秀，松原 茂樹，外山 勝彦，稲垣 康善， \主辞情報との比較を行った．ただし，式 (3) の の値を 5 として付き文脈自由文法に基づく漸進的な依存構造解析"，電子情計算し，形態素あたりの処理時間を最大 10 秒に制限した．
報通信学会論文誌， Vol.86-D-II, No.1, pp.86-97 (2003).
形態素あたりの解析時間，および，文正解率を表 1に示[3] S. Matsubara, S. Asai, K. Toyama and Y. Inagaki,
す．本手法による解析時間は平均 0.05 秒であり，漸進的\Chart-based Parsing and Transfer in Incremental Spoチャート解析に比べ，解析速度が大幅に向上した．日本
ken Language Translation System", Proc. of NLPRS語の発話速度は，通常，形態素あたり 0.25 秒程度である
97, pp.521-524 (1997).という報告があり [6, 7]，これは，本手法による漸進的構[4] T. Murase, S. Matsubara， Y. Kato and Y. Inagaki,
文解析が，話者発話に追随可能な解析速度を備えている\Incremental CFG Parsing with Statistical Lexical Deことを意味している．一方，解析の正解率は 88.7% であpendencies", Proc. of NLPRS-2001, pp.353-358 (2001).
り，話し言葉の構文解析としての本手法の利用可能性を[5] E. Roche and Y. Schabes, \Finite-State Language Pro確認した．なお，比較対象である漸進的チャート解析でcessing", The MIT Press (1997).の正解率が低いのは，解析時間の制限によるものである．
次に，弧の置き換え優先度を導入する効果を測定する [6] 篠崎 隆宏, 斎藤 洋平, 堀 智織, 古井 貞煕, \話し言葉音声の認識を目指して", 情報処理学会研究報告, SLP34-22,
ために，置き換え優先度を使用しなかったとき，および，pp.125-130 (2000).
式 (3) の N の値が 1 〜 5 のそれぞれの場合について，正[7]高木 亮, 松原 茂樹, 稲垣 康善, \同時通訳コーパスを用いた解率を測定した．結果を図 8に示す．優先度を用いること
通訳者発声タイミングの分析", 言語処理学会第 8 回年次大により正解率が大幅に向上しており，置き換え戦略の重会発表論文集,
pp.383-386(2002).
要性を示している．また，文脈を考慮して文法規則の適用確率を求めることにより，正解率が向上することを確 [8] 浦谷則好，竹沢寿幸，松尾秀彦，森田千帆， \音声言語デー
タベースの構成", テクニカルレポート TR-IT-0056, ATR
認した．

N

音声翻訳通信研究所 (1994).
2 http://tanaka-www.cs.titech.ac.jp/pub/sldb-tree/