What does it mean to sample from an RBM? In restricted Boltzmann machines we ofter say that given $v$ we sample $h$, and also that given $h$ we sample $v$.
Can someone explain the physical meaning of this, considering a MNIST image as example? 
 A: RBMs are energy-based models. Quoting from LuCun et al. notes (pdf):

Energy-Based Models (EBMs) capture dependencies by associating a
  scalar energy (a measure of compatibility) to each configuration of
  the variables. Inference, i.e., making a prediction or decision,
  consists in setting the value of observed variables and finding values
  of the remaining variables that minimize the energy. Learning consists
  in finding an energy function that associates low energies to correct
  values of the remaining variables, and higher energies to incorrect
  values.

In practice, for an RBM, this means that the state of the network, completely characterised by the weights and biases, defines an energy function of the form
$$E(\boldsymbol v, \boldsymbol h) = -\boldsymbol a^T\boldsymbol v - \boldsymbol b^T\boldsymbol h - \boldsymbol v^T  W\,\boldsymbol h.$$
This energy function then defines a probability distribution over hidden and visible neurons of the network as
$$ P(\boldsymbol v, \boldsymbol h) = \frac{\exp(-E(\boldsymbol v, \boldsymbol h))}{Z},
\quad Z \equiv \sum_{\boldsymbol v, \boldsymbol h} \exp(-E(\boldsymbol v, \boldsymbol h)).
$$
Notice that the above actually defines a probabily distribution, as $\sum_{\boldsymbol v, \boldsymbol h} P(\boldsymbol v, \boldsymbol h) = 1$.
To sample from the network (without fixing a state for hidden or visible neurons) means to sample from the above probability distribution, that is, to draw states of the network's neurons according to $P(\boldsymbol v, \boldsymbol h)$.
To sample $\boldsymbol h$ given $\boldsymbol v$ means to sample from the conditional probability distribution $P(\boldsymbol h|\boldsymbol v)$. "Physically" this means that you are asking what are the probabilities of getting a specific set of values for the hidden neurons, having fixed the values $\boldsymbol v$ for the visible neurons, and sampling from this probability distribution.
This conditional probability distribution is computed as
$$ P(\boldsymbol h|\boldsymbol v) = \frac{\exp(-E(\boldsymbol v, \boldsymbol h))}{\sum_{\boldsymbol{\tilde h}}\exp(-E(\boldsymbol v, \boldsymbol{\tilde h}))}.$$
Sampling $\boldsymbol v$ given $\boldsymbol h$ has similar meaning.
As also explained in this related answer, this conditional sampling can be used to obtain the way an input is represented by the network. For example, after having trained the RBM, feeding a MNIST image in the visible layer, and sampling from the hidden layer conditionally to this input, gives the internal representation that the network has built of the image, which can then later be used for classification or whatever other purpose.
A: Sampling simply means to draw a sample from a probability distribution. For example, you can draw a sample from a Gaussian distribution. When you draw one sample, it tells you nothing about the distribution. But after you draw lots of samples, their values should follow the distribution.
RBM is a stochastic neural network, meaning that the values of every neuron follow certain probability distributions. When you have the p(v, h), theoretically you can draw samples of pair value (v, h) from the distribution. But it does not make much sense to do that, because that is almost useless.
On the other hand, it is useful to know the distribution of p(h|v) and p(v|h), because then you can sample h given v. It means, when you have an observed value v, you can compute the probability distribution of the hidden value h, i.e., p(h|v). Once you have the distribution, you can sample the value of h, and vice verse.
This is important, because then you can use value h to represent v (together with the weights and biases). That means, you can reconstruct v from h, and you can use h for any learning or computations in place of v. It also means you can pretrain a layer of network with RBM unsupervisedly, while still extracting the useful features.
