The core idea of a Markov chain is to have a state $x$ that begins as an arbitrary value. Over time, we randomly update $x$ repeatedly. Eventually $x$ becomes a fair sample from $p(x)$. Formally, a Markov chain is deﬁned by a random state $x$ and a transition distribution $T(x^{’}| x)$ specifying the probability that a random update will go to state $x^’$ if it starts in state x. Running the Markov chain means repeatedly updating the state x to a value $x^’$  sampled from $T(x^{’}| x)$.

State University of New York at Stony Brook

Markov Chain is a useful tool to approximately sample from $P_{model} (X)$, when $P_{model} (X)$ is represented by an undirected model that there is no tractable method to draw exact samples. The most standard, generic guarantees for Markov chain Monte Carlo methods (MCMC) techniques are the model does not assign zero probability to any state. Therefore, it is most convenient to present these techniques as sampling from an energy-based model (EBM) because every state is guaranteed to have nonzero probability in EBM.

Markov Chain Monte Carlo Methods

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

In EBM, if there are just two variables, deﬁning a distribution $p(a, b)$. In order to sample $a$, we must draw a from $p(a | b)$, and in order to sample $b$, we must draw it from $p(b | a)$. It seems to be an intractable chicken-and-egg problem. We can use Markov chain to avoid this situation. 

Reason of using MCMC

- In statistics, Gibbs sampling or a Gibbs sampler is a Markov chain Monte Carlo (MCMC) algorithm for obtaining a sequence of observations which are approximated from a specified multivariate probability distribution, when direct sampling is difficult. 
- This sequence can be used to approximate the joint distribution (e.g., to generate a histogram of the distribution); to approximate the marginal distribution of one of the variables, or some subset of the variables.
-  Gibbs Sampling is applicable when the joint distribution is not known explicitly or is difficult to sample from directly, but the conditional distribution of each variable is known and is easier to sample from.
- A blocked Gibbs sampler groups two or more variables together and samples from their joint distribution conditioned on all other variables, rather than sampling from each one individually. 

Gibbs sampling in RBM

Annealed Importance Sampling (AIS) is a strategy of importance sampling, applied to an extended state with a sequence of intermediate distributions ($ p_0 $ to $ p_1 $). AIS is the most common way of estimating partition function for undirected probabilistic models, such as a trained model of Restricted Boltzmann Machine.

Annealed Importance Sampling

The Core Idea of MCMC

There are some drawbacks of using Markov chain Monte Carlo methods. It is expensive to use because it required more time, and it is hard to evaluate the length of running time because we do not know in advance how many steps the Markov chain must run before reaching its equilibrium distribution. 


Learn Before

Related