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

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

本年度は、無矛盾仮説探索における質問の有効性を検証するために,以下の課題について研究を行なった.まず,昨年度開発した高々2個の木パタン言語の和集合族に対する無矛盾仮説探索の手法を,一般のk個の場合に対して拡張することを行なった.すなわち,与えられた2つの木パタンの集合に対し,その片方を正の例,もう一方を負の例とみなし,それら正負の例に矛盾しない高々k個の木パタンからなる仮説を,所属性質問のみを用いて多項式時間で見つける手法を開発した.次に,この手法に基づいた木パタン言語の和集合族に対する学習アルゴリズムについて考察を行なった,結果として,高々k個の木パタン言語の和集合族を,等価性質問と所属性質問を用いて多項式時間で厳密学習するアルゴリズムを得た.また,このことにより,PAC学習や予測学習といった他のいくつかの学習モデルにおいても,所属性質問を用いることにより,多項式時間学習が可能であることを示した.さらに,等価性質問と所属性質問のどちらか一方だけでは,多項式時間で厳密学習することが出来ないことを示すことにより,木パタン言語の和集合族の効率的な厳密学習にとって両方の質問が必要であることを明らかにした.現在,上記の結果を,文字列パタン言語の和集合族に対して拡張するための手法について検討中である.文字列を対象とした無矛盾仮説探索問題は,ゲノムデータ解析等と直接関連する重要な研究課題である.