研究の成果

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

再インプリメントによる使用仮想記憶領域等の改善

これまでにインプリメントされていたNBP法による命題版仮説推論システムは、 使用仮想記憶領域が非常に大(200MB)になってしまっており、より大きな知識 ベースへの拡張が困難になっていた。記憶領域の使用法を改善、整理を中心に した再インプリメントを行い、実用規模の知識を扱えるように改善した。

NBP法のインタフェース作成

重み付き仮説推論の準最適解を低次多項式時間で求めるNBP法は、速度性能は 優れているものの、その動作は必ずしも理解しやすいものではない。これは、 望ましい解が得られない場合の知識修正やデバッグ時に問題となる。この問題 を緩和する一つの方法は良いユーザインタフェースを提供し、NBP法の動作が ビジュアルに追えるようにすること、知識制約の修正、改訂を容易にして異な る条件下でNBP法を再動作できるようにすることである。

ここでは使いやすいツールとするために、次のことに留意して作成を進めた。

• X ウィンドウ システム上で、ネットワークとして推移が可視なものとする。
• X ウィンドウ システム上ですべての操作が簡便に行なえるツールとする。
• 知識ベースの編集機能を付加する。
• 拡大・縮小機能をつける（ネットワークの表示のため）。

1. ネットワーク化
2. インタフェース

ネットワーク化について

ネットワーク化について

知識ベースから知識を読み込んできてからNBP法の推論ネットワークを形成す るわけであるが、まずこのネットワークの簡単化と表示法について記す。

NBP法で扱う知識は与えられたゴールに関係するものだけに限定するため、こ のゴールを起点としてトップダウンの後向き推論で、このような関係のある知 識のみを抽出する。更に、
a:-c,d.
d:-h.
という知識があり、この“d”が他に出現しないときは、
a:-c,h.
の知識にしてしまうことにより、ネットワークの簡略化を図る。このようにし てネットワークのノード数を減少させることは、NBP法の効率化と共に、表示 するネットワークの簡略化を可能とし、見やすいものにすることができる。

伝播パスについて

NBP法の伝播パスとは支配リンクの上流を除いた領域であり、この伝播パスの 影響範囲のノードが、基底と非基底の交換の候補になる。この範囲がどのよう に絞られているかというのが、NBP法が単純な整数計画法の近似解法の適用に 比べた効果を示すことになる。よって、この伝播パスの領域がどうなっている かを知ることは、NBP法にとって重要である。

今回のツールの中では、伝播パスの領域を赤くフラッシュさせることでその領 域を示し、どの程度の効果が上がっているのかを視覚化している。

ネットワークの描写上の工夫

ネットワークの規模は、知識ベースによってさまざまである。中には非常に簡 単な構造のネットワークになる場合もあるし、非常に膨大な規模のネットワー クになる場合もある。その異なる規模ごとに効果的な表示法を指定するのはな かなか容易ではない。

知識や仮説数が莫大になってくると、ノードの数も増え、ネットワークが非常 に見にくくなってしまう。できるだけそのような問題を回避するために、ここ ではノードの位置を以下のようにした。

• ゴールは頂上に配置。
• 次からのノードは、深さによって下の段の右、左、右、・・というように、 なるべく均等な位置になるように表示を工夫している。すると、ネットワーク は必然的にツリー上に見やすくなる。
• 深さは、順次深くしていく。

  
図１: ツリー上に配置された ノード

これらの工夫によって、ネットワークをなるべく見やすいものにしている。図１にネットワークの表示例を示す。

インタフェースについて

X ウィンドウ システムによるユーザインタフェース

ツールとして使いやすいものにするため、X ウィンドウ システムの上ですべ て動くようなものにした。起動から終了まで、X ウィンドウ システムの上で 操作ができるように設計した。そのため、X ウィンドウ システムの上で働く ような機能をいくつか備えることが必要であり、そのためのインターフェース 部分を記述するためにCを基礎としたTcl/Tkを使用した。それによって以下の ような機能を持つことができ、X ウィンドウ システム上で動くツールという 形を整えている。

知識ベースの編集

例えば、ある知識ベースに基づく動作をNBP法が示し結果を得たとする。この 結果を見て、次のようなことを考えるのはよくあることである。

• 与えられた結果が気に入らなくて、その結果をinc(矛盾)として加え、他 の解を求める推論をもう一度行わせたい時
• 他のルールを加えたくなった時
• あるルール・条件を外したくなった時

ネットワーク表示における拡大・縮小機能

知識ベースの規模が大きくなってくると、ノードの数はルールの数以上に増え ていくので、表示のネットワークがかなり大きくなる。しかし、推論の推移を 見ていく上で、ネットワークの全体を見ていく視野や、ある部所に集中して注 意を払う視野を持つことは、推論の流れを掴む上でも重要であり、ユーザ自身 が推論の流れに参加していくきっかけにもなる、推論の流れをつかむことや、 どのノードがどのような働きをしているかなどということが分かりやすくなる。 そして何より、自分の見やすいように見たいという基本的な欲求が満たされる ことは、ユーザのストレスを軽減し、誤りの回避や知識等のデバッグを容易と する。

以上に基づいて設計、作成したインタフェースの使用状況を、図２に示す。

  
図２: 現在のインタフェースの 使用状況

残された課題

準最適解の多項式時間仮説推論を達成するネットワーク化バブル伝播法(NBP法) の効率的な再インプリメントとユーザインタフェース部の作成を行った。使い 勝手は向上したが、以下のような課題が残されている。

1. より完全なモジュールとしての機能
   他手法との結合を前提としたソフトウェアモジュールとしての働きも設計構想 に含まれていたわけだが、今回は他のソフトウェアから結合して使用する実験 を行うことはできず、モジュールとしての働きを十分に検証できていはいない。
2. NBPネットワークの視覚化については、記号的知識とビジュアルなネット ワーク上のノードやリンクとの対応を容易に理解できるようにする、特定の知 識・命題記号を指定して推論プロセスでこれらがどのように動作するのかを重 点的に見えるようにするなどの機能拡張が望まれる。
3. 述語論理への拡張に対する指針
   今回作成したソフトウェア及びインタフェースは、命題論理に基づくNBP法で ある。知識ベースに述語論理を含む場合の方法として、ネットワークの段階的 拡張による方法やQSQR法を用いた方法などが考案されており、本命題論理版 NBP法ソフトウェア及びKLICを利用して、述語版仮説推論システムとする。

自己評価

速度性能に優れているNBP法のアルゴリズム自体はほぼ確定していることから、 ここでは広く利用できるソフトウェアツール化することを主要なねらいとして きた。アルゴリズムを創案した学生が博士学位を取得して卒業したため、イン タフェースの作成・ツール化を別の学生に引き継いで行った訳であるが、基本 アルゴリズムの理解と存在していた初期プログラムの解読に時間を取ってしま うことになった(これは大学でのソフトウェア開発の一般的な課題であるとい える)。

期待していた進行状況よりやや遅れ気味というのが自己評価である。後期１年 の述語版NBP法ソフトウェア開発で追い付くようにしたと思っている。