Study on Pattern Inference from Positive Data

本研究的目的是在调查机器学习的可实现性，通过研究归纳推理作为一个理论模型，从例子中学习。一般来说，学习中使用的例子分为积极的和消极的。在语言（或语法）学习中，积极的例子对应于（语法上）正确的句子。当实验数据与某个性质有关时，可以看作是该性质的正例。本文研究了基于正例的归纳学习的理论局限性，并从实际应用的角度研究了有效的学习算法。模式是由常量符号和变量组成的字符串。模式的语言是由获得的常量字符串的集合。用非空常量字符串替换模式中的变量。对于任何固定的k，最多k个模式语言的联合类已经被证明是从正数据推断的。我们应用模式语言的学习算法从氨基酸序列中发现一个模体。从只有积极的例子与字母索引的帮助下，该算法成功地发现了一组模式，可以被认为是motifs.We还研究了加速的语言受体的基本形式化系统，在那里我们采用快速字符串模式匹配机。最后，我们提出了一种可能的方法来扩展多模式的学习算法。

The aim of this research is in investigating realizability of machine learning, by studying inductive inferece as a theoretical model of learning from examples. In general, examples using in learning are categorized in positive ones and negative ones. In language (or grammar) learning, positive examples are corresponding to (grammatically) correct sentences. Data obtained from experiments can be considered as positive examples of a certain property, when they are concernd with the property. In this research, we have considered theoretical limits of inductive learning based on positive examples and investigated efficient learning algorithms from the viewpoint of practical applications.A pattern is a string consisting of constant symbols and variables. The language of a pattern is the set of constant strings obtained by. substituting nonempty constant strings for variables in the pattern. For any fixed k, the class of unions of at most k pattern languages is already shown to be inferable from positive data.We apply a learning algorithm for pattern languages to discover a motif from amino-acid sequences. From only positive examples with the help of an alphabet indexing, the algorithm successfully finds sets of patterns, that can be considered as motifs.We have also studied speed-up of language acceptors for elementary formal systems, where we employ fast string pattern matching machines. Finally, we propose a possible approach to extending leaning algorithms for multiple patterns.