<commit_before>.. _RBM:

Restricted Boltzmann Machines (RBM)
===================================

Boltzmann Machines (BM)
+++++++++++++++++++++++

Boltzmann Machines (BM) are probabilistic generative models which learn to
model a distribution :math:`p_T(x)`, by attempting to capture the underlying
structure in the input. BMs contain a network of binary probabilistic units,
which interact through weighted undirected connections. The probability of a
unit :math:`s_i` being "on" given its connected neighbours, is stochastically
determined by the state of these neighbours, the strength of the weighted
connections and the internal offset :math:`b_i`. The model parameters are thus
:math:`\theta=\{W,b\}`. Positive weights :math:`W_{ij}` indicate a tendency for
units :math:`s_i` and :math:`s_j` to be "on" together, while :math:`W_{ij} <
0` indicates some form of inhibition. The entire network defines an energy
function, defined as:

.. math::
    E(s) = - \sum_i \sum_{j > i} W_{ij}s_is_j - \sum_i b_i x_i.

The stochastic update equation is then given by:

.. math::
    p(s_i = 1 | \{s_j: \forall j \neq i \}) = sigm(\sum_j W_{ij} s_j + b_i),
a stochastic version of the neuronal activation function found in Artificial
Neural Networks (ANNs). 

Under these conditions and at a stochastic equilibrium, it can also be shown
that the probability of a given global configuration is given as

.. math::
    p(s) = \frac{1}{Z} e^{-E(s)},
where :math:`Z` is the partition function defined as :math:`Z = \sum_s E(s)`.
Notice how high probability configurations correspond to low-energy states.

Splitting the units into *visible* and *hidden* units leads to a more powerful
model (shown below).

.. image:: images/bm.png
    :align: center

During training, visible units are driven by training samples :math:`x^{(i)}`
and the hidden units are left free to converge to the equilibrium
distribution. The goal of learning is then to modify the network parameters
:math:`\theta` in such a way that :math:`p(v) = \sum_h p(v,h)` is
approximately the same during training (with visible units clamped) and when
the entire network is free-running. This amounts to maximizing the empirical
log-likelihood

.. math::
    \mathcal{L}(\theta, \mathcal{D}) = \frac{1}{N} \sum_{x^{(i)} \in \mathcal{D}} log\ p(v=x^{(i)}).

From this likelihood, we can derive a stochastic gradient over the parameters
:math:`\theta` for training example :math:`x^{(i)}`:

.. math::
   :label: bm_grad

    \left. \frac {\partial{log p(v)}} {\partial\theta} \right|_{v=x^{(i)}} =
    -\sum_h p(h|v=x^{(i)}) \frac {\partial{E(x^{(i)},h)}} {\partial\theta}
    +\sum_{v,h} p(v,h)
      \frac {\partial{E(v,h)}} {\partial\theta}

The above gradient is the sum of two terms, corresponding to the so-called
**positive** and **negative phases**. The first term is an average
over :math:`p(h|v=x^{(i)})` (i.e. probability over the hidden units given that the
visible units are clamped to training data). It will act to decrease the
energy of the training examples, referred to as *positive examples*.
The second term, an average over :math:`p(v,h)`, is of opposite sign and will thus act
to increase the energy of configurations sampled from the model.
These configurations are referred to as *negative examples*, as they
are training examples which the network needs to *unlearn*. Together,
this *push-pull* mechanism attempts to mold an energy landscape where
configurations with visible units corresponding to training examples have
low-energy and all other configurations have high-energy.


Restricted Boltzmann Machines (RBM)
+++++++++++++++++++++++++++++++++++

Restricted Boltzmann Machines are variants of BMs, where visible-visible
and hidden-hidden connections are prohibited. The energy function :math:`E(v,h)` is
thus defined as,

.. math::
    E(v,h) = - b'v - c'h - h'Wv 

where :math:`W` represents the weights connecting hidden and visible units and
:math:`b`, :math:`c` are the offsets of the visible and hidden layers
respectively.

The biggest advantage of such an architecture is that the hidden units become
conditionally independent, given the visible layer (and vice-versa). This is
self-evident from looking at the graphical model shown below.

.. image:: images/rbm.png
    :align: center

This property allows us to write:

.. math::
    p(h|v) &= \prod_i p(h_i|v) \\
    p(v|h) &= \prod_j p(v_j|h).

This greatly simplifies the learning rule of Eq. :eq:`bm_grad`.
As an example, we derive the gradient on :math:`W_{ij}`. For derivations of
the other gradients, we refer the reader to [Bengio09]_.

.. math::
    \left. \frac {\partial{log p(v)}} {\partial W_{ij}} \right|_{v=x^{(i)}} = 
    - x^{(i)}_j \cdot sigm(W_i \cdot x^{(i)} + c_i) + E_v[p(h_i|v) \cdot v_j]

