Message Passing in Markov Networks

Mental Model

Fully connected nodes in a network (cliques) have their own atomic compatibility table.

Whenever a clique gets connected to another one, the comp. table of the resulting structure can be constructed in 2 ways.

You either:

• link the 2 tables together by the node that connects both cliques (B).
  
  and whenever we want to calculate a probability across both cliques, u just multiply the correct rows in both tables.
  
• merge the 2 tables into a composite one that will include redundant calculations.
  

Given those 2 methods, which one do u think is easier in figuring out the summation of all the compatibility scores (Z) across all rows?

Using the Merged Table method

We will need to sum every single score in every single row within that incredibly long table, good luck with that.

Using the Linked Tables method

The sum of all scores (Z) is equivalent to summing all scores when B=0 + when B=1, that is,

$$Z=Z_{B=0}+Z_{B=1}$$

When B=0

A can either be 0 or 1, summing all the scores for both possibilities will give us $Z_{B=0}$, that is,

$$Z_{B=0}=Z_{B=0,A=0}+Z_{B=0,A=1}$$

The Summation when A=0:

The Summation when A=1:

Since both $Z_{B=0,A=0}$ and $Z_{B=0,A=1}$ multiply the same (D, E) rows, we can factor the summation of all the (D, E) rows out of the summation.

This is a huge shortcut, since we now know we can compute $Z_{B=0}$ by multiplying the summation of scores in the (A, B) table when B=0, with the summation of scores in the (B, D, E) table when B=0.

The notation for the (A, B) table summation is $m_{A\to B}(0)$.

The 0 stands for “when B=0”

The notation for the (B, D, E) table summation is $m_{D,E\to B}(0)$.

$$Z_{B=0}=m_{A\to B}(0)\ast m_{D,E\to B}(0)=(12)\ast (13)=156$$

When B=1

We can do the exact same shortcut when B=1.

$$Z_{B=1}=m_{A\to B}(1)\ast m_{D,E\to B}(1)=(11)\ast (13)=143$$

The Total Sum

Now that we have both $Z_{B=0}$ and $Z_{B=1}$, sum them both to get the overall $Z$.

$$Z=Z_{B=0}+Z_{B=1}=156+143=299$$

Or in the more compact form,

$$Z=\sum _{B=0,1}{Z}_B=\sum _{B=0,1}{m}_{A\to B}(B)\ast m_{D,E\to B}(B)$$

---

Connections