Sequence prediction in realizable and non-realizable cases - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Sequence prediction in realizable and non-realizable cases

Daniil Ryabko
  • Fonction : Auteur
  • PersonId : 848126

Résumé

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 realizable case is when the measure $\mu$ belongs to an arbitrary but known class $C$ of process measures. The non-realizable case is when $\mu$ is completely arbitrary, but the prediction performance is measured with respect to a given set $C$ of process measures. We are interested in the relations between these problems and between their solutions, as well as in characterizing the cases when a solution exists, and finding these solutions. We show that if the quality of prediction is measured by total variation distance, then these problems coincide, while if it is measured by expected average KL divergence, then they are different. For some of the formalizations we also show that when a solution exists, it can be obtained as a Bayes mixture over a countable subset of $C$. As an illustration to the general results obtained, we show that a solution to the non-realizable case of the sequence prediction problem exists for the set of all finite-memory processes, but does not exist for the set of all stationary processes.
Fichier principal
Vignette du fichier
pqout.pdf (195.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00440669 , version 1 (11-12-2009)
inria-00440669 , version 2 (17-05-2010)
inria-00440669 , version 3 (20-06-2011)

Identifiants

  • HAL Id : inria-00440669 , version 3
  • ARXIV : 1005.5603

Citer

Daniil Ryabko. Sequence prediction in realizable and non-realizable cases. Conference on Learning Theory, 2010, Haifa, Israel. pp.119-131. ⟨inria-00440669v3⟩
138 Consultations
151 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More