TY - GEN

T1 - Orbit-product representation and correction of Gaussian belief propagation

AU - Johnson, Jason K.

AU - Chernyak, Vladimir Y.

AU - Chertkov, Michael

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=71149111885&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=71149111885&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:71149111885

SN - 9781605585161

T3 - Proceedings of the 26th International Conference On Machine Learning, ICML 2009

SP - 473

EP - 480

BT - Proceedings of the 26th International Conference On Machine Learning, ICML 2009

T2 - 26th International Conference On Machine Learning, ICML 2009

Y2 - 14 June 2009 through 18 June 2009

ER -