On the relation between realizable and non-realizable cases of the sequence prediction problem

Daniil Ryabko 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : A sequence x1,...,xn,... of discrete-valued observations is generated according to some unknown probabilistic law (measure) μ. After observing each outcome, one is required to give conditional probabilities of the next observation. The realizable case is when the measure μ belongs to an arbitrary but known class C of process measures. The non-realizable case is when μ 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 using the total variation distance, then these problems coincide, while if it is measured using the 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. We also obtain several characterization of those sets C for which solutions to the considered problems exist. 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. It should be emphasized that the framework is completely general: the processes measures considered are not required to be i.i.d., mixing, stationary, or to belong to any parametric family.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2011, 12, pp.2161-2180
Liste complète des métadonnées

https://hal.inria.fr/hal-00639474
Contributeur : Daniil Ryabko <>
Soumis le : mercredi 9 novembre 2011 - 12:05:06
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : hal-00639474, version 1

Collections

Citation

Daniil Ryabko. On the relation between realizable and non-realizable cases of the sequence prediction problem. Journal of Machine Learning Research, Journal of Machine Learning Research, 2011, 12, pp.2161-2180. 〈hal-00639474〉

Partager

Métriques

Consultations de la notice

207