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 defined by a random state $$x$$ and a transition distribution $$T(x' \mid 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' \mid x)$$.

State University of New York at Stony Brook

Google

Markov chain Monte Carlo (MCMC) methods are useful tools to approximately sample from $$P_{model}(X)$$ when $$P_{model}(X)$$ is represented by an undirected model for which there is no tractable method to draw exact samples. The most standard, generic guarantees for MCMC techniques require that 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), as every state is guaranteed to have a nonzero probability in an 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

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. 


Drawbacks of MCMC

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 the partition function for undirected probabilistic models, such as a trained Restricted Boltzmann Machine.

Learn Before

Related