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

使用问题提高一致假设搜索的效率

基本信息

批准号：
06780333
负责人：
石坂裕毅
金额：
$ 0.58万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780333/
关键词：
無矛盾仮説探索所属性質問部分性質問木パタン言語機械学習

项目摘要

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

在这个财政年度，我们对以下问题进行了研究，以验证问题在寻找不一致的假设中的有效性。是一个积极的例子，另一个是一个负面的例子，它与正面和负面的例子不一致，这是找到由上述树模式组成的假设的问题考虑到对话中有效地使用问题的算法，我们通过使用部分问题，在给定木材模式的总数中有一个不一致的假设。问题是多个问题的属性问题，仅用于属性问题，这是一种更自然的形式。搜索问题，目前使用问题是非常有效的，我们正在研究一种将来扩展到日本木材模式语言的方法。对线性的多种格式，并计划对矛盾假设的有效解决方案进行检查。将其应用于基因组数据分析等。