?
Algorithmic Statistics, Prediction and Machine Learning
Algorithmic statistics considers the following problem: given a binary string
x
(e.g., some
experimental data), find a “good” explanation of this data. It uses algorithmic information
theory to define formally what is a good explanation. In this paper we extend this framework in
two directions.
First, the explanations are not only interesting in themselves but also used for prediction: we
want to know what kind of data we may reasonably expect in similar situations (repeating the
same experiment). We show that some kind of hierarchy can be constructed both in terms of
algorithmic statistics and using the notion of a priori probability, and these two approaches turn
out to be equivalent (Theorem 5).
Second, a more realistic approach that goes back to machine learning theory, assumes that
we have not a single data string
x
but some set of “positive examples”
x
1
,...,x
l
that all belong
to some unknown set
A
, a property that we want to learn. We want this set
A
to contain all
positive examples and to be as small and simple as possible. We show how algorithmic statistic
can be extended to cover this situation (Theorem 11)