"Wir müssen wissen — wir werden wissen" — David Hilbert

MCMC:Gibbs Sampling

In the Important Sampling, all the samples are independent. But in MCMC, samples are dependent.

Intro:
Randomly generate a sample D1 as the initial sample, with the same Evidence = e. Then in the following steps, a new sample comes out with the current sample.

If current step is i-1, we are intend to go from D i-1 and get D i. First set D i = D i-1 , then follow an order and get samples. Change the values of variables in D 1 . Here, we set Z as the next sampling variable, Y as the set of Markov margin, y i is value of Y in D i . Which is P(Z | Y = y i ), use the prob dist to sample from Z.

GibbsSampling (N,m,E,e,Q,q,p)
Input:
N: Bayesian Network
m: number of samples
E: evidence variable
e: value of evendence
Q: query varialbe
q: value of query
p: non-evidence sampling order

Output:
The approximate conditions of P(Q=q | E = e):

Example:
Each node: t and f (true and false)

Suppose to calculate P(R=t | S=t ) , init a sample with {S=t}.
sampling….(check the last post)

The steps are in the photo:

Random walk: a Markov chain.

“Past” -> “Now” -> “Future” Future has nothing to do with Past.

When given a starting state, in the ith step, the distribution will converge to a Stationary Distribution (平稳分布), when i -> positive infinite.

The problem for Gibbs Sampling is that, the speed of covergence is slow. When an extreme condition exists in the Bayesian Network (like the prob is 0 or 1), Gibbs sampling might gave wrong results.

If all prob are positive, Gibbs Chain is regular.

Reference:
《贝叶斯网引论》(Basic Introduction of Bayesian Networks) Chapter 6.1