Bounds on max-product algorithms for multiple fault diagnosis in graphs with loops
Date
2007ISBN
978-3-9524173-8-6Publisher
Institute of Electrical and Electronics Engineers Inc.Source
2007 European Control Conference, ECC 20072007 European Control Conference, ECC 2007
Pages
1008-1015Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Conference Object
A neural-type parallel algorithm for fast matrix inversion
Polycarpou, Marios M.; Ioannou, P. A. (1991)
-
Article
Online parallel scheduling of non-uniform tasks: Trading failures for energy
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 ...
-
Article
Max-product algorithms for the generalized multiple-fault diagnosis problem
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 ...