The Living Thing / Notebooks :

Grammatical inference

Mathematically speaking, inferring the “formal language” which can describe a set of expressions. In the slightly looser sense used by linguists studying natural human language, discovering the syntactic rules of a given language, which is kinda the same thing but with every term sloppier, and the subject matter itself messier.

This is already a crazy complex area, and being naturally perverse, I am interested in an especially esoteric corner of it, to whit, grammars of things that aren’t speech; inferring design grammars, say, could allow you to produce more things off the same “basic plan” from some examples of the thing; look at enough trees and you know how to build the rest of the forest, that kind of thing. I’m especially interested in things expressed not as a sequence of symbols from a finite alphabet - i.e. not over the free monoid, or over the free monoid but the symbol expression is hidden. This is a boutique interest. I also care about probabilistic ones, i.e. assigning measures to these things. That part is not at all boutique.

Normally design grammars deal with simple languages, such as, say “regular” languages. I’m interested in things a rung or two up the Chomsky hierarchy - Context-free grammars, maybe even context-sensitive ones.

See also design grammars, iterated function systems and my research proposal in this area.

Things to read


Araujo, L. (2000) Evolutionary parsing for a probabilistic context free grammar. In Proc. of the Int. Conf. on on Rough Sets and Current Trends in Computing (RSCTC-2000), Lecture Notes in Computer Science 2005 (p. 590).
Ates, K., Kukluk, J., Holder, L., Cook, D., & Zhang, K. (2006) Graph grammar induction on structural data for visual programming. In 18th IEEE International Conference on Tools with Artificial Intelligence, 2006. ICTAI ’06 (pp. 232–242). DOI.
Badii, R., & Politi, A. (1999) Complexity: Hierarchical Structures and Scaling in Physics (Cambridge Nonlinear Science Series). . Cambridge University Press
Bailly, R., Denis, F., Gilbert, É., & Habrard, A. (2010) Using PCA for Probabilistic Grammatical Inference on Trees.
Barnsley, M., & Hurd, L. (1993) Fractal Image Compression. . A K Peters/CRC Press
Bartsch-Spörl, B. (1983) Grammatical inference of graph grammars for syntactic pattern recognition. In H. Ehrig, M. Nagl, & G. Rozenberg (Eds.), Graph-Grammars and Their Application to Computer Science (Vol. 153, pp. 1–7). Springer Berlin / Heidelberg
Bolhuis, J. J., Tattersall, I., Chomsky, N., & Berwick, R. C.(2014) How Could Language Have Evolved?. PLoS Biol, 12(8), e1001934. DOI.
Boulanger-Lewandowski, N., Bengio, Y., & Vincent, P. (2012) Modeling Temporal Dependencies in High-Dimensional Sequences: Application to Polyphonic Music Generation and Transcription. In 29th International Conference on Machine Learning.
Casacuberta, F., & de la Higuera, C. (2000) Computational Complexity of Problems on Probabilistic Grammars and Transducers. In A. Oliveira (Ed.), Grammatical Inference: Algorithms and Applications (Vol. 1891, pp. 211–212). Springer Berlin / Heidelberg
Charniak, E. (1996a) Statistical Language Learning. (Reprint.). A Bradford Book
Charniak, E. (1996b) Tree-bank Grammars. In In Proceedings of the Thirteenth National Conference on Artificial Intelligence (pp. 1031–1036).
Chater, N., & Manning, C. D.(2006) Probabilistic models of language processing and acquisition. Trends Cogn Sci, 10(7), 335–344. DOI.
Chomsky, N. (1956) Three models for the description of language. IRE Transactions on Information Theory, 2(3), 113–124. DOI.
Chomsky, N. (1969) Aspects of the Theory of Syntax. . The MIT Press
Chomsky, N. (2002) Syntactic Structures. (2nd ed.). Walter de Gruyter
Christiansen, M. H., Dale, R. A. C., Ellefson, M. R., & Conway, C. M.(2002) The role of sequential learning in language evolution: computational and experimental studies. In A. Cangelosi & D. Parisi (Eds.), Simulating the Evolution of Language. Springer-Verlag New York, Inc.
Cruz-Alcázar, P. P., & Vidal, E. (2008) Two grammatical inference applications in music processing. Applied Artificial Intelligence, 22(1-2), 53–76. DOI.
Cruz-Alcázar, P., & Vidal-Ruiz, E. (1998) Learning regular grammars to model musical style: Comparing different coding schemes. In V. Honavar & G. Slutzki (Eds.), Grammatical Inference (Vol. 1433, pp. 211–222). Springer Berlin / Heidelberg
DeDeo, S. (2011) Effective Theories for Circuits and Automata. Chaos, 21. DOI.
de la Higuera, C. (2000) Current Trends in Grammatical Inference. In F. Ferri, J. Iñesta, A. Amin, & P. Pudil (Eds.), Advances in Pattern Recognition (Vol. 1876, pp. 28–31). Springer Berlin / Heidelberg
de la Higuera, C. (2005) A bibliographical study of grammatical inference. Pattern Recognition, 38(9), 1332–1348. DOI.
de la Higuera, C. (2010) Grammatical inference : learning automata and grammars. . Cambridge; New York: Cambridge University Press
de la Higuera, C., Piat, F., & Tantini, F. (2006) Learning Stochastic Finite Automata for Musical Style Recognition. In J. Farré, I. Litovsky, & S. Schmitz (Eds.), Implementation and Application of Automata (Vol. 3845, pp. 345–346). Springer Berlin / Heidelberg
Denis, F., Lemay, A., & Terlutte, A. (2004) Learning regular languages using RFSAs. Algorithmic Learning Theory, 313, 267–294. DOI.
Duvenaud, D., Lloyd, J. R., Grosse, R., Tenenbaum, J. B., & Ghahramani, Z. (2013) Structure Discovery in Nonparametric Regression through Compositional Kernel Search. arXiv:1302.4922 [cs, Stat].
Džeroski, S., Todorovski, L., Bratko, I., Kompare, B., & Križman, V. (1999) Equation discovery with ecological applications. In A. H. Fielding (Ed.), Machine Learning Methods for Ecological Applications (pp. 185–207). Springer US
Ellerman, D. (2014) Four Ways from Universal to Particular: How Chomsky’s Language-Acquisition Faculty is Not Selectionist. arXiv:1410.4501 [math].
Ellis, C. A.(1971) Probabilistic tree automata. Information and Control, 19(5), 401–416. DOI.
Elman, J. L.(1990) Finding structure in time. Cognitive Science, 14, 179–211. DOI.
Elman, J. L.(1991) Distributed representations, simple recurrent networks, and grammatical structure. Machine Learning, 7, 195–225. DOI.
Elman, J. L.(1993) Learning and development in neural networks: the importance of starting small. Cognition, 48, 71–99. DOI.
Elman, J. L.(2003) Generalization from Sparse Input. In Proceedings of the 38th Annual Meeting of the Chicago Linguistic Society. Citeseer
Fee, M. S., Kozhevnikov, A. A., & Hahnloser, R. H.(2004) Neural mechanisms of vocal sequence generation in the songbird. Annals of the New York Academy of Sciences, 1016, 153–170. DOI.
Flasiński, M. (2007) Inference of parsable graph grammars for syntactic pattern recognition. Fundamenta Informaticae, 80(4), 379–413.
Gaillard, P., & Baudin, P. (2014) A consistent deterministic regression tree for non-parametric prediction of time series. arXiv:1405.1533 [cs, Math, Stat].
Gallo, S., & Leonardi, F. G.(2014) Nonparametric statistical inference for the context tree of a stationary ergodic process. arXiv:1411.7650 [math, Stat].
Giesa, T., Spivak, D., & Buehler, M. (2011) Reoccurring Patterns in Hierarchical Protein Materials and Music: The Power of Analogies. BioNanoScience, 1(4), 153–161. DOI.
Gold, E. M.(1967) Language identification in the limit. Information and Control, 10(5), 447–474. DOI.
Grosse, R., Salakhutdinov, R. R., Freeman, W. T., & Tenenbaum, J. B.(2012) Exploiting compositionality to explore a large space of model structures. arXiv:1210.4856 [cs, Stat].
Grünwald, P. (1996) A minimum description length approach to grammar inference. In Connectionist, Statistical, and Symbolic Approaches to Learning for Natural Language Processing (Vol. 1040, pp. 203–216). London, UK, UK: Springer-Verlag
Heckel, R., Lajios, G., & Menge, S. (2004) Stochastic Graph Transformation Systems. In H. Ehrig, G. Engels, F. Parisi-Presicce, & G. Rozenberg (Eds.), Graph Transformations (Vol. 3256, pp. 243–246). Springer Berlin / Heidelberg
Horning, J. J.(1969) A study of grammatical inference.
Jackendoff, R. (2002) Foundations of Language: Brain, Meaning, Grammar, Evolution. . Oxford University Press, USA
Jin, D. Z., & Kozhevnikov, A. A.(2011) A compact statistical model of the song syntax in Bengalese finch. PLoS Comput Biol, 7(3), -1001108. DOI.
Johnson, K. (2004) Gold’s Theorem and Cognitive Science. Philosophy of Science, 71(4), 571–592. DOI.
Jonyer, I., Holder, L. B., & Cook, D. J.(2004) MDL-based context-free graph grammar induction and applications. International Journal on Artificial Intelligence Tools, 13(01), 65–79. DOI.
Keller, B., & Lutz, R. (1997) Evolving stochastic context-free grammars from examples using a minimum description length principle. In 1997 Workshop on Automata Induction Grammatical Inference and Language Acquisition. Citeseer
Keller, B., & Lutz, R. (2005) Evolutionary induction of stochastic context free grammars. Pattern Recognition, 38(9), 1393–1406. DOI.
Kippen, J., & Bel, B. (1992) Modelling music with grammars: formal language representation in the Bol Processor. Computer Representations and Models in Music, 207–232.
Koza, J. R.(1993) Discovery of rewrite rules in Lindenmayer systems and state transition rules in cellular automata via genetic programming.
Kukluk, J. P., Holder, L. B., & Cook, D. J.(2006) Inference of Node Replacement Recursive Graph Grammars. In Proceedings of the 2006 SIAM International Conference on Data Mining.
Lin, L., Wu, T., Porway, J., & Xu, Z. (2009) A stochastic graph grammar for compositional object representation and recognition. Pattern Recognition, 42(7), 1297–1307. DOI.
López, D., Sempere, J. M., & García, P. (2004) Inference of reversible tree languages. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 34(4), 1658–1665. DOI.
Manning, C. D.(2002) Probabilistic syntax. In Probabilistic linguistics (pp. 289–341). Cambridge, MA: MIT Press
Manning, C. D., & Schütze, H. (1999) Foundations of statistical natural language processing. . Cambridge, Mass.: MIT Press
Müller, P., Zeng, G., Wonka, P., & Van Gool, L. (2007) Image-based procedural modeling of facades. In ACM SIGGRAPH 2007 papers. New York, NY, USA: ACM DOI.
Nevill-Manning, C. G., & Witten, I. H.(1997) Identifying Hierarchical Structure in Sequences: A linear-time algorithm.
Nowak, M. A., Komarova, N. L., & Niyogi, P. (2001) Evolution of universal grammar. Science, 291, 114–118. DOI.
Pereira, F. (2000) Formal grammar and information theory: together again?. Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 358(1769), 1239–1253. DOI.
Pinker, S., & Bloom, P. (1990) Natural language and natural selection. Behavioral and Brain Sciences, 13, 707.
Shalizi, C. R., & Crutchfield, J. P.(2000) Computational Mechanics: Pattern and Prediction, Structure and Simplicity.
Smith, A. R.(1984) Plants, fractals, and formal languages. In SIGGRAPH Comput. Graph. (Vol. 18, pp. 1–10). ACM DOI.
Smith, T. C., & Witten, I. H.(1995) A Genetic Algorithm for the Induction of Natural Language Grammars. (Vol. 17, p. 17). Presented at the Proc IJCAI-95 Workshop on New Approaches to Learning for Natural Language Processing
Stolcke, A., & Omohundro, S. (1994) Inducing probabilistic grammars by Bayesian model merging. In R. Carrasco & J. Oncina (Eds.), Grammatical Inference and Applications (Vol. 862, pp. 106–118). Springer Berlin / Heidelberg
Todorovski, L., Džeroski, S., & Kompare, B. (1998) Modelling and prediction of phytoplankton growth with equation discovery. Ecological Modelling, 113(1–3), 71–81. DOI.
Torrini, P., Heckel, R., Rath, I., & Bergmann, G. (2010) Stochastic Graph Transformation with Regions. Electronic Communications of the EASST, 29.
Valiant, L. G.(1984) A theory of the learnable. Commun. ACM, 27(11), 1134–1142. DOI.
Valiant, L. G.(2009) Evolvability. J. ACM, 56(1), 3:1–3:21. DOI.
Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., & Carrasco, R. C.(2005a) Probabilistic finite-state machines - part I. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7), 1013–1025. DOI.
Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., & Carrasco, R. C.(2005b) Probabilistic finite-state machines - part II. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7), 1026–1039. DOI.
Vinyals, O., Kaiser, Ł., Koo, T., Petrov, S., Sutskever, I., & Hinton, G. (2015) Grammar as a Foreign Language. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, R. Garnett, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 28 (pp. 2755–2763). Curran Associates, Inc.
Zhao, Y., & Zhu, S.-C. (2011) Image Parsing via Stochastic Scene Grammar. . Presented at the Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS 2011), Granada, Spain