Name
Abstract | ||
|---|---|---|
In this paper, we propose low-complexity max-product algorithms for the problem of multiple fault diagnosis (MFD). The MFD problem is described by a bipartite diagnosis graph (BDG) which consists of a set of components, a set of alarms and a set of connections (or causal dependencies) between them. Given the alarm observations, along with a probabilistic description of the system and the dependencies among components, our goal is to find the combination of component states that has the maximum a posteriori (MAP) probability. Iterative belief propagation max-product algorithms (developed in our earlier work for the MFD problem) work well on systems associated with sparse BDGs (especially when connections and/or alarms are unreliable). However, these iterative algorithms are exponentially dependent on the maximum number of components per alarm and hence, not suitable for many practical applications. In this paper, by limiting during each iteration the maximum number of possibly faulty components per alarm, we study low-complexity versions of these existing max-product algorithms. On acyclic bipartite graphs, we show that under certain conditions on the solutions, the low-complexity algorithms are guaranteed to return the MAP solution. For arbitrary bipartite graphs, our experimental results indicate that the proposed algorithms still perform comparably to the original (more computationally expensive) algorithms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/ICARCV.2008.4795564 | ICARCV |
Keywords | Field | DocType |
iterative belief propagation max-product algorithms,belief networks,low-complexity max-product algorithms,bipartite diagnosis graph,max-product algorithms,acyclic bipartite graphs,maximum a posteriori probability,fault diagnosis,belief propagation,graph theory,reliability theory,multiple fault diagnosis,probabilistic description,probability,iterative algorithm,tin,data mining,probability density function,bipartite graph | Graph theory,Computer science,ALARM,Bipartite graph,Algorithm,Theoretical computer science,Probabilistic logic,Maximum a posteriori estimation,Probability density function,Belief propagation,Reliability theory | Conference |
ISBN | Citations | PageRank |
978-1-4244-2287-6 | 0 | 0.34 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tung Le | 1 | 37 | 5.87 |
| Christoforos N. Hadjicostis | 2 | 1425 | 127.48 |