Probabilistic Graphical Models(CMU)-4

Probabilistic_Graphical_Models CMU notes

---

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

Lecture notes 4

Notice: we both need Markov Random Field and Bayesian Network to represent different subset of distribution.

Partially Directed Acyclic Graphs

 NAlso called chain graphs
 Nodes can be disjointly partitioned into several chain components
 An edge within the same chain component must be undirected
 An edge between two nodes in different chain components must be
directed

Typical tasks:

• Task 1: How do we answer queries about $P_M$, e.g., $P_M(X|Y)$?
  
  • We use inference as a name for the process of computing answers to such queries
• Task 2: How do we estimate a plausible model $M$ from data $D$?
  i. We use learning as a name for the process of obtaining point estimate of M.
  ii. But for Bayesian, they seek $p(M |D)$, which is actually an inference problem.
  iii. When not all variables are observable, even computing point estimate of $M$ need to do inference to impute the missing data.

Approaches to inference

• The elimination algorithm
• Message-passing algorithm (sum-product, belief propagation)
• The junction tree algorithms

Approximate inference techniques

• Stochastic simulation / sampling methods
• Markov chain Monte Carlo methods
• Variational algorithms

The basic algorithm for inference is elimination algorithm.

Complexity:

• Each step costs $O(|Val(X_i)|*|Val(X_{i+1})|)$ operations: $O(kn^2)$
• Compare to naive evaluation that sums over joint values of n-1 variables $O(n^k)$

And we also want to whether this idea can extend to some other cases ......

First, Hidden Markov Model

$=\sum_y_2 \sum_y_3...\sum_y_Tp(y_2)p(x_2|y_2)...p(x_T|y_T)\sum_y_1p(y_1)p(x_1|y_1)p(y_2|y_1)$

where $\sum_y_1p(y_1)p(x_1|y_1)p(y_2|y_1) = M(y_2) = p(x_1,y_2)$

Likewise, we further eliminate $y_2$ by $\sum_y_2 M(y_2)p(x_2|y_2)p(y_3|y_2) = M(y_3) = p(x_1,x_2,y_3)$

And amazingly this is the raw idea of most famous algorithm: forward-backward algorithm(derived from the elimination algorithm!!!).

This is the backward information...

And this elimination algorithm also can apply to resolve
Conditional Random Fields:

Summation

In general, we can view the task at hand as that of computing
the value of an expression of the form:

$$\sum_t \prod_{\phi \in f}\phi$$
where $F$ is a set of factors
We call this task the sum-product inference task.

General idea:
Write query in the form

this suggests an "elimination order" of latent variables to be
marginalized

$$P(X_1,e) = \sum_{x_n}...\sum_{x_3}\sum_{x_2}\prod_ip(x_1|pa_i)$$
this suggests an "elimination order" of latent variables to be
marginalized

Iteratively

• Move all irrelevant terms outside of innermost sum
• Perform innermost sum, getting a new term
• Insert the new term into the product

The elimination algorithm

An example:

Understanding Variable Elimination

Elimination Cliques

Graph elimination and marginalization

A Clique tree

Complexity

--