Studies on Efficient Learning Algorithms from Examples

我们已经建立了一个多项式时间的算法，通过成员查询，准确地学习简单的确定性语言，给定的目标语言的代表性样本。该算法采用了一种多项式时间的简单确定性语言等价性检验算法，对于一个终端符号只有一条转移规则的实时确定性受限单计数器自动机（droca），可以精确地得到一个多项式大小的特征样本.在此基础上，我们设计了一个识别droca的算法，该算法在多项式更新时间和多项式更新次数的限制下，我们已经开发了一个算法，近似学习某些布尔函数，称为AC^0，从它们的行为的例子可能属性和分类噪声，如果我们给定的噪声比的上限小于1/2。随后，我们设计了一个算法来猜测噪声比的上限。结合这些结果，我们成功地设计了在不事先知道噪声比的情况下近似学习这类函数的算法，并设计了一些算法从正样本中识别极限下的亚正则语言。在此基础上，给出了一种从正例中识别极限语言类的统一方法。求图中最大团的算法是聚类问题中的重要算法。然后，我们设计了一个非常快速的算法，找到一个最大团连同一些扩展。我们已经成功地将这些算法应用于一些实际问题，如生物信息学，图像处理等。

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.