Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University
Learning Linearly Separable Languages
This report supercedes CMU-CALD-04-105
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.
||SCS Technical Report Collection
School of Computer Science homepage
This page maintained by firstname.lastname@example.org