分類型問題に対する最適な仮説検証木の効率的な生成法 : MINISTAR法
スポンサーリンク
概要
- 論文の詳細を見る
分類型問題解決における大きな問題の一つに,与えられた情報が解を求めるのに不十分な場合に対処しなければならないという問題がある.本稿では,情報はテストを行うことによって収集されると仮定し,行うべきテストの順序を表した仮説検証木を生成することにより,この問題の解決をはかる.我々の目的は,最適な仮説検証木,すなわち行うべきテストのコストの期待値が最小となる仮説検証木を効率的に生成することである最適な仮説検証木を生成する方法として,ガンマ最小平均法が提案されている.ガンマ最小平均法はすべての仮説検証木を含む潜在的な木を,コストの期待値を計算しながら探索する方法であるしかし,探索の方法が深さ優先であるため,計算丑が膨大になるという問題がある.本稿では,最適な仮説検証木の効率的な生成法としてministar法を提案する.本法はガンマ最小平均法の改良であり,以下の2点の特徴を持つ探索法である:・コストの期待値の下界値をトップダウンに計算する.・この下界値を用いて最良優先探索を行う.次に,minismtar法の正当性について述べ,本法の探索空間が常にガンマ最小平均法の探索空間の部分空間になることから本法の優位性を示す.さらに計算機による実験を行い,テスト数が10個のときに探索空間がガンマ最小平均法の約10分の1で済むことを示す.
- 一般社団法人情報処理学会の論文
- 1989-09-15
著者
関連論文
- 分類型問題に対する最適な仮説検証木の効率的な生成法 : MINISTAR法
- サーカムスクリプションを用いたモデルに基づく診断の定式化
- D-9-30 企業内における情報共有の実践とその活用 : 利用組織拡大による特徴的な活用状況の分析と評価(D-9.ライフインテリジェンスとオフィス情報システム,一般セッション)
- 知識蓄積に適応可能なスケジュールデータ構成方法の評価