**About BN**

Belief Network, or directed acyclic graphical model (DAG).

When BN is huge:

Exact Inference(variable elimination)

Stochastic Inference(MCMC)

**Dependence**

Samples are

**dependent**, form Markov Chain.Converge to real distribution, when all p > 0.

Methods to improve convergence:

– Blocking

– Rao-Blackwellised

In each sample, variables are all

**dependent**.9 variables, binary states.

Parallel Computing the same colour ones. [1]

Sequentially:

MRF: divided into collections of variables (???)

Problem of Synchronous Gibbs:

Strong positive correlation at the start.

——Sequential Execution shows a strong positive correlation

——Parallel Execution shows a strong negative correlation

Conclusion is that:

**Adjacent variables cannot be sampled simultaneously**.DADG (Directed Acyclic Dependency Graph)

**Chromatic Sampler (色度采样)**

For models with

**weak**dependencies.k-coloring of the graphical model

9 variables (means a part form a huge image), each vertex only depends on the peers (left, right, up, down)

So two threads start simultanously: from red and blue.

sequential consistency (顺序一致性)

**Synchronous Gibbs Sampler**

Fortunately, the parallel computing community has developed methods to directly transform sequential graph algorithms into equivalent parallel graph algorithms using graph colorings. [3]

The algo provided by [1]:

So in the MRF, all of the vertexes(variables) can be divided into two groups, as marked as two colors.

From this point of view, given k colors (states), we believe that in the same group, simutaiously we can flip a coin at each vertex.

I think it is like a pre-processing, which guarentees all variables within a color are conditionally independent given the variables in the remaining colors and can therefore be sampled independently and in parallel.

**Ergodic Markov Chain[4]**

Markov Chain discretes in time and states. If we say at time u, the MC is in state i, but when it is in time t+u, the state is in j, and the transition probability and process are not depend on time u, then we say it is an ergodic MC.

p ij represents the prob of i to j, then pij = P { xn+1 = j | xn = i } , i,j=0,1,2,…

So we can have a transition matrix:

**Splash Gibbs Sampler**

An asynchronous Gibbs Sampler that adaptively addresses

**strong**dependencies.Adaptive asynchronous tree construction.

Conditaionally independent:

**Markov Blanket**.The set of all variables XNi adjacent to variable Xi is called the Markov Blanket of Xi.

When given its MB, a variable is independent with other variables.

where X-i refers to the set of all variables excluding the variable Xi.

Reference: