A^*探索に基づく仮説推論の効率化

• Item type: SIG Technical Reports(1)
• 公開日: 2014-06-26
• タイトル: A^*探索に基づく仮説推論の効率化
• タイトル / 言語: en
• タイトル: Efficient Estimation of Plausible Abductive Hypotheses Using A^* Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 知識獲得・推論
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学
• 著者所属: 東北大学
• 著者所属: 東北大学
• 著者所属: Microsoft Research Asia
• 著者所属: Microsoft Research Asia
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Microsoft Research Asia
• 著者所属(英): en
• 著者所属(英): Microsoft Research Asia
• 著者名: 山本, 風人; 井之上, 直也; 乾, 健太郎; 荒瀬, 由紀; 辻井, 潤一
• 著者名(英): Kazeto, Yamamoto; Naoya, Inoue; Kentaro, Inui; Yuki, Arase; Junichi, Tsujii
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 仮説推論は、観測に対する最良の説明を求める推論である。仮説推論は、文章に明示されていない情報の顕在化を行うための有望な枠組みとして考えられてきた一方で、最良の説明を求めるための計算時間が入力の規模に対して指数関数的に増加するため、実問題への適用事例は未だ限定的であるのが現状である。そこで我々は、仮説推論の探索空間を効率良く削減するために、A* 探索に基づく説明候補生成アルゴリズムを提案する。より具体的には、複数の証拠により支持されない仮説リテラルを、効率良く探索空間から排除する手法を提案する。また、評価実験を通して、最新の仮説推論アルゴリズムの計算効率が提案手法により大幅に改善されることを報告する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Abduction is inference to the best explanation. While abduction has long been considered as a promising framework for natural language processing (NLP), its computational complexity hinders applying abduction to practical NLP problems. In this paper, we adapt an A* search-based technique for abduction in order to prune its search space efficiently. More specifically, we present an algorithm to effectively eliminate literals which do not introduce any unification from the search space. Our experiment reveals that our search-based technique considerably reduces the size of the search space and improves the efficiency of the state-of-the-art inference algorithm for abduction on first-order logic.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10115061
• 書誌情報: 研究報告自然言語処理（NL）; 巻 2014-NL-217, 号 10, p. 1-9, 発行日 2014-06-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会