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.

Software

Things to read

Arau00
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).
AKHC06
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.
BaPo99
Badii, R., & Politi, A. (1999) Complexity: Hierarchical Structures and Scaling in Physics (Cambridge Nonlinear Science Series). . Cambridge University Press
BDGH10
Bailly, R., Denis, F., Gilbert, É., & Habrard, A. (2010) Using PCA for Probabilistic Grammatical Inference on Trees.
BaHu93
Barnsley, M., & Hurd, L. (1993) Fractal Image Compression. . A K Peters/CRC Press
Bart83
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
BTCB14
Bolhuis, J. J., Tattersall, I., Chomsky, N., & Berwick, R. C.(2014) How Could Language Have Evolved?. PLoS Biol, 12(8), e1001934. DOI.
BoBV12
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.
CaHi00
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
Char96a
Charniak, E. (1996a) Statistical Language Learning. (Reprint.). A Bradford Book
Char96b
Charniak, E. (1996b) Tree-bank Grammars. In In Proceedings of the Thirteenth National Conference on Artificial Intelligence (pp. 1031–1036).
ChMa06
Chater, N., & Manning, C. D.(2006) Probabilistic models of language processing and acquisition. Trends Cogn Sci, 10(7), 335–344. DOI.
Chom56
Chomsky, N. (1956) Three models for the description of language. IRE Transactions on Information Theory, 2(3), 113–124. DOI.
Chom69
Chomsky, N. (1969) Aspects of the Theory of Syntax. . The MIT Press
Chom02
Chomsky, N. (2002) Syntactic Structures. (2nd ed.). Walter de Gruyter
CDEC02
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.
CrVi08
Cruz-Alcázar, P. P., & Vidal, E. (2008) Two grammatical inference applications in music processing. Applied Artificial Intelligence, 22(1-2), 53–76. DOI.
CrVi98
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
Dede11
DeDeo, S. (2011) Effective Theories for Circuits and Automata. Chaos, 21. DOI.
Higu00
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
Higu05
de la Higuera, C. (2005) A bibliographical study of grammatical inference. Pattern Recognition, 38(9), 1332–1348. DOI.
Higu10
de la Higuera, C. (2010) Grammatical inference : learning automata and grammars. . Cambridge; New York: Cambridge University Press
HiPT06
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
DeLT04
Denis, F., Lemay, A., & Terlutte, A. (2004) Learning regular languages using RFSAs. Algorithmic Learning Theory, 313, 267–294. DOI.
DLGT13
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].
DTBK99
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
Elle14
Ellerman, D. (2014) Four Ways from Universal to Particular: How Chomsky’s Language-Acquisition Faculty is Not Selectionist. arXiv:1410.4501 [math].
Elli71
Ellis, C. A.(1971) Probabilistic tree automata. Information and Control, 19(5), 401–416. DOI.
Elma90
Elman, J. L.(1990) Finding structure in time. Cognitive Science, 14, 179–211. DOI.
Elma91
Elman, J. L.(1991) Distributed representations, simple recurrent networks, and grammatical structure. Machine Learning, 7, 195–225. DOI.
Elma93
Elman, J. L.(1993) Learning and development in neural networks: the importance of starting small. Cognition, 48, 71–99. DOI.
Elma03
Elman, J. L.(2003) Generalization from Sparse Input. In Proceedings of the 38th Annual Meeting of the Chicago Linguistic Society. Citeseer
FeKH04
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.
Flas07
Flasiński, M. (2007) Inference of parsable graph grammars for syntactic pattern recognition. Fundamenta Informaticae, 80(4), 379–413.
GaBa14
Gaillard, P., & Baudin, P. (2014) A consistent deterministic regression tree for non-parametric prediction of time series. arXiv:1405.1533 [cs, Math, Stat].
GaLe14
Gallo, S., & Leonardi, F. G.(2014) Nonparametric statistical inference for the context tree of a stationary ergodic process. arXiv:1411.7650 [math, Stat].
GiSB11
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.
Gold67
Gold, E. M.(1967) Language identification in the limit. Information and Control, 10(5), 447–474. DOI.
GSFT12
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ün96:
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
HeLM04
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
Horn69
Horning, J. J.(1969) A study of grammatical inference.
Jack02
Jackendoff, R. (2002) Foundations of Language: Brain, Meaning, Grammar, Evolution. . Oxford University Press, USA
JiKo11
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.
John04
Johnson, K. (2004) Gold’s Theorem and Cognitive Science. Philosophy of Science, 71(4), 571–592. DOI.
JoHC04
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.
KeLu97
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
KeLu05
Keller, B., & Lutz, R. (2005) Evolutionary induction of stochastic context free grammars. Pattern Recognition, 38(9), 1393–1406. DOI.
KiBe92
Kippen, J., & Bel, B. (1992) Modelling music with grammars: formal language representation in the Bol Processor. Computer Representations and Models in Music, 207–232.
Koza93
Koza, J. R.(1993) Discovery of rewrite rules in Lindenmayer systems and state transition rules in cellular automata via genetic programming.
KuHC06
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.
LWPX09
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óSG04:
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.
Mann02
Manning, C. D.(2002) Probabilistic syntax. In Probabilistic linguistics (pp. 289–341). Cambridge, MA: MIT Press
MaSc99
Manning, C. D., & Schütze, H. (1999) Foundations of statistical natural language processing. . Cambridge, Mass.: MIT Press
MZWV07
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.
NeWi97
Nevill-Manning, C. G., & Witten, I. H.(1997) Identifying Hierarchical Structure in Sequences: A linear-time algorithm.
NoKN01
Nowak, M. A., Komarova, N. L., & Niyogi, P. (2001) Evolution of universal grammar. Science, 291, 114–118. DOI.
Pere00
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.
PiBl90
Pinker, S., & Bloom, P. (1990) Natural language and natural selection. Behavioral and Brain Sciences, 13, 707.
ShCr00
Shalizi, C. R., & Crutchfield, J. P.(2000) Computational Mechanics: Pattern and Prediction, Structure and Simplicity.
Smit84
Smith, A. R.(1984) Plants, fractals, and formal languages. In SIGGRAPH Comput. Graph. (Vol. 18, pp. 1–10). ACM DOI.
SmWi95
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
StOm94
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
ToDK98
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.
THRB10
Torrini, P., Heckel, R., Rath, I., & Bergmann, G. (2010) Stochastic Graph Transformation with Regions. Electronic Communications of the EASST, 29.
Vali84
Valiant, L. G.(1984) A theory of the learnable. Commun. ACM, 27(11), 1134–1142. DOI.
Vali09
Valiant, L. G.(2009) Evolvability. J. ACM, 56(1), 3:1–3:21. DOI.
VTHC05a
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.
VTHC05b
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.
VKKP15
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.
ZhZh11
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