Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2010 | Published
Book Section - Chapter Open

Feedback Message Passing for Inference in Gaussian Graphical Models


For Gaussian graphical models with cycles, loopy belief propagation often performs reasonably well, but its convergence is not guaranteed and the computation of variances is generally incorrect. In this paper, we identify a set of special vertices called a feedback vertex set whose removal results in a cycle-free graph. We propose a feedback message passing algorithm in which non-feedback nodes send out one set of messages while the feedback nodes use a different message update scheme. Exact inference results can be obtained in O(k^2n), where k is the number of feedback nodes and n is the total number of nodes. For graphs with large feedback vertex sets, we describe a tractable approximate feedback message passing algorithm. Experimental results show that this procedure converges more often, faster, and provides better results than loopy belief propagation.

Additional Information

© 2010 IEEE. Date of Current Version: 23 July 2010. This work is supported in part by ARO under MURI Grant W911NF-06-1-0076, by AFOSR under Grant FA9550-08-1-1080 and MURI Grant FA9550-06-1-0324. We thank Professor Devavrat Shah and Justin Dauwels for many helpful discussions.

Attached Files

Published - 05513321.pdf


Files (162.8 kB)
Name Size Download all
162.8 kB Preview Download

Additional details

August 19, 2023
October 19, 2023