Studies on Efficient Learning Algorithms from Examples
Studies on Efficient Learning Algorithms from Examples
批准号:
13680435
负责人:
TOMITA Etsuji
金额:
$2.18万
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (C)
财政年份:
2001
资助国家:
日本
项目状态:
已结题
起止时间:
2001 至 2003
中文摘要
我们已经建立了一个多项式时间算法,用于通过隶属查询准确地学习简单确定性语言,给出了一个具有代表性的目标语言样本。该算法采用了一种多项式时间算法来检验简单确定性语言的等价性,对于每个终端符号恰好有一个转移规则的实时确定性受限一计数器自动机(DROCA),精确地获得了多项式大小的特征样本。基于这一结果,我们设计了一个多项式更新时间和多项式更新次数的极限Droca的识别算法;在给定噪声比的上界小于1/2的情况下,我们给出了一个近似学习某些布尔函数的算法,称为AC^0,只要给定噪声比的上界,就可以猜测噪声比的上界。结合这些结果,我们已经成功地设计了在不知道噪声比的情况下近似学习这类函数的算法,并设计了一些算法来从正样本中识别一些极限内的次正则语言。然后给出了一种从正例中识别极限内语言类的统一方法,图中求最大团的算法对于聚类问题具有重要意义。然后我们设计了一个非常快速的算法来寻找最大团,并进行了一些扩展。我们已经成功地将这些算法应用于生物信息学、图像处理等实际问题。
英文摘要
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.
期刊论文(32)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
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:“基于高效最大团算法的非均匀扭曲和蛋白质侧链包装下的点匹配”基因组信息学。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
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 的技术报告。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
富田 悦次: "オートマトン・言語理論・学習理論と組合せ最適化の研究及び教育"電子情報通信学会技術研究報告. COMP2003・60. 45-52 (2003)
富田悦司:“自动机、语言理论、学习理论和组合优化的研究和教育”IEICE COMP2003・60(2003)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
若月 光夫: "正則言語の幾つかの部分クラスに対する正の例からの極限同定の統一的一方式"LA シンポジウム(夏). 2002S・22. 8.1-6.14 (2002)
Mitsuo Wakatsuki:“正则语言某些子类的极限识别的统一公式”洛杉矶研讨会(夏季)2002S·22(2002)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 30 条
Much faster algorithms for finding maximum and maximal cliques and their applications
-
批准号:25330009
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$3.0万
-
财政年份:2013
-
负责人:TOMITA Etsuji
-
依托单位:
Development of efficient algorithms for finding a maximum clique with theoretical and experimental evaluations and their applications
-
批准号:22500009
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.66万
-
财政年份:2010
-
负责人:TOMITA Etsuji
-
依托单位:
Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications
-
批准号:19500010
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.83万
-
财政年份:2007
-
负责人:TOMITA Etsuji
-
依托单位:
Development and Applications of Efficient Algorithms for Combinatorial Optimization Problems
-
批准号:09680331
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.18万
-
财政年份:1997
-
负责人:TOMITA Etsuji
-
依托单位:
Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems
-
批准号:06680311
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.41万
-
财政年份:1994
-
负责人:TOMITA Etsuji
-
依托单位:
Development and Evaluations of Efficient Algorithms for Finding a Maximum Clique Based upon Nueral Networks
-
批准号:02650261
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.79万
-
财政年份:1990
-
负责人:TOMITA Etsuji
-
依托单位:
海外基金