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

Peter Norvig on Chomsky and statistical versus explanatory models of natural language syntax. Full of sick burns.

In January of 2011, television personality Bill O’Reilly weighed in on more than one culture war with his statement “tide goes in, tide goes out. Never a miscommunication. You can’t explain that,” which he proposed as an argument for the existence of God. […] O’Reilly realizes that it doesn’t matter what his detractors think of his astronomical ignorance, because his supporters think he has gotten exactly to the key issue:

*why*? He doesn’t care*how*the tides work, tell him*why*they work.*Why*is the moon at the right distance to provide a gentle tide, and exert a stabilizing effect on earth’s axis of rotation, thus protecting life here?*Why*does gravity work the way it does? Why does anything at all exist rather than not exist? O’Reilly is correct that these questions can only be addressed by mythmaking, religion or philosophy, not by science.Chomsky has a philosophy based on the idea that we should focus on the deep whys and that mere explanations of reality don’t matter. In this, Chomsky is in complete agreement with O’Reilly. (I recognize that the previous sentence would have an extremely low probability in a probabilistic model trained on a newspaper or TV corpus.)

Cosma Shalizi’s inevitable mention in 3, 2, 1… go

## Refs

- Higu05: (2005) A bibliographical study of grammatical inference.
*Pattern Recognition*, 38(9), 1332–1348. DOI - JiKo11: (2011) A compact statistical model of the song syntax in Bengalese finch.
*PLoS Comput Biol*, 7(3), 1001108. DOI - GaBa14: (2014) A consistent deterministic regression tree for non-parametric prediction of time series.
*ArXiv:1405.1533 [Cs, Math, Stat]*. - MoRi16: (2016) A disambiguation algorithm for weighted automata.
*Theoretical Computer Science*. DOI - Grün96: (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
- Vali84: (1984) A theory of the learnable.
*Commun. ACM*, 27(11), 1134–1142. DOI - BaPo99: (1999)
*Complexity: Hierarchical Structures and Scaling in Physics*. Cambridge University Press - ShCr00: (2000) Computational Mechanics: Pattern and Prediction, Structure and Simplicity.
- Higu00: (2000) Current Trends in Grammatical Inference. In Advances in Pattern Recognition (Vol. 1876, pp. 28–31). Springer Berlin / Heidelberg
- Elma91: (1991) Distributed representations, simple recurrent networks, and grammatical structure.
*Machine Learning*, 7, 195–225. DOI - NoKN01: (2001) Evolution of universal grammar.
*Science*, 291, 114–118. DOI - Vali09: (2009) Evolvability.
*J. ACM*, 56(1), 3:1–3:21. DOI - KeLu97: (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
- GSFT12: (2012) Exploiting compositionality to explore a large space of model structures. In Proceedings of the Conference on Uncertainty in Artificial Intelligence.
- Elma90: (1990) Finding structure in time.
*Cognitive Science*, 14, 179–211. DOI - Jack02: (2002)
*Foundations of Language: Brain, Meaning, Grammar, Evolution*. Oxford University Press, USA - MaSc99: (1999)
*Foundations of statistical natural language processing*. Cambridge, Mass.: MIT Press - John04: (2004) Gold’s Theorem and Cognitive Science.
*Philosophy of Science*, 71(4), 571–592. DOI - VKKP15: (2015) Grammar as a Foreign Language. In Advances in Neural Information Processing Systems 28 (pp. 2755–2763). Curran Associates, Inc.
- Higu10: (2010)
*Grammatical inference : learning automata and grammars*. Cambridge; New York: Cambridge University Press - BTCB14: (2014) How Could Language Have Evolved?
*PLoS Biol*, 12(8), e1001934. DOI - NeWi97: (1997) Identifying Hierarchical Structure in Sequences: A linear-time algorithm.
- LóSG04: (2004) Inference of reversible tree languages.
*IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics*, 34(4), 1658–1665. DOI - Gold67: (1967) Language identification in the limit.
*Information and Control*, 10(5), 447–474. DOI - Elma93: (1993) Learning and development in neural networks: the importance of starting small.
*Cognition*, 48, 71–99. DOI - TBCC07: (2007) Learning grammatical structure with Echo State Networks.
*Neural Networks*, 20(3), 424–432. DOI - HiPT06: (2006) Learning Stochastic Finite Automata for Musical Style Recognition. In Implementation and Application of Automata (Vol. 3845, pp. 345–346). Springer Berlin / Heidelberg
- BoBV12: (2012) Modeling Temporal Dependencies in High-Dimensional Sequences: Application to Polyphonic Music Generation and Transcription. In 29th International Conference on Machine Learning.
- PiBl90: (1990) Natural language and natural selection.
*Behavioral and Brain Sciences*, 13, 707. - FeKH04: (2004) Neural mechanisms of vocal sequence generation in the songbird.
*Annals of the New York Academy of Sciences*, 1016, 153–170. DOI - Smit84: (1984) Plants, fractals, and formal languages. In SIGGRAPH Comput. Graph. (Vol. 18, pp. 1–10). ACM DOI
- VTHC05a: (2005a) Probabilistic finite-state machines - part I.
*IEEE Transactions on Pattern Analysis and Machine Intelligence*, 27(7), 1013–1025. DOI - VTHC05b: (2005b) Probabilistic finite-state machines - part II.
*IEEE Transactions on Pattern Analysis and Machine Intelligence*, 27(7), 1026–1039. DOI - ChMa06: (2006) Probabilistic models of language processing and acquisition.
*Trends in Cognitive Sciences*, 10(7), 335–344. DOI - Mann02: (2002) Probabilistic syntax. In Probabilistic linguistics (pp. 289–341). Cambridge, MA: MIT Press
- GiSB11: (2011) Reoccurring Patterns in Hierarchical Protein Materials and Music: The Power of Analogies.
*BioNanoScience*, 1(4), 153–161. DOI - Char96a: (1996a)
*Statistical Language Learning*. A Bradford Book - HeLM04: (2004) Stochastic Graph Transformation Systems. In Graph Transformations (Vol. 3256, pp. 243–246). Springer Berlin / Heidelberg
- DLGT13: (2013) Structure Discovery in Nonparametric Regression through Compositional Kernel Search. In Proceedings of the 30th International Conference on Machine Learning (ICML-13) (pp. 1166–1174).
- Chom02: (2002)
*Syntactic Structures*. Walter de Gruyter - Chom56: (1956) Three models for the description of language.
*IRE Transactions on Information Theory*, 2(3), 113–124. DOI - Char96b: (1996b) Tree-bank Grammars. In In Proceedings of the Thirteenth National Conference on Artificial Intelligence (pp. 1031–1036).