From the archives
Context Tree Selection: A Unifying View
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName:
Stochastic Processes and their Applications
Date: November, 2011
PageStart: 2 488
PageEnd: 2 506
Arxiv Number: 1011.2424
Authors: Aurélien GarivierFlorencia Leonardi
Abstract: Context tree models have been introduced by Rissanen as a
parsimonious generalization of Markov models. Since then, they have been widely used in
applied probability and statistics. The present paper investigates non-asymptotic properties
of two popular procedures of context tree estimation: Rissanen’s algorithm Context and
penalized maximum likelihood. First showing how they are related, we prove finite horizon
bounds for the probability of over- and under-estimation. Concerning over-estimation, no
boundedness or loss-of-memory conditions are required: the proof relies on new deviation
inequalities for empirical probabilities of independent interest. The under-estimation
properties rely on classical hypotheses for processes of infinite memory. These results
improve on and generalize the bounds obtained in Duarte et al. (2006), Galves et al. (2008),
Galves and Leonardi (2008), Leonardi (2010), refining asymptotic results of Bühlmann and
Wyner (1999) and Csiszár and Talata (2006).
Direct link: available on ScienceDirect
Issue: 11
Volume: 121
Keywords:
