High-order hidden Markov models - Estimation and implementation

While the Hidden Markov Model (HMM) has been used for a wide range of applications, an efficient procedure for estimating the model parameters and finding the optimal state sequence has not been generally formulated for orders higher than first, i.e., for models that assume higher order of either the state sequence memory, or the dependency of the observations on the states. We propose a simple method that transforms any high order HMM (including models in which the state sequence and observation dependency are of different orders) into an equivalent first order one, and thus makes the first order HMM formulation applicable to models of any order.