各処理の全体の処理に占める割合の測定、及び問題が大規模になった際のシス テムに与える影響の解析を行なった。
表1は、(1)最弱仮説の生成、(2)仮説束内探 索、に要する時間の、全体の処理に対する割合を示したものである。学習にか かる時間のうち、その多くが仮説束内探索に費やされていることが分かる。こ の傾向は、問題が複雑になるほど顕著であると言える。
表2は、リストを反転させる述語'reverse'を 学習させる際、与える正負事例の大きさと実行速度との関係を示したものであ る。最弱仮説の生成に要する時間は、事例数に関係なくほぼ一定であるのに対 し、サーチ処理に要する時間は与える事例数に比例して増大している。全体の 処理時間に対するサーチ時間の割合は、実に平均で99.8%、そのうちカバーチェッ ク計算には平均87.2%の時間が費やされている。
以上のことから、カバーチェック計算の効率的な並列化が、直接システム全体 のパフォーマンスに影響を与えると言える。
並列カバーチェック計算の実現方式として、トップダウン、ボトムアップの両 アプローチから、(1)複数のPrologプロセスの並列実行、(2)モデル生成型定理 証明系:MGTPの利用、(3)候補仮説本体部のSQL変換によるデータベース検索機 能の利用、の3つの方式を検討した。
(1)は複数のPrologプロセスを予め起動しておき、必要に応じて各プロセスに 対してタスクを送信する方式である。(2)はMGTPを利用することで、それぞれ の事例に対して個別にカバーチェックを行なうのではなく、一度に全ての事例 に対してカバーチェックを行なう方式である。この場合には、証明に無関係な 節の生成の抑制、値域限定条件を満たす目的などから、節の変換が必要となる。 (3)は候補仮説の本体部をSQLに変換することで、既存の並列データベースの問 い合わせ評価技術を直接、利用する方式である。
今回は、並列性との親和性、実装の容易さなどの理由から、(2)の方式を採用 した。
候補仮説を背景知識に加え、そこから得られる目的概念の基底アトム集合と、 正事例集合との共通集合を得ることで、MGTPを利用したカバーチェック計算を 実現することができる。この共通集合を得る操作を効率的に行なうために、候 補仮説の本体部に、事例を表すアトム'pos_exam'を付加する(図1)。さらに事例'p'をpos_exam(p)という形で、 MGTPの初期モデルとして登録する。 この追加されたアトムがフィルタの役割 を果たし、後処理としてではなく、推論の過程で直接共通集合を求めることが 可能となる。
このアプローチは、MGTP固有の問題である値域限定条件の回復という観点から も有効である。候補仮説は、一般に不完全であり、節の前件と後件とで入出力 関係が完成していない場合が多い。しかし候補仮説に、事例を表すアトムを付 加することで、入出力関係を完成させることができ、値域限定条件を満たす節 を得ることができる。
一般にボトムアップ計算では、目的のゴール以外に、不必要な帰結アトムを多 数計算してしまい、効率が低下する場合がある。この不必要な節の生成を抑制 する方法として、マジックセット法の適用を行なった。マジックセット法は、 節の変換によりボトムアップ推論を用いてトップダウン推論を模倣するアプロー チで、証明に無関係な節の生成を抑制することができる。一般にマジック変換 を行なうには、節の引数の入出力関係を解析する必要があるが、Progolではこ の情報をモード宣言から直接得ることができ、解析なしに容易に変換を行なう ことができる。さらにこの変換は、MGTPの値域限定条件を自動的に回復してく れる場合が多く、MGTP利用の観点からも有益であると言える。
Progolでは、学習された知識の追加、仮説束内探索中に動的に生成される候補 仮説の評価など、動的に変化する知識を扱う必要がある。しかし従来のMGTPで は、MGTP節をKL1プログラムに変換しコンパイルする方式を採用しているので、 高速ではあるが、節の追加や削除といった知識の動的な変化に対応することは 不可能である。一方、昨年インタプリタ方式のMGTPが開発された。これにより 知識の変化に対応することは可能となったが、従来のものと比較して実行速度 が遅いという欠点がある。
そこで、高速なコンパイル方式と、知識の動的な変化に対応できるインタプリ タ方式の両方の特徴を活かしたHybrid MGTPを試作し、カバーチェック計算部 に適用した。最初にシステムに与える知識に関しては従来のコンパイル方式を、 学習の途中で動的に生成される知識に関してはインタプリタ方式を、それぞれ 適用させるというのが基本的なアイディアである。これにより、高速かつ知識 の動的な変化に対応できるカバーチェック計算部が実現された。またMGTPを基 礎においているので高い並列性が得られると予想される。
生成された仮説に対する利用者の理解を助ける、及び正事例、背景知識といっ たシステムに与える知識の動的な修正(デバッグ)を行なう、という2つの目的 で利用環境の設計を行なった。
学習された仮説を利用者に提示する際、その仮説によって説明される正事例、 及び説明に必要な背景知識を合わせて表示する機能を、システムのインタフェー ス部に付加することとした。こうすることで、単に学習された仮説のみを提示 する場合に比べ、利用者の仮説に対する理解を深めることができる。
学習の際、正事例や背景知識の欠落により、仮説の生成が困難な場合がある。 この問題を解決する一つの方法として、正事例、背景知識を漸増的に追加する 機能、つまり知識のデバッグ機能をシステムに付加することがあげられる。現 在与えられている背景知識に対して、仮説をボトムアップ的に適応することで、 その仮説によって説明される、目的概念の基底アトム集合を抽出することがで きる。この集合の要素は、仮説によって説明される概念なので、正事例の候補 と考えることができる。この候補集合と、既与の正事例集合との差をとり、そ の要素を正事例として追加するかを利用者に問い合わせることで、対話的かつ 漸増的に正事例を増加させることが可能となる。
また、必要な背景知識の欠落により、本来仮説によって説明される正事例が説 明されない場合がある。この場合、背景知識の欠落により説明されなかった事 例と、説明に必要な(現在欠落している)背景知識の両方を利用者に提示し、問 い合わせることで、背景知識の動的な修正を行なうことが可能となる。