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

Shun‐Zheng Yu

doi:10.1109/LSP.2002.806705

Return

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

2003-01-01

176

PRE

Shun‐Zheng Yu

H. Kobayashi

DOI：10.1109/LSP.2002.806705

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

explicit-duration HMM

hidden Markov model (HMM)

hidden semi-Markov model

traffic characterization

variable-duration HMM

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.