Study on Pattern Inference from Positive Data

实证数据模式推断研究

• 批准号: 12680391
• 负责人: SHINOHARA Takeshi
• 金额: $ 1.66万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12680391/
• 关键词: Inductive Inference; Machine Learning; Inductive Inference from Positive Data; Pattern Languages; Elementary Formal Systems; Efficiency of Learning; 正例からの帰納推論; パターン照合

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.

这项研究的目的是通过将归纳推理作为从示例中学习的理论模型来研究机器学习的可靠性。通常，在学习中使用的示例分类为积极的示例和负面的示例。在语言（或语法）学习中，积极的例子与（语法上）正确的句子相对应。当从实验中获得的数据是某个特性的积极示例，当它们关注该属性时。在这项研究中，我们考虑了基于积极示例的归纳学习的理论限制，并从实际应用的角度研究了有效的学习算法。一种模式是由恒定的符号和变量组成的字符串。模式的语言是由恒定字符串获得的集合。将非空的恒定字符串替换为模式中的变量。对于任何固定的K，大多数K模式语言的工会类别都可以从正数据中推断出来。我们对模式语言进行学习算法，以从氨基酸序列中发现图案。从仅借助字母索引的积极示例，该算法成功地找到了一组模式，可以将其视为主题。我们还研究了基础正式系统的语言受体的加快，我们采用了快速的字符串模式匹配机器。最后，我们提出了一种扩展多种模式倾斜算法的可能方法。

项目成果

Takeshi Shinohara, Hiroki Ishizaka: "On Dimension Reduction Mappings for Approximate Retrieval of Multi-dimensional Data"Progress Discovery Science, Final Report of the Japanese Discovery Science Project,(Lecture Notes in Artificial intelligence Vol.2281)

Takeshi Shinohara、Hiroki Ishizaka：“On Dimension Reduction Mappings for Approxival Retrieval of Multi-Dimensional Data”Progress Discovery Science，日本发现科学项目最终报告，（人工智能讲座笔记第2281卷）

Takeshi Shinohara: "Speed-up of Aho-Corasick Pattern Matching Machines by Rearranging States"Proceedings of 8^<th> International Symposium on String Processing and Information Retrieval. 175-185 (2001)

Takeshi Shinohara：“通过重新排列状态加速 Aho-Corasick 模式匹配机”第 8 届国际字符串处理和信息检索研讨会论文集。

Shuichi Fukamachi: "Speed-Up of approximate string matching using lossy compression"Proceedings of the 10th European-Japanese Conference on Information Modeling and Knowledge bases. 262-263 (2000)

Shuichi Fukamachi：“使用有损压缩加速近似字符串匹配”第十届欧洲-日本信息建模和知识库会议论文集。

Takeshi Shinohara: "On dimension reduction mappings for approximate retrieval of multi-dimensional data"Lecture Notes in Artificial Intelligence Vol.2281. 224-231 (2002)

Takeshi Shinohara：“关于多维数据近似检索的降维映射”人工智能讲义第2281卷。

Yen Kaow Ng: "The Discovery of Consensus Patterns"火の国情報シンポジウム2004予稿集. 8 (2004)

Yen Kaow Ng：“共识模式的发现”火国信息研讨会论文集2004. 8 (2004)