INDUCTIVE LEARNING OF DECISION TREES OVER REGULAR PATTERNS AND ITS APPLICATION TO GENOME INFORMATICS

规则模式决策树归纳学习及其在基因组信息学中的应用

• 批准号: 13680457
• 负责人: SATO Masako
• 金额: $ 1.86万
• 依托单位: OSAKA PREFECTURE UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680457/
• 关键词: Inductive learning; Regular pattern; Decision tree; Positive example; Inductive inference; Compactness; Genome Informatics; Formal Language; パターン言語; 正規言語; ゲノム情報; 基本形式体系

Our main results are as follows:1)We have investigated the problem of learning decision trees over regular patterns from a view point of knowledge discovery for Genome information processing. We first obtained some results about relations between the semantics containment and the syntactic containment of decision trees over regular patterns. Then we gave an efficient learning algorithm for some kind of decision trees with at most depth two over regular patterns from positive examples.2) Compactness for a class of unions of regular patterns garantees an equivalency between semantic containment and syntactic containment, and plays an important role for designing efficient learning algorithm of unions of regular pattern languages. We obtained a neccesary and sufficient condition for a class of unions of regular patterns to have compactness.3)We proposed refutable/inductive learning model from neighborhood examples, and apply it to the regular pattern languages.4) Furthermore, we investigate the fundamental theory on regular pattern languages which plays an important role for designing efficient learning algorithms in the above problems.

主要研究结果如下：1）从基因组信息处理知识发现的角度研究了规则模式上决策树的学习问题。本文首先得到了规则模式上决策树的语义包含性与句法包含性之间关系的一些结果。2）正则模式并集的紧性保证了语义包含和语法包含的等价性，对于设计正则模式并集的有效学习算法具有重要意义。我们得到了一类规则模式并具有紧性的充分必要条件。3）我们提出了基于邻域例子的可反驳/归纳学习模型，并将其应用于规则模式语言。4）此外，我们研究了规则模式语言的基本理论，这些理论对于设计上述问题中的高效学习算法起着重要作用。

项目成果

Jin Uemura and Masako Sato: "Compactness and Learning of Classes of Unions of Erasing Regular Pattern Languages."Lecture Notes in Artificial Intelligence. 2533. 293-307 (2002)

Jin Uemura 和 Masako Sato：“擦除规则模式语言的并集类的紧致性和学习”。人工智能讲义。

Jin Uemura, Masako Sato: "Compactness and Learning of Classes of Unions of Erasing Regular Pattern Languages"Lecture Notes in Artificial Intelligence. 2533. 293-307 (2002)

Jin Uemura、Masako Sato：《擦除规则模式语言并集类的紧致性与学习》人工智能讲义。

Masako Sato, Yasuhito Mukouchi, Mikiharu Terada: "Refutable/Inductive Learning from Neighbor Examples and its Application to Decision Trees over Patterns"Lecture Notes in Computer Science. 2281. 201-213 (2002)

Masako Sato、Yasuhito Mukouchi、Mikiharu Terada：“来自邻居示例的可反驳/归纳学习及其在模式决策树中的应用”计算机科学讲义。