Murakami, Junko (Victoria Univ. of Wellington), Taylor, Thomas (Arizona State Univ.)

Least Square Estimation of a Hidden Markov Chain Parameters

Scheduled for presentation during the Regular Session "Nonlinear Estimation and Identification" (ThP09), Thursday, July 27, 2006, 15:45−16:10, Room J

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on May 19, 2024

Abstract

Among the algorithms used for the parameter estimate of discrete-time time-homogeneous Hidden Markov Models (HMM), Baum-Welch (B-W) algorithm, which is used to find the maximum likelihood estimate, is by far the most popular algorithm. However, one of its well-known shortcomings is an "overfitting" problem: it tends to fit the observation sequence well but not so much the HMM which generated the sequence, when the data size is small.

Experiments show the least square error (LSE) estimator (or Bayes estimate) outperforms the B-W algorithm in such occasions. Although the computational complexity for the LSE estimator could be very high with a naive approach, we have shown that a polynomial complexity in the data size (with still exponential complexity in the state space size) can be achieved using an algorithm proposed in this paper, making the LSE estimation quite feasible in various applications.