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 i...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73579 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1811078627731701760 |
|---|---|
| author | Liu, Ying Chandrasekaran, Venkat Anandkumar, Animashree Willsky, Alan S. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Liu, Ying Chandrasekaran, Venkat Anandkumar, Animashree Willsky, Alan S. |
| author_sort | Liu, Ying |
| collection | MIT |
| description | 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[subscript 2]n), 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. |
| first_indexed | 2024-09-23T11:03:12Z |
| format | Article |
| id | mit-1721.1/73579 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:03:12Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/735792022-09-27T16:48:13Z Feedback Message Passing for Inference in Gaussian Graphical Models Liu, Ying Chandrasekaran, Venkat Anandkumar, Animashree Willsky, Alan S. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Liu, Ying Chandrasekaran, Venkat Anandkumar, Animashree Willsky, Alan S. 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[subscript 2]n), 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. 2012-10-03T19:23:49Z 2012-10-03T19:23:49Z 2010-07 2010-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-7891-0 978-1-4244-7890-3 http://hdl.handle.net/1721.1/73579 Liu, Ying et al. “Feedback Message Passing for Inference in Gaussian Graphical Models.” IEEE International Symposium on Information Theory Proceedings (ISIT), 2010. 1683–1687. © Copyright 2010 IEEE https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/ISIT.2010.5513321 Proceedings of the IEEE International Symposium on Information Theory Proceedings (ISIT), 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Liu, Ying Chandrasekaran, Venkat Anandkumar, Animashree Willsky, Alan S. Feedback Message Passing for Inference in Gaussian Graphical Models |
| title | Feedback Message Passing for Inference in Gaussian Graphical Models |
| title_full | Feedback Message Passing for Inference in Gaussian Graphical Models |
| title_fullStr | Feedback Message Passing for Inference in Gaussian Graphical Models |
| title_full_unstemmed | Feedback Message Passing for Inference in Gaussian Graphical Models |
| title_short | Feedback Message Passing for Inference in Gaussian Graphical Models |
| title_sort | feedback message passing for inference in gaussian graphical models |
| url | http://hdl.handle.net/1721.1/73579 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT liuying feedbackmessagepassingforinferenceingaussiangraphicalmodels AT chandrasekaranvenkat feedbackmessagepassingforinferenceingaussiangraphicalmodels AT anandkumaranimashree feedbackmessagepassingforinferenceingaussiangraphicalmodels AT willskyalans feedbackmessagepassingforinferenceingaussiangraphicalmodels |