Characterizing predictable classes of processes

Daniil Ryabko 1, 2
2 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
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.
Type de document :
Communication dans un congrès
UAI, 2009, Montreal, Canada. pp.471-478, 2009, Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI'09)
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00388523
Contributeur : Daniil Ryabko <>
Soumis le : mardi 26 mai 2009 - 22:10:50
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 10 juin 2010 - 19:59:21

Fichiers

pq3_a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Daniil Ryabko. Characterizing predictable classes of processes. UAI, 2009, Montreal, Canada. pp.471-478, 2009, Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI'09). 〈inria-00388523〉

Partager

Métriques

Consultations de la notice

388

Téléchargements de fichiers

123