Study on Inductive Learning Based on Positive Examples

点击翻译按钮获取中文摘要

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 alphsbet indexing, the algorithm succesfully finds sets of patterns, that can be considered as motifs.The class of all the unions of arbitrarily finitely many pattern languages in not inferable, because any constant string defines a singleton set consisting of itself, and the class of unions contains all the finite languages. A proper pattern is a pattern that contains at least one variable. The language of a proper pattern is infinite. In this paper, we consider the class of unions when patterns are restricted to be priper and show that the class is not inferable from positive data. When patterns are restricted not to contain more than l consecutive occurrences of constant symbols for some l, the class of unions is shown to be inferable from positive data.