In RBMs, the positive phase gradient is thus straightforward to compute.
Computing the negative phase gradient is still problematic however, since
it requires samples from :math:`p(v)` to compute the expectation. Samples of
:math:`p(v)` can be obtained by running a Markov chain to convergence, using
Gibbs sampling as the transition operator.

.. image:: images/markov_chain.png
    :align: center

In the figure above, the superscript refers to the sample index within the
Markov chain. Visible and hidden samples are obtained as follows:

.. math::
    h^{(n+1)} &\sim sigm(W'v^{(n)} + c) \\
    v^{(n+1)} &\sim sigm(W h^{(n+1)} + b).

Samples :math:`(v^{(t)}, h^{(t)})` are guaranteed to be accurate samples of
:math:`p(v,h)` as :math:`t \rightarrow \infty`. Since each parameter update
would require running this chain to convergence, learning algorithms for RBMs
tend to use different tricks to efficiently sample from :math:`p(v,h)`.

Contrastive Divergence
----------------------

Contrastive Divergence uses two tricks to speed up the sampling process:

* since we eventually want :math:`p(v) \approx p_T(v)` (the true, underlying
  distribution of the data), initialize the Markov chain with a training
  example. This should help speed up convergence of the chain.
  
* do not wait for the chain to converge: samples are obtained after k-steps of
  Gibbs sampling. In pratice, :math:`k=1` has been shown to work surprisingly
  well.

Persistent CD
-------------

Persistent CD [Tieleman08]_ uses another approximation for sampling from
:math:`p(v,h)`.  It relies on a single Markov chain, which has a persistent
state. For each parameter update, we extract new samples by simply running the
chain for k-steps. The state of the chain is then preserved for subsequent updates.

The general intuition is that if parameter updates are small enough compared
to the mixing rate of the chain, the Markov chain should be able to "catch up"
to changes in the model.


References
++++++++++

.. [Bengio09] <NAME>, `Learning deep architectures for AI <http://www.iro.umontreal.ca/~lisa/publications2/index.php/publications/show/239>`_, Foundations and Trends in Machine Learning 1(2) pages 1-127.

.. [Tieleman08] <NAME>, `Training restricted boltzmann machines using approximations to the likelihood gradient`, ICML 2008.
<commit_msg>removed section on Boltzmann Machines, instead added more general section on Energy-Based Machine (mostly taken from "Learning Deep Architectures in AI")<commit_after>.. _RBM:

Restricted Boltzmann Machines (RBM)
===================================

Energy-Based Models (EBM)
+++++++++++++++++++++++++

**Energy-based** models associate a scalar energy to each configuration of the
variables of interest. Learning corresponds to modifying that energy function
so that its shape has desirable properties. For example, we would like
plausible or desirable configurations to have low energy.  Energy-based
probabilistic models define a probability distribution through an energy
function, as follows:

.. math::
  :label: energy1

  p(x) = \frac {e^{-E(x)}} {Z}.

The normalizing factor :math:`Z` is called the **partition function** by analogy
with physical systems.

.. math::
    Z = \sum_x e^{-E(x)}

An energy-based model can be learnt by performing (stochastic) gradient
descent on the empirical log-likelihood of the training data:

.. math::
    \mathcal{L}(\theta, \mathcal{D}) = \frac{1}{N} \sum_{x^{(i)} \in
    \mathcal{D}} log\ p(x^{(i)}).

using the stochastic gradient :math:`\frac{\partial p(x^{(i)})}{\partial
\theta}`, where :math:`\theta` are the parameters of the model.


**EBMs with Hidden Units**

In many cases of interest, we do not observe the example :math:`x` fully, or we
want to introduce some non-observed variables to increase the expressive power
of the model. So we consider an observed part (still denoted :math:`x` here) and a
**hidden** part :math:`h`. We can then write:

.. math::
  :label: energy2

   P(x) = \sum_h P(x,h) = \sum_h \frac{e^{-E(x,h)}}{Z}.

In such cases, to map this formulation to one similar to Eq. :eq:`energy1`, we
introduce the notation (inspired from physics) of **free energy**, defined as
follows:

.. math::
    &P(x) = \frac{e^{-\mathcal{F}(x)}}{Z}, \\
    &\text{with } \mathcal{F}(x) = - \log \sum_h e^{-E(x,h)}
    \text{ and } Z=\sum_x e^{-\mathcal{F}(x)}.

The data log-likelihood gradient then has a particularly interesting form.

.. math::
  \frac{\partial log p(x)}{\partial \theta}
   &= - \frac{\partial \mathcal{F}(x)}{\partial \theta} + 
         \sum_{\tilde{x}} p(\tilde{x}) \
             \frac{\partial \mathcal{F}(\tilde{x})}{\partial \theta}.

Notice that the above gradient contains two terms, which are referred to as
the **positive** and **negative phase**. The terms positive and negative do
not refer to the sign of each term in the equation, but rather reflect their
effect on the energy landscape. The first term increases the probability of
training data (by reducing the corresponding free energy), while the second
term decreases the probability of samples generated by the model.

It is usually difficult to determine this gradient analytically, as it
requires us to draw samples :math:`\tilde{x}` of the model. While tons of
sampling algorithms exist in the litterature, we will see how Markov Chain
Monte Carlo methods are especially well suited for models such as the
Restricted Boltzmann Machines (RBM), a specific type of EBM.


Restricted Boltzmann Machines (RBM)
+++++++++++++++++++++++++++++++++++

Boltzmann Machines (BMs) are a particular form of energy-based model which
contain hidden variables. Restricted Boltzmann Machines further restrict BMs
to those without visible-visible and hidden-hidden connections.

The energy function :math:`E(v,h)` of an RBM is defined as:

.. math::
    :label: rbm_energy

    E(v,h) = - b'v - c'h - h'Wv 

where :math:`W` represents the weights connecting hidden and visible units and
:math:`b`, :math:`c` are the offsets of the visible and hidden layers
respectively. A graphical depiction of an RBM is shown below.

.. image:: images/rbm.png
    :align: center

Because of the specific structure of RBMs, visible and hidden units are
conditionally independent given one-another. Using this property, along with
Eqs. :eq:`energy2` and :eq:`rbm_energy`, allows us to write:

.. math::
    p(h|v) &= \prod_i p(h_i|v) = \prod_i sigm(Wv + c) \\
    p(v|h) &= \prod_j p(v_j|h) = \prod_j sigm(W'h + b).


Sampling Negative Particles
+++++++++++++++++++++++++++

Samples of :math:`p(v)` can be obtained by running a Markov chain to
convergence, using Gibbs sampling as the transition operator.

Gibbs sampling of the joint of N random variables :math:`S=(S_1, ... , S_N)`
is done through a sequence of N sampling sub-steps of the form 
:math:`S_i \sim p(S_i | S_{-i})` where :math:`S_{-i}` contains the :math:`N-1`
other random variables in :math:`S` excluding :math:`S_i`.

For RBMs, the :math:`N` random variables consist of the set of visible and
hidden units. However, since they are conditionally independent, one can
perform block Gibbs sampling. In this setting, visible units can be sampled
simultaneously given fixed values for the hidden units, and vice-versa. A
step in the Markov chain is thus taken as follows: 

.. math::
    h^{(n+1)} &\sim sigm(W'v^{(n)} + c) \\
    v^{(n+1)} &\sim sigm(W h^{(n+1)} + b).

This can be illustrated graphically:

.. image:: images/markov_chain.png
    :align: center

In the figure above, the superscript refers to the index of the sample within
the Markov chain. As :math:`t \rightarrow \infty`, samples :math:`(v^{(t)},
h^{(t)})` are guaranteed to be accurate samples of :math:`p(v,h)`.

In theory, each parameter update in the learning process would require running
one such chain to convergence. It is needless to say that doing so would be
prohibitively expensive. As such, several algorithms have been devised for
RBMs, in order to efficient sample from :math:`p(v,h)` during the learning
process.


Contrastive Divergence
----------------------

Contrastive Divergence uses two tricks to speed up the sampling process:

* since we eventually want :math:`p(v) \approx p_T(v)` (the true, underlying
  distribution of the data), we initialize the Markov chain with a training
  example. This should help speed up convergence of the chain.
  
* CD does not wait for the chain to converge. Samples are obtained after only
  k-steps of Gibbs sampling. In pratice, :math:`k=1` has been shown to work
  surprisingly well.


Persistent CD
-------------

Persistent CD [Tieleman08]_ uses another approximation for sampling from
:math:`p(v,h)`.  It relies on a single Markov chain, which has a persistent
state. For each parameter update, we extract new samples by simply running the
chain for k-steps. The state of the chain is then preserved for subsequent updates.

The general intuition is that if parameter updates are small enough compared
to the mixing rate of the chain, the Markov chain should be able to "catch up"
to changes in the model.



References
++++++++++

.. [Bengio09] <NAME>, `Learning deep architectures for AI <http://www.iro.umontreal.ca/~lisa/publications2/index.php/publications/show/239>`_, Foundations and Trends in Machine Learning 1(2) pages 1-127.

.. [Tieleman08] <NAME>, `Training restricted boltzmann machines using approximations to the likelihood gradient`, ICML 2008.

{'fraction_non_alphanumeric': 0.1255731922398589, 'fraction_numerical': 0.004303350970017637, 'mean_word_length': 4.242603550295858, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '166461', 'n_tokens_mistral': 4274, 'n_tokens_neox': 4027, 'n_words': 1862}