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

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

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.