Grammatical Inference
25 Sep 2007 14:54Meaing: inferring the rules of a formal language (its grammar) from examples, positive or negative. I'm mostly interested in the positive case, since I want to describe physical processes as though they were formal languages or (what is equivalent) automata.
See also: Bioinformatics; Computation, Automata and Languages; Computational Mechanics; Linguistics; Machine Learning, Statistical Inference and Induction; Transducers
- Recommended:
- Remo Badii and Antonio Politi, Complexity: Hierarchical Structure and Scaling in Physics [Treating dynamical systems like formal languages. Review.]
- Eugene Charniak, Statistical Language Learning [Good stuff on learning grammars for the two lowest levels of the Chomsky hierarchy; explains the grammar ideas for the benefit of engineers.]
- Jim Engle-Warnick, William J. McCausland and John H. Miller, "The Ghost in the Machine: Inferring Machine-Based Strategies from Observed Behavior" [i.e., inferring stochastic transducers from data; hence the inclusion here]
- Michael J. Kearns and Umesh V. Vazirani, An Introduction to Computational Learning Theory [Review: How to Build a Better Guesser]
- Craig G. Nevill-Manning and Ian H. Witten, "Identifying Hierarchical Structure in Sequences: a Linear-Time Algorithm," cs.AI/9709102 [Scheme for inferring context-free grammars from sequential data streams; no consideration of probabilistic properties]
- Leonid Peshkin, "Structure induction by lossless graph compression", cs.DS/0703132 [Adapting data-compression ideas, a la Nevill-Manning and Witten, to graphs]
- Patrick Suppes, Representation and Invariance of Scientific Structures [Provides a very counter-intuitive proof, originally presented in papers from the 1960s and 1970s, that certain stimulus-response learning models can, asymptotically, become isomorphic to arbitrary grammars.]
- To read:
- Juan-Carlos Amengual, Alberto Sanchis, Enrique Vidal and Jose-Miguel Benedi, "Language Simplification through Error-Correcting and Grammatical Inference Techniques," Machine Learning 44 (2001): 143--159
- Miguel Bugalho and Arlindo L. Oliveira, "Inference of regular languages using state merging algorithms with search", Pattern Recognition 38 (2005): 1457--1467
- Andreas Blume, "A Learning-Efficiency Explanation of Structure in Language", Theory and Decision 57 (2004): 265--285
- Roberto Bonato, "A Study on Learnability for Rigid Lambek Grammars", cs.LG/0608033 ["we present Lambek grammars, a formalism issued from categorial grammars which, although not as expressive as needed for a full formalization of natural languages, is particularly suited to easily implement a natural interface between syntax and semantics. In the last part of this work, we present a learnability result for Rigid Lambek grammars from structured examples."]
- Rafael C. Carrasco, Jose Oncina and Jorge Calera-Rubio, "Stochastic Inference of Regular Tree Languages," Machine Learning 44 (2001): 185--197
- Francisco Casacuberta, Enrique Vidal and David Picó, "Inference of finite-state transducers from regular languages", Pattern Recognition 38 (2005): 1431--1443 ["Given a training corpus of input-output pairs of sentences, the proposed approach uses statistical alignment methods to produce a set of conventional strings from which a stochastic finite-state grammar is inferred. This grammar is finally transformed into a resulting finite-state transducer."]
- P. Collet, A. Galves and A. Lopes, "Maximum Likelihood and Minimum Entropy Identfication of Grammars," Random and Computational Dynamics 3 (1995): 241--250
- Colin de la Higuera, "A bibliographical study of grammatical inference", Pattern Recognition 38 (2005): 1332--1348
- C. de la Higuera and J. C. Janodet, "Inference of \omega-languages from prefixes", Theoretical Computer Science 313 (2004): 295--312 [abstract]
- Francois Denis, Aurelien Lemay and Alain Terlutte, "Learning regular languages using RFSAs", Theoretical Computer Science 313 (2004): 267--294 [abstract]
- Francois Denis, Yann Esposito and Amaury Habrard, "Learning rational stochastic languages", cs.LG/0602062
- P. Dupont, F. Denis and Y. Esposito, "Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms", Pattern Recognition 38 (2005): 1349--1371
- Jeroen Geertzen, "String Alignment in Grammatical Inference : what suffix trees can do" [PDF]
- C. Lee Giles, Steve Lawrence and Ah Chung Tsoi, "Noisy Time Series Prediction Using Recurrent Neural Networks and Grammatical Inference," Machine Learning 44 (2001): 161--183
- Bill Keller and Rudi Lutz, "Evolutionary induction of stochastic context free grammars", Pattern Recognition 38 (2005): 1393--1406
- Dan Klein and Christopher D. Manning, "Natural language grammar induction with a generative constituent-context model", Pattern Recognition 38 (2005): 1407--1419 ["We present a generative probabilistic model for the unsupervised learning of hierarchical natural language syntactic structure. Unlike most previous work, we do not learn a context-free grammar, but rather induce a distributional model of constituents which explicitly relates constituent yields and their linear contexts.... [Gets the] best published unsupervised parsing results on the ATIS corpus...."]
- Leo Kontorovich, John Lafferty and David Blei, "Variational Inference and Learning for a Unified Model of Syntax, Semantics and Morphology" [Abstract, PDF]
- The Informational Complexity of Learning: Perspectives on Neural Networks and Generative Grammars [How many licks does it take to get to the core of a context-free grammar, Uncle Noam?]
- The Computational Nature of Language Learning and Evolution [Blurb]
- "Grammatical Inference in Bioinformatics", IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (2005): 1051--1062
- "Learning context-free grammars using tabular representations", Pattern Recognition 38 (2005): 1272--1383 ["By employing this representation... the problem of learning context-free grammars from [positive and negative] examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem."]
