コストに基づく仮説推論の2種の連続値最適化問題への置換法とその協調による推論法
スポンサーリンク
概要
- 論文の詳細を見る
仮説推論は, 真か偽か不明な事柄をとりあえず真と考えて推論を進め, 矛盾なくゴールを導くことができれば立てた仮説は正しかったと考える推論形式である.コストに基づく仮説推論は, 各仮説に付与されたコストの和を最小とするような仮説の組を最も望ましいものとする.しかし, コスト最小の仮説を見つける問題はNP困難となるため.コストが最小に近い準最適解を多項式オーダの推論時間で求める研究が行われてきた.従来手法であるNBP法やSL法は多項式オーダの推論時間で準最適解を得ることができるが, これらは仮説推論問題の各ホーン節を不等式制約で置き換えることにより, シンプレックス法を利用してコストの低い解の目星を付け, その近傍を探索する手法である.一方, 仮説推論と関連の深いSAT問題に対しては, 陽には示されていないものの, 各節を非線形等式で置き換えて得られた問題をさまざまな方法で解くアルゴリズムが提案されている.本論文では, 仮説推論で従来から用いられてきた節を不等式制約に置き換える方法(置換Lと呼ぶ)と, 等式制約に置き換える方法(置換NLと呼ぶ)を統合することを試みる.置換Lはコストの低い解を見つける働きが強く, 置換NLは実行可能解を見つける働きが強いため, これらをうまく統合することにより, コストの低い解が得られることが期待される.2種類の異なる置換法による制約を扱うために, 本論文では並行計算の手法の一つである拡張ラグランジェ法を利用し, 変数と制約をそれぞれプロセッサと考えることで, 制約の付加・除去を実現する.そして, 初期フェーズでは, 置換Lによる制約プロセッサにより探索を行い, 以降のフェーズでは置換NLによる制約プロセッサを追加していくアルゴリズムを提案する.置換NLによる制約プロセッサをどのように追加していくかに関して, 論文中では2種類の戦略を紹介する.評価実験として, 集合被覆問題および最短経路問題をもとにした仮説推論問題に対して推論時間および解のコストを比較する.それにより, 従来手法と同程度の探索時間でコストの低い解を得られることを示す.
- 2001-09-01
論文 | ランダム
- シII-A. 婦人科悪性腫瘍における免疫細胞組織化学の臨床的応用(細胞診のための細胞化学, シンポジウム(II), 第27回日本臨床細胞学会学術集会)
- 卵巣漿液性嚢胞腺癌の細胞診
- 子宮頸部病変における human Keratin Protein(hKP) の免疫細胞組織化学的検討
- 43. 卵巣腫瘍における各種腫瘍マーカーの局在について(示説, 第24回日本臨床細胞学会秋季大会記事)
- 38. 子宮癌における EMA( Epithelial Membarane Antigen)の免疫細胞組織学的検討(示説, 第24回日本臨床細胞学会秋季大会記事)