Identification of probabilities

DOI10.1016/J.JMP.2016.11.004zbMATH Open1396.91659arXiv1708.01611OpenAlexW2761369391WikidataQ37686913 ScholiaQ37686913MaRDI QIDQ514153FDOQ514153

Authors: Paul M. B. Vitányi, Nick Chater 

Publication date: 28 February 2017

Published in: Journal of Mathematical Psychology (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1708.01611

Recommendations

• Probabilistic inductive inference
• Algorithmic Probability: Theory and Applications
• Algorithmic identification of probabilities is hard
• On the power of probabilistic strategies in inductive inference
• scientific article; zbMATH DE number 1283992

zbMATH Keywords

Markov chainlearningstrong law of large numbersKolmogorov complexitytypicalityBayesian brain, identificationcomputable measurecomputable probabilityMartin-Löf randomness

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Learning and adaptive systems in artificial intelligence (68T05) Memory and learning in psychology (91E40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimum complexity density estimation
• Merging of Opinions with Increasing Information
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Title not available (Why is that?)
• Title not available (Why is that?)
• The definition of random sequences
• Language identification in the limit
• A formal theory of inductive inference. Part II
• Prediction and Entropy of Printed English
• On Computable Numbers, with an Application to the Entscheidungsproblem
• An introduction to Kolmogorov complexity and its applications
• Learning recursive functions: A survey
• How to grow a mind: statistics, structure, and abstraction
• Limiting recursion
• Title not available (Why is that?)
• `Ideal learning' of natural language: positive results about learning from positive evidence
• Algorithmic identification of probabilities is hard
• Title not available (Why is that?)

Cited In (6)

• Unprincipled
• Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy
• Equivalences between learning of data and probability distributions, and their applications
• Algorithmic identification of probabilities is hard
• Identification of probability measures via distribution of quotients
• Absolutely no free lunches!

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)