On Performance Analysis of State Estimators for Hidden Markov Models


The class of stochastic models known as hidden Markov model (HMM), initially introduced and studied in the late 1960’s and early 1970’s, has received much attention in recent years. Some applications are machine recognition of speech, frequency tracking, multi-target tracking and in the modelling of signal sources in the field of telecommunications. The issues of stability and performance of state estimators for the hidden states in HMMs are explored in this thesis. In particular we are concerned with estimation via maximum a posteriori (MAP) estimates, and the Viterbi algorithm (VA). MAP estimation determines the most probable state at each time instant, while the VA determines the most probable state sequence for a given observation sequence.

In the first part of this thesis, the property of exponential stability present in Kalman filters is extended to HMM filters. This result is based upon the generalised Perron-Frobenius theorem, which states that under certain conditions, an inhomogeneous product of nonnegative and irreducible matrices has an asymptotic rank of 1. The implication is that initial conditions for HMM filter are forgotten at an exponential rate. Applying the same theorem shows that for fixed-lag smoothers, the smoothed estimates become independent of smoothing lag for sufficiently large lags. This means that as the smoothing lag is increased, there is no practical gain in smoothing over filtering when the lag is increased beyond some finite value. We also provide calculations on bounds on the rate of such convergence.

The next question we consider is a quantitative comparison of HMM filters and smoothers. In particular, we restrict attention to a class of HMMs parametrised by an ε. As ε → 0, the HMMs approach deterministic systems. The asymptotic smoothing error is studied in this context, and it is seen that the gains of smoothing over filtering is significant when the underlying Markov chain is ‘slow’; this can be regarded in some sense as a situation of high signal-to-noise ratio. This is consistent with previous observations made by a number of other authors.

Following this we study the issue of quantisation, with filtering performance as the primary performance measure. By taking an information-theoretic approach to choosing the quantisation levels, we have shown improvement in filtering performance over the simple uniform quantisation scheme. It is seen that for the nonlinear filters considered, reducing the quantisation noise does not necessarily lead to a reduction in filtering error when compared against the scheme using uniform quantisation.

For the dynamical programming algorithm known as the Viterbi algorithm, only the operations of addition and maximisation are required. This lends itself naturally to the framework of the max-plus algebra, a tool for the analysis of Discrete Event Dynamical Systems. By developing an analog to the rank-1 property in conventional linear algebra, it is observed that under suitable conditions inhomogeneous products in the max-plus algebra also exhibit the property of having an asymptotic rank of 1. However, the rate of convergence to rank-1 for this problem, as well as for more general max-plus products, remains an open problem.

* Soft copy of the thesis available on request.

Leave a Reply