ATMSのラベル遅延更新アルゴリズム

情報処理学会

書誌事項

タイトル別名
  • Lazy Updating Algorithm of ATMS Labels

この論文をさがす

説明

解法をアルゴリズムとして定式化することが困難な問題解決にとっては,探索が本質的である.仮説推論は仮説的な状況を明示的に取り扱うことにより,探索を効率良く制御することができる,de Kleerが提唱したATMS(Assumption-based Truth Maintenance System)は,仮説推論を現在までのところ最も適切に定式化した枠組である.ATMSは多重世界の扱い方に基づいて平行型と巡回型に大きく2つに分類することができる.前者は特定の世界に注目することなく全ての世界を一括して取り扱う,後者は単一の世界に注目して個々の世界を巡回し,問題解決は巡回中の世界のみで行う.de KleerによるDDB-Guided ATMSは巡回型として分類することができる.ATMSベースの問題解決システムの性能が良いといえるための前提の一つに,ATMSを用いることによるオーバーヘッドよりも,ATMSを用いることによって回避できるようになった探索のパスの負荷が大きいということがあげられる.設計型のエキスパートシステムなどといった,問題解決器が消費するCPU時間が極めて大きい問題では,この前提が成立するため,ATMSを用いることが有利であると言える.しかし,この前提は多くの問題解決にとって必ずしも成立するものではない.例えば,音声理解システムにおいては,問題解決器の一つのコンシューマが消費するCPU時間は少なく,ATMSの消費するCPU時間が全実行時間の半分を越えるようなこともまれではない.このような問題においてはATMS自身の性能がシステム全体の性能を左右するといえる.特に,ATMSはその実行時間の大半をラベル更新に費やしていることから,効率的なラベル再計算のアルゴリズムを与えることは問題解決システム全体の性能向上にとっても重要である.本稿では,ATMSにおけるラベルの取り扱いに着目することにより,効率的なラベル更新のためのアルゴリズムを提案する.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