An efficient forward-backward algorithm for an explicit-duration hidden Markov model

作者：Yu, SZ^*; Kobayashi, H

来源：IEEE Signal Processing Letters, 2003, 10(1): 11-14.

DOI：10.1109/LSP.2002.806705

• explicit-duration HMM
• hidden Markov model (HMM)
• hidden semi-Markov model
• traffic characterization
• variable-duration HMM

Existing algorithms for estimating the model parameters of an explicit-duration hidden Markov model (HMM) usually require computations as large as O((MD2 M-2)T) or O(M-2 DT), where M is the number of states; D is the maximum possible interval between state transitions; and T is the period of observations used to estimate the model parameters. Because of such computational requirements, these algorithms are not practical when we wish to construct an HMM model with large state space and large explicit state duration and process a large amount of measurement data to obtain high accuracy. We propose a new forward-backward algorithm whose computational complexity is only O ((MD M-2) T), a reduction by almost a factor of D when D > M and whose memory requirement is O(MT). As an application example, we discuss an HMM characterization of access traffic observed at a large-scale Web site: we formulate the Web access pattern in terms of an HMM with explicit duration and estimate the model parameters using our algorithm.

• 出版日期2003-1
• 单位中山大学