Context tree weighting for signal processing, bayesian inference, and model selection: theoryand algorithms

Abstract

The goal of the present thesis is to explore, extend and utilize a family of algorithms that arose over the past twenty years in the Information Theoryliterature, under the umbrella of “Context Tree Weighting”. Although these methods were originally motivated by and applied to problems in source coding and data compression, we argue that there range of applicability extends to a large variety of problems in statistical inference and signal processing.We will examine the Maximum A Posteriori Probability Tree Algorithm(MAPT) as an efficient method for Bayesian inference, in the context of discrete series data. The MAPT algorithm computes the maximum a posteriori probability tree model, as well as the corresponding model posterior probability. Experimental results will be given, illustrating its performance,both on independent data and on more complex signals generated by variable memory Markov chains.