LiEP CIS-2001-016: The nonprobabilistic approach to learning the best prediction.

The nonprobabilistic approach to learning the best prediction.

Title:	The nonprobabilistic approach to learning the best prediction.
Authors:	Boris Ryabko
Series:	Linköping Electronic Articles in Computer and Information Science ISSN 1401-9841
Issue:	Vol. 6(2001): nr 016
URL:	http://www.ep.liu.se/ea/cis/2001/016/

Abstract:	The problem of predicting a sequence x₁ , x₂ , .... 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₁ , x₂ ...., 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₁ , x₂ ....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.
Keywords:

Abstract:

The problem of predicting a sequence x₁ , x₂ , .... 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₁ , x₂ ...., 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₁ , x₂ ....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.

Keywords:

Intended publication 2001-08-30	Postscript Checksum
Info from authors
Third-party information

Intended publication
2001-08-30

Postscript Checksum

Info from authors

Third-party information