Orbit-product representation and correction of Gaussian belief propagation

Jason K. Johnson, Vladimir Y. Chernyak, Michael Chertkov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th International Conference On Machine Learning, ICML 2009
Pages473-480
Number of pages8
StatePublished - 2009
Externally publishedYes
Event26th International Conference On Machine Learning, ICML 2009 - Montreal, QC, Canada
Duration: Jun 14 2009Jun 18 2009

Publication series

NameProceedings of the 26th International Conference On Machine Learning, ICML 2009

Conference

Conference26th International Conference On Machine Learning, ICML 2009
Country/TerritoryCanada
CityMontreal, QC
Period6/14/096/18/09

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'Orbit-product representation and correction of Gaussian belief propagation'. Together they form a unique fingerprint.

Cite this