Inference algorithms in Graphical Model

Inference algorithms in undirected graphical model or markov random field categories:

• Propagation based
• Loopy belief propagation
• Variational method based (approximate not exact)
• Mean field
• Advantage
• Intuition is that complex graphs can be probabilistically simple; in particular, in graphs with dense connectivity there are averaging phenomena that can come into play, rendering nodes relatively insensitive to particular settings of values of their neighbors. This average phenomena leads to simple inference algorithm.
• 
  
• Monte Carlo method based
• Gibbs sampling based
• Advantage
• simple to implement
• theoretical guarantee to converge
• Disadvantage
• slow to converge
• hard to diagnose

Inference algorithms:

• Exact inference by the Junction-Tree algorithm (Lauritzen and Spiegelhalter, 1988)
• Loopy Belief Propagation (Pearl, 1988)
• Generalized Belief Propagation (Yedidia et al., 2005)
• Tree Re-weighted Belief Propagation (Wainwright et al., 2005)
• Propagation based on convexification of the Bethe free energy (Meshiet al., 2009).
• Mean field (Jordan et al., 1998)
• Gibbs sampling (Geman and Geman, 1984)