A generalization of discrete hidden Markov model and of viterbi algorithm

摘要

A hidden Markov model (HMM) is generalized to allow the variable length and depth of dependency by introducing the concept of composite state vs. basic state. A recursive function is defined to compute the probability distribution of the transitions from basic or composite states to composite states. A Viterbi Algorithm is generalized to compute the optimal state sequence when given an observation sequence in time of O(T × (max (N, Nc))2), where N is the number of basic states, Nc the number of composite states, and T the length of the observation symbol sequence.