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），精确地获得了一个多项式大小的特征样本。在此基础上，我们设计了一种以多项式更新时间和多项式更新次数为极限的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）。