Learning Hidden Markov Models from Pairwise Co-occurrences with Application to Topic Modeling

Kejun Huang, Xiao Fu, Nicholas Sidiropoulos
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2068-2077, 2018.

Abstract

We present a new algorithm for identifying the transition and emission probabilities of a hidden Markov model (HMM) from the emitted data. Expectation-maximization becomes computationally prohibitive for long observation records, which are often required for identification. The new algorithm is particularly suitable for cases where the available sample size is large enough to accurately estimate second-order output probabilities, but not higher-order ones. We show that if one is only able to obtain a reliable estimate of the pairwise co-occurrence probabilities of the emissions, it is still possible to uniquely identify the HMM if the emission probability is sufficiently scattered. We apply our method to hidden topic Markov modeling, and demonstrate that we can learn topics with higher quality if documents are modeled as observations of HMMs sharing the same emission (topic) probability, compared to the simple but widely used bag-of-words model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-huang18c, title = {Learning Hidden {M}arkov Models from Pairwise Co-occurrences with Application to Topic Modeling}, author = {Huang, Kejun and Fu, Xiao and Sidiropoulos, Nicholas}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2068--2077}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/huang18c/huang18c.pdf}, url = {https://proceedings.mlr.press/v80/huang18c.html}, abstract = {We present a new algorithm for identifying the transition and emission probabilities of a hidden Markov model (HMM) from the emitted data. Expectation-maximization becomes computationally prohibitive for long observation records, which are often required for identification. The new algorithm is particularly suitable for cases where the available sample size is large enough to accurately estimate second-order output probabilities, but not higher-order ones. We show that if one is only able to obtain a reliable estimate of the pairwise co-occurrence probabilities of the emissions, it is still possible to uniquely identify the HMM if the emission probability is sufficiently scattered. We apply our method to hidden topic Markov modeling, and demonstrate that we can learn topics with higher quality if documents are modeled as observations of HMMs sharing the same emission (topic) probability, compared to the simple but widely used bag-of-words model.} }
Endnote
%0 Conference Paper %T Learning Hidden Markov Models from Pairwise Co-occurrences with Application to Topic Modeling %A Kejun Huang %A Xiao Fu %A Nicholas Sidiropoulos %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-huang18c %I PMLR %P 2068--2077 %U https://proceedings.mlr.press/v80/huang18c.html %V 80 %X We present a new algorithm for identifying the transition and emission probabilities of a hidden Markov model (HMM) from the emitted data. Expectation-maximization becomes computationally prohibitive for long observation records, which are often required for identification. The new algorithm is particularly suitable for cases where the available sample size is large enough to accurately estimate second-order output probabilities, but not higher-order ones. We show that if one is only able to obtain a reliable estimate of the pairwise co-occurrence probabilities of the emissions, it is still possible to uniquely identify the HMM if the emission probability is sufficiently scattered. We apply our method to hidden topic Markov modeling, and demonstrate that we can learn topics with higher quality if documents are modeled as observations of HMMs sharing the same emission (topic) probability, compared to the simple but widely used bag-of-words model.
APA
Huang, K., Fu, X. & Sidiropoulos, N.. (2018). Learning Hidden Markov Models from Pairwise Co-occurrences with Application to Topic Modeling. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2068-2077 Available from https://proceedings.mlr.press/v80/huang18c.html.

Related Material