Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
Hidden Markov models (HMMs) are popular models to identify a finite number of latent states from sequential data. However, fitting them to large data sets can be computationally demanding because most likelihood maximization techniques require iterating through the entire underlying data set for eve...
Main Authors: | , , , , , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2023
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2310.04620 |
id |
ftarxivpreprints:oai:arXiv.org:2310.04620 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2310.04620 2023-11-12T04:24:11+01:00 Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models Sidrow, Evan Heckman, Nancy Bouchard-Côté, Alexandre Fortune, Sarah M. E. Trites, Andrew W. Auger-Méthé, Marie 2023-10-06 http://arxiv.org/abs/2310.04620 unknown http://arxiv.org/abs/2310.04620 Statistics - Computation text 2023 ftarxivpreprints 2023-10-22T01:06:45Z Hidden Markov models (HMMs) are popular models to identify a finite number of latent states from sequential data. However, fitting them to large data sets can be computationally demanding because most likelihood maximization techniques require iterating through the entire underlying data set for every parameter update. We propose a novel optimization algorithm that updates the parameters of an HMM without iterating through the entire data set. 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 and to regions of higher likelihood compared to standard numerical optimization techniques. Our algorithm allows practitioners to fit complicated HMMs to large time-series data sets more efficiently than existing baselines. Comment: 23 pages, 7 figures. Code available at https://github.com/evsi8432/sublinear-HMM-inference Text Orca Orcinus orca ArXiv.org (Cornell University Library) Canada |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Statistics - Computation |
spellingShingle |
Statistics - Computation Sidrow, Evan Heckman, Nancy Bouchard-Côté, Alexandre Fortune, Sarah M. E. Trites, Andrew W. Auger-Méthé, Marie Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models |
topic_facet |
Statistics - Computation |
description |
Hidden Markov models (HMMs) are popular models to identify a finite number of latent states from sequential data. However, fitting them to large data sets can be computationally demanding because most likelihood maximization techniques require iterating through the entire underlying data set for every parameter update. We propose a novel optimization algorithm that updates the parameters of an HMM without iterating through the entire data set. 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 and to regions of higher likelihood compared to standard numerical optimization techniques. Our algorithm allows practitioners to fit complicated HMMs to large time-series data sets more efficiently than existing baselines. Comment: 23 pages, 7 figures. Code available at https://github.com/evsi8432/sublinear-HMM-inference |
format |
Text |
author |
Sidrow, Evan Heckman, Nancy Bouchard-Côté, Alexandre Fortune, Sarah M. E. Trites, Andrew W. Auger-Méthé, Marie |
author_facet |
Sidrow, Evan Heckman, Nancy Bouchard-Côté, Alexandre Fortune, Sarah M. E. Trites, Andrew W. Auger-Méthé, Marie |
author_sort |
Sidrow, Evan |
title |
Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models |
title_short |
Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models |
title_full |
Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models |
title_fullStr |
Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models |
title_full_unstemmed |
Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models |
title_sort |
variance-reduced stochastic optimization for efficient inference of hidden markov models |
publishDate |
2023 |
url |
http://arxiv.org/abs/2310.04620 |
geographic |
Canada |
geographic_facet |
Canada |
genre |
Orca Orcinus orca |
genre_facet |
Orca Orcinus orca |
op_relation |
http://arxiv.org/abs/2310.04620 |
_version_ |
1782338721745469440 |