Statistical Inference in Hidden Markov Models using $k$-segment Constraints

Fundamentally, the HMM is a mixture model whose mixing distribution is a finite state Markov chain (Rabiner, 1989; Capp e et al., 2005). Whilst the Markov assumptions rarely correspond to the true physical generative process, it often adequately captures first-order properties that make it a useful approximating model for sequence data in many instances whilst remaining tractable even for very large datasets. As a consequence, HMM-based algorithms can give highly competitive performance in many applications. Central to the tractability of HMMs is the availability of recursive algorithms that allow fundamental quantities to be computed efficiently (Baum and Petrie, 1966; Viterbi, 1967). These include the Viterbi algorithm which computes the most probable hidden state sequence and the forward-backward algorithm which computes the marginal probability of a given state at a point in the sequence. Computation for the HMM has been well-summarized in the comprehensive and widely read tutorial by Rabiner (1989) with a Bayesian treatment given more recently by Scott (2002). It is a testament to the completeness of these recursive methods that there have been few generic additions to the HMM toolbox since these were first described in the 1960s. However, as HMM approaches continue to be applied in increasingly diverse scientific domains and ever larger data sets, there is interest in expanding the generic toolbox available for HMM inference to encompass unmet needs. The motivation for our work is to develop mechanisms to allow theexploration of the posterior sequence space.