Probabilistic Graphical Models(CMU)-5

Probabilistic_Graphical_Models CMU notes

The class link: Probabilistic Graphical Models(Spring 2014) - Eric Xing

Lecture notes 5

Algebraic elimination $\equiv$ graphical elimination

Recap

Defn: A DAG G is a perfect map (P-map) for a distribution $P$ if
$I(P) = I(G)$.

Tree GMs

• Complexity

  • The overall complexity is determined by the number of the
    largest elimination clique
  • “good” elimination orderings lead to small cliques and hence reduce complexity
  • Find the best elimination ordering of a graph --- NP-hard
    i.e., Inference is NP-hard
  • But there often exist "obvious" optimal or near-opt elimination ordering

Elimination $\equiv$ message passing on a clique tree

Correctness of BP no tree

different ways of passing information we will get different equations. That's weird!!! which means the Belief Propagation algorithm is not going to solve the problems (since it may get multiple different results but except for tree structure, you will see it later).

Notice:

• $P(x_1)$ proportional to all the potentials and messages relevant to $x_1$

• The same query gets two different answers because of different ways of passing massages.

• Tree structure is good since in the tree-structure you got only one way to pass the massages.

Belife Propogation is only guaranteedly valid on tree, and if it is non-tree it is going to generate inconsistency

Thus, an idea to turn non-tree to tree is obvious......

Factor Graph

Message Passing on a Factor Tree

• factor tree is boarder than tree graphic model.

Summary

• Sum-Product algorithm computes singleton marginal
  probabilities on:
  
  • Trees
  • Tree-like graphs
  • Poly-trees
• Maximum a posteriori configurations can be computed by
  replacing sum with max in the sum-product algorithm

Junction tree

Local Consistency

Summary

--