Author: miyabe

News
July 2019, Proof reading

Title
Computable prediction

Type
Conference paper

Publication
Miyabe K. (2019) Computable Prediction. In: Hammer P., Agrawal P., Goertzel B., Iklé M. (eds) Artificial General Intelligence. AGI 2019. Lecture Notes in Computer Science, vol 11654. Springer, Cham
DOI https://doi.org/10.1007/978-3-030-27005-6_14

Abstract
We try to predict the next bit from a given finite binary string
when the sequence is sampled from a computable probability measure on the Cantor space.
There exists the best betting strategy among a class of effective ones up to a multiplicative constant,
the induced prediction from which is called algorithmic probability or universal induction by Solomonoff.
The prediction converges to the true induced measure for sufficiently random sequences.
However, the prediction is not computable.

We propose a framework to study the properties of computable predictions.
We prove that all sufficiently general computable predictions also converge to the true induced measure.
The class of sequences along which the prediction converges is related to computable randomness.

We also discuss the speed of the convergence.
We prove that, even when a computable prediction predicts a computable sequence,
the speed of the convergence cannot be bounded by a computable function monotonically decreasing to $0$.

download
preprint
slide