High-order extensions of the Double Chain Markov Model

Abstract

The Double Chain Markov Model is a fully Markovian model for the representation of time-series in random environments. In this article, we show that it can handle transitions of high-order between both a set of observations and a set of hidden states. In order to reduce the number of parameters, each transition matrix can be replaced by a Mixture Transition Distribution model. We provide a complete derivation of the algorithms needed to compute the model. Three applications, the analysis of a sequence of DNA, the song of the wood pewee, and the behavior of young monkeys show that this model is of great interest for the representation of data that can be decomposed into a finite set of patterns.

Keywords:

• Double Chain Markov Model (DCMM)
• High-order transitions
• Mixture Transition Distribution model (MTD)
• Forward–backward algorithm
• Baum–Welch algorithm
• Viterbi algorithm
• DNA
• Pewee
• Behavior

Acknowledgments

Most of this research was done during a stay at the Department of Statistics of the University of Washington, in Seattle. This research was supported by a grant from the Swiss National Science Foundation and by Office of Naval Research grant no. N00014-96-1-0192. I would like to thank Adrian Raftery for his very helpful comments, and Gene Sackett for providing the young monkeys data.