From the archives
Redundancy of the Context-Tree Weighting Method on Renewal and Markov Renewal Processes
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: IEEE Transactions on Information Theory
Date: December, 2006
PageStart: 5 579
PageEnd: 5 586
Authors: 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.
Direct link: available on IEEE Xplore
Issue: 12
Volume: 52
Keywords:
