Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University
Learning Linearly Separable Languages
Leonid Kontorovich
May 2004
Erratum: the proof of Thm. 4.3. in this paper is wrong,
as pointed out to me by Corinna Cortes and Mehryar Mohri.
A corrected proof will be posted shortly.
For a finite alphabet A, we define a class of embeddings of A* into an infinite-dimensional feature space X and show that its finitely supported hyperplanes define regular languages. This suggests a general strategy for learning regular languages from positive and negative examples. We apply this strategy to the piecewise testable languages, presenting an embedding under which these are precisely the linearly separable ones, and thus are efficiently learnable.
12 pages
School of Computer Science homepage
This page maintained by reports@cs.cmu.edu