複雑な問題を解こうとする時,我々は試行錯誤だけで答えを得ることはしていない.目星を立てて,その後意識しない内に次第に解に近づいて行くことが多い.この論文は,計算機にその様なプロセスを実行させる試みである.知識を表現する新しいタイプのネットワークの上でそれを実現することにより,自動的に知識の構造も考慮した高速仮説推論を行う.

　仮説推論の問題を0-1整数計画問題に帰着し,0-1整数計画問題の多項式時間の近似解法である掃き出し補数法を適用した従来研究では,推論速度の点で有為な成果を納めている.しかし,その有効性はPC法を用いることを決めた時点で予想されていた.知識処理の問題を変換して数理計画法の領域での解法を得たものであり,元のPC法はBalasの論文によって十分効果を見い出されていたからである.しかし,動作中は数字の羅列ばかりで推論中のプロセスが元の知識をどう反映しているのか把握しにくかった.これは,与えられた背景知識を制約と見なす際にそれを不等式の集合,即ち制約充足する多面体として扱うからである.この多面体にはもはや,元の知識の構造の名残を見いだすことも難しい.もしさらに知識が付け加わった場合には,新しい多面体を切り出し直さなければならず,それまでの推論のプロセスも結果も参考することができなくなる.

　では,知識の構造を見やすい形でPC法の高速メカニズムを実現できるとすれば,それはどの様な形であろうか.構造とは部分と部分との関係の集合であるから,知識を構成する各部分は陽な形で異なる位置に配置され,しかも関係が知識に示された部分間にはリンクを与えなければならない.その様な性質を持つ知識表現を知識ネットワークと呼ぶ.例えば,推論パスネットワークやSLD導出木は知識ネットワークである.

　この知識ネットワーク上で推論プロセスを実現できれば,先ず第1に知識処理の観点から理解し易いものとなり,第2に知識構造をネットワークを媒介として利用できるので更なる高速化も可能となる.第1のメリットは本論文の第6章で表現の枠組みを拡げた場合への拡張に,第2のメリットは次章以降の随所で実現を示される.

　本論文は「多項式時間で仮説推論の準最適解を求めるネットワーク化バブル伝播法に関する研究」と題し、知識処理の重要な枠組みである仮説推論の低い推論速度という大きな課題の克服を図る、ネットワーク化された知識上で動作する高速推論手法を提示している。

　第1章「序論」では、本論文で対象とする論理に基づく仮説推論の原理、関連研究、実用的応用について説明している。そして、仮説推論は仮説という否定される可能性を有する知識を扱うために推論の非単調性が生じ、一般にNP完全問題となり、厳密解を得ようとすると問題規模に対して推論時間が最悪値で指数的に増大してしまうという点が最大の課題になることを論じている。この課題の克服に向けて、要素仮説に数値的重みを付して解仮説に含まれる要素仮説の重みの和を解のコストとし、それを最小とする解を求めるコストに基づく仮説推論において、準最適解を計算する効率的推論手法を考案することが有力なアプローチとなることを論じている。

　第2章「従来の研究から数理計画法のネットワーク化へ」では、これまでの仮説推論の効率化の研究を概観している。第1章に述べている視点からの効率的化に際しては、記号操作による推論よりも仮説推論の論理的知識を等価な不等式表現に変換し、数理計画法、特に0-1整数計画法の問題に変換して解くアプローチの有効性が見い出されていることを述べている。そして、人工知能の推論技術とこれまで主としてオペレーションズリサーチ分野で研究が展開されてきた数理計算法の手法との融合が、本研究の重要な視点となっていることを述べている。

