Generalized belief propagation for probabilistic systems

• US 6,910,000 B1
• Filed: 06/02/2000
• Issued: 06/21/2005
• Est. Priority Date: 06/02/2000
• Status: Expired due to Term

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Corporation
• Inventors: Yedidia, Jonathan S., Freeman, William T.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US09/586,282
• Time in Patent Office: 1,845 Days
• Field of Search: 703/2, 706/52, 706/45, 345/419, 708/801, 704/256, 382/203
• US Class Current: 703/2
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A method determines approximate probabilities of states of a system represented by a model. The model includes nodes connected by links. Each node represents possible states of a corresponding part of the system, and each link represents statistical dependencies between possible states of related nodes. The nodes are grouped into arbitrary sized clusters such that every node is included in at least one cluster and each link is completely contained in at least one cluster. Messages, based on the arbitrary sized cluster, are defined. Each message has associated sets of source nodes and destination nodes, and a value and a rule depending on other messages and on selected links connecting the source nodes and destination nodes. The value of each message is updated until a termination condition is reached. When the termination condition is reached, approximate probabilities of the states of the system are determined from the values of the messages.

Claims

1. A computer implemented method for determining probabilities of states of a system represented by a model including a plurality of nodes connected by links, each node representing possible states of a corresponding part of the system, and each link representing statistical dependencies between possible states of related nodes, comprising:

grouping the plurality of nodes into arbitrary-sized clusters such that every node is included in at least one cluster and each link is completely contained in at least one cluster;

identifying nodes in intersections of clusters, and intersections of intersections of clusters as regions of nodes;

defining messages based on the regions of nodes, each message having associated sets of source nodes and destination nodes and a value and a rule depending on other messages and selected links connecting the source nodes and destination nodes;

assigning initial values to the messages;

updating the value of each message using the associated rule; and

determining approximate probabilities of the states of the system from the messages when a termination condition is reached.

2. The method of claim 1 wherein the network has pair-wise statistical dependencies between nodes, and the overall probability of a particular assignment of states s at the nodes is:

$P<br><br>\left(s_1,s_2,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_N\right)=\frac{1}{Z}<br><br>\underset{i,j}{\prod <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\varphi <br><br>}}_{\mathrm{ij}}<br><br>\left(s_i,s_j\right)<br><br>\underset{i}{\prod <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\psi <br><br>}<br><br>\left(s_i\right),$

where the first product runs over all linked neighboring nodes, i and j, and wherein a φ

compatibility matrix represents the statistical dependencies between the possible states s of the related nodes, and the ψ

function for each node represents evidence that a particular node is in a particular state, and Z is a normalization constant to insure that the sum of the probabilities of all possible states of the system is equal to one.

3. The method of claim 1 wherein the initial values of the messages are random positive numbers.

4. The method of claim 1 wherein the initial values of the messages are all ones.

5. The method of claim 1 wherein the termination condition is a convergence of the probabilities of the states of the system to a predetermined precision.

6. The method of claim 1 wherein the approximate probabilities are marginal probabilities.

7. The method of claim 1 wherein the approximate probabilities are maximum a posteriori probabilities.

8. The method of claim 1 wherein the states are discrete.

9. The method of claim 1 wherein the states are continuous.

10. The method of claim 1 wherein the network model includes closed loops.

11. The method of claim 1 wherein the nodes are arranged in a square lattice.

12. The method of claim 1 wherein the nodes are arranged in a triangular lattice.

13. The method of claim 1 wherein the nodes and links are a Markov network representation of an error-correcting code.

14. A computer implemented method for determining probabilities of states of a system represented by a model including a plurality of nodes connected by links, each node representing possible states of a corresponding part of the system, and each link representing statistical dependencies between possible states of neighboring nodes, comprising:

grouping the plurality of nodes into arbitrary-sized clusters such that every node is included in at least one cluster, and each link is completely contained in at least one cluster;

identifying nodes in intersecting clusters, and intersections of intersecting clusters as regions, and intersections of regions as sub-regions;

discarding duplicate regions and sub-regions;

arranging the regions and sub-regions in a top-to-bottom hierarchy of intersections;

defining messages between regions and direct sub-regions directly connected in the hierarchy, each message having associated sets of source nodes and destination nodes and a value and a rule depending on other messages and selected links connecting the source nodes and destination nodes, the destination nodes being those nodes in the sub-region, and the source nodes being those nodes in the region and outside the sub-region;

assigning initial values to the messages;

updating the value of each message using the associated rule until a termination condition is reached;

determining approximate probabilities of the states of the system from the messages when a termination condition is reached.