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 characterised 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-Lof (there may be more than one such measure). The technical tool is the theory of Kolmogorov complexity. We analyse the associated predictions in both cases. We also briefly consider special cases, including language learning, and wider theoretical implications for psychology.
Recommendations
Cites work
- scientific article; zbMATH DE number 3427210 (Why is no real title available?)
- scientific article; zbMATH DE number 3136643 (Why is no real title available?)
- scientific article; zbMATH DE number 3438120 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3068529 (Why is no real title available?)
- scientific article; zbMATH DE number 3093119 (Why is no real title available?)
- A formal theory of inductive inference. Part II
- Algorithmic identification of probabilities is hard
- An introduction to Kolmogorov complexity and its applications
- How to grow a mind: statistics, structure, and abstraction
- Language identification in the limit
- Learning recursive functions: A survey
- Limiting recursion
- Merging of Opinions with Increasing Information
- Minimum complexity density estimation
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Prediction and Entropy of Printed English
- Quantum theory, the Church–Turing principle and the universal quantum computer
- The definition of random sequences
- `Ideal learning' of natural language: positive results about learning from positive evidence
Cited in
(6)- Unprincipled
- Identification of probability measures via distribution of quotients
- Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy
- Absolutely no free lunches!
- Algorithmic identification of probabilities is hard
- Equivalences between learning of data and probability distributions, and their applications
This page was built for publication: Identification of probabilities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q514153)
