Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models

Abstract

Hidden Markov models (HMMs) are popular models to identify a finite number of latent states from sequential data. However, fitting them to large datasets can be computationally demanding because most likelihood maximization techniques require iterating through the entire underlying dataset for every parameter update. We propose a novel optimization algorithm that updates the parameters of an HMM without iterating through the entire dataset. Namely, we combine a partial E step with variance-reduced stochastic optimization within the M step. We prove the algorithm converges under certain regularity conditions. We test our algorithm empirically using a simulation study as well as a case study of kinematic data collected using suction-cup attached biologgers from eight northern resident killer whales (Orcinus orca) off the western coast of Canada. In both, our algorithm converges in fewer epochs, with less computation time, and to regions of higher likelihood compared to standard numerical optimization techniques. Our algorithm allows practitioners to fit complicated HMMs to large time-series datasets more efficiently than existing baselines. Supplemental materials are available online.

KEYWORDS:

• Expectation-maximization algorithm
• Maximum likelihood estimation
• State space model
• Statistical ecology
• Stochastic gradient descent

Acknowledgments

All killer whale data was collected under University of British Columbia Animal Care Permit no. A19-0053 and Fisheries and Oceans Canada Marine Mammal Scientific License for Whale Research no. XMMS 6 2019. Tags were deployed by Mike deRoos, the tagging boat skipper was Chris Hall, and photo-ID was done by Taryn Scarff. This research was enabled in part by support provided by WestGrid (www.westgrid.ca) and Compute Canada (www.computecanada.ca). We also thank the reviewers for their constructive comments.

Disclosure Statement

The authors report there are no competing interests to declare.

Additional information

Funding

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) as well as the support of Fisheries and Oceans Canada (DFO). This project was supported by a financial contribution from the DFO and NSERC (Whale Science for Tomorrow). This work was also supported by the NSERC Discovery program under grant RGPIN-2020-04629; the Canadian Research Chairs program for Statistical Ecology; the BC Knowledge Development fund; the Canada Foundation for Innovation (John R. Evans Leaders Fund) under grant 37715; and the University of British Columbia via the Four-Year Doctoral Fellowship program.