# Characterizing predictable classes of processes

2 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : The problem is sequence prediction in the following setting. A sequence $x_1,\dots,x_n,\dots$ 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.
Document type :
Conference papers
Domain :

Cited literature [12 references]

https://hal.inria.fr/inria-00388523
Contributor : Daniil Ryabko <>
Submitted on : Tuesday, May 26, 2009 - 10:10:50 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Thursday, June 10, 2010 - 7:59:21 PM

### Files

pq3_a.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00388523, version 1
• ARXIV : 0905.4341

### Citation

Daniil Ryabko. Characterizing predictable classes of processes. UAI, 2009, Montreal, Canada. pp.471-478. ⟨inria-00388523⟩

Record views