A Polynomial-Time Algorithm for Learning K-Variable Pattern Languages from Examples
Abstract
This chapter focuses on a polynomial-time algorithm for learning k-variable pattern languages in the learning model introduced by Valiant for each constant k. A pattern is a string of constant and variable symbols. For any constant k, the algorithm learns a k-variable target pattern p by producing a polynomial-sized disjunction of patterns, each of between 0 and k variables. The algorithm allows empty substitutions and can be extended to handle restricted homomorphisms on the substitution strings. It is assumed that the algorithm has access to a random source of negative examples, generated according to an arbitrary distribution, and a random source of positive examples of the target pattern p in which the k-tuple of substitution strings is drawn not from an arbitrary distribution but from any product distribution.
Cite
Text
Kearns and Pitt. "A Polynomial-Time Algorithm for Learning K-Variable Pattern Languages from Examples." Annual Conference on Computational Learning Theory, 1989. doi:10.1016/B978-0-08-094829-4.50007-6Markdown
[Kearns and Pitt. "A Polynomial-Time Algorithm for Learning K-Variable Pattern Languages from Examples." Annual Conference on Computational Learning Theory, 1989.](https://mlanthology.org/colt/1989/kearns1989colt-polynomial/) doi:10.1016/B978-0-08-094829-4.50007-6BibTeX
@inproceedings{kearns1989colt-polynomial,
title = {{A Polynomial-Time Algorithm for Learning K-Variable Pattern Languages from Examples}},
author = {Kearns, Michael J. and Pitt, Leonard},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1989},
pages = {57-71},
doi = {10.1016/B978-0-08-094829-4.50007-6},
url = {https://mlanthology.org/colt/1989/kearns1989colt-polynomial/}
}