Bounds on the probability of misclassification among hidden Markov models
Date
2011ISBN
9781612848006Source
Proceedings of the IEEE Conference on Decision and ControlProceedings of the IEEE Conference on Decision and Control
Pages
385390Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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. © 2011 IEEE.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.

Conference Object
Hidden markov model classification based on empirical frequencies of observed symbols
Keroglou, C.; Hadjicostis, Christoforos N. (IFAC Secretariat, 2014)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 ...

Conference Object
Bound on the probability of HMM misclassification
Keroglou, C.; Hadjicostis, Christoforos N. (2011)In this paper we consider the problem of classifying a sequence of observations among two known hidden Markov models (HMMs). We use a classifier that minimizes the probability of error (i.e., the probability of misclassification), ...

Article
Approximation of Markov Processes by Lower Dimensional Processes via Total Variation Metrics
Tzortzis, I.; Charalambous, C. D.; Charalambous, T.; Hadjicostis, Christoforos N.; Johansson, M. (2017)The aim of this paper is to approximate a FiniteState Markov (FSM) process by another process defined on a lower dimensional state space, called the approximating process, with respect to a total variation distance fidelity ...