Study on Inductive Learning Based on Positive Examples

基于实证的归纳学习研究

• 批准号: 07680406
• 负责人: SHINOHARA Takeshi
• 金额: $ 1.34万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 1996
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07680406/
• 关键词: Inductive Inference; Machine Learning; Learning from Positive Examples; Pattern Languages; Elementary Formal Systems; Efficiency of Learning

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.

模式是由恒定符号和变量组成的字符串。模式的语言是通过将非空的恒定字符串替换为模式中的变量获得的恒定字符串集。对于任何固定的K，大多数K模式语言的工会类别都可以从正数据中推断出来。我们对模式语言进行学习算法，以从氨基酸序列中发现图案。从仅借助Alphsbet索引的积极示例，该算法成功地找到了一组模式，可以被视为主题。在不可推断的所有常数字符串中，任意多个图案语言的所有工会的类别都可以被推断出来，因为任何常数字符串都定义了单身人士集合，并且包含所有有限的工会。适当的模式是一种包含至少一个变量的模式。正确模式的语言是无限的。在本文中，我们认为，当模式被限制为priper时，工会类别表明该类是从正数据中推断出来的。当模式被限制不超过某些L的常数符号连续发生时，根据正数据可推断出工会的类别。

项目成果

H.Arimura, T.Shinohara: "Logical generalization for learning with background knowledge" ICLP'95 Post-Conference Workshop on Inductive Logic Programming. IATR-95-03. 1-11 (1995)

H.Arimura、T.Shinohara：“背景知识学习的逻辑概括”ICLP95 归纳逻辑编程会后研讨会。

K.P.Jantke, T.Shinohara, T.Zeugmann (Eds.): "Algorithmic Learning Theory" (Lecture Notes in Artificial Intelligence 997) Springer-Verlag. 319 (1995)

K.P.Jantke、T.Shinohara、T.Zeugmann（编）：“算法学习理论”（人工智能讲义 997）Springer-Verlag。

Hiroki Arimura: "Learning Unions of Tree Patterns Using Queries" Proc.the 6th International Workshop on Algorithmic Learning Theory (Lecture Notes in Artificial Intelligence 997,Springer-Verlag). 997. 66-79 (1995)

Hiroki Arimura：“使用查询学习树模式的联合”，第六届算法学习理论国际研讨会（人工智能讲义 997，Springer-Verlag）。

篠原 武: "複数文字列パターンによる正例からのタンパク質モチーフの発見" 1995年度人工知能学会全国大会(第9回)講演論文集. 93-96 (1995)

Takeshi Shinohara：“使用多个字符串模式从正面例子中发现蛋白质基序”日本人工智能学会 1995 年全国会议记录（第 93-96 期）（1995 年）。

有村 博紀: "帰納論理プログラムにおける背景知識を用いた多項式時間一般化アルゴリズム" 情報処理学会第51回(平成7年後期)全国大会講演論文集. 3. 135-136 (1995)

Hironori Arimura：“在归纳逻辑程序中使用背景知识的多项式时间泛化算法”日本信息处理学会第 51 届（1995 年末）全国会议论文集 3. 135-136 (1995)。