Bounds on the probability of misclassification among hidden Markov models
- 1 December 2011
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Conference on Decision and Control and European Control Conference
- p. 385-390
- https://doi.org/10.1109/cdc.2011.6161128
Abstract
Given a sequence of observations, classification among two known hidden Markov models (HMMs) can be accomplished with a classifier that minimizes the probability of error (i.e., the probability of misclassification) by enforcing the maximum a posteriori probability (MAP) rule. For this MAP classifier, we are interested in assessing the a priori probability of error (before any observations are made), something that can be obtained (as a function of the length of the sequence of observations) by summing up the probability of error over all possible observation sequences of the given length. To avoid the high complexity of computing the exact probability of error, we devise techniques for merging different observation sequences, and obtain corresponding upper bounds by summing up the probabilities of error over the merged sequences. We show that if one employs a deterministic finite automaton (DFA) to capture the merging of different sequences of observations (of the same length), then Markov chain theory can be used to efficiently determine a corresponding upper bound on the probability of misclassification. The result is a class of upper bounds that can be computed with polynomial complexity in the size of the two HMMs and the size of the DFA.Keywords
This publication has 9 references indexed in Scilit:
- A Novel Low-Complexity HMM Similarity MeasureIEEE Signal Processing Letters, 2010
- Probability of error bounds for failure diagnosis and classification in hidden Markov modelsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Diagnosability of stochastic discrete-event systemsIEEE Transactions on Automatic Control, 2005
- Speech recognition of a natural text read as isolated wordsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- State Observation and Diagnosis of Discrete-Event Systems Described by Stochastic AutomataDiscrete Event Dynamic Systems, 2001
- Hidden Markov Models for BioinformaticsPublished by Springer Science and Business Media LLC ,2001
- Biological Sequence AnalysisPublished by Cambridge University Press (CUP) ,1998
- Kronecker Products, Unitary Matrices and Signal Processing ApplicationsSIAM Review, 1989
- A Probabilistic Distance Measure for Hidden Markov ModelsAT&T Technical Journal, 1985