Fulltext

Three Kinds of Probabilistic Induction: Universal Distributions and Convergence Theorems

Solomonoff, Ray J.

In: The Computer Journal, 2008, vol. 51, no. 5, p. 566-570

Add to personal list
    Title
    • Three Kinds of Probabilistic Induction: Universal Distributions and Convergence Theorems
    Author
    • Solomonoff, Ray J.. Computer Learning Research Centre Royal Holloway, University of London, London, UK IDSIA, Galleria 2, CH-6928 Manno-Lugano, Switzerland
    Document Type
    • Postprint
    Language
    • English
    Published in
    • The Computer Journal, 2008, vol. 51, no. 5, p. 566-570. Oxford University Press
    Other Version
    OAI-PMH Identifier
    • oai:doc.rero.ch:294547
    Summary
    We will describe three kinds of probabilistic induction problems, and give general solutions for each, with associated convergence theorems which show that they tend to give good probability estimates. The first kind extrapolates a sequence of strings and/or numbers. The second extrapolates an unordered set of strings and/or numbers. The third extrapolates an unordered set of ordered pairs of elements that may be strings and/or numbers. Given the first element of a new pair, to get a probability distribution on possible second elements of the pair. Each of the three kinds of problems is solved using an associated universal distribution. In each case a corresponding convergence theorem is given, showing that as sample size grows, the expected error in probability estimate decreases rapidly. The solutions given are very general and cover a great variety of induction problems. Time series prediction, grammar discovery (for both formal and natural languages), curve fitting, the identification problem and the categorization problem, are a few of the kinds of problems amenable to the methods described