Context Tree Switching
Joel Veness, Kee Siong Ng, Marcus Hütter et al. · DCC · 2012
This paper describes the Context Tree Switching technique, a modification of Context Tree Weighting for the prediction of binary, stationary, n-Markov sources. By modifying Context Tree Weighting's recursive weighting scheme, it is possible to mix over a strictly larger class of models without increasing the asymptotic time or space complexity of the original algorithm. We prove that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and show empirically that this new technique leads to consistent improvements over Context Tree Weighting as measured on the Calgary Corpus.
Cited by 36 works. doi:10.1109/dcc.2012.39
Authors
References
- Arithmetic coding for data compression
- Data Compression Using Adaptive Coding and Partial String Matching
- Universal coding, information, prediction, and estimation
- The context-tree weighting method: basic properties
- The performance of universal encoding
- Tracking the Best Expert
- On Prediction Using Variable Order Markov Models
- Lossless Compression Based on the Sequence Memoizer
- On Prediction Using Variable Order Markov Models
- Switching between two universal source coding algorithms