‘Ideal learning’ of natural language: Positive results about learning from positive evidence
Open accessThe DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Abstract
Within psychology, neuroscience and artificial intelligence, there has been increasing interest in the proposal that the brain builds probabilistic models of sensory and linguistic input: that is, to infer a probabilistic model from a sample. The practical problems of such inference are substantial: the brain has limited data and restricted computational resources. But there is a more fundamental question: is the problem of inferring a probabilistic model from a sample possible even in principle? We explore this question and find some surprisingly positive and general results. First, for a broad class of probability distributions characterized by computability restrictions, we specify a learning algorithm that will almost surely identify a probability distribution in the limit given a finite i.i.d. sample of sufficient but unknown length. This is similarly shown to hold for sequences generated by a broad class of Markov chains, subject to computability assumptions. The technical tool is the strong law of large numbers. Second, for a large class of dependent sequences, we specify an algorithm which identifies in the limit a computable measure for which the sequence is typical, in the sense of Martin-Löf (there may be more than one such measure). The technical tool is the theory of Kolmogorov complexity. We analyze the associated predictions in both cases. We also briefly consider special cases, including language learning, and wider theoretical implications for psychology.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Whatever next? Predictive brains, situated agents, and the future of cognitive science
Clark, A. (2013) · Behavioral and Brain Sciences · doi:10.1017/s0140525x12000477 · Cited by 5,924
Statistical learning by 8-month-old infants
Saffran, J. R., Aslin, R. N., & Newport, E. L. (1996) · Science · doi:10.1126/science.274.5294.1926 · Cited by 5,659
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597
Language identification in the limit
Gold, E. M. (1967) · Information and Control · doi:10.1016/s0019-9958(67)91165-5 · Cited by 3,572 · cited 6×
“Previous results in the formal analysis of language learnability have reached more pessimistic conclusions, using different assumptions (Gold, 1967; Jain, Osherson, Royer, & Sharma, 1999).”
InfluentialA learning algorithm for Boltzmann machines
Ackley, D. H., Hinton, G. E., & Sejnowski, T. J. (1985) · Cognitive Science · doi:10.1207/s15516709cog0901_7 · Cited by 3,402
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
Prediction and Entropy of Printed English
Shannon, C. E. (1951) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1951.tb01366.x · Cited by 2,686
The Bayesian brain: The role of uncertainty in neural coding and computation
Knill, D. C., & Pouget, A. (2004) · Trends in Neurosciences · doi:10.1016/j.tins.2004.10.007 · Cited by 2,588 · cited 2×
“Finally, the view that the brain recovers probabilistic models from sensory data is both theoretically prevalent and has received considerable empirical support in neuroscience ([36]).”
Learning and development in neural networks: the importance of starting small
Elman, J. L. (1993) · Cognition · doi:10.1016/0010-0277(93)90058-4 · Cited by 1,988
How to grow a mind: Statistics, structure, and abstraction
Tenenbaum, J. B., Kemp, C., Griffiths, T. L., & Goodman, N. D. (2011) · Science · doi:10.1126/science.1192788 · Cited by 1,815
Cited by
The myth of language universals: Language diversity and its importance for cognitive science
Evans, N., & Levinson, S. C. (2009) · Behavioral and Brain Sciences · doi:10.1017/s0140525x0999094x · Cited by 2,623
Language as shaped by the brain
Christiansen, M. H., & Chater, N. (2008) · Behavioral and Brain Sciences · doi:10.1017/s0140525x08004998 · Cited by 1,063
Self-citationProbabilistic models of cognition: exploring representations and inductive biases
Griffiths, T. L., Chater, N., Kemp, C., Perfors, A., & Tenenbaum, J. B. (2010) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2010.05.004 · Cited by 568
How Efficiency Shapes Human Language
Gibson, E., Futrell, R., Piantadosi, S. P., Dautriche, I., Mahowald, K., Bergen, L., & Levy, R. (2019) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2019.02.003 · Cited by 485
“Essentially, a language that is more complex is harder to learn than one which is simpler, a general property of algorithmic and statistical theories of learning [132, 133, 129].”
The learnability of abstract syntactic principles
Perfors, A., Tenenbaum, J. B., & Regier, T. (2011) · Cognition · doi:10.1016/j.cognition.2010.11.001 · Cited by 285
Metadata
- Authors
- Chater, N., & Vitányi, P.
- Venue
- Journal of Mathematical Psychology
- Publisher
- Elsevier BV
- Published
- 2007-06
- Volume
- 51
- Issue
- 3
- Pages
- 135-163
- ISSN
- 0022-2496 (ISSN-L)
- OpenAlex
- W2054986668
- Cited by
- 113
- References
- 21
- FWCI
- 16.61
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: ‘Ideal learning’ of natural language: Positive results about learning from positive evidence. https://app.cochat.ai/papers/10.1016/j.jmp.2006.10.002
- The paper
- Chater, N., & Vitányi, P. (2007). ‘Ideal learning’ of natural language: Positive results about learning from positive evidence. Journal of Mathematical Psychology. https://doi.org/10.1016/j.jmp.2006.10.002
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.