Languages as Hyperplanes: Grammatical Inference with String Kernels

Alex Clark, Department of Computer Science, Royal Holloway, University of London
30 January 2007
(1pm, WIN004, Windsor Building)

Using string kernels, languages can be represented as hyperplanes in a high dimensional feature space. We discuss the language theoretic properties of this formalism with particular reference to the implicit feature maps defined by string kernels, considering the expressive power of the formalism, their closure properties and their relationship to other formalisms.

We present a new family of grammatical inference algorithms based on this idea. We demonstrate that some mildly context-sensitive languages can be represented in this way and it is possible to efficiently learn these using kernel PCA.

We present some experiments demonstrating the effectiveness of this approach on some standard examples of context-sensitive languages using small synthetic data sets.