Context tree selection: a unifying view

DOI10.1016/J.SPA.2011.06.012zbMATH Open1397.60130arXiv1011.2424OpenAlexW1987149108WikidataQ98839681 ScholiaQ98839681MaRDI QIDQ719769FDOQ719769

Authors: Aurélien Garivier, Florencia Leonardi 

Publication date: 11 October 2011

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: The present paper investigates non-asymptotic properties of two popular procedures of context tree (or Variable Length Markov Chains) estimation: Rissanen's algorithm Context and the Penalized Maximum Likelihood criterion. First showing how they are related, we prove finite horizon bounds for the probability of over- and under-estimation. Concerning overestimation, no boundedness or loss-of-memory conditions are required: the proof relies on new deviation inequalities for empirical probabilities of independent interest. The underestimation properties rely on loss-of-memory and separation conditions of the process. These results improve and generalize the bounds obtained previously. 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.

Full work available at URL: https://arxiv.org/abs/1011.2424

Recommendations

• Some upper bounds for the rate of convergence of penalized likelihood context tree estimators
• Context tree estimation for not necessarily finite memory processes, via BIC and MDL
• Consistency of the Unlimited BIC Context Tree Estimator
• Exponential inequalities for VLMC empirical trees
• Exponential inequalities for empirical unbounded context trees

zbMATH Keywords

model selectionpenalized maximum likelihoodBayesian information criteriondeviation inequalitiesalgorithm contextvariable length Markov chains

Mathematics Subject Classification ID

Non-Markovian processes: estimation (62M09) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stationary stochastic processes (60G10) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Special processes (60K99)

Cites Work

• Title not available (Why is that?)
• Prediction, Learning, and Games
• Context tree selection and linguistic rhythm retrieval from written texts
• Context tree estimation for not necessarily finite memory processes, via BIC and MDL
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• The minimum description length principle in coding and modeling
• New dependence coefficients. Examples and applications to statistics
• Processes with long memory: Regenerative construction and perfect simulation
• On upper-confidence bound policies for switching bandit problems
• Markov approximations of chains of infinite order
• Exponential inequalities for empirical unbounded context trees
• A universal data compression system
• Large-scale typicality of Markov sample paths and consistency of MDL order estimators
• On Rate of Convergence of Statistical Estimation of Stationary Ergodic Processes
• Markov approximation and consistent estimation of unbounded probabilistic suffix trees
• Some upper bounds for the rate of convergence of penalized likelihood context tree estimators
• The context-tree weighting method: basic properties
• Exponential inequalities for VLMC empirical trees
• Variable length Markov chains
• Testing statistical hypothesis on random trees and applications to the protein classification problem
• Consistency of the Unlimited BIC Context Tree Estimator
• Joint estimation of intersecting context tree models

Cited In (11)

• Learning the distribution with largest mean: two bandit frameworks
• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Exponential inequalities for empirical unbounded context trees
• Joint estimation of intersecting context tree models
• Context tree estimation for not necessarily finite memory processes, via BIC and MDL
• Structure recovery for partially observed discrete Markov random fields on graphs under not necessarily positive distributions
• Nonparametric statistical inference for the context tree of a stationary ergodic process
• Variable length memory chains: characterization of stationary probability measures
• Some upper bounds for the rate of convergence of penalized likelihood context tree estimators
• Consistency of the Unlimited BIC Context Tree Estimator
• Approximate group context tree

This page was built for publication: Context tree selection: a unifying view

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719769)