Languages as hyperplanes: grammatical inference with string kernels
作者： Alexander Clark , Christophe Costa Florêncio , Chris Watkins
DOI: 10.1007/S10994-010-5218-3
关键词: Algorithm 、 Theoretical computer science 、 String (computer science) 、 Hyperplane 、 Mathematics 、 Kernel principal component analysis 、 Feature vector 、 Context-sensitive language 、 Rotation formalisms in three dimensions 、 Kernel method 、 Grammar induction
摘要: 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 implicit maps defined by considering expressive power formalism, its closure and relationship other formalisms. present new family grammatical inference algorithms based on idea. demonstrate that some mildly context-sensitive way it is possible efficiently learn these using kernel PCA. experimentally effectiveness approach standard examples small synthetic data sets.
springer.com
uva.nl
paperity.org参考文章(47)
Leonor Becerra Bonache, On the learnibility of Mildly Context-Sensitive languages using positive data and correction queries TDX (Tesis Doctorals en Xarxa). ,(2006)
Text classification using string kernels Journal of Machine Learning Research. ,vol. 2, pp. 419- 444 ,(2002) , 10.1162/153244302760200687
Koby Crammer, Yoram Singer, Learning Algorithms for Enclosing Points in Bregmanian Spheres Learning Theory and Kernel Machines. pp. 388- 402 ,(2003) , 10.1007/978-3-540-45167-9_29
José M. Sempere, Learning Context-Sensitive Languages from Linear Structural Information international colloquium on grammatical inference. pp. 175- 186 ,(2008) , 10.1007/978-3-540-88009-7_14
Nello Cristianini, John Shawe-Taylor, Kernel Methods for Pattern Analysis ,(2004)
Leonid Kontorovich, Corinna Cortes, Mehryar Mohri, Learning linearly separable languages algorithmic learning theory. pp. 288- 303 ,(2006) , 10.1007/11894841_24
Umesh V. Vazirani, Michael J. Kearns, An Introduction to Computational Learning Theory ,(1994)
S. Chalup, A.D. Blair, Hill climbing in recurrent neural networks for learning the a/sup n/b/sup n/c/sup n/ language international conference on neural information processing. ,vol. 2, pp. 508- 513 ,(1999) , 10.1109/ICONIP.1999.845646
Alexander Clark, Christophe Costa Florêncio, Chris Watkins, Mariette Serayet, Planar Languages and Learnability Grammatical Inference: Algorithms and Applications. pp. 148- 160 ,(2006) , 10.1007/11872436_13
Corinna Cortes, Leonid Kontorovich, Mehryar Mohri, Learning languages with rational kernels conference on learning theory. pp. 349- 364 ,(2007) , 10.1007/978-3-540-72927-3_26