Linear-time inference in Hierarchical HMMs

The hierarchical hidden Markov model (HHMM) is a generalization of the popular hidden Markov model that eciently models sequences with hierarchical structure. The conventional inference algorithm for HHMMs is somewhat complicated, and its time complexity is cubic in the length of the observation sequence, making it impractical for many problems. In this paper, we show how HHMMs are a special case of the more general framework of dynamic Bayesian networks (DBNs), and thereby derive a much simpler and faster inference algorithm with complexity linear in the length of the observation sequence. Furthermore, by drawing the connection between HHMMs and DBNs, we open a whole array of approximation techniques to further speed up inference. 1