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.