Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University


Learning Linearly Separable Languages

Leonid Kontorovich

May 2004

This report supercedes CMU-CALD-04-105
and includes the corrected proof.

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