Skip Context Tree Switching
Marc G. Bellemare, Joel Veness, Erik Talvitie · 2014
Context Tree Weighting is a powerful proba-bilistic sequence prediction technique that effi-ciently performs Bayesian model averaging over the class of all prediction suffix trees of bounded depth. In this paper we show how to generalize this technique to the class of K-skip prediction suffix trees. Contrary to regular prediction suffix trees,K-skip prediction suffix trees are permitted to ignore up toK contiguous portions of the con-text. This allows for significant improvements in predictive accuracy when irrelevant variables are present, a case which often occurs within record-aligned data and images. We provide a regret-based analysis of our approach, and empirically evaluate it on the Calgary corpus and a set of Atari 2600 screen prediction tasks. 1.
Cited by 31 works.
Authors
References
- Arithmetic coding for data compression
- The context-tree weighting method: basic properties
- Modeling for text compression
- The performance of universal encoding
- Bayesian CART Model Search
- Tracking the Best Expert
- The power of amnesia: Learning probabilistic automata with variable memory length
- Reinforcement learning with selective perception and hidden state
- Lossless Compression Based on the Sequence Memoizer
- Bayesian Learning of Recursively Factored Environments