Source-linked AI summary
Solomonoff Induction and Singular Integrals
Will Troiani, Daniel Murfet
TL;DR
The paper asks how Solomonoff’s discrete notion of simplicity relates to Bayesian evidence and singular model complexity. It reorganizes the Solomonoff sum into Riemann sums and constructs one fixed monotone machine for each computable Bayesian model. Under Watanabe’s conditions, the learning coefficient appears as the coefficient of log n in an upper bound on Solomonoff code length.
Problem
The paper studies how Solomonoff description-based simplicity relates to Bayesian evidence and learning-coefficient-based singular model simplicity.
Method
For each computable Bayesian model, the paper hard-wires its description into a single monotone Turing machine whose semimeasure reproduces the model’s evidence up to a uniform constant.
Results
−log M(X^n) ≤ nL_n(w0) + λ log n − (m − 1) log log n + O_P(1) under Watanabe’s hypotheses.
Takeaways & Limitations
The learning coefficient, a geometric measure of model simplicity, becomes the coefficient of log n in a Solomonoff code-length bound.
Takeaways & Limitations
The analysis considers binary-input monotone Turing machines and assumes the model and data satisfy the stated hypotheses, including Watanabe’s asymptotic conditions.
Abstract
from arXiv · showhide
The Solomonoff distribution $M$ assigns an a priori probability to a finite binary string $z$ by summing over all programs whose output begins with $z$, weighting a program of length $\ell$ by $2^{-\ell}$. Thus, likely strings are those with many short explanations. This appears to be a purely discrete notion of complexity. However, Riemann sums are also countable. We show that the sum defining $M$, suitably reorganised, contains Riemann sums approximating the Bayesian evidence of any computable statistical model. These evidence integrals are singular integrals whose asymptotics are governed by Singular Learning Theory and, through it, by invariants of algebraic geometry. Concretely, for every computable Bayesian model, we construct a single monotone Turing machine whose induced semimeasure agrees with the evidence $Z_n$ up to a uniform multiplicative constant. If the model also satisfies the hypotheses of Watanabe's free-energy asymptotics, then a sample $X^n=X_1\cdots X_n$ drawn i.i.d. from the true distribution satisfies $-\log M(X^n) \le nL_n(w_0)+λ\log n-(m-1)\log\log n+O_{\mathbb{P}}(1)$, where $L_n$ is the empirical loss, $w_0$ is an optimal parameter, $λ$ is the learning coefficient, and $m$ is its multiplicity. Thus the learning coefficient, a geometric measure of model simplicity, appears within the Solomonoff distribution as the coefficient of $\log n$ in an upper bound on code length.
1 Introduction
The paper connects Solomonoff’s discrete program mixture to Bayesian evidence by reorganizing its sum into Riemann sums. For computable Bayesian models, a single fixed monotone machine then transfers singular-learning asymptotics, including the learning coefficient, into Solomonoff code-length bounds.
- Construction: Bayesian samplers draw w from the prior and then sample observations from p(· | w), embedding computable model learning within Solomonoff’s program mixture.The construction uses cells partitioning parameter space at a resolution that grows with n.
- Asymptotics: Singular-learning asymptotics give Fn = nL_n(w0) + λ log n − (m − 1) log log n + O_P(1), with λ the learning coefficient and m its multiplicity.Here L_n is empirical loss and w0 is an optimal parameter.
- Motivation: Solomonoff’s distribution can be viewed as containing Riemann sums for the evidence integrals of computable Bayesian models.This bridges countable program sums with continuous parameter-space integrals whose asymptotics are governed by singular learning theory.
- Construction: A single monotone Turing machine Bm, fixed by the model description alone, reproduces the model’s Bayesian evidence on every prefix up to a uniform constant.It receives neither the sample size nor the data and writes one infinite output string.
- Asymptotics: −log M(X^n) ≤ nL_n(w0) + λ log n − (m − 1) log log n + O_P(1) for i.i.d. samples satisfying Watanabe’s hypotheses.The bound follows because Bm is one of the monotone machines dominated by the Solomonoff distribution.
- Interpretation: The resulting bound relates description length and singular model simplicity: the model description affects the additive constant, while λ is the coefficient of log n.In regular models, λ equals half the number of parameters and acts as an effective parameter count.
2 An explicit sampler: description length and the learning coefficient
The paper constructs a computable Bayesian sampler and a single fixed monotone Turing machine for each model, linking its induced semimeasure to Bayesian evidence and learning-coefficient asymptotics.
- Computability assumptions: A computable Bayesian model is specified by a bit-string length, statistical model, compact parameter set, rational box, prior, and computability programs.The model description includes programs for approximating likelihoods and computing dyadic-cell prior masses.
- Sampler construction: BayesSampler repeatedly refines a positive dyadic cell according to conditional prior mass, samples at the cell centre, and outputs observations from the corresponding model distribution.The refinement schedule is determined by the Lipschitz bound and the target time step.
- Sampler construction: Hard-wiring a model description into BayesSampler yields a single monotone Turing machine Bm whose input consists only of random bits and is fixed independently of the data and sample length.A universal wrapper can instead read the model description before the random bits.
- Sampler construction: The sampled nested positive cells converge almost surely to a parameter w∞ distributed according to the prior, establishing the sampler’s probabilistic interpretation.Each finite cell in the sequence has probability equal to its prior mass.
- Evidence and learning coefficient: The induced semimeasure of Bm has the model’s free-energy asymptotics, and Solomonoff dominance transfers them to an upper bound on −log M.The bound is −log M(X^n) ≤ nL_n(w0) + λ log n − (m − 1) log log n + O_P(1), under Watanabe’s hypotheses.
- Evidence and learning coefficient: The construction addresses the central requirement that one fixed machine serve every n, allowing singular-model evidence to enter the Solomonoff distribution.The additive O(1) term is independent of n and the data, though it may depend on the model description.
A The Solomonoff distribution
This section defines monotone Turing machines and the Solomonoff distribution through output-prefix probabilities under uniformly random input bits. Universality then yields dominance over every encoded monotone machine.
- Machine model: A monotone Turing machine reads a binary input tape in one direction and writes to a binary output tape without revising its output.Its formal data include a finite state set, work tapes, and binary tape alphabets.
- Induced semimeasures: The semimeasure induced by a machine assigns each finite string the probability that the machine’s output begins with that string under uniformly random input bits.This probability can equivalently be expressed using minimal programs producing the output prefix.
- Universality: A universal monotone Turing machine simulates every monotone machine when given its canonical prefix-free encoding followed by the simulated machine’s input.The reference machine U satisfies U(⟨T⟩ω) = T(ω).
- Solomonoff distribution: The Solomonoff distribution M is the universal machine’s output-prefix probability, equivalently the weighted sum over minimal programs producing that prefix.For a finite string y, M(y) abbreviates the corresponding cylinder probability.
- Universality: Universal dominance gives M(y) ≥ 2^−ℓ(⟨T⟩)P_T(y) for every monotone machine T and finite string y.Thus each machine’s contribution is bounded below by a constant determined by its encoding length.
B Singular learning theory (SLT)
This section introduces the Bayesian quantities and regularity assumptions used in Singular Learning Theory, then states Watanabe-style asymptotics for the evidence. Under these hypotheses, the learning coefficient and multiplicity determine the logarithmic and log-log corrections to empirical loss.
- Setup: The setup uses i.i.d. data from q, a prior density φ on a parameter space W, and a model distribution p(· | w).The binary formulation extends to any finite outcome alphabet.
- Assumptions: The analysis assumes absolute continuity, analyticity of the log density ratio, integrability, and regularity conditions on the model and prior.The parameter space is required to be compact semianalytic, with a structured prior density and relatively finite variance.
- Definitions: The population and empirical losses, centered KL functions, Bayesian evidence, and zeta function provide the main objects for the asymptotic analysis.The learning coefficient λ is defined from the pole of the zeta function with largest real part, while m is its order.
- Asymptotics: Under the standard SLT hypotheses and an additional positivity condition, the normalized free energy has a Watanabe asymptotic expansion.The expansion includes λ log n, a correction −(m − 1) log log n, and O_P(1).
- Asymptotics: Equivalently, the Bayesian evidence satisfies −log Z_n = nL_n(w_0) + λ log n −(m −1) log log n + O_P(1).Here w_0 is a minimizer of the population loss, and all optimal parameters induce the same distribution q-almost surely under the stated condition.