Belief Propogation

Jake

06/12/2022

  • Generalised belief propogation algorithms can provide approximations for inference

Belief Propogation

  • Belief propogation is a message passing algorithm

Exact Polytree Algorithm

  • Create a jointree with the same structure as the polytree
    • A node \(i\) in the jointree has cluster \(C_i=XU\)
    • Edge \(U\rightarrow X\) in the jointree has separator \(S_{ij}=U\)
  • Each jointree message is over a single variable
  • Jointree width equals polytree width

  • Exact Belief Propogation is the jointree algorithm with different notation:

  • Message notation:
    • Note that \(\nu\) is a normalising constant
    • \(\lambda_e\) is evidence factor

Connected Networks

  • Belief propogation is not exact when the underlying network is connected
    • Can still provide high-quality approximations in many cases
  • Messages get stuck as they are dependent on eachother in the loop
    • Need to set initial values so that messages can be propogated, then we alter the messages iteratively.

Iterative Belief Propagation

  • Assumes inital value to each message in the network
    • Given these inital values, each node is ready to send a message to each of its neighbors
    • At each iteration every node sends a message to its neighbours using the messages recieved from its other neighbours in the previous iteration
    • Algorithm iterates until convergence
      • Messages at convergence are called fixed point
      • May be multiple fixed points on a given network
  • For some networks, IBP can oscillate and never converge
    • Convergence rate can dependend on order the messages are propagated, the message schedule
      • Parallel - the order of messages does not affect algo
      • Sequential - messages are propogated as soon as they are computed
      • All schedules have the same fixed points
  • Parallel Iterative Belief

Kullback-Leibler Divergence

  • Distance between the approximate and true distribution

  • Approximate inference can be posed as an optimization problem where we want to minimise KL divergence

  • Iterative Belief Algorithm assumes that approximate distribution \(P'(X)\) factors as:

    • Expressive enough to describe polytree distributions
    • If network is not a polytree, we are trying to fit a more complicated network into the polytree factorisation as a form of approximation

  • This polytree representation however may not be expressive enough to get a good approximation and find the local KL divergence minima.
    • Can increase representation power by assuming different networks, known as joingraphs.
    • The most expressive, and ‘exact’ network is the jointree

Generalised Belief Propogation

  • Joingraph factorisations fall between the efficient but rough polytree and expensive but exact jointree.
  • Joingraphs obtain factorizations according to:

\[ P'(X|e)=\frac{\prod_C P'(C|e)}{\prod_S P'(S|e)}\]

  • Iterative joingraph propogation is used to approximate the distribution according to the joingraph factorization
  • Parallel iterative algorithm:

Message Schedule

  • Convergence is often improved by using asynchronous approaches
    • Implementing message scheduling
  • Two common asychronous message scheduling approaches:
    • Tree reparameterization
    • Residual belief propogation
  • Smoothing Messages

\[ M_{ij} = \lambda\left(\nu\sum_{C_i\backslash S_{ij}}\psi_i\prod_{k\neq j}M_{ki}\right) + (1-\lambda)M_{ij}^{t-1}\]