State sequence prediction in imprecise hidden Markov models
(2011) ISIPTA '11 - PROCEEDINGS OF THE SEVENTH INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS. p.159-168- abstract
- We present an efficient exact algorithm for estimating state sequences from outputs (or observations) in imprecise hidden Markov models (iHMM), where both the uncertainty linking one state to the next, and that linking a state to its output, are represented using coherent lower previsions. The notion of independence we associate with the credal network representing the iHMM is that of epistemic irrelevance. We consider as best estimates for state sequences the (Walley-Sen) maximal sequences for the posterior joint state model (conditioned on the observed output sequence), associated with a gain function that is the indicator of the state sequence. This corresponds to (and generalises) finding the state sequence with the highest posterior probability in HMMs with precise transition and output probabilities (pHMMs). We argue that the computational complexity is at worst quadratic in the length of the Markov chain, cubic in the number of states, and essentially linear in the number of maximal state sequences. For binary iHMMs, we investigate experimentally how the number of maximal state sequences depends on the model parameters.
Please use this url to cite or link to this publication:
http://hdl.handle.net/1854/LU-1978382
- author
- Jasper De Bock UGent and Gert De Cooman UGent
- organization
- year
- 2011
- type
- conference (proceedingsPaper)
- publication status
- published
- subject
- keyword
- maximality, optimal state sequence, coherent lower prevision, epistemic irrelevance, credal network, Imprecise hidden Markov model
- in
- ISIPTA '11 - PROCEEDINGS OF THE SEVENTH INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS
- editor
- F Coolen, G DeCooman, T Fetz and M Oberguggenberger
- pages
- 159 - 168
- conference name
- 7th International symposium on Imprecise Probability: Theories and Applications (ISIPTA 2011)
- conference location
- Innsbruck, Austria
- conference start
- 2011-07-25
- conference end
- 2011-07-28
- Web of Science type
- Proceedings Paper
- Web of Science id
- 000323983600019
- ISBN
- 9783902652409
- project
- Bioinformatics: from nucleotids to networks (N2N)
- language
- English
- UGent publication?
- yes
- classification
- P1
- copyright statement
- I have retained and own the full copyright for this publication
- id
- 1978382
- handle
- http://hdl.handle.net/1854/LU-1978382
- date created
- 2012-01-04 15:59:41
- date last changed
- 2016-12-19 15:37:19
@inproceedings{1978382, abstract = {We present an efficient exact algorithm for estimating state sequences from outputs (or observations) in imprecise hidden Markov models (iHMM), where both the uncertainty linking one state to the next, and that linking a state to its output, are represented using coherent lower previsions. The notion of independence we associate with the credal network representing the iHMM is that of epistemic irrelevance. We consider as best estimates for state sequences the (Walley-Sen) maximal sequences for the posterior joint state model (conditioned on the observed output sequence), associated with a gain function that is the indicator of the state sequence. This corresponds to (and generalises) finding the state sequence with the highest posterior probability in HMMs with precise transition and output probabilities (pHMMs). We argue that the computational complexity is at worst quadratic in the length of the Markov chain, cubic in the number of states, and essentially linear in the number of maximal state sequences. For binary iHMMs, we investigate experimentally how the number of maximal state sequences depends on the model parameters.}, author = {De Bock, Jasper and De Cooman, Gert}, booktitle = {ISIPTA '11 - PROCEEDINGS OF THE SEVENTH INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS}, editor = {Coolen, F and DeCooman, G and Fetz, T and Oberguggenberger, M}, isbn = {9783902652409}, keyword = {maximality,optimal state sequence,coherent lower prevision,epistemic irrelevance,credal network,Imprecise hidden Markov model}, language = {eng}, location = {Innsbruck, Austria}, pages = {159--168}, title = {State sequence prediction in imprecise hidden Markov models}, year = {2011}, }
- Chicago
- De Bock, Jasper, and Gert De Cooman. 2011. “State Sequence Prediction in Imprecise Hidden Markov Models.” In ISIPTA ’11 - PROCEEDINGS OF THE SEVENTH INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS, ed. F Coolen, G DeCooman, T Fetz, and M Oberguggenberger, 159–168.
- APA
- De Bock, Jasper, & De Cooman, G. (2011). State sequence prediction in imprecise hidden Markov models. In F Coolen, G. DeCooman, T. Fetz, & M. Oberguggenberger (Eds.), ISIPTA ’11 - PROCEEDINGS OF THE SEVENTH INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS (pp. 159–168). Presented at the 7th International symposium on Imprecise Probability: Theories and Applications (ISIPTA 2011).
- Vancouver
- 1.De Bock J, De Cooman G. State sequence prediction in imprecise hidden Markov models. In: Coolen F, DeCooman G, Fetz T, Oberguggenberger M, editors. ISIPTA ’11 - PROCEEDINGS OF THE SEVENTH INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS. 2011. p. 159–68.
- MLA
- De Bock, Jasper, and Gert De Cooman. “State Sequence Prediction in Imprecise Hidden Markov Models.” ISIPTA ’11 - PROCEEDINGS OF THE SEVENTH INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS. Ed. F Coolen et al. 2011. 159–168. Print.