基于二维结构熵的置信传播算法收敛性分析

为了对置信传播(BP)算法在结构比较复杂的命题公式上有时会失效,常常表现为不收敛的现象给予理论解释,提出了基于警示传播的社区发现算法(WPLPA).依据BP算法在因子图上的信息迭代策略,利用WPLPA算法对命题公式所对应因子图的社区结构进行划分.借助二维结构熵的相关理论技术,建立了命题公式的二维结构熵度量模型,通过该模型分析了BP算法的收敛性与二维结构熵之间的关系,给出BP算法的收敛性判定条件,对BP算法的收敛性进行系统分析.实验分析证明该方法有效可行,能为信息传播算法的后续研究提供理论支持.

Convergence analysis of belief propagation algorithm based on two-dimensional structural entropy

In order to provide theoretical explanations for the belief propagation(BP) algorithm often appear as non-convergence in the propositional formulas with more complex structure, this paper proposed the community discovery algorithm(WPLPA) based on warning propagation. It used the WPLPA algorithm to divide the community structure of the factor graph corresponding to the proposition formula by the message iteration strategy on the graph in BP algorithm. It established twodimensional structure entropy measurement model of the proposition formula with the help of the related theory and technology of two-dimensional structure entropy. It analyzed the relationship between the convergence of the BP algorithm and the twodimensional structure entropy through this model, and gave the convergence judgment of the BP algorithm. It systematically analyzed the convergence of BP algorithm. Experimental analysis prove that the method is effective and feasible, and it can provide theoretical support for the follow-up research of information dissemination algorithm.