初年度の研究では、自然言語解析等のアプリケーションを記述にむけて、まずは既存 の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の推論エンジン
ソフトウェア名: lmgtp.kl1
記述言語処理系: KLIC
プログラム行数: 517行
機能: 動的補題生成を組み込んだMGTPの推論エンジン
研究内容(1)、(4)の成果である。実験的な使用のために補題の要求回数や枝刈りの効 果に関する統計情報を採取でき、オプションとして、左右の優先探索および、上下の 補題要求を選択できる。また、従来の推論エンジン(MGTPおよび、CMGTP)と違和感な く使用することができる。
MGTP処理系の入出力整備および記述力の向上
ソフトウェア名: mg2klic.kl1, (wt-unify.kl1), mgtp.pl
記述言語処理系: KLIC, perl
プログラム行数: 781行(KLIC), 68行(perl)
機能: MGTPプログラムからKL1言語へのトランスレータ及び、
MGTPプログラムから実行形式までの変換処理を統合するスクリプト
研究内容(5)の成果である。
MGTP上でアプリケーションを記述するために、現在のMGTPの記述力を強化した。これ により、MGTP節の前件のどの位置にもガードが配置でき、後件部には KLIC で記述し た述語をアクションとして配置できるようになった。アクション記述の付加により MGTPプログラム中に KLIC プログラムを埋め込むことができるようになったため、 KLICユーザが、KL1のアプリケーション中でMGTPを推論エンジンとして使用するこ とも可能であり、今後KLICユーザへのMGTP普及に貢献すると考えられる。
入出力については、上記のアクション記述により KLIC の入出力がそのまま使用でき るようになったため、外延データを変更する度に、MGTPプログラムからKLICへの翻訳 系を通し、さらにKLICによるコンパイルという手順を辿る必要がなくなった。これに より、来年度のアプリケーション記述に向けて、最低限の環境は整った。
本トランスレータはMERC法による前件部マッチを実用的なものとして採用し、他のア ルゴリズムは実装していない。また、弁別木を用いた項メモリも標準的な手法として 採用し、変換後、弁別木の添字情報を出力する仕様になっている。また、MGTPプログ ラムから、KL1言語への変換、KLICによるコンパイル、推論エンジンとのリンクとい う煩雑な作業をperlスクリプトにより統合し自動化した。
今後、さらに必要に応じて環境の整備をしていく予定である。
文脈自由文法から構文解析を行うMGTPプログラムへのトランスレータ
ソフトウェア名: cfg2mg.kl1
記述言語処理系: KLIC, perl, (bison)
機能: LALR(1)表に基づく構文解析、および、左隅構文解析を行うMGTPプログ
ラムを
文脈自由文法から生成するトランスレータ
研究内容(2)の検討のためのプログラムである。
MGTP上での自然言語アプリケーション記述の例であり、ナイーブな構文解析器である。 現在、作成中であり、今年度中の完成を予定している。
残された課題
初年度は、MGTP上で自然言語アプリケーションを記述するための、MGTPの推論技術、 実行環境の開発、整備が目的であった。来年度は、初年度の研究で新たに見つかった 改良点、たとえば、folding up や regressive merging といった強力な補題生成手 法のMGTPへの実装などを引続き行う。同時に、予定の自然言語アプリケーションの記 述について調査検討を行い、関連ソフトウェアを開発する。
自己評価
初年度の目標として掲げていた項目については、研究内容および、ソフトウェア成果 について概ね予定どおり達成できた。しかし、今年度の調査研究によって新たに改良、 発展させるべき点が見つかったため、予定通り来年度のMGTP上のアプリケーション記 述に完全に移行する前に、引続き初年度の研究を完結させる必要がある。
