0
$\begingroup$

Let $v \in \{0,1\}^M$ be the visible layer, $h \in \{0,1\}^N$ be the hidden layer, where $M$ and $N$ are natural numbers. Given the biases $b \in \Re^M$, $c \in \Re^N$ and weights $W \in \Re^{M \times N}$, the energy and probability of an RBM is given by:

$$\text{Energy} \quad E(v,h; b,c,W) = -b^T v - c^T h - h^T W^T v$$

$$\text{Probability} \quad p(v, h; b, c, W) = \frac{e^{-E(v,h; b,c,W)}}{Z}$$

where $Z = \sum_{v,h} e^{-E(v,h; b,c,W)}$

The negative log likelihood error for a Restricted Boltzmann Machine (RBM) is given by:

$$\mathcal{L}(b,c,W) = \frac{1}{T} \sum_{t=1}^{T} \left( -\log \sum_{h} e^{-E(v^t, h; b,c,W)} \right) + \log Z$$

where:

$T$ is size of training dataset; and

$v^t$ represents $t^{th}$ data point in the training dataset

It is clear that computing $Z$ (and hence $\log Z$) is intractable because we have to sum over $2^{M+N}$ configurations of $v$ and $h$ - exponential time algorithm.

However, shouldn't computing $\sum_{h} e^{-E(v^t, h; b,c,W)}$ be intractable as well? Aren't we summing over all the $2^N$ configurations of $h$ here? If say $N = 64$, then we are already reaching exascale computations ($2^{64} = 1.84 \times 10^{19}$)!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

However, shouldn't computing $\sum_{h} e^{-E(v^t, h; b,c,W)}$ be intractable as well?

It is. That's why RBMs are mostly trained with Contrastive Divergence which only approximates Maximum Likelihood. The idea is to approximate updates to ML using the following:

$\frac{\partial{\log(p(x))}}{\partial{W_{ij}}} = \mathbb{E_{data}}[v_i h_j] - \mathbb{E_{model}}[v_i h_j]$

Where expectations are taken respectively for the distributions specified by data and equilibrium distribution of Markov Chain that is formed by alternating the process of generating (using sampling) visible given hidden states and hidden states given visible. The trick is to run this Markov Chain and get the approximation for $\mathbb{E_{model}}$ (some applications even report running only one step).

Hinton's original paper on Contrastive Divergence gives more details, concrete examples and mentions the previous papers on the topic (I personally recommend going through the paper, it's pretty straightforward).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the answer! So, while training the RBM (i.e. iteratively updating the weights) is efficient, explicitly computing the NLL error is not. Now then, a follow up question is: if you cannot efficiently compute the NLL error, how do you know when to stop training? In a classification task, a work around could be to compute the classification accuracy - this of course assumes that low error corresponds to high accuracy. But what about in the clustering case, where data labels are not available? When would one conclude training? $\endgroup$
    – Dr. Prasanna Date
    Apr 19, 2018 at 19:28
  • $\begingroup$ CD gives you a cost function for training. $\endgroup$
    – Jakub Bartczuk
    Apr 20, 2018 at 12:39
  • $\begingroup$ Yes, and it is called Reconstruction Error as described in this guide: cs.toronto.edu/~hinton/absps/guideTR.pdf. To give an intuition for Reconstruction Error, we compare the original input $v$ to the reconstructed input obtained by first sampling $h$ from $p(h|v)$ and then sampling $v_R$ (reconstructed input) from $p(v|h)$. Reconstruction Error is then $\frac{1}{T} \sum_{t=1}^{T}(v_R - v)^2$. $\endgroup$
    – Dr. Prasanna Date
    May 2, 2018 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.