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