### On Learning Unions of Pattern Languages and Tree Patterns

**Authors: Sally A. Goldman and Stephen S. Kwek**.

**Source: ***Lecture Notes in Artificial Intelligence* Vol. 1720,
1999, 347 - 363.

**Abstract.**
We present efficient on-line algorithms 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 general 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 the same variable, must be substituted by the
same terminal string. An instance is positive iff the
penalty incurred for violating these rules is below a given tolerable
threshold.

©Copyright 1999 Springer-Verlag