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

点击翻译按钮获取中文摘要

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.