Recursive FMP for distributed inference in Gaussian graphical models
For inference in Gaussian graphical models with cycles, loopy belief propagation (LBP) performs well for some graphs, but often diverges or has slow convergence. When LBP does converge, the variance estimates are incorrect in general. The feedback message passing (FMP) algorithm has been proposed to...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91025 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1811094141522673664 |
|---|---|
| author | Liu, Ying 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 Willsky, Alan S. |
| author_sort | Liu, Ying |
| collection | MIT |
| description | For inference in Gaussian graphical models with cycles, loopy belief propagation (LBP) performs well for some graphs, but often diverges or has slow convergence. When LBP does converge, the variance estimates are incorrect in general. The feedback message passing (FMP) algorithm has been proposed to enhance the convergence and accuracy of inference. In FMP, standard LBP is run twice on the subgraph excluding the pseudo-FVS (a set of nodes that breaks most crucial cycles) while nodes in the pseudo-FVS use a different protocol. In this paper, we propose recursive FMP, a purely distributed extension of FMP, where all nodes use the same message-passing protocol. An inference problem on the entire graph is recursively reduced to those on smaller subgraphs in a distributed manner. One advantage of this recursive approach compared with FMP is that there is only one active feedback node at a time, so centralized communication among feedback nodes can be turned into message broadcasting from the single feedback node. We characterize this algorithm using walk-sum analysis and provide theoretical results for convergence and accuracy. We also demonstrate the performance using both simulated models on grids and large-scale sea surface height anomaly data. |
| first_indexed | 2024-09-23T15:55:38Z |
| format | Article |
| id | mit-1721.1/91025 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:55:38Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/910252022-09-29T17:06:07Z Recursive FMP for distributed inference in Gaussian graphical models Liu, Ying 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 Willsky, Alan S. For inference in Gaussian graphical models with cycles, loopy belief propagation (LBP) performs well for some graphs, but often diverges or has slow convergence. When LBP does converge, the variance estimates are incorrect in general. The feedback message passing (FMP) algorithm has been proposed to enhance the convergence and accuracy of inference. In FMP, standard LBP is run twice on the subgraph excluding the pseudo-FVS (a set of nodes that breaks most crucial cycles) while nodes in the pseudo-FVS use a different protocol. In this paper, we propose recursive FMP, a purely distributed extension of FMP, where all nodes use the same message-passing protocol. An inference problem on the entire graph is recursively reduced to those on smaller subgraphs in a distributed manner. One advantage of this recursive approach compared with FMP is that there is only one active feedback node at a time, so centralized communication among feedback nodes can be turned into message broadcasting from the single feedback node. We characterize this algorithm using walk-sum analysis and provide theoretical results for convergence and accuracy. We also demonstrate the performance using both simulated models on grids and large-scale sea surface height anomaly data. United States. Air Force Office of Scientific Research (Grant FA9550-12-1-0287) 2014-10-21T15:24:40Z 2014-10-21T15:24:40Z 2013-07 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-0446-4 2157-8095 http://hdl.handle.net/1721.1/91025 Liu, Ying, and Alan S. Willsky. “Recursive FMP for Distributed Inference in Gaussian Graphical Models.” 2013 IEEE International Symposium on Information Theory (July 2013). https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/ISIT.2013.6620673 Proceedings of the 2013 IEEE International Symposium on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Liu, Ying Willsky, Alan S. Recursive FMP for distributed inference in Gaussian graphical models |
| title | Recursive FMP for distributed inference in Gaussian graphical models |
| title_full | Recursive FMP for distributed inference in Gaussian graphical models |
| title_fullStr | Recursive FMP for distributed inference in Gaussian graphical models |
| title_full_unstemmed | Recursive FMP for distributed inference in Gaussian graphical models |
| title_short | Recursive FMP for distributed inference in Gaussian graphical models |
| title_sort | recursive fmp for distributed inference in gaussian graphical models |
| url | http://hdl.handle.net/1721.1/91025 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT liuying recursivefmpfordistributedinferenceingaussiangraphicalmodels AT willskyalans recursivefmpfordistributedinferenceingaussiangraphicalmodels |