コストに基づく仮説推論の2種の連続値最適化問題への置換法とその協調による推論法
スポンサーリンク
概要
- 論文の詳細を見る
仮説推論は, 真か偽か不明な事柄をとりあえず真と考えて推論を進め, 矛盾なくゴールを導くことができれば立てた仮説は正しかったと考える推論形式である.コストに基づく仮説推論は, 各仮説に付与されたコストの和を最小とするような仮説の組を最も望ましいものとする.しかし, コスト最小の仮説を見つける問題はNP困難となるため.コストが最小に近い準最適解を多項式オーダの推論時間で求める研究が行われてきた.従来手法であるNBP法やSL法は多項式オーダの推論時間で準最適解を得ることができるが, これらは仮説推論問題の各ホーン節を不等式制約で置き換えることにより, シンプレックス法を利用してコストの低い解の目星を付け, その近傍を探索する手法である.一方, 仮説推論と関連の深いSAT問題に対しては, 陽には示されていないものの, 各節を非線形等式で置き換えて得られた問題をさまざまな方法で解くアルゴリズムが提案されている.本論文では, 仮説推論で従来から用いられてきた節を不等式制約に置き換える方法(置換Lと呼ぶ)と, 等式制約に置き換える方法(置換NLと呼ぶ)を統合することを試みる.置換Lはコストの低い解を見つける働きが強く, 置換NLは実行可能解を見つける働きが強いため, これらをうまく統合することにより, コストの低い解が得られることが期待される.2種類の異なる置換法による制約を扱うために, 本論文では並行計算の手法の一つである拡張ラグランジェ法を利用し, 変数と制約をそれぞれプロセッサと考えることで, 制約の付加・除去を実現する.そして, 初期フェーズでは, 置換Lによる制約プロセッサにより探索を行い, 以降のフェーズでは置換NLによる制約プロセッサを追加していくアルゴリズムを提案する.置換NLによる制約プロセッサをどのように追加していくかに関して, 論文中では2種類の戦略を紹介する.評価実験として, 集合被覆問題および最短経路問題をもとにした仮説推論問題に対して推論時間および解のコストを比較する.それにより, 従来手法と同程度の探索時間でコストの低い解を得られることを示す.
- 2001-09-01
論文 | ランダム
- テーラワーダ仏教の教科書(第16回)五戒を守ることは仏道を歩むこと(7)まとめ
- テーラワーダ仏教の教科書(第15回)五戒を守ることは仏道を歩むこと(6)不殺生戒(その2)対話編
- テーラワーダ仏教の教科書(第14回)五戒を守ることは仏道を歩むこと(5)不殺生戒(その1)殺してはならない理由(わけ)
- テーラワーダ仏教の教科書(第13回)五戒を守ることは仏道を歩むこと(4)不偸盗戒 法則に従って生きる
- テーラワーダ仏教の教科書(第12回)五戒を守ることは仏道を歩むこと(3)不邪淫戒 仏教と性道徳