递推信度传播算法—按良序的信度传播

Recursive Belief Propagation—Belief Propagation in a Well-order

针对循环信度传播算法在多环的贝叶斯网中迭代次数较多且不一定收敛的问题,提出了递推信度传播算法.它与循环信度传播及其推广算法的区别就在于按某一特定顺序(良序)进行信度传播.该算法经过一轮信度传播便达到不动点,显著降低了计算量.按这种顺序传播信度等价于去掉网络中某些边而解除了网络中的环,从而使信度不再出现环流.此算法得到的不动点与循环信度传播算法在收敛时得到的不动点是一致的,也就是网络的Bethe自由能的最小值点.最后,实验验证本文所提的算法在实际应用中能有效地降低推理的复杂度.

Aimed at the loopy belief propagation s unknown convergence and too many iterations on Bayesian networks with cycles,an algorithm named recursive belief propagation （RBP） is proposed.Different from the classical belief propagation,a special order （well-order） is followed by RBP.Passing messages according to this order is equivalent to breaking the cycles sequentially,so the messages cannot circulate and the fixed point is arrived at in one trial.Furthermore,this fixed point is the same as the result of the loopy belief propagation or the minimal point of Bethe free energy.At last,we prove the good performance of the proposed algorithm by experiments.