Orbit-product representation and correction of Gaussian belief propagation
Orbit-product representation and correction of Gaussian belief propagation
复制标题
高斯置信传播的轨道积表示和校正
DOI：
10.1145/1553374.1553436
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Chertkov
中科院分区：
文献类型：
--
作者：
Jason K. Johnson;V. Chernyak;M. Chertkov
我们提出了一个新的观点高斯信念传播（GaBP）的基础上表示的行列式作为一个产品的轨道图。我们发现，GaBP行列式估计捕获完全回溯轨道的图形，并考虑如何纠正这种估计。我们发现，丢失的轨道可以被分组到对应于backtrackless轨道的等价类和每个等价类的贡献是很容易确定的GaBP解决方案。此外，我们证明了这个乘法校正因子可以被解释为一个无回溯邻接矩阵的图的边权重的基础上GaBP的行列式。最后，提出了一种有效的方法来计算截断的校正因子，包括所有的无回溯轨道到指定的长度。
We present a new view of Gaussian belief propagation (GaBP) based on a representation of the determinant as a product over orbits of a graph. We show that the GaBP determinant estimate captures totally backtracking orbits of the graph and consider how to correct this estimate. We show that the missing orbits may be grouped into equivalence classes corresponding to backtrackless orbits and the contribution of each equivalence class is easily determined from the GaBP solution. Furthermore, we demonstrate that this multiplicative correction factor can be interpreted as the determinant of a backtrackless adjacency matrix of the graph with edge weights based on GaBP. Finally, an efficient method is proposed to compute a truncated correction factor including all backtrackless orbits up to a specified length.