Probabilistic Graphical Models(CMU)-3

Probabilistic_Graphical_Models CMU notes

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

Lecture notes 3

P-maps

Defn: A DAG G is a perfect map (P-map) for a distribution P if
I(P)=I(G).
* Thm: not every distribution has a perfect map as DAG.

* The fact that G is a minimal I-map for P is far from a guarantee that G captures the independence structure in P
* The P-map of a distribution is unique up to I-equivalence between networks. That is, a distribution P can have many P-maps, but all of them are I-equivalent (different BN structures can actually encode the same set of conditional independence).

Undirected graphical models(UGM)

Canonical example

• The grid mode
  

• Global Markov Independencies
  A probability distribution satisfies the global Markov property
  if for any disjoint A, B, C, such that B separates A and
  C, A is independent of C given B:

  $$I(H) = {A \perp C|B: sep_H(A;C|B)}$$

• Local Markov independencies
  The local Markov independencies associated with H is:
  

  $$I_l(H): \{ X_i \perp V - {X_i} - MB_{X_i} | MB_{X_i}: \forall i\}$$
  In other words, $X_i$ is independent of the rest of the nodes in the graph given its immediate neighbors

• Computing partition function $Z$ is a hard problem!!!

• Thm: Let P be a positive distribution over V, and H a Markov network graph over V. If H is an I-map for P, then P is a Gibbs distribution over H.

Defn: An UG $H$ is an I-map for a distribution $P$ if $I(H)\subseteq I(P)$i.e., $P$ entails $I(H)$.

Defn: $P$ is a Gibbs distribution over $H$ if it can be represented as

• Thm (soundness): If P is a Gibbs distribution over H, then H is an I-map of P.

• Thm (completeness): If $sep_H(X; Z|Y)$ in some $P$ that factorizes over H.
  

Boltzmann machine

A fully connected graph with pairwise (edge) potentials on
binary-valued nodes (for $x_i \in \{1,-1 \}$ or $x_i \in \{ 0,1 \}$) is called a Boltzmann machine.

• nodal potential + pair potential

Conditional Random Fields

--