(15) 一般化 LR 法を用いた頑健な並列構文解析に関する研究

［目次］

1. 研究の背景
2. 研究の目的
3. 研究の内容
4. ソフトウェア成果

［研究の背景］

しかし，これまでの自然言語解析ツールは，システムの文法に適合する文のみ を受理するものが主であった．システムが現実に処理するテキストや対話文に は，様々な非文法的表現や誤りがしばしば現れるため，入力文が文法的に正し いと仮定する従来の解析ツールは，適用範囲が広く柔軟な処理を要求する実用 的なシステムには必ずしも適していない．ここで，非文法的表現や誤りを含む 文を「不適格文」とよび，不適格文を処理する能力をもつシステムを「頑健な」 自然言語処理システムとよぶ．近年研究が活発な対話を処理する場合には，文 法から逸脱した文は日常的であると考えられ，文法に適合しない文をも受理で きる頑健な自然言語解析ツールの需要は高まっていると考えられる．

しかし，頑健な自然言語解析を行なう際には，計算量が膨大になるという問題 がある．これは，不適格文を受理するために，通常の制約(文法など)を緩和す るため，探索空間が大きくなるからである．長さが同じ適格文の解析よりも数 万倍の解析時間が不適格文の場合には必要になることがある．このように，頑 健な自然言語解析システムを実現するには，膨大な計算量の問題を克服しなけ ればならない．これに対する有望な解決法としては，処理の並列化が考えられ る．最近のVLSI技術の進歩には著しいものがあり，従来では不可能であったよ うな計算パワー，メモリ空間が容易に得られるようになってきた．さらに，数 万オーダのプロセッサを持つ並列マシンを実装することも可能になってきてい る．並列マシン上でのプロセスの並列化は，頑健な自然言語解析の計算量の問 題に対する一つの解決法を提供する．

［研究の目的］

本研究の目的は，以下の通りである．（１）並列論理型言語 KL1 を用い，並 列環境 PIM/PIMOS 上で動作する頑健な構文解析ツールおよび，（２）KLIC を 用い，ワークステーションなどの汎用計算機上かつ UNIX 環境で動作する頑健 な構文解析ツール，を開発・整備する．（１）においては，頑健な構文解析ツー ルの並列アルゴリズムの提案および，並列環境での実装および，実験による有 効性の評価を目的とする．（２）においては，他の自然言語処理研究者への提 供を前提とし，（１）のアルゴリズムをベースにした，UNIX 環境の汎用計算 機上で効率的に動作する頑健な構文解析ツールの開発を目指す．また，これま でに整備されている自然言語処理資源のうち，計算機用辞書EDR，自然言語解 析ツールjumanとの接続を行ない，これからの自然言語処理研究に有用な研究 環境を提供することを目指す．

［研究の内容］

我々は，1993 年から昨年までの 2 年間の委託研究(東工大，田中研究室)で， チャート法に基づく並列で頑健な構文解析法を PIM 上で開発した．256 プロ セッサを用いて長さ 6-18 の不適格文を解析した結果，60-170 という，高い 台数効果が得られた．本研究では，この研究から得られた知見を生かしながら， 逐次マシンでもっとも高速な構文解析アルゴリズムの一つといわれている一般 化 LR 法をベースにした頑健な並列構文解析法を提案し，並列マシン上および 汎用計算機上で動作するツールを開発する．

一般化 LR 法では，使用される文法を予め，先読み語を含む動作表(LR 表とよ ぶ)にコンパイルし，この表を用いて入力文の解析を決定的に行なうため，高 速な解析が実現できる．また，最近音声認識の言語処理部に一般化 LR 法がよ く用いられるが，これは一般化 LR 法の解析速度のメリットだけでなく，一般 化 LR 法が音素レベル，形態素レベル，そして，構文解析レベルの制約を統合 して処理できる点が注目されるからである．これらのことから，不適格文が日 常的である音声対話理解などには，一般化 LR 法を用いた頑健な構文解析シス テムは有用であると考えられる．

