Low-complexity max-product algorithms for problems of multiple fault diagnosis

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.