Hostname: page-component-7b7567c8c-lpg2g Total loading time: 0 Render date: 2026-11-15T21:25:22.737Z Has data issue: false hasContentIssue false
  • English
  • Français

No Free Lunch in Linguistics Or Machine Learning: Response to Pater

Published online by Cambridge University Press:  01 January 2026

Jonathan Rawski and
Jeffrey Heinz
Jonathan Rawski*
Affiliation:
Stony Brook University
Jeffrey Heinz*
Affiliation:
Stony Brook University
*
Department of Linguistics, Institute for Advanced Computational Science, Stony Brook University [jonathan.rawski@stonybrook.edu]
Department of Linguistics, Institute for Advanced Computational Science, Stony Brook University [jonathan.rawski@stonybrook.edu]
Get accessRights & Permissions [Opens in a new window]

Abstract

Pater's (2019) target article proposes that neural networks will provide theories of learning that generative grammar lacks. We argue that his enthusiasm is premature since the biases of neural networks are largely unknown, and he disregards decades of work on machine learning and learnability. Learning biases form a two-way street: all learners have biases, and those biases constrain the space of learnable grammars in mathematically measurable ways. Analytical methods from the related fields of computational learning theory and grammatical inference allow one to study language learning, neural networks, and linguistics at an appropriate level of abstraction. The only way to satisfy our hunger and to make progress on the science of language learning is to confront these core issues directly.

Keywords

learnabilitycomputational learning theoryneural networkspoverty of the stimuluslanguage acquisition

Information

Type
Perspectives
Information
Language , Volume 95 , Issue 1 , March 2019, pp. e125 - e135
Copyright
Copyright © 2019 Linguistic Society of America

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

*

We thank Alëna Aksënova, Aniello de Santo, Hossep Dolatian, and William Idsardi for helpful discussions.

References

