仮設推論における準最適解を多項式時間で計算するネットワーク化バブル伝搬法

概要

論文の詳細を見る
論理に基づく仮説推論は,理論的な基盤性と診断や設計に応用できるといった実用性の両面で,知識処理の重要な枠組みである.しかし,仮説推論の最大の課題はその低い推論速度である.実用的に実行可能な推論速度を達成するため,コストに基づく仮説推論に対しこれまでに0-1整数計画法の近似解法である掃出し補数法(Pivot and Complement Method)が適用され,多項式時間での求解が達成されている.この手法は要素仮説に重みを与え,解仮説の要素の重みの和であるコストを最小にする仮説推論において,知識を制約とみなして制約不等式に置き換え,0-1整数計画法を適用する.仮説推論の計算複雑度はNP完全またはNP困難であるが,0-1整数計画法の近似解法を用いることにより,Nを可能な要素仮説の数とするとN^4オーダの計算時間で準最適解を求めることができる.本論文では,知識処理的な視点からこの高速な数理計画法のプロセスを理解し,同時に更に高速な推論を達成するという目的から掃出し補数法の動作を知識ネットワーク上で実現する.ネットワーク化バブル伝搬法と名づけたこの推論手法の動作は知識処理の視点から理解しやすく,その性能は上記の手法と同等のあるいはこれを上回る.特に推論速度の点では,知識の構造的情報を有利に利用できるためN^2オーダの計算時間を得た.
1994-09-25

仮設推論における準最適解を多項式時間で計算するネットワーク化バブル伝搬法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク