Bounds on max-product algorithms for multiple fault diagnosis in graphs with loops
Hadjicostis, Christoforos N.
PublisherInstitute of Electrical and Electronics Engineers Inc.
Source2007 European Control Conference, ECC 2007
2007 European Control Conference, ECC 2007
Google Scholar check
MetadataShow full item record
In this paper, we analyze the performance of algorithms that use belief propagation max-product iterations to solve the generalized multiple fault diagnosis (GMFD) problem. The GMFD problem is described by a bipartite diagnosis graph which consists of a set of components (or diseases), a set of alarms (or symptoms) and a set of connections (or causal dependencies) between them, along with a set of parameters that describe the prior probabilities for component, alarm and connection failures. Given the alarm observations, our goal is to find the status of the components that has the maximum a posteriori (MAP) probability. The max-product algorithm (MPA) and the improved sequential max-product algorithm (SMPA) that we developed in earlier work are guaranteed to converge to the MAP solution if the underlying diagnosis graph is a tree (the MPA requires in addition that the MAP solution is unique). By using several properties of the MPA and the SMPA, we obtain in this paper upper bounds on the probability Pe of diagnosis error (for both algorithms) with respect to the MAP solution. These upper bounds apply to arbitrary graphs (possibly with loops) and show that Pe decreases exponentially with the size of the smallest loop (i.e., the loop with the least number of alarms). We also provide examples to verify our theoretical analysis. © 2007 EUCA.
Showing items related by title, author, creator and subject.
Polycarpou, Marios M.; Ioannou, P. A. (1991)
Fernández Anta, Antonio; Georgiou, Chryssis; Kowalski, D. R.; Zavou, Elli (2015)Consider a system in which tasks of different execution times arrive continuously and have to be executed by a set of machines that are prone to crashes and restarts. In this paper we model and study the impact of parallelism ...
Le, T.; Hadjicostis, Christoforos N. (2007)In this paper, we study the application of the max-product algorithm (MPA) to the generalized multiple-fault diagnosis (GMFD) problem, which consists of components (to be diagnosed) and alarms/connections that can be ...