Universal Codes from Switching Strategies
This work addresses incremental improvements in universal coding algorithms for time series data with parameter drift, relevant for researchers in information theory and sequential prediction.
The paper tackles the problem of combining sequential prediction strategies for universal coding by introducing graphical models based on Hidden Markov Models, including new models for clustered switches and related-strategy jumps. It provides theoretical contributions with an interpolation construction and a new lemma for analyzing individual sequence regret in parameterized models.
We discuss algorithms for combining sequential prediction strategies, a task which can be viewed as a natural generalisation of the concept of universal coding. We describe a graphical language based on Hidden Markov Models for defining prediction strategies, and we provide both existing and new models as examples. The models include efficient, parameterless models for switching between the input strategies over time, including a model for the case where switches tend to occur in clusters, and finally a new model for the scenario where the prediction strategies have a known relationship, and where jumps are typically between strongly related ones. This last model is relevant for coding time series data where parameter drift is expected. As theoretical ontributions we introduce an interpolation construction that is useful in the development and analysis of new algorithms, and we establish a new sophisticated lemma for analysing the individual sequence regret of parameterised models.