Aurélien Garivier
Abstract
The Context Tree Weighting method (CTW) is shown to be almost adaptive on the classes of
renewal and Markov renewal processes. Up to logarithmic factor, ctw achieves the minimax
pointwise redundancy described by I. Csiszaacuter and P. Shields in IEEE Trans. Inf.
Theory, vol. 42, no. 6, pp. 2065-2072, Nov. 1996. This result not only complements
previous results on the adaptivity of the Context-Tree Weighting method on the
relatively small class of all finite context-tree sources (which encompasses the class
of all finite order Markov sources), it shows that almost minimax redundancy can be
achieved on massive classes of sources (classes that cannot be smoothly parameterized by
subsets of finite-dimensional spaces). Moreover, it shows that (almost) adaptive
compression can be achieved in a computationally efficient way on those massive classes.
While previous adaptivity results for CTW could rely on the fact that any Markov source
is a finite-context-tree source, this is no longer the case for renewal sources. In
order to prove almost adaptivity of CTW over renewal sources, it is necessary to
establish that CTW carefully balances estimation error and approximation error.
Aurélien Garivier
Mathématiques [math]. Université Paris-Sud, 2006. Français
Original publication details
Mémoire de thèse (PhD dissertation) · Nov. 2006
MDL; BIC; Context trees; CTW; HMM; VLMC; Source coding; Renewal processes; Pattern coding;
Minimax; Infinite alphabet
Aurélien Garivier
Abstract
The Bayesian information criterion (BIC) and Krichevsky- Trofimov (KT) version of
minimum description length (MDL) principle are popular in the study of model selection.
For order estimation of Markov chains, both are known to be strongly consistent when
there is an upper-bound on the order. In the unbounded case, the BIC is also known to be
consistent, but the KT estimator is consistent only with a bound o(log n) on the order.
For context trees, a flexible generalization of Markov models widely used in data
processing, the problem is more complicated both in theory and practice, given the
substantially higher number of possible candidate models. Imre Csiszar and Zsolt Talata
proved the consistency of BIC and KT when the hypothetical tree depths are allowed to
grow as o(log n). This correspondence proves that such a restriction is not necessary
for finite context sources: the BIC context tree estimator is strongly consistent even
if there is no constraint at all on the size of the chosen tree. Moreover, an algorithm
computing the tree minimizing the BIC criterion among all context trees in linear time
is provided.