Marginalized Viterbi algorithm for hierarchical hidden Markov models

• We consider the problem of finding the most likely state sequence for hierarchical HMMs.
• The generalized Viterbi algorithm finds the most likely whole level state sequence.
• We propose a marginalized Viterbi algorithm, which finds the most likely upper level state sequence.
• The marginalized Viterbi algorithm is more accurate in terms of upper level state sequence estimation.

The generalized Viterbi algorithm, a direct extension of the Viterbi algorithm for hidden Markov models (HMMs), has been used to find the most likely state sequence for hierarchical HMMs. However, the generalized Viterbi algorithm finds the most likely whole level state sequence rather than the most likely upper level state sequence. In this paper, we propose a marginalized Viterbi algorithm, which finds the most likely upper level state sequence by marginalizing lower level state sequences. We show experimentally that the marginalized Viterbi algorithm is more accurate than the generalized Viterbi algorithm in terms of upper level state sequence estimation.