Page 147 - 《软件学报》2021年第5期

王晓峰 等:可满足性问题中信念传播算法的收敛性分析 1371

[36] Tatikonda S, Jordan MI. Loopy belief propagation and Gibbs measure. In: Proc. of the 18th Annual Conf. on Uncertainty in
Artificial Intelligence. 2002. 493−500.
[37] Heskes T. On the uniqueness of loopy belief propagation fixed points. Neural Computation, 2004,16(11):2379−2413.
[38] Ihler AT, Lii JWF, Willsky AS. Loopy belief propagation: Convergence and effects of message errors. Machine Learning Research,
2005,6(1):905−936.
[39] Shi XQ, Schonfeld D, Tuninetti D. Message error analysis of loopy belief propagation for the sum-product algorithm. Computer
and Information Science, 2010,1009:1−30.
[40] Feige U, Mossel E, Vilenchik D. Complete convergence of message passing algorithms for some satisfiability problems. Theory of
Computing, 2013,9(19):617−651.
[41] Wang XF, Xu DY, Wei L. Convergence of warning propagation algorithms for random satisfiable instances. Ruan Jian Xue Bao/
Journal of Software, 2013,24(1):1−11 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4213.htm [doi: 10.3724/
SP.J.1001.2013.04213]
[42] Wang XF, Xu DY. Convergence of the belief propagation algorithm for RB model instances. Ruan Jian Xue Bao/Journal of
Software, 2016,27(11):2712−2724 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4877.htm [doi: 10.13328/j.
cnki.jos.004877]
[43] Wang XF, Xu DY. Sufficient conditions for convergence of the warning propagation algorithm. Ruan Jian Xue Bao/Journal of
Software, 2016,27(12):3003−3013 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4940.htm [doi: 10.13328/j.
cnki.jos.004940]
[44] Wang XF, Xu DY, Jiang JL, Tang YH. A sufficient condition for survey propagation convergence. SCIENTIA SINICA
Informationis, 2017,47(12):1646−1661 (in Chinese with English abstract).
[45] Du J, Ma S, Wu YC, Kar S, Moura JMF. Convergence analysis of distributed inference with vector valued Gaussian belief
propagation. Journal of Machine Learning Research, 2018,18(172):1−38.
[46] Du J, Ma S, Wu YC, Kar S, Moura JMF. Convergence analysis of the information matrix in Gaussian belief propagation. In: Proc.
of the IEEE Int’l Conf. on Acoustics, Speech and Signal Processing. 2017. 4074−4078.
[47] Du J, Ma S, Wu YC, Kar S, Moura JMF. Convergence analysis of belief propagation for pairwise linear Gaussian models. In: Proc.
of the IEEE Global Conf. on Signal and Information Processing. 2017. 548−552.
[48] Su Q, Wu YC. Convergence analysis of the variance in Gaussian belief propagation. IEEE Trans. on Signal Processing, 2014,
62(19):5119−5131.
[49] Su Q, Wu YC. On convergence conditions of Gaussian belief propagation. IEEE Trans. on Signal Processing, 2015,63(5):
1144−1155.
[50] Park S, Shin J. Convergence and correctness of max-product belief propagation for linear programming. Siam Journal on Discrete
Mathematics, 2017,31(3):2228−2246.
[51] Wang Y, Reyes MG, Neuhoff DL. Correct convergence of min-sum loopy belief propagation in a block interpolation problem.
arXiv Preprint arXiv:1702.06391, 2017.
[52] Sui T, Marelli D, Fu M. Convergence analysis for guassian belief propagation: Dynamic behaviour of marginal covariances. In:
Proc. of the IEEE Int’l Conf. on Acoustics, Speech and Signal Processing. 2016. 2599−2602.
[53] Mooij JM, Kappen HJ. Sufficient conditions for convergence of the sum-product algorithm. IEEE Trans. on Information Theory,
2007,53(12):4422−4437.
[54] Dieudonne J. Foundations of Modern Analysis. New York: Academic Press, 1960.

附中文参考文献:
[18] 赵春艳,郑志明.一种基于变量熵求解约束满足问题的置信传播算法.中国科学:信息科学,2012,42(9):1170−1180.
[19] 殷明浩,周俊萍,孙吉贵,谷文祥.求解 QBF 问题的启发式调查传播算法.软件学报,2011,22(7):1538−1550. http://www.jos.org.cn/
1000-9825/3859.htm [doi: 10.3724/SP.J.1001.2011.03859]
[41] 王晓峰,许道云,韦立.随机实例集上警示传播算法的收敛性.软件学报,2013,24(1):1−11. http://www.jos.org.cn/1000-9825/4213.
htm [doi: 10.3724/SP.J.1001.2013.04213]