A Caltech Library Service

Feedback Message Passing for Inference in Gaussian Graphical Models

Liu, Ying and Chandrasekaran, Venkat and Anandkumar, Animashree and Willsky, Alan S. (2012) Feedback Message Passing for Inference in Gaussian Graphical Models. IEEE Transactions on Signal Processing, 60 (8). pp. 4135-4150. ISSN 1053-587X. doi:10.1109/TSP.2012.2195656.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


While loopy belief propagation (LBP) performs reasonably well for inference in some Gaussian graphical models with cycles, its performance is unsatisfactory for many others. In particular for some models LBP does not converge, and in general when it does converge, the computed variances are incorrect (except for cycle-free graphs for which belief propagation (BP) is non-iterative and exact). In this paper we propose feedback message passing (FMP), a message-passing algorithm that makes use of a special set of vertices (called a feedback vertex set or FVS) whose removal results in a cycle-free graph. In FMP, standard BP is employed several times on the cycle-free subgraph excluding the FVS while a special message-passing scheme is used for the nodes in the FVS. The computational complexity of exact inference is O(k^(2)n), where is the number of feedback nodes, and is the total number of nodes. When the size of the FVS is very large, FMP is computationally costly. Hence we propose approximate FMP, where a pseudo-FVS is used instead of an FVS, and where inference in the non-cycle-free graph obtained by removing the pseudo-FVS is carried out approximately using LBP. We show that, when approximate FMP converges, it yields exact means and variances on the pseudo-FVS and exact means throughout the remainder of the graph. We also provide theoretical results on the convergence and accuracy of approximate FMP. In particular, we prove error bounds on variance computation. Based on these theoretical results, we design efficient algorithms to select a pseudo-FVS of bounded size. The choice of the pseudo-FVS allows us to explicitly trade off between efficiency and accuracy. Experimental results show that using a pseudo-FVS of size no larger than log (n), this procedure converges much more often, more quickly, and provides more accurate results than LBP on the entire graph.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemConference Paper
Additional Information:© 2012 IEEE. Manuscript received May 09, 2011; revised January 09, 2012; accepted April 03, 2012. Date of publication May 03, 2012; date of current version July 10, 2012. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Raviv Raich. This research was supported in part by AFOSR through Grant FA9550-08-1-1080 and in part by Shell International Exploration and Production, Inc. This paper was presented in part at the International Symposium of Information Theory, Austin, Texas, 2010. The authors would like to thank D. Shah, J. Dauwels, V. Tan for helpful discussions, and the reviewers for their constructive comments.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-08-1-1080
Shell International Exploration and Production, Inc.UNSPECIFIED
Subject Keywords:Belief propagation; feedback vertex set; Gaussian graphical models; graphs with cycles; Markov random field
Issue or Number:8
Record Number:CaltechAUTHORS:20120820-094221711
Persistent URL:
Official Citation:Ying Liu; Chandrasekaran, V.; Anandkumar, A.; Willsky, A.S.; , "Feedback Message Passing for Inference in Gaussian Graphical Models," Signal Processing, IEEE Transactions on, vol.60, no.8, pp.4135-4150, Aug. 2012 doi: 10.1109/TSP.2012.2195656
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:33349
Deposited By: Jason Perez
Deposited On:20 Aug 2012 18:01
Last Modified:09 Nov 2021 21:34

Repository Staff Only: item control page