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 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)$.

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. 


Drawbacks of MCMC

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.

State University of New York at Stony Brook

Monte Carlo algorithms return results with variability. The variability can typically be reduced by allocating more resources. The benefit of Monte Carlo algorithms is that they can provide an approximated estimation with limited source while maintaining a certain degree of accuracy. In Machine Learning, many problems are too complicated to have precise answers. Monte Carlo approximations are therefore a good approach to these problems.

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

Markov Chain Monte Carlo Methods

When a sum or integral of a variable cannot be computed directly, we can use Monte Carlo sampling to approximate the expected mean and variance of the random variable. For example, if s is a random variable, then
$$s = \sum_{x}p(x)f(x) = E_p[f(x)]$$
or
$$s = \int p(x)f(x) = E_p[f(x)]$$
We can approximate s by drawing n samples, and compute its estimator:
$$\hat{s} = \frac{1}{n}\sum_{i=1}^{n}f(x^{(i)})$$
$$\mathbb{E}[\hat{s}] = \frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[f(x^{(i)})] = \frac{1}{n}\sum_{i=1}^{n}s = s$$
Similarly, we can obtain expected sampling variance. We can then compute the variance estimator:

$$\mathrm{Var}[\hat{s_n}] = \frac{1}{n^2}\sum_{i=1}^{n}\mathrm{Var}[f(x^{(i)})] = \frac{\mathrm{Var}[f(x)]}{n}$$

By Central Limit Theorem, the random variable thus follows Normal Distribution with mean s and variance $\frac{\mathrm{Var}[f(x)]}{n}$.

Learn Before

Related

Learn After