　第3章「ネットワーク化バブル伝播法(命題論理版)」では、まず先行研究となった0-1整数計画法の近似解法である掃出し補数法(pivot and compliment method)を用いることにより、問題規模に対して多項式時間で準最適解を計算するコストに基づく仮説推論法について説明している。掃出し補数法は大略、まず第1フェーズで0-1整数条件を緩和して単体法で初期実数最適解を求め、次いで第2フェーズで近傍探索によりこの周囲で制約を充足する0-1整数解を求め、第3フェーズでより良い0-1整数解を局所探索により求めて、これを準最適解とする。この方法は大変有効であるが、知識処理の観点から見ると0-1整数計画法の部分の動作がブラックボックス的となり、知識構造等を考慮した改善が困難であることを指摘し、本研究を開始する契機となったことを記している。

　創案、開発した手法は上記の掃出し補数法と同等のプロセスを、ネットワーク化した命題論理表現の仮説推論知識上で動作させるものであり、「ネットワーク化バブル伝播法(NBP法)」と名付けている。ネットワークのノードは[0,1]間の実数真理値をとり、リンクで結ばれたノード間でこの真理値の変化を伝播させて状態を遷移させることにより、最終的に準最適解の状態に収束させる。掃出し補数法で最も時間のかかる第2フェーズの基底変数と非基底変数の有効な交換に相当する操作を、ネットワーク化した知識上では知識の構造的情報を利用して効率化する方法を明かにしている。これを実装し、実験を通して元の掃出し補数法の利用を上回る、可能な要素仮説数をNとするとN²オーダの多項式時間のコストに基づく命題論理版仮説推論が達成できることを明かにしている。

　第4章「NBP法の計算量とネットワーク構造の関係」では、知識間の矛盾の定義により知識のネットワークが複雑になると仮説推論の速度は低下するが、このような知識構造と仮説推論の計算複雑度との関係を新たな視点から論じている。これにより、単結合ネットワークを含むあるクラスの知識構造の場合には、非常に高速に厳密解が得られることを見い出している。また、推論の進行と共に問題の複雑さが解消されていくメカニズムも描き出している。

　第5章「知識の実行時リフォメーションによる高速化」では、論理回路設計分野で開発された多段化による論理回路最小化の技術を導入して、知識ベースの論理式を編成し直すことによる推論の効率化法について記している。この再編成後にネットワーク化バブル伝播法を適用することにより、仮説推論の速度を向上できることを実験により示している。

　第6章「述語論理への拡張」では、命題論理表現の仮説推論に対して開発したネットワーク化バブル伝播法を、述語論理表現の仮説推論へと拡張する方法を提示している。対象の知識は、関数なしで変数は含むがレンジ限定(range restricted)の述語ホーン節である。述語表現はエルブラン領域で展開すれば命題表現に変換可能だが、知識数が増え過ぎてしまい実用的でなくなる。ここでは、述語ホーン節を変数間の関係に対する制約と見なすことにより、これらの変数間にネットワーク化バブル伝播法を適用させることにより仮説推論を達成する方法を明かにしている。また、推論のゴールを起点とするトップダウン推論により、ネットワーク化バブル伝播法の適用対象となる知識を段階的に追加していく方法を採用することにより、過大な範囲の知識への適用を回避し、述語ホーン節の再帰呼出し構造にも対処して、適正な深さの推論で準最適解を見い出すことを可能にしている。この手法を実装し、実験により達成した推論速度を示している。

　第7章は「結論」であり、本論文の成果をまとめている。

　以上これを要するに、知識処理の重要な枠組みであるにもかかわらず低い推論速度が大きな課題となっていた仮説推論に対して、ネットワーク化した知識上で動作し、解のコストに関して準最適解を多項式時間で計算する高速推論手法を創案、開発している。これは、記号操作を主体としてきた人工知能の推論手法と、数学的手法により多次元実数空間で制約を充足する最適値の探索を行なってきた数理計画法の手法との間に橋渡しを可能にしたという点でも意義が大きく、電子情報工学上貢献するところが大である。

　よって、著者は東京大学大学院工学系研究科電子工学専攻における博士の学位論文審査に合格したものと認める。