Approximate Realization of Hidden Markov Models

Open Access
Author:
Bardakci, Ibrahim Ekrem
Graduate Program:
Electrical Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
December 04, 2014
Committee Members:
  • Constantino Manuel Lagoa, Thesis Advisor
Keywords:
  • Hidden Markov Model
  • Approximate Realization
  • Hankel Matrix
  • Nuclear Norm
Abstract:
The realization problem for hidden Markov models (HMMs) has been studied over years. However, it does not always have solution and requires the exact string probabilities of all string of finite length. In real world applications, it is not feasible and only fi nite number of approximate string probabilities of strings up to certain length are usually available. Since the string probabilities are approximate, the realization algorithms will produce an outcome of HMM that has high order. Accordingly, it may be more useful to make a good low order approximate realization of string probabilities rather than try to match them exactly. In this thesis, we aim to give a heuristic as a solution to approximate realization problem for HMM by presenting a low-order approximation of the HMM given a sequence of observations. We propose an algorithm to fi nd an HMM that approximately generates the given string probabilities which are computed from the observation sequence. The algorithm fi rst minimizes the rank of Hankel matrix constructed from an HMM using nuclear norm generalization, subsequently given the rank information finds an HMM using non-negative matrix factorization that approximately realizes the given string probabilities.