Belief Propagation and Revision in Networks with Loops
Local belief propagation rules of the sort proposed by Pearl(1988) are guaranteed to converge to the optimal beliefs for singly connected networks. Recently, a number of researchers have empirically demonstrated good performance of these same algorithms on networks with loops, but a theoretical unde...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/7249 |
| _version_ | 1811094277944508416 |
|---|---|
| author | Weiss, Yair |
| author_facet | Weiss, Yair |
| author_sort | Weiss, Yair |
| collection | MIT |
| description | Local belief propagation rules of the sort proposed by Pearl(1988) are guaranteed to converge to the optimal beliefs for singly connected networks. Recently, a number of researchers have empirically demonstrated good performance of these same algorithms on networks with loops, but a theoretical understanding of this performance has yet to be achieved. Here we lay the foundation for an understanding of belief propagation in networks with loops. For networks with a single loop, we derive ananalytical relationship between the steady state beliefs in the loopy network and the true posterior probability. Using this relationship we show a category of networks for which the MAP estimate obtained by belief update and by belief revision can be proven to be optimal (although the beliefs will be incorrect). We show how nodes can use local information in the messages they receive in order to correct the steady state beliefs. Furthermore we prove that for all networks with a single loop, the MAP estimate obtained by belief revisionat convergence is guaranteed to give the globally optimal sequence of states. The result is independent of the length of the cycle and the size of the statespace. For networks with multiple loops, we introduce the concept of a "balanced network" and show simulati. |
| first_indexed | 2024-09-23T15:57:29Z |
| id | mit-1721.1/7249 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:57:29Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/72492019-04-12T08:34:34Z Belief Propagation and Revision in Networks with Loops Weiss, Yair Local belief propagation rules of the sort proposed by Pearl(1988) are guaranteed to converge to the optimal beliefs for singly connected networks. Recently, a number of researchers have empirically demonstrated good performance of these same algorithms on networks with loops, but a theoretical understanding of this performance has yet to be achieved. Here we lay the foundation for an understanding of belief propagation in networks with loops. For networks with a single loop, we derive ananalytical relationship between the steady state beliefs in the loopy network and the true posterior probability. Using this relationship we show a category of networks for which the MAP estimate obtained by belief update and by belief revision can be proven to be optimal (although the beliefs will be incorrect). We show how nodes can use local information in the messages they receive in order to correct the steady state beliefs. Furthermore we prove that for all networks with a single loop, the MAP estimate obtained by belief revisionat convergence is guaranteed to give the globally optimal sequence of states. The result is independent of the length of the cycle and the size of the statespace. For networks with multiple loops, we introduce the concept of a "balanced network" and show simulati. 2004-10-20T21:04:11Z 2004-10-20T21:04:11Z 1997-11-01 AIM-1616 CBCL-155 http://hdl.handle.net/1721.1/7249 en_US AIM-1616 CBCL-155 881373 bytes 972380 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Weiss, Yair Belief Propagation and Revision in Networks with Loops |
| title | Belief Propagation and Revision in Networks with Loops |
| title_full | Belief Propagation and Revision in Networks with Loops |
| title_fullStr | Belief Propagation and Revision in Networks with Loops |
| title_full_unstemmed | Belief Propagation and Revision in Networks with Loops |
| title_short | Belief Propagation and Revision in Networks with Loops |
| title_sort | belief propagation and revision in networks with loops |
| url | http://hdl.handle.net/1721.1/7249 |
| work_keys_str_mv | AT weissyair beliefpropagationandrevisioninnetworkswithloops |