Characterizing predictable classes of processes

Daniil Ryabko
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:479-486, 2009.

Abstract

The problem is sequence prediction in the following setting. A sequence x1,..., xn,... of discrete-valued observations is generated according to some unknown probabilistic law (measure) mu. After observing each outcome, it is required to give the conditional probabilities of the next observation. The measure mu belongs to an arbitrary class C of stochastic processes. We are interested in predictors $\rho$ whose conditional probabilities converge to the ’true’ mu-conditional probabilities if any $\mu \in C$ is chosen to generate the data. We show that if such a predictor exists, then a predictor can also be obtained as a convex combination of a countably many elements of C. In other words, it can be obtained as a Bayesian predictor whose prior is concentrated on a countable set. This result is established for two very different measures of performance of prediction, one of which is very strong, namely, total variation, and the other is very weak, namely, prediction in expected average Kullback-Leibler divergence.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-ryabko09a, title = {Characterizing predictable classes of processes}, author = {Ryabko, Daniil}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {479--486}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/ryabko09a/ryabko09a.pdf}, url = {https://proceedings.mlr.press/r7/ryabko09a.html}, abstract = {The problem is sequence prediction in the following setting. A sequence x1,..., xn,... of discrete-valued observations is generated according to some unknown probabilistic law (measure) mu. After observing each outcome, it is required to give the conditional probabilities of the next observation. The measure mu belongs to an arbitrary class C of stochastic processes. We are interested in predictors $\rho$ whose conditional probabilities converge to the ’true’ mu-conditional probabilities if any $\mu \in C$ is chosen to generate the data. We show that if such a predictor exists, then a predictor can also be obtained as a convex combination of a countably many elements of C. In other words, it can be obtained as a Bayesian predictor whose prior is concentrated on a countable set. This result is established for two very different measures of performance of prediction, one of which is very strong, namely, total variation, and the other is very weak, namely, prediction in expected average Kullback-Leibler divergence.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Characterizing predictable classes of processes %A Daniil Ryabko %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-ryabko09a %I PMLR %P 479--486 %U https://proceedings.mlr.press/r7/ryabko09a.html %V R7 %X The problem is sequence prediction in the following setting. A sequence x1,..., xn,... of discrete-valued observations is generated according to some unknown probabilistic law (measure) mu. After observing each outcome, it is required to give the conditional probabilities of the next observation. The measure mu belongs to an arbitrary class C of stochastic processes. We are interested in predictors $\rho$ whose conditional probabilities converge to the ’true’ mu-conditional probabilities if any $\mu \in C$ is chosen to generate the data. We show that if such a predictor exists, then a predictor can also be obtained as a convex combination of a countably many elements of C. In other words, it can be obtained as a Bayesian predictor whose prior is concentrated on a countable set. This result is established for two very different measures of performance of prediction, one of which is very strong, namely, total variation, and the other is very weak, namely, prediction in expected average Kullback-Leibler divergence. %Z Reissued by PMLR on 04 October 2026.
APA
Ryabko, D.. (2009). Characterizing predictable classes of processes. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:479-486 Available from https://proceedings.mlr.press/r7/ryabko09a.html. Reissued by PMLR on 04 October 2026.

Related Material