研究の成果

初年度の研究では、自然言語解析等のアプリケーションを記述にむけて、まず は既存のMGTPの証明機構を強化し環境整備をおこなうことが主な狙いである。 上記項目では、(1)、(4)、(5)について成果をあげ、(2)に関して着手検討して いるところである。

研究上の成果

動的補題生成法の導入

研究内容の(1)、(4)にあたる成果である。

強力な証明の枝刈り手法である補題生成法を導入し、補題を制約とみなして効 率良い伝搬を行うための手法を開発、実装した。 まず、補題生成手法の一つ であり、タブロー法で factorization の実装法として知られている folding down に着目し、制約MGTP上での実装と評価を行った。folding down は静的な 補題生成手法とみなすことができ、分岐したモデル間で通信を行う必要はない ために、実装はシンプルであり基本的には制約MGTPに入力として与える節を folding down 用に変換するだけでよい。

しかし、folding down のような静的な証明手法では、補題を証明の最初に天 下りに与えなければならないため、無駄な補題の与え方をしてしまうと逆効果 になってしまうことがある。また、補題の与え方はあらかじめ予測が困難であ る。そこで、証明を進めながら必要に応じて動的に補題を生成するための動的 補題生成法を開発、実装した。本実装に当っては、分岐したモデル間の通信量 を抑えるために、局所的に補題候補集合を儲け、可能な限り局所的に補題生成 ができるよう配慮した。

上記の両手法について、定理証明の標準的ベンチマーク問題であるTPTPの問題 を対象にKLICを用いて逐次マシン上で評価実験を行ったところ、folding down では、枝刈りの効果はみられたものの最初に静的に与える補題によって枝数と 証明時間に大きくな影響がでてしまった。一方、動的補題生成法では、枝刈り ができる可能性がある場合は常に一定の効果をあげることができ、モデル間の 通信を伴うにもかかわらず証明時間でも folding down を上回る良好な結果を 得た。

今後は、並列環境下での実験を行う予定である。動的補題生成法はサブゴール の選択関数に依らすに、補題を生成する戦略を用いているため、並列環境下で も効果を上げることが期待できる。また、タブロー法の強力な枝刈り手法とし て知られている、folding up や regressive merging と同様の手法をMGTP 上 に導入しさらに証明機構の強化をはかる予定である。

構文解析への応用

研究内容(2)の来年度に向けた検討のために、LALR(1)および、BUPを対象に構 文解析器をMGTPプログラムで記述した。

LALR(1)については現在のところ、コンフリクトが生じると解析木をコピーし 以後独立して解析を続けるナイーブな方法である。BUP については、同様の左 隅構文解析法を行う MGTPプログラムが記述できる。いずれも、文脈自由文法 からMGTPプログラムに変換可能である。

今後、分岐したモデル間での通信技術を用いてLALR(1)表に基づく構文解析の 洗練を行い、各フレーム等の制約を加えていく予定である。

ソフトウェアとしての成果

以下の図１にソフトウェア構成の概要を 示す。網のかかっている部分が本研究で作成したソフトウェアである(cfg2mg については、現在実装中)。

  
図１: ソフトウェア構成の概要

動的補題生成を組み込んだMGTPの推論エンジン

研究内容(1)、(4)の成果である。実験的な使用のために補題の要求回数や枝刈 りの効果に関する統計情報を採取でき、オプションとして、左右の優先探索お よび、上下の補題要求を選択できる。また、従来の推論エンジン(MGTPおよび、 CMGTP)と違和感なく使用することができる。

MGTP処理系の入出力整備および記述力の向上

研究内容(5)の成果である。

MGTP上でアプリケーションを記述するために、現在のMGTPの記述力を強化した。 これにより、MGTP節の前件のどの位置にもガードが配置でき、後件部には KLIC で記述した述語をアクションとして配置できるようになった。アクショ ン記述の付加により MGTPプログラム中に KLIC プログラムを埋め込むことが できるようになったため、KLICユーザが、KL1のアプリケーション中でMGTPを 推論エンジンとして使用することも可能であり、今後KLICユーザへのMGTP普及 に貢献すると考えられる。

入出力については、上記のアクション記述により KLIC の入出力がそのまま使 用できるようになったため、外延データを変更する度に、MGTPプログラムから KLICへの翻訳系を通し、さらにKLICによるコンパイルという手順を辿る必要が なくなった。これにより、来年度のアプリケーション記述に向けて、最低限の 環境は整った。

本トランスレータはMERC法による前件部マッチを実用的なものとして採用し、 他のアルゴリズムは実装していない。また、弁別木を用いた項メモリも標準的 な手法として採用し、変換後、弁別木の添字情報を出力する仕様になっている。 また、MGTPプログラムから、KL1言語への変換、KLICによるコンパイル、推論 エンジンとのリンクという煩雑な作業をperlスクリプトにより統合し自動化し た。

今後、さらに必要に応じて環境の整備をしていく予定である。

文脈自由文法から構文解析を行うMGTPプログラムへのトランスレータ

研究内容(2)の検討のためのプログラムである。

MGTP上での自然言語アプリケーション記述の例であり、ナイーブな構文解析器 である。現在、作成中であり、今年度中の完成を予定している。

残された課題

初年度は、MGTP上で自然言語アプリケーションを記述するための、MGTPの推論 技術、実行環境の開発、整備が目的であった。来年度は、初年度の研究で新た に見つかった改良点、たとえば、folding up や regressive merging といっ た強力な補題生成手法のMGTPへの実装などを引続き行う。同時に、予定の自然 言語アプリケーションの記述について調査検討を行い、関連ソフトウェアを開 発する。

自己評価

初年度の目標として掲げていた項目については、研究内容および、ソフトウェ ア成果について概ね予定どおり達成できた。しかし、今年度の調査研究によっ て新たに改良、発展させるべき点が見つかったため、予定通り来年度のMGTP上 のアプリケーション記述に完全に移行する前に、引続き初年度の研究を完結さ せる必要がある。