Solomonoff induction of selected bits and online classification
Abstract
Solomonoff induction is a general solution for sequence prediction that started the field of algorithmic information theory around 1960. Let M be the universal semimeasure. After observing a string ω1 ⋯ ωn−1, it predicts the next bit ωn to be b with conditional probability proportional to M(ω1 ⋯ ωn−1 b). Thus the error of this probability is eω(n) = 1 − (M(ω1 ⋯ ωn−1ωn))/(M(ω1 ⋯ ωn−1 0) + M(ω1 ⋯ ωn−1 1)). If ω a computable infinite sequence with a self-delimiting description of at most k bits, then ∑n eω(n) ≤ kln 2+O(1). Lattimore, Hutter and Gavane consider the problem of predicting computable patterns in a sequence, for example, the pattern of repeated bits ω= 00 11 00 00 11 00⋯ They show that the error probabilities of the bits fixed by a computable pattern have limit zero, for example, for repeated bits, one has limn eω(2n) = 0. We show that for some computable pattern, the sum of eω(n) over positions n from the pattern is not bounded. However, the sum of squares (eω(n))2 is bounded exponentially in the program length of the pattern. It is also shown that bits of ω that are fixed by a computable classification function f:{0,1}* → {0,1}, converges faster: the sum of (eω(n))2 is bounded by a polynomial in the program length for programs whose runtime is bounded by any fixed computable time bound.
Related
- Solomonoff Induction and Singular Integrals
- What Can Language Models Inherit from Solomonoff Induction? Limits, Attainable Properties, and What Served Conditionals Reveal
- Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors
- Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
- Online gas classification at the edge
BibTeX
@misc{bauwens2026solomonoff,
title = {{Solomonoff induction of selected bits and online classification}},
author = {Bruno Bauwens and German Kuznetsov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18632},
eprint = {2610.18632},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18632},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Solomonoff induction of selected bits and online classification
AU - Bruno Bauwens
AU - German Kuznetsov
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18632
UR - https://arxiv.org/abs/2610.18632
AB - Solomonoff induction is a general solution for sequence prediction that started the field of algorithmic information theory around 1960. Let M be the universal semimeasure. After observing a string ω_1 ⋯ ω_n−1, it predicts the next bit ω_n to be b with conditional probability proportional to M(ω_1 ⋯ ω_n−1 b). Thus the error of this probability is e_ω(n) = 1 − (M(ω_1 ⋯ ω_n−1ω_n))/(M(ω_1 ⋯ ω_n−1 0) + M(ω_1 ⋯ ω_n−1 1)). If ω a computable infinite sequence with a self-delimiting description of at most k bits, then ∑_n e_ω(n) ≤ kln 2+O(1). Lattimore, Hutter and Gavane consider the problem of predicting computable patterns in a sequence, for example, the pattern of repeated bits ω= 00 11 00 00 11 00⋯ They show that the error probabilities of the bits fixed by a computable pattern have limit zero, for example, for repeated bits, one has lim_n e_ω(2n) = 0. We show that for some computable pattern, the sum of e_ω(n) over positions n from the pattern is not bounded. However, the sum of squares (e_ω(n))^2 is bounded exponentially in the program length of the pattern. It is also shown that bits of ω that are fixed by a computable classification function f:{0,1}^* → {0,1}, converges faster: the sum of (e_ω(n))^2 is bounded by a polynomial in the program length for programs whose runtime is bounded by any fixed computable time bound.
ER -