Prediction and MDL for infinite sequences
Open Access
- 20 May 2024
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (5) , 1124-1137
Abstract
We combine Solomonoff’s approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best “explanation” for the observed data (in the sense of algorithmic statistics) for prediction. In this way we keep the expected sum of squares of prediction errors bounded (as it was for the Solomonoff’s predictor) and, moreover, guarantee that the sum of squares of prediction errors is bounded along any Martin-Löf random sequence. An extended abstract of this paper was presented at the 16th International Computer Science Symposium in Russia (CSR 2021) (Milovanov 2021).Keywords
Funding Information
- HORIZON EUROPE European Research Council (01041696)
- Unidade Local de Saúde de São José
This publication has 11 references indexed in Scilit:
- Predictions and Algorithmic Statistics for Infinite Sequences2021
- Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms2018
- Kolmogorov Complexity and Algorithmic Randomness2017
- Algorithmic Statistics: Forty Years Later2016
- On Martin-Löf Convergence of Solomonoff’s Mixture2013
- On semimeasures predicting Martin-Löf random sequencesTheoretical Computer Science, 2007
- Sequential predictions based on algorithmic complexityJournal of Computer and System Sciences, 2005
- Algorithmic statisticsIEEE Transactions on Information Theory, 2001
- Complexity-based induction systems: Comparisons and convergence theoremsIEEE Transactions on Information Theory, 1978
- A formal theory of inductive inference. Part IIInformation and Control, 1964