Statistical and computational guarantees for the Baum-Welch algorithm

MaRDI QIDQ4637049zbMATH OpenFDO

Authors Fanny Yang, Sivaraman Balakrishnan, Martin J. Wainwright

Publication date 17 April 2018

Full work available at URL https://arxiv.org/abs/1512.08269, http://jmlr.csail.mit.edu/papers/v18/16-093.html

zbMATH Keywords

Baum-Welch algorithmEM algorithmgraphical modelshidden Markov modelsnon-convex optimization

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Probabilistic graphical models (62H22) Markov processes: estimation; hidden Markov models (62M05)

Abstract: The Hidden Markov Model (HMM) is one of the mainstays of statistical modeling of discrete time series, with applications including speech recognition, computational biology, computer vision and econometrics. Estimating an HMM from its observation process is often addressed via the Baum-Welch algorithm, which is known to be susceptible to local optima. In this paper, we first give a general characterization of the basin of attraction associated with any global optimum of the population likelihood. By exploiting this characterization, we provide non-asymptotic finite sample guarantees on the Baum-Welch updates, guaranteeing geometric convergence to a small ball of radius on the order of the minimax rate around a global optimum. As a concrete example, we prove a linear rate of convergence for a hidden Markov mixture of two isotropic Gaussians given a suitable mean separation and an initialization within a ball of large radius around (one of) the true parameters. To our knowledge, these are the first rigorous local convergence guarantees to global optima for the Baum-Welch algorithm in a setting where the likelihood function is nonconvex. We complement our theoretical results with thorough numerical simulations studying the convergence of the Baum-Welch algorithm and illustrating the accuracy of our predictions.

Recommendations

• Publication:3468423
• The Baum-Welch algorithm with limiting distribution constraints
• The Baum--Welch algorithm for parameter estimation of Gaussian autoregressive mixture models
• The influence of initial conditions on maximum likelihood estimation of the parameters of a binary hidden Markov model
• A spectral algorithm for learning hidden Markov models

Cites work

• A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains
• A note on uniform laws of averages for dependent processes
• A spectral algorithm for learning hidden Markov models
• A spectral algorithm for learning mixture models
• Asymptotic normality of the maximum-likelihood estimator for general hidden Markov models
• Biological Sequence Analysis
• Factor graphs and the sum-product algorithm
• Graphical models, exponential families, and variational inference
• scientific article; zbMATH DE number 3567782 (Why is no real title available?)
• scientific article; zbMATH DE number 722978 (Why is no real title available?)
• scientific article; zbMATH DE number 2019610 (Why is no real title available?)
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
• On Talagrand's deviation inequalities for product measures
• On the convergence properties of the EM algorithm
• Probability in Banach spaces. Isoperimetry and processes
• Rates of convergence for empirical processes of stationary mixing sequences
• Statistical guarantees for the EM algorithm: from population to sample-based analysis
• Statistical Inference for Probabilistic Functions of Finite State Markov Chains
• Weak convergence and empirical processes. With applications to statistics

Cited in

(4)

• The Baum-Welch algorithm with limiting distribution constraints
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Approximating optimal SMC proposal distributions in individual-based epidemic models
• Instability, computational efficiency and statistical accuracy

This page was built for publication: Statistical and computational guarantees for the Baum-Welch algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637049)