Partition Tree Weighting
  This paper introduces the Partition Tree Weighting technique, an efficient
meta-algorithm for piecewise stationary sources. The technique works by
performing Bayesian model averaging over a large class of possible partitions
of the data into locally stationary segments. It uses a prior, closely related
to the Context Tree Weighting technique of Willems, that is well suited to data
compression applications. Our technique can be applied to any coding
distribution at an additional time and space cost only logarithmic in the
sequence length. We provide a competitive analysis of the redundancy of our
method, and explore its application in a variety of settings. The order of the
redundancy and the complexity of our algorithm matches those of the best
competitors available in the literature, and the new algorithm exhibits a
superior complexity-performance trade-off in our experiments.
