Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE credits
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
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.