Abstract
Hidden Markov Models (HMM) are interpretable statistical models that specify distributions over sequences of symbols by assuming these symbols are generated from hidden states. Once learned, these models can be used to determine the most likely sequence of hidden states for unseen observable sequences. This is done in practice by solving the shortest path problem in a layered directed acyclic graph using dynamic programming. In some applications, although the hidden states are unknown, we argue that it is known that some observable elements must be generated from the same hidden state. Finding the most likely hidden state in this contrained setting is however a hard problem. We propose a number of alternative approaches for this problem: an Integer Programming (IP), Dynamic Programming (DP), a Branch and Bound (B &B) and a Cost Function Network (CFN) approach. Our experiments show that the DP approach does not scale well; B &B scales better for a small number of constraints imposed on many elements and CFNs are the most robust approach when many smaller constraints are imposed. Finally, we show that the addition of consistency constraints indeed allows to better recover the correct hidden states.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The source code and the data sets can be found at https://github.com/AlexandreDubray/consistent-viterbi.
References
Adam, A., Finance, O., Thomas, I.: Monitoring trucks to reveal belgian geographical structures and dynamics: From GPS traces to spatial interactions. J. Transp. Geogr. 91, 102977 (2021)
Bird, S., Klein, E., Loper, E.: Natural Language Processing with Python: Analyzing Text with the Natural Language Toolkit. O’Reilly Media, Inc. (2009)
Christiansen, H., Have, C.T., Lassen, O.T., Petit, M.: Inference with constrained hidden markov models in prism. Theory Pract. Logic Program. 10, (2010)
Cooper, M.C., De Givry, S., Sánchez, M., Schiex, T., Zytnicki, M., Werner, T.: Soft arc consistency revisited. Artif. Intell. 174, 449-478 (2010)
Dubray, A., Derval, G., Nijssen, S., Schaus, P.: On the complexity of the shortest path problem in a layered directed acyclic graph with consistency constraints (2022). 2078.1/264677
Fallmann, S., Kropf, J.: Human activity recognition of continuous data using hidden markov models and the aspect of including discrete data. In: UIC, pp.121–126 (2016)
Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2022). https://www.gurobi.com
Hurley, B., et al.: Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3), 413–434 (2016). https://doi.org/10.1007/s10601-016-9245-y
Kabir, M.H., Hoque, M.R., Thapa, K., Yang, S.H.: Two-layer hidden markov model for human activity recognition in home environments. Int. J. Distrib. Sens. Netw. IJDSN. 2016, 1–12 (2016)
Rabiner, L.R.: A tutorial on hidden markov models and selected applications in speech recognition. In: Proceedings of the IEEE (1989)
Roth, D., Yih, W.T.: Integer linear programming inference for conditional random fields. In: ICML (2005)
Rush, A.M., Sontag, D., Collins, M., Jaakkola, T.: On dual decomposition and linear programming relaxations for natural language processing (2010)
Sato, T., Kameya, Y.: Prism: a language for symbolic-statistical modeling. In: IJCAI (1997)
Schiex, T., de Givry, S., Sanchez, M.: Toulbar2-an open source weighted constraint satisfaction solver (2006). https://toulbar2.github.io/toulbar2
Sonnhammer, E.L., et al.: A hidden markov model for predicting transmembrane helices in protein sequences. In: ISMB (1998)
Taghavi, M., Irannezhad, E., Prato, C.G.: Identifying truck stops from a large stream of GPS data via a hidden markov chain model. In: ITCS (2019)
Takeuchi, F., Nishino, M., Yasuda, N., Akiba, T., Minato, S.I., Nagata, M.: BDD-constrained a* search: a fast method for solving constrained shortest-path problems. IEICE Trans. Inform. Syst. 10(12), 2945–2952 (2017)
Van Kasteren, T., Noulas, A., Englebienne, G., Kröse, B.: Accurate activity recognition in a home setting. In: UbiComp, pp. 1-9,(2008)
Viterbi, A.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inform. Theo. 13(2), 260–269 (1967)
Yoshikawa, M., Mineshima, K., Noji, H., Bekki, D.: Consistent CCG parsing over multiple sentences for improved logical reasoning. arXiv preprint (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dubray, A., Derval, G., Nijssen, S., Schaus, P. (2022). Optimal Decoding of Hidden Markov Models with Consistency Constraints. In: Pascal, P., Ienco, D. (eds) Discovery Science. DS 2022. Lecture Notes in Computer Science(), vol 13601. Springer, Cham. https://doi.org/10.1007/978-3-031-18840-4_29
Download citation
DOI: https://doi.org/10.1007/978-3-031-18840-4_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-18839-8
Online ISBN: 978-3-031-18840-4
eBook Packages: Computer ScienceComputer Science (R0)