1990 年に沼崎らは，一般化 LR 法を並列論理型言語により実装する手法を提 案し，64 台構成の並列マシン Multi-PSI 上で実験を行ない，10 倍程度の台 数効果を得ている．本研究では，この研究を踏まえ，一般化 LR 法を用いて不 適格文を解析するアルゴリズムを並列論理型言語を用いて並列環境に実装する． その際，これまでの不適格文解析研究で扱ってきた終端記号(単語)レベルの誤 りだけでなく，非終端記号(句)レベルの誤りにも対処できる枠組を実現し，よ り多様な誤りを含む文をも扱える構文解析ツールを目指す．

また，不適格文解析では，通常の構文的曖昧性だけでなく，誤りの位置とタイ プによる曖昧性も存在するため，得られる解析結果の数が非常に多くなり，そ れらをすべて出力した場合，その中から妥当なものを選択するのは容易なこと ではなくなってしまう．そこで，頑健な構文解析ツールでは，解析結果にスコ アをつけ，スコアの低い結果を妥当でないものとして排除し，妥当な結果のみ を，その妥当性の順に出力する機能が必要である．本研究では，誤りの位置， 誤りのタイプ，誤りの数，そして，誤りの(入力文中での)範囲を尺度として， 解析結果にスコア付けを行なう．また，既存の計算機用辞書EDRの共起辞書， 概念辞書を用いることで，単語(概念)間の意味的整合性をベースにした解析結 果のスコア付けの手法も検討する．

開発環境は，PIMOS 上と UNIX 上の両方である．前者において並列アルゴリズ ムを実装し，並列度の評価を行なう．後者では，KLIC でプログラムを記述し， 既存の計算機用辞書EDRや形態素解析器jumanと連結する．入力文をEDR単語辞 書で辞書引きした結果，あるいはjumanを用いて形態素解析した結果，得られ る品詞列を入力とし，構文解析結果を出力するプログラムとして，頑健な構文 解析ツールは動作する．

［ソフトウェア成果］

(1)作成されるソフトウェア名称

頑健な並列構文解析プログラム

(2)そのソフトウェアの機能／役割／特徴

1. 本ソフトウェアは，予め与えられた文脈自由文法のもとで，入力文(自然言 語)に対する構文解析結果を出力する．この解析結果が，それに続く意味解析， 文脈解析，推論などの処理プロセスの入力となる．また，一般化 LR 法に基づ いた構文解析アルゴリズムを採用しているので，高速な解析が実現できる．

2. 本ソフトウェアは，これまでの構文解析ツールのように，システムの文法 に適合する文だけでなく，不適格文をも受理できる頑健な構文解析ツールであ る．その際，文法に適合する文に対しては，不必要な誤り解析は行なわないの で，無用な効率の低下を引き起こさない．

3. 並列アルゴリズムの効率を決定するのは負荷分散方式である．負荷分散方 式としては，動的負荷分散方式，静的負荷分散方式，要求駆動による動的負荷 分散方式などが考えられる．これらの負荷分散方式にはそれぞれ利点，欠点が あるので，本ソフトウェアでは，これらの負荷分散方式からユーザが自由に選 択し実行できるような機能を用意する．

4. 従来の構文解析プログラムは，解析結果が複数得られる場合，それらをた だ任意の順にすべて出力するものが多い．本ソフトウェアでは，解析結果にス コアをつけ，スコアの低い結果を妥当でないものとして排除し，妥当な結果の みを，その妥当性の順に出力する機能を提供する．スコア付けの手法としては， 誤りの位置，誤りのタイプ，誤りの数，そして，誤りの(入力文中での)範囲な どの構文的要素に基づくものおよび，EDR共起辞書，概念辞書を用いた意味的 要素に基づくものを予め用意し提供するが，ユーザがスコア付けの手法を自由 に設定する機能を追加することも検討する．

5. 本構文解析プログラムには，与えられた文法や入力文のデバッグを支援す るのに必要不可欠な解析過程のトレーサが用意されている．