On Identification of Hidden Markov Models Using Spectral and Non-Negative Matrix Factorization Methods

Sammanfattning: Hidden Markov Models (HMMs) are popular tools for modeling discrete time series. Since the parameters of these models can be hard to derive analytically or directly measure, various algorithms are available for estimating these from observed data. The most common method, the Expectation-Maximization algorithm, su ers from problems with local minima and slow convergence. A spectral algorithm that has received considerable attention in the eld of machine learning claims to avoid these issues. This thesis implements and benchmarks said algorithm on various systems to see how well it performs. One of the concerns with the proposed spectral algorithm is that it cannot guarantee that the estimates are stochastically valid: it may recover negative or complex probabilities, due to an eigenvalue decomposition. Another approach to the HMM identication problem is to leverage results from Non- Negative Matrix Factorization (NNMF) theory. Inspired by an algorithm employing a Structured NNMF (SNNMF), assumptions are presented to guarantee that the factorization problem can be cast into a convex optimization problem. Three novel recursive algorithms are then derived for estimating the dynamics of an HMM when the sensor dynamics are known. These can be used in an online setting where time and/or computational resources are limited, since they only require the current estimate of the HMM parameters and the new observation. Numerical results for the algorithms are provided.