Change search
ReferencesLink to record
Permanent link

Direct link
On Identification of Hidden Markov Models Using Spectral and Non-Negative Matrix Factorization Methods
KTH, School of Electrical Engineering (EES), Automatic Control.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
National Category
Control Engineering
URN: urn:nbn:se:kth:diva-165799OAI: diva2:808842
Educational program
Master of Science in Engineering -Engineering Physics
Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2015-04-29Bibliographically approved

Open Access in DiVA

fulltext(931 kB)433 downloads
File information
File name FULLTEXT01.pdfFile size 931 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Automatic Control
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 433 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 391 hits
ReferencesLink to record
Permanent link

Direct link