A Model Reduction Algorithm for Hidden Markov Models

This paper presents a two step model reduction algorithm for discrete-time, finite state, finite alphabet hidden Markov models. The complexity measure used is the cardinality of the state space of the underlying Markov chain. In the first step, hidden Markov models are associated with a certain class of stochastic jump linear systems, namely the ones where the parametric input is a sequence of independent identically distributed random variables. The image of the high dimensional hidden Markov model in this class of stochastic jump linear systems is simplified by means of a balanced truncation algorithm, which was developed by Kotsalis (2006). Subsequently, the reduced order stochastic jump linear system is modified, so that it meets the constraints of an image of a hidden Markov model of the same order. This is achieved by solving a low dimensional non convex optimization problem. Numerical simulation results provide evidence that the proposed algorithm computes accurate reduced order hidden Markov models, while achieving a compression of the state space by orders of magnitude