Optimization of BP Algorithm in Repeated Inference
Ren Zhi-ping · Jisuanji gongcheng · 2011
It always produces redundant computation when applying Belief Propagation(BP) algorithm to MEU problem.To improve such a situation,an optimization to BP is proposed that reuse last influent result instead of recomputing the marginal probability if the node is not significantly affected by the change of condition,and prove is given to confirm that the optimization does not significantly affect the influence result.A simulation by applying the optimized algorithm to combinatorial auctions gives the result that compare to the standard BP algorism,optimized algorism efficiently improve the efficiency of inference without significantly affect the quality of the solutions.