Studies on Efficient Learning Algorithms from Examples

高效学习算法的实例研究

• 批准号: 13680435
• 负责人: TOMITA Etsuji
• 金额: $ 2.18万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680435/
• 关键词: Learning; Formal language; Automaton; Positive example; Updating time; Number of updates; Identification in the limit; Maximum clique; ブール関数

We have established a polynomial-time algorithm for exactly learning simple deterministic languages via membership queries, given a representative sample of the target language. This algorithm sophisticatedly employs a polynomial-time algorithm for checking the equivalence of simple deterministic languages that was devised by ourselves previously.For a real-time deterministic restricted one counter automation (droca) which has exactly one transition rule per one terminal symbol, a polynomial-sized characteristic sample is exactly obtained. Based on this result, we have devised an algorithm for identifying droca's in the limit with polynomial updating time and polynomial number of updates.We have developed an algorithm for approximately learn certain Boolean functions, called AC^0, from examples of their behavior with possibly attribute and classification noise, provided we are given the upper bound of the noise ratio which is less than 1/2. Subsequently, we devised an algorithm for guessing the upper bound of the noise ratio. Combining these results, we have succeeded in designing and algorithm for approximately learn such functions without any knowledge of the noise ratio in advance.Some algorithms were devised to identify some subregular languages in the limit from positive samples. Then we gave a unified method to identify some classes of languages in the limit from positive examples.Algorithms for finding a maximum clique in a graph are important for clustering problems. Then we devised a very fast algorithm for finding a maximum clique together with some extensions. We have successfully applied these algorithms for some practical problems as in bioinformatics, image processing, and so on.

我们建立了一种多项式时间算法，在给定目标语言的代表性样本的情况下，通过成员资格查询精确学习简单的确定性语言。该算法巧妙地采用了我们之前设计的一种多项式时间算法来检查简单确定性语言的等价性。对于每个终端符号恰好有一个转换规则的实时确定性限制性计数器自动化（droca），精确地获得了多项式大小的特征样本。基于这个结果，我们设计了一种算法，用于在多项式更新时间和多项式更新次数的限制内识别德罗卡。我们开发了一种算法，用于从具有可能属性和分类噪声的行为示例中近似学习某些布尔函数，称为 AC^0，前提是我们给出小于 1/2 的噪声比上限。随后，我们设计了一种猜测噪声比上限的算法。结合这些结果，我们成功地设计和算法来近似学习此类函数，而无需事先了解噪声比。设计了一些算法来在正样本的限制内识别一些次正则语言。然后我们给出了一种统一的方法来从正例中识别有限的某些语言类别。在图中找到最大派系的算法对于聚类问题很重要。然后我们设计了一种非常快速的算法来寻找最大派系以及一些扩展。我们已经成功地将这些算法应用于生物信息学、图像处理等一些实际问题。

项目成果

Junnosuke. Moriya: "Relationships between the computational capabilities of simple recurrent networks and finite automata"IEICE Trans.on Fundamentals. E84-A. 1184-1194 (2001)

淳之介。

Dukka BAHADUR K.C., Tatsuya AKUTSU, Etsuji TOMITA, Tomokazu SEKI, Asao.FUJIYAMA: "Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms"Genome Informatics. 13. 143-152 (2002)

Dukka BAHADUR K.C.、Tatsuya AKUTSU、Etsuji TOMITA、Tomokazu SEKI、Asao.FUJIYAMA：“基于高效最大团算法的非均匀扭曲和蛋白质侧链包装下的点匹配”基因组信息学。

Mitsuo.Wakatsuki: "Polynomial time identification of strict deterministic restricted one-counter automata in some class from positive data"Technical Report of IEICE. COMP2003(to appear). (2004)

Mitsuo.Wakatsuki：“从正数据中对某类严格确定性限制单计数器自动机进行多项式时间识别”IEICE 的技术报告。

富田 悦次: "オートマトン・言語理論・学習理論と組合せ最適化の研究及び教育"電子情報通信学会技術研究報告. COMP2003・60. 45-52 (2003)

富田悦司：“自动机、语言理论、学习理论和组合优化的研究和教育”IEICE COMP2003・60（2003）。

若月 光夫: "正則言語の幾つかの部分クラスに対する正の例からの極限同定の統一的一方式"LA シンポジウム(夏). 2002S・22. 8.1-6.14 (2002)

Mitsuo Wakatsuki：“正则语言某些子类的极限识别的统一公式”洛杉矶研讨会（夏季）2002S·22（2002）。