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

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

基本信息

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

项目摘要

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

今年，为了验证一致性假设搜索问题的有效性，我们对以下问题进行了研究：首先，我们将去年开发的一致性假设搜索方法应用于最多两种树模式语言的并集进行了扩展。这就是 k 的一般情况，即给定一组两个树模式，其中一个是正例，另一个是正例。我们开发了一种方法，仅使用隶属问题来查找由最多 k 个树模式组成的假设，这些假设在多项式时间内不矛盾这些正例和负例。接下来，我们开发了一种基于该方法的方法，我们考虑了联合族的学习算法。因此，我们研究了树型语言并族的学习算法。我们获得了一种使用隶属问题在多项式时间内执行精确学习的算法。这也使得在其他几种学习模型（例如 PAC 学习和预测学习）中使用隶属问题执行多项式时间学习成为可能。仅使用等价问题和隶属问题之一在多项式时间内进行精确学习。通过证明这两个问题对于树模式语言的并集家族的高效精确学习是必要的，我们目前正在将上述结果应用于字符串模式语言的并集家族。我们目前正在考虑一种扩展该方法的方法。寻找字符串的一致假设是一个与基因组数据分析直接相关的重要研究课题。