On Finding Predictors for Arbitrary Families of Processes

Daniil Ryabko 1, 2
1 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 but known class $C$ of stochastic process measures. We are interested in predictors $\rho$ whose conditional probabilities converge (in some sense) to the ``true'' $\mu$-conditional probabilities if any $\mu\in C$ is chosen to generate the sequence. The contribution of this work is in characterizing the families $C$ for which such predictors exist, and in providing a specific and simple form in which to look for a solution. We show that if any predictor works, then there exists a Bayesian predictor, whose prior is discrete, and which works too. We also find several sufficient and necessary conditions for the existence of a predictor, in terms of topological characterizations of the family $C$, as well as in terms of local behaviour of the measures in $C$, which in some cases lead to procedures for constructing such predictors. It should be emphasized that the framework is completely general: the stochastic processes considered are not required to be i.i.d., stationary, or to belong to any parametric or countable family.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00442881
Contributor : Daniil Ryabko <>
Submitted on : Wednesday, December 23, 2009 - 1:30:14 PM
Last modification on : Thursday, June 27, 2019 - 1:36:06 PM
Long-term archiving on : Friday, June 18, 2010 - 12:05:54 AM

Files

pq3+.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00442881, version 1
  • ARXIV : 0912.4883

Collections

Citation

Daniil Ryabko. On Finding Predictors for Arbitrary Families of Processes. Journal of Machine Learning Research, Microtome Publishing, 2010, 11, pp.581-602. ⟨inria-00442881⟩

Share

Metrics

Record views

293

Files downloads

240