Parameter estimation in HMMs with guaranteed convergence

The EM (Expectation-Maximization) algorithm is a heuristic for parameter estimation in statistical models with latent variables, where explicit computation of the maximum likelihood estimate (MLE) is infeasible. Although widely used in practice, the theoretical guarantees associated with EM are quite weak. We study the setting of a hidden Markov model (HMM) with two hidden states, where the (symmetric) transition matrix [mu] is unknown and observations are Gaussian with known covariance and unknown mean [mu]. The EM algorithm for HMMs, also known as the Baum-Welch algorithm, was previously studied by Yang, Balakrishnan, and Wainwright [1] but without global convergence guarantees. In this paper we propose a "local" version of the EM algorithm and prove absolute convergence of this algorithm to the true parameters ([mu], E) in both the population and finite-sample regime. To the best of our knowledge this is the first algorithm for simultaneous parameter estimation with global convergence guarantees. Additionally, we prove several theoretical results and supply some counterexamples for the ordinary Baum-Welch algorithm in this setting.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Aiylam, Dhroova (Dhroova S.)

Advisor dc:contributor.advisor

• Guy Bresler.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/119735

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/119735