Redundancy of the Context-Tree Weighting Method on Renewal and Markov Renewal Processes
Author:
- 30 November 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 52 (12) , 5579-5586
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 errorKeywords
This publication has 17 references indexed in Scilit:
- Context tree estimation for not necessarily finite memory processes, via BIC and MDLIEEE Transactions on Information Theory, 2006
- Extensions to the context tree weighting method2002
- The consistency of the BIC Markov order estimatorThe Annals of Statistics, 2000
- Variable length Markov chainsThe Annals of Statistics, 1999
- The minimum description length principle in coding and modelingIEEE Transactions on Information Theory, 1998
- Universal coding, information, prediction, and estimationIEEE Transactions on Information Theory, 1984
- A universal data compression systemIEEE Transactions on Information Theory, 1983
- Nonparametric Estimation in Renewal ProcessesThe Annals of Statistics, 1982
- The performance of universal encodingIEEE Transactions on Information Theory, 1981
- Universal modeling and codingIEEE Transactions on Information Theory, 1981