質問による無矛盾仮説探索の効率化

点击翻译按钮获取中文摘要

本年度は,無矛盾仮説探索における質問の有効性を検証するために,以下の課題について研究を行なった.まず,木パタン言語と呼ばれる言語族を対象とし,その言語の和集合族に対する無矛盾仮説探索問題がNP完全であることを示した.すなわち,与えられた2つの木パタンの集合に対し,その片方を正の例,もう一方を負の例とみなし,それら正負の例に矛盾しない,2個以上の木パタンからなる仮説を見つける問題が,計算量的に非常に困難な問題であることを示した.次に,高々2個の木パタン言語の和集合からなる言語族に対する無矛盾仮説探索を,質問を利用して対話的に効率良く解くアルゴリズムについて考察を行なった.結果として,部分性質問を利用することによって,与えられた木パタンのサイズの合計の多項式時間で,無矛盾な仮説を見つけるアルゴリズムを得た.さらに,各部分性質問が多項式個の所属性質問によって代替可能であることを示すことにより,質問としてはより自然な形態である所属性質問のみを用いて,同問題が多項式時間で解けることを示した.このことより,NP完全な探索問題である無矛盾仮説探索において,質問を利用することが極めて有効であるとの結論を得た.現在,上記の結果を,高々κ個の木パタン言語の和集合族に対して拡張するための手法について検討中である.今後は,探索時間を多項式から線形へと更に短縮するための手法,および,一般の文字列パタン言語を対象とした無矛盾仮説探索の効率的解法について検討を行なう予定である.また,効率的無矛盾仮説探索に基づく機械発見手法を確立し,ゲノムデータ解析等への応用を試みることも今後の重要な課題である.