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.