Angluin, Dana. 1987. Learning regular sets from queries and counterexamples. Information and Computation 75. 87–106. DOI: 10.1016/0890-5401(87)90052-6.CrossRefGoogle Scholar
Angluin, Dana. 1988. Queries and concept learning. Machine Learning 2. 319-42. DOI: 10.1023/A:1022821128753.CrossRefGoogle Scholar
Applegate, Richard B. 1972. Ineseño Chumash grammar. Berkeley: University of California, Berkeley dissertation.Google Scholar
Avcu, Enes, Shibata, Chihiro; and Heinz, Jeffrey. 2017. Subregular complexity and deep learning. CLASP papers in computational linguistics: Proceedings of the Conference on Logic and Machine Learning in Natural Language (LaML 2017), Gothenburg, 12–13 June, ed. by Dobnik, Simon and Lappin, Shalom, 20–33.Google Scholar
Ayache, Stéphane, Eyraud, Rémi; and Goudian, Noé. 2018. Explaining black boxes on sequential data using weighted automata. Proceedings of Machine Learning Research (Proceedings of the 14th International Conference on Grammatical Inference) 93. 81–103.Google Scholar
Bach, Emmon W. 1975. Long vowels and stress in Kwakiutl. Texas Linguistic Forum 2. 9–19.Google Scholar
Berwick, Robert. 1985. The acquisition of syntactic knowledge. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Chater, Nick, and Vitányi, Paul. 2007. ‘Ideal learning’ of natural language: Positive results about learning from positive evidence. Journal of Mathematical Psychology 51. 135-63. DOI: 10.1016/j.jmp.2006.10.002.CrossRefGoogle Scholar
Chomsky, Noam. 1956. Three models for the description of language. IRE Transactions on Information Theory 2. 113-24. DOI: 10.1109/TIT.1956.1056813.Google Scholar
Chomsky, Noam. 1959. On certain formal properties of grammars. Information and Control 2. 137-67. DOI: 10.1016/S0019-9958(59)90362-6.CrossRefGoogle Scholar
Clark, Alexander. 2010. Three learnable models for the description of language. Language and Automata Theory and Applications (LATA 2010), 16–31. DOI: 10.1007/978-3-642-13089-2_2.CrossRefGoogle Scholar
Clark, Alexander, and Lappin, Shalom. 2011. Linguistic nativism and the poverty of the stimulus. Oxford: Wiley-Blackwell.CrossRefGoogle Scholar
Clements, George N., and Keyser, Samuel Jay. 1983. CV phonology: A generative theory of the syllable. Cambridge, MA: MIT Press.Google Scholar
de la Higuera, Colin. 2010. Grammatical inference: Learning automata and grammars. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Gold, E. Mark. 1967. Language identification in the limit. Information and Control 10. 447-74. DOI: 10.1016/S0019-9958(67)91165-5.CrossRefGoogle Scholar
Goldwater, Sharon, and Johnson, Mark. 2003. Learning OT constraint rankings using a maximum entropy model. Proceedings of the Stockholm Workshop on Variation within Optimality Theory, ed. by Spenader, Jennifer, Eriksson, Anders, and Dahl, Östen, 111-20.Google Scholar
Griffiths, Thomas, Kemp, Charles; and Tenenbaum, Joshua. 2008. Bayesian models of cognition. The Cambridge handbook of computational cognitive modeling, ed. by Sun, Ron, 59–100. Cambridge: Cambridge University Press.Google Scholar
Harrison, Michael A. 1978. Introduction to formal language theory. Boston: Addison-Wesley.Google Scholar
Heinz, Jeffrey. 2010. Learning long-distance phonotactics. Linguistic Inquiry 41. 623-61. DOI: 10.1162/LING_a_00015.CrossRefGoogle Scholar
Heinz, Jeffrey. 2016. Computational theories of learning and developmental psycholinguistics. The Oxford handbook of developmental linguistics, ed. by Lidz, Jeffrey, Synder, William, and Pater, Joe, 633-63. Oxford: Oxford University Press. DOI: 10.1093/oxfordhb/9780199601264.013.27.Google Scholar
Heinz, Jeffrey. 2018. The computational nature of phonological generalizations. Phonological typology (Phonology and phonetics 23), ed. by Hyman, Larry and Plank, Frans, 126-95. Berlin: De Gruyter Mouton.Google Scholar
Heinz, Jeffrey, de, Colin Higuera, la; and Zaanen, Menno van. 2015. Grammatical inference for computational linguistics. (Synthesis lectures on human language technologies.) San Rafael, CA: Morgan and Claypool. DOI: 10.2200/S00643ED1V01Y201504HLT028.Google Scholar
Heinz, Jeffrey, and Idsardi, William. 2011. Sentence and word complexity. Science 333. 295-97. DOI: 10.1126/science.1210358.CrossRefGoogle ScholarPubMed
Heinz, Jeffrey, and Idsardi, William. 2013. What complexity differences reveal about domains in language. Topics in Cognitive Science 5. 111-31. DOI: 10.1111/tops.12000.CrossRefGoogle ScholarPubMed
Heinz, Jeffrey, and Sempere, José (eds.) 2016. Topics in grammatical inference. Berlin: Springer.CrossRefGoogle Scholar
Hopcroft, John, Motwani, Rajeev; and Ullman, Jeffrey. 1979. Introduction to automata theory, languages, and computation. Boston: Addison-Wesley.Google Scholar
Jäger, Gerhard, and Rogers, James. 2012. Formal language theory: Refining the Chomsky hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences 367(1598). 1956-70. DOI: 10.1098/rstb.2012.0077.CrossRefGoogle ScholarPubMed
Kearns, Michael, Li, Ming, Pitt, Leonard; and Valiant, Leslie. 1987. On the learnability of Boolean formulae. Proceedings of the nineteenth annual ACM Symposium on Theory of Computing, 285-95. DOI: 10.1145/28395.28426.CrossRefGoogle Scholar
Kleene, Stephen C. 1956. Representation of events in nerve nets and finite automata. Automata studies (Annals of mathematical studies 34), ed. by Shannon, Claude E. and McCarthy, John, 3–41. Princeton, NJ: Princeton University Press.CrossRefGoogle Scholar
Kobele, Gregory. 2006. Generating copies: An investigation into structural identity in language and grammar. Los Angeles: University of California, Los Angeles dissertation.Google Scholar
Kornai, András. 2011. Probabilistic grammars and languages. Journal of Logic, Language and Information 20. 317-28. DOI: 10.1007/s10849-011-9135-z.CrossRefGoogle Scholar
Lappin, Shalom, and Shieber, Stuart M.. 2007. Machine learning theory and practice as a source of insight into universal grammar. Journal of Linguistics 43. 393–427. DOI: 10.1017/S0022226707004628.CrossRefGoogle Scholar
McCulloch, Warren S., and Pitts, Walter. 1943. A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics 5(4). 115-33. DOI: 10.1007/BF02478259.CrossRefGoogle Scholar
Minsky, Marvin L. 1967. Computation: Finite and infinite machines. Upper Saddle River, NJ: Prentice-Hall.Google Scholar
Mitchell, Tom. 2017. Key ideas in machine learning. Pittsburgh, PA: Carnegie Mellon University, ms. (Draft chapter for Machine learning, 2nd edn., McGraw Hill, to appear.) Online: http://www.cs.cmu.edu/~tom/mlbook/keyIdeas.pdf.Google Scholar
Niyogi, Partha. 2006. The computational nature of language learning and evolution. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Nowak, Martin A., Komarova, Natalia L.; and Niyogi, Partha. 2001. Evolution of universal grammar. Science 291. 114-18. DOI: 10.1126/science.291.5501.114.CrossRefGoogle ScholarPubMed
Nowak, Martin A., Komarova, Natalia L.; and Niyogi, Partha. 2002. Computational and evolutionary aspects of language. Nature 417. 611-17. DOI: 10.1038/nature00771.CrossRefGoogle ScholarPubMed
Oncina, José, and Garcia, Pedro. 1992. Identifying regular languages in polynomial time. Advances in structural and syntactic pattern recognition (Series in machine perception and artificial intelligence 5), ed. by Bunke, Horst, 99–108. DOI: 10.1142/9789812797919_0007.CrossRefGoogle Scholar
Osherson, Daniel, Weinstein, Scott; and Stob, Michael. 1986. Systems that learn. Cambridge, MA: MIT Press.Google Scholar
Pater, Joe. 2019. Generative linguistics and neural networks at 60: Foundation, friction, and fusion. Language 95(1). e41–e74.CrossRefGoogle Scholar
Perrin, Dominique. 1990. Finite automata. Handbook of theoretical computer science, vol. B: Formal models and semantics, ed. by Leeuwen, Jan van, 1–57. Amsterdam: Elsevier.Google Scholar
Piattelli-Palmarini, Massimo (ed.) 1980. Language and learning: The debate between Jean Piaget and Noam Chomsky. Cambridge, MA: Harvard University Press.Google Scholar
Rahimi, Ali, and Recht, Ben. 2017. Reflections on random kitchen sinks. arg min blog, December 5, 2017. Online: http://www.argmin.net/2017/12/05/kitchen-sinks/.Google Scholar
Rumelhart, David E., and McClelland, James L.. 1986. On learning the past tenses of English verbs. Parallel distributed processing: Explorations in the microstructures of cognition, vol. 2, ed. by Rumelhart, David E., McClelland, James L., and PDP, the Group, Research, 216-71. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Shieber, Stuart. 1985. Evidence against the context-freeness of natural language. Linguistics and Philosophy 8. 333-43. DOI: 10.1007/BF00630917.CrossRefGoogle Scholar
Steedman, Mark. 2008. On becoming a discipline. Computational Linguistics 34. 137-44. DOI: 10.1162/coli.2008.34.1.137.CrossRefGoogle Scholar
Tesar, Bruce, and Smolensky, Paul. 2000. Learnability in optimality theory. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Valiant, Leslie. 1984. A theory of the learnable. Communications of the ACM 27. 1134-42. DOI: 10.1145/1968.1972.CrossRefGoogle Scholar
Weiss, Gail, Goldberg, Yoav; and Yahav, Eran. 2018. Extracting automata from recurrent neural networks using queries and counterexamples. Proceedings of Machine Learning Research (Proceedings of the 35th International Conference on Machine Learning) 80. 5247-56. Online: http://proceedings.mlr.press/v80/weiss18a.html.Google Scholar
Wexler, Kenneth, and Culicover, Peter. 1980. Formal principles of language acquisition. Cambridge, MA: MIT Press.Google Scholar
Wolpert, David H., and Macready, William G.. 1997. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1. 67–82. DOI: 10.1109/4235.585893.CrossRefGoogle Scholar
Yang, Charles. 2013. Who's afraid of George Kingsley Zipf? Or: Do children and chimps have language? Significance 10. 29–34. DOI: 10.1111/j.1740-9713.2013.00708.x.CrossRefGoogle Scholar