On learning unions of pattern languages and tree patterns in the mistake bound model

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 occu...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2002-10, Vol.288 (2), p.237-254
Main Authors: Goldman, Sally A., Kwek, Stephen S.
Format: Article
Language:English
Subjects:
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Exact sciences and technology
Information retrieval. Graph
Learning and adaptive systems
Mistake bound learning model
On-line learning
Pattern languages
Theoretical computing
Tree patterns
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 occurrence of variable x i must be substituted by terminal strings of fixed length l( x i ). We prove that if 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 we give results to learn a class that generalizes pattern languages.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(01)00402-9