Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-011 | 14th October 2001 00:00

The nonprobabilistic approach to learning the best prediction.


Authors: Boris Ryabko
Publication: 4th February 2002 16:05
Downloads: 1171


The problem of predicting a sequence $x_1, x_2,.... $ where each $x_i$ belongs
to a finite alphabet $A$ is considered. Each letter $x_{t+1}$ is predicted
using information on the word $x_1, x_2, ...., x_t $ only. We use the game
theoretical interpretation which can be traced to Laplace where there exists a gambler who
tries to estimate probabilities for the letter $x_{t+1}$ in order to maximize
his capital . The optimal method of prediction is described for the case when
the sequence $x_1, x_2,.... $ is generated by a stationary and ergodic source. It turns out
that the optimal method is based only on estimations of conditional probabilities.
In particular, it means that if we work in the framework of the ergodic and
stationary source model, we cannot consider pattern recognition and other complex
and interesting tools, because even the optimal method does not need them.
That is why we suggest a so-called nonprobabilistic
approach which is not based on the stationary and ergodic source model and
show that complex algorithms of prediction can be considered in the framework
of this approach.

The new approach is to consider a set of all infinite
sequences (over a given finite alphabet) and estimate the size of sets of
predictable sequences with the help of the Hausdorff dimension.
This approach enables us first, to show that there exist large sets of well
predictable sequences which have zero measure for each stationary and ergodic
measure. (In fact, it means that such sets are invisible in the framework of
the ergodic and stationary source model and shows the necessity of the new approach.)
Second, it is shown that there exist quite large sets of such sequences
that can be predicted well by complex algorithms which use not only estimations of
conditional probabilities.

ISSN 1433-8092 | Imprint