On Learning Unions of Pattern Languages and Tree Patterns

摘要

We present efficient on-line algoirhtms for learning unions of a constant number of tree patterns, unions of a constant number of one-variable pattern languages, and unions of a constant number of pattern languages with fixed length substitutions. By fixed length substitutions we mean that each occurence of variable x_i must be substituted by terminal strings of fixed length l(x_i). We prove that if an arbitrary unions of pattern languages with fixed length substitutions can be learned efficiently then DNFs are efficiently learnable in the mistake bound model. Since we use a reduction to Winnow, our algorithms are robust against attribute noise. Furthermore, they can be modified to handle concept drift. Also, our approach is quite gneeral and may be applicable to learning other pattern related classes. For example, we could learn a more general pattern language class in which a penalty (i.e. weight) is assigned to each violation of the rule that a terminal symbol cannot be changed or that a pair of variable symbols, of he same variable, must be substituted by the same terminal string. An instance is positive iff the penalty incurred for violaitng these rules is below a given tolerable threshold.