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.


Keywords: Regular language, piecewise testable, learning, kernel, strings

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

SCS Technical Report Collection
School of Computer Science homepage

This page maintained by