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个模式语言的联合类已经被证明是从正数据推断的。我们应用模式语言的学习算法从氨基酸序列中发现一个模体。该算法仅从正例中，通过一个双比特索引，成功地找到了可视为模体的模式集，任意多个模式语言的所有联合的类是不可推断的，因为任何常量字符串定义了一个由其自身组成的单例集，而联合的类包含了所有的有限语言.正确的模式是至少包含一个变量的模式。一个适当的模式的语言是无限的。本文考虑了模式被限制为正的并类，并证明了该类不能从正数据中推断。当模式被限制为不包含超过l个连续出现的常数符号的一些l，工会的类示出是推断从积极的数据。

项目成果

宮崎 哲司,深町 修一,篠原,武: "マルコフモデルを用いた圧縮データのための文字列パターン照合" 情報基礎論ワークショップ(LAシンポジウム). (1996)

Tetsuji Miyazaki、Shuichi Fukamachi、Takeshi Shinohara：“使用马尔可夫模型进行压缩数据的字符串模式匹配”信息基础研讨会（洛杉矶研讨会）（1996 年）。

山口美千代: "複数文字列パターンによるアミノ酸配列からのタンパク質モティーフの発見" 情報処理学会研究報告,情報学基礎. No.38. 33-40 (1995)

Michiyo Yamaguchi：“使用多个字符串模式从氨基酸序列中发现蛋白质基序”日本信息处理学会研究报告，信息学基础第 38 期 33-40（1995 年）。

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 归纳逻辑编程会后研讨会。

T.Shinohara, H.Arimura: "Inductive inference of unbounded unions of pattern languages from positive data" Proc.the 7th International Workshop on Algorithmic Learning Theory (Lecture Notes in Artificial Intelligence 1160). 256-271 (1996)

T.Shinohara、H.Arimura：“从正面数据中对模式语言的无界联合进行归纳推理”Proc.第七届国际算法学习理论研讨会（人工智能讲座笔记 1160）。

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

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