Improved Performance Bounds on Max-Product Algorithms for Multiple Fault Diagnosis in Graphs with Loops

In this paper, we analyze the performance of belief propagation max-product algorithms when used to solve the multiple fault diagnosis (MFD) problem. 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, 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. By using properties of the max-product algorithm (MPA) and the sequential max-product algorithm (SMPA), we are able to analyze in this paper the performance of both algorithms with respect to the MAP solution (in terms of the probability of erroneous diagnosis). Our theoretical analysis indicates that the upper bounds in this paper are up to several orders of magnitude better than existing bounds, especially when the smallest loop size is an odd number. We also provide examples which demonstrate that our theoretical upper bounds match very well with simulation results.