General
Solomonoff induction of selected bits and online classification
arXiv math.IT0 views
arXiv:2610.18632v2 Announce Type: replace 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 $\omega_1 \cdots \omega_{n-1}$, it predicts the next bit $\omega_n$ to be $b$ with conditional probability proportional to $M(\omega_1 \cdots \omega_{n-1} b)$. Thus the error of this probability is \[ e_\omega(n) = 1 - \frac {M(\omega_1 \cdots \omega_{n-1}\omega_n)} {M(\omega_1 \cdots \omega_{n-1} 0) + M(\omega_{1} \cdots \omega_{n-1} 1)}. \] If $\omega$ a computable infinite sequence with a self-delimiting description of at most $k$ bits, then $\sum_n e_\omega(n) \le k\ln 2+O(1)$. Lattimore, Hutter and Gavane consider the problem of predicting computable patterns in a sequence, for example, the pattern of repeated bits $\omega = 00\,11\,00\,00\,11\,00\cdots$ 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_\omega(2n) = 0$. We show that for some computable pattern, the sum of $e_{\omega}(n)$ over positions $n$ from the pattern is not bounded. However, the sum of squares $(e_\omega(n))^2$ is bounded exponentially in the program length of the pattern. It is also shown that bits of $\omega$ that are fixed by a computable classification function $f:\{0,1\}^* \rightarrow \{0,1\}$, converges faster: the sum of $(e_\omega(n))^2$ is bounded by a polynomial in the program length for programs whose runtime is bounded by any fixed computable time bound.
Source:https://arxiv.org/abs/2610.18632PreviousFinite-Support Structure of Optimal i.i.d. Inputs for Finite-Memory Poisson ChannelsNextQuantum Anticodes
Related posts
Kernel Regression using Persistence Diagrams
0arXiv stat.TH
The Scaled Dirichlet Distribution: Lauricella Representations and Estimation
0arXiv stat.TH
Functional Estimation under Local Differential Privacy: General Lower Bounds and Applications to Entropy and Power Sums
0arXiv stat.TH
Scaling GR(1) Synthesis via a Compositional Framework for LTL Discrete Event Control
0arXiv cs.SE
Generalized Covering radii and Deep Holes of a Family of Antiprimitive Narrow-Sense BCH Codes in Even Characteristic
0arXiv math.IT
Open Response Explorer: a Structured Collaborative Writing System for Peer-Informed Open-Response Assignments
0arXiv cs.HC