Solomonoff induction

Tom F. Sterkenburg

cs.FLMar 17, 2026

Solomonoff induction

Authors: Tom F. Sterkenburg

Abstract

This chapter discusses the Solomonoff approach to universal prediction. The crucial ingredient in the approach is the notion of computability, and I present the main idea as an attempt to meet two plausible computability desiderata for a universal predictor. This attempt is unsuccessful, which is shown by a generalization of a diagonalization argument due to Putnam. I then critically discuss purported gains of the approach, in particular it providing a foundation for the methodological principle of Occam's razor, and it serving as a theoretical ideal for the development of machine learning methods.

Inductive Inference

See all 23 papers

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model
Aug 2, 2026Nathan YoungHierarchical Bayesian Modeling Statistical Learning Theory
Strong AI Lab, University of Auckland
Understanding Generalization Requires Universal Induction
Sep 28, 2026Aram Ebtekar, Marcus Hutter, Danica J. SutherlandInductive Bias Statistical Learning Theory
AIXI Labs · Google DeepMind & ANU · UBC & Amii
Statistical learning theory and Occam's razor: Regularization
Aug 4, 2026Tom F. SterkenburgInductive Bias

Aug 2, 2026J/K move · Enter open · S save

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

Nathan Young

Strong AI Lab, University of Auckland

Hierarchical Bayesian Modeling Statistical Learning Theory Sequence Modeling Sequence Prediction Inductive Inference

Open paper AskPDF arXiv

Solomonoff Induction, or SolInd, provides an ideal unbounded model of a priori sequence prediction but cannot naturally describe extrapolation from a given training dataset, as performed by Large Language Models. We apply de Finetti's theorem on exchangeable distributions to SolInd to produce what we call Hierarchical Solomonoff Induction, or HSI, which maintains a hyperprior over all Solomonoff priors that can be conditioned on previously observed sequences. We extend Wood et al.'s proof that universal mixtures of semimeasures are equivalent to SolInd to show that universal mixtures of these mixtures are also equivalent, proving that HSI=SolInd. We also prove that HSI's excess error on any distribution, compared to its true generator, is bounded by that generator's complexity in the hyperprior. This result is directly comparable to SolInd's prediction error being bounded by the Kolmogorov complexity of the sequence being predicted, and forces HSI's average excess error to converge to 0 as a dataset grows, leading to optimal prediction in the limit. We claim that HSI is an ideal unbounded model of sequence prediction given a dataset in the same way that SolInd is ideal over individual sequences.

Abstract

Inductive Inference

Explore similar work

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

Understanding Generalization Requires Universal Induction

Statistical learning theory and Occam's razor: Regularization