7 concepts20 worked examples30 exercises4 exam-level7 figures
What are you here for?
13 Restricted Boltzmann machines and deep learning
Start with this
One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§13.1 — a pairwise model on three pixels
Three-pixel images come in four versions, each a quarter of the time: $000$, $011$, $101$ and $110$. A model with one bias per pixel and one weight per pair of pixels is fitted to them by maximum likelihood.
Find(a) What probability does the fitted model give to the image $001$?
Given
data: $000,\ \allowbreak 011,\ \allowbreak 101,\ \allowbreak 110$, a quarter each
Before fitting anything, ask what this model can see in data: single pixels and pairs of pixels, nothing more.
Hint 2/4
At the maximum likelihood fit of this model, the model's rate of each $x_j=1$ and of each $x_jx_k=1$ equals the data's rate.
Hint 3/4
Here each pixel is on in 2 of the 4 images, rate $\tfrac12$, and each pair is $11$ in 1 of the 4, rate $\tfrac14$: the rates of three fair coins.
Hint 4/4
So the fit is three fair coins, and every image, $001$ included, gets $\tfrac18$.
Show solution
For this family the log-likelihood gradient of each parameter is the data rate minus the model rate of its feature, so the fit is where the rates match; matching is quicker than maximizing.
Three fair coins belong to the family and have exactly these rates.
Its value at 001
$$p(001)=\big(\tfrac12\big)^3=\tfrac18$$
Fair coins give every image the same probability.
Answer $$\boxed{p(001)=\tfrac18}$$
Check
Check one rate by hand: under fair coins $P(x_2x_3=1)=\tfrac12\cdot\tfrac12=\tfrac14$, and in the data $x_2x_3=1$ only for $011$, one image in four.
A model that sees only pairs cannot see a rule about triples; can.
A $28\times28$ image has $784$ black-or-white pixels, and $500$ on-off units sit above them. A model that gives each joint pattern of these $1284$ switches a probability must divide by a sum of $2^{1284}$ terms, a number with $387$ digits. That sum will never be computed, yet such models are trained one image at a time by climbing their log-likelihood.
By the end you can compute an RBM's conditionals and by hand, carry out one update, and explain how RBMs are stacked into a deep network and trained layer by layer.
In 60 seconds
An RBM scores patterns of binary pixels and hidden units by an energy. Its conditionals are products of sigmoids, its gradient is data statistics minus model statistics, and contrastive divergence replaces the model statistics by a short Gibbs chain started at the data. Stacked RBMs, trained one layer at a time, make a deep network.
Dropping the minus signs of the energy, or writing $p\propto e^{+E}$: low energy must mean high probability.
Reading $W$ the wrong way: hidden unit $i$ uses row $i$ and $c_i$, pixel $j$ uses column $j$ and $b_j$.
Swapping the two phases, or putting the training image into the model statistic: data first, reconstruction second.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The STARS weekly list has naive Bayes, and contrastive divergence as its eleventh item and deep learning as its twelfth; the lecture slides teach RBMs and deep networks in chapter 13 and naive Bayes in chapter 12.
How much time do you have?
10 minutes
The energy, the two sigmoid conditionals and one CD-1 update, enough for the standard computational question.
The 60-second card · The RBM · Conditionals · Contrastive divergence · Formula card
45 minutes
Every result once with a worked example, then CD-1 by hand from a full solution down to a bare problem.
The 60-second card · The RBM · Conditionals · Learning · Contrastive divergence · Why a short chain works · Deep networks · Scaffolding comes off · Formula card
full read
Adds the proofs, feature learning, the look-alike pairs, a full exam-style question and mixed practice with earlier sections.
The opening pages · Recall first · The RBM · Conditionals · Learning · Contrastive divergence · Why a short chain works · Feature learning · Deep networks · Method boxes · Look-alike pairs · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Compute energies, $Z$ and joint probabilities of a small RBM by listing configurations, and image probabilities through the free energy.
Derive the factorized sigmoid conditionals $p(h\mid x)$ and $p(x\mid h)$ from the energy, and compute them.
Derive the log-likelihood gradient as data statistics minus model statistics, and explain why the model term is intractable.
Perform one CD-k update by hand, sampling with given uniform numbers, and read it as raising what the data implies and lowering what the network implies.
Explain why CD works: compute Gibbs transition probabilities, check stationarity, and measure the bias of CD-k on a small machine.
Interpret rows of $W$ as , compute reconstructions, and explain why training starts from small random weights.
Describe a deep network's factorization and its layer-by-layer training, build the data for the next layer, and count its weights.
Syllabus coverage
covered
Restricted Boltzmann Machines — covered
The bipartite model of binary visible and hidden units
energy
joint distribution and partition function
the marginal and the free energy
the factorized sigmoid conditionals
Named in both halves of the weekly line. The first two blocks follow the lecture's slides on the model.
covered
Contrastive Divergence — covered
on the log-likelihood with its data and model terms
the CD-k Gibbs chain and update rule
why the chain works
the CD-1 heuristic
The gradient comes first in the gradient block, the algorithm here, and the argument for it in the next block.
covered
Deep learning — covered
A deep network as a stack of RBMs
its factorization
layer-by-layer training by CD
The lecture's chapter title pairs it with RBMs, and the STARS list gives it a week of its own; here it is the deep network of the lecture, built from RBMs.
covered
Naive Bayes — covered
The classifier whose features are independent given one observed label, set beside the RBM, whose units are independent given the other layer.
The chapter 12 slides teach the classifier itself, and the graphical models section covers it. Here it is recalled for the comparison, and it returns in a look-alike pair and an interleaved question.
covered
Feature learning via RBM — covered
Rows of $W$ as feature images, reconstruction, and starting from small random weights; the lecture's example trains 50 hidden units on $16\times16$ images of the digit 2.
A subtopic of the lecture's chapter. The lecture's figures are not reproduced; a small run of the same kind was computed for this page.
covered
Deep network for digit classification and generation — covered
The lecture's network: 784 pixels, layers of 500 and 500 units, and a top RBM of 2000 units joined to 10 label units.
Its sizes are the lecture's; the weight counts and the generation example were worked out here.
Recall first
The logistic function
$\sigma(z)=\dfrac1{1+e^{-z}}$, with $\sigma(0)=0.5$ and $\sigma(-z)=1-\sigma(z)$; logistic regression sets $P(Y=1\mid x)=\sigma(\beta^Tx)$.
Every conditional of an RBM is this function of a weighted sum.
Energy models and Z
$p(x)=e^{-E(x)}/Z$ with $Z=\sum_xe^{-E(x)}$; lower energy means higher probability, and for $D$ binary nodes $Z$ has $2^D$ terms.
An RBM is such a model with two layers of units.
Separation in undirected graphs
$A\perp\!\!\!\perp B\mid C$ when every path from $A$ to $B$ passes through a node of $C$.
It is why the conditionals of an RBM factorize.
Naive Bayes
$p(y=c\mid x)\propto\pi_c\prod_jp(x_j\mid y=c)$: the features are independent given the class label.
An RBM's conditionals have the same product shape, with a hidden layer in place of the label.
Hidden variables and the marginal
$p(x)=\sum_zp(x,z)$, and the log-likelihood of a model with hidden $z$ is $\log\sum_zp(x,z)$, as for a mixture fitted by EM.
The hidden units of an RBM are summed out the same way.
Averages of binary variables
$\mathbb E[h]=P(h=1)$ for $h\in\{0,1\}$, and $\mathbb E[f(X)]=\sum_xp(x)f(x)$.
The gradient is a difference of two such averages.
Stochastic gradient steps
One example at a time: $\theta\leftarrow\theta-\eta\nabla_\theta e$ lowers a loss $e$; to raise a log-likelihood, move along the gradient, $\theta\leftarrow\theta+\eta\nabla_\theta l$.
RBM training climbs $\log p(x^t)$ one training image at a time.
Try it yourself first (2 questions)
1§13.1 — terms in a normalizing constant
An undirected model has 3 binary and 2 binary hidden units, and its joint is $e^{-E(x,h)}/Z$.
Find(a) How many terms does the sum $Z$ have?
Given3 visible and 2 hidden units, each $0$ or $1$
Hint 1/4
$Z$ adds one term for every joint configuration of all the units; count configurations.
Hint 2/4
$n$ binary units have $2^n$ joint configurations.
Hint 3/4
Here there are $3+2=5$ binary units.
Hint 4/4
So $Z$ has $2^5=32$ terms.
Show solution
Each unit doubles the number of configurations, so the count is a power of 2.
Count
$$2^{3+2}=32$$
Every unit is $0$ or $1$ independently of the others in the sum.
Answer $$\boxed{32}$$
Check
Counted in two stages: $2^3=8$ images times $2^2=4$ hidden patterns is $32$.
For 784 pixels and 500 hidden units the same count is $2^{1284}$, which is why $Z$ is never summed.
2§13.2 — independence given a separating node
In the undirected chain $a - c - b$ of three binary nodes, $c$ separates $a$ from $b$. A classmate concludes that $a$ and $b$ are independent.
Find(a) Are $a$ and $b$ independent when $c$ is not observed?
Given
graph: $a - c - b$
$a\perp\!\!\!\perp b\mid c$
Hint 1/4
Separation statements are always about some set that is observed; check which set this one needs.
Hint 2/4
Separation gives $a\perp\!\!\!\perp b\mid c$. Without $c$, $p(a,b)=\sum_cp(c)\,p(a\mid c)\,p(b\mid c)$, which need not factor.
Hint 3/4
Here try a concrete case: $c$ a fair coin, and $a=b=c$ always. Given $c$ both are fixed; without $c$, seeing $a$ tells you $b$.
Hint 4/4
So in general $a$ and $b$ are dependent when $c$ is not observed.
Show solution
One counterexample settles a claim meant for every distribution on the graph.
Build a case
$$c\sim\text{fair coin},\quad a=c,\quad b=c$$
Given $c$ both $a$ and $b$ are fixed, so they are independent given $c$.
Drop c
$$P(a=1,b=1)=\tfrac12\ne P(a=1)P(b=1)=\tfrac14$$
Without $c$ the two always agree.
Answer $$\boxed{\text{not independent in general}}$$
Check
The formula $p(a,b)=\sum_cp(c)p(a\mid c)p(b\mid c)$ gives $\tfrac12\cdot1\cdot1=\tfrac12$ for $a=b=1$, the same value.
Separation needs the separating set observed; the RBM's hidden units are independent only given the pixels.
Notation
symbol
reads as
means
watch out
$x=[x_1,\dots,x_m]^T$
x, the visible vector
the $m$ visible units, the pixels; $x_j\in\{0,1\}$
$1$ means on, ink; $0$ means off.
$h=[h_1,\dots,h_n]^T$
h, the hidden vector
the $n$ hidden units; $h_i\in\{0,1\}$, never observed
A pattern like $h=10$ lists $h_1$ first.
$w_{ij},\ \ W$
w i j; W
the weight between $h_i$ and $x_j$; $W$ is $n\times m$
Row $i$ belongs to hidden unit $i$, column $j$ to pixel $j$.
$b_j,\ \ c_i$
b j; c i
the bias of pixel $j$; the bias of hidden unit $i$
$b$ goes with the visible layer, $c$ with the hidden one.
$E(x,h),\ \ Z$
energy; partition function
$-h^TWx-b^Tx-c^Th$; the sum of $e^{-E}$ over all $2^{m+n}$ configurations
Lower energy, higher probability.
$\sigma(z)$
sigma of z
$1/(1+e^{-z})$
$\sigma(-z)=1-\sigma(z)$.
$a_i(x)$
input of hidden unit i
$c_i+\sum_jw_{ij}x_j$, so $p(h_i=1\mid x)=\sigma(a_i(x))$
A shorthand of this page; the lecture writes the sum out.
$F(x)$
free energy of x
$-b^Tx-\sum_i\log(1+e^{a_i(x)})$, with $p(x)=e^{-F(x)}/Z$
Lower $F$, more probable image.
$\theta,\ \ l(\theta),\ \ \eta_t$
theta; l of theta; eta t
all weights and biases; $\log p(x^t\mid\theta)$; the step size
$l$ is for one training image.
$x^t$
x t
the training image used at iteration $t$
$t$ is an index, not a power; $x^t_j$ is its pixel $j$.
$\tilde x^{(k)},\ \ \tilde h^{(k)}$
x tilde k; h tilde k
the chain's visible and hidden samples after $k$ steps; $\tilde x^{(0)}=x^t$
The tilde marks a sample, the bracket a step.
$\Delta w_{ij},\ \Delta b_j,\ \Delta c_i$
delta w i j, and so on
the CD increments; each parameter then moves by $\eta$ times its increment
the hidden layers of a deep network, from the pixels up
Bold is a whole layer; italic $h_i$ is one unit.
Conventions used here
Binary units.
Every unit is $0$ or $1$; for pixels $1$ means ink. A pattern such as $110$ lists the units in index order.
The energy and all conditionals are written for $\{0,1\}$ units, as in the lecture.
Rows and columns of W.
$w_{ij}$ joins hidden unit $i$ and pixel $j$. A hidden unit reads its row of $W$ and adds $c_i$; a pixel reads its column and adds $b_j$.
Most slips in RBM arithmetic are a row read as a column.
Drawing a binary sample.
To set a unit that is on with probability $q$, draw $u$ uniform on $[0,1)$ and set it to $1$ if $u<q$. Questions list the $u$ values in unit order.
Fixed numbers make every sampling step checkable.
Ascent, not descent.
Parameters move up the log-likelihood: $\theta\leftarrow\theta+\eta\,\Delta\theta$, with $\Delta\theta$ the gradient or its CD estimate.
The lecture climbs $l(\theta)$; a descent step on $-l$ is the same move.
Probabilities in the CD statistics.
In $\Delta w_{ij}$ and $\Delta c_i$ the hidden units enter through $p(h_i=1\mid\tilde x)$; the 0/1 samples only drive the chain.
This is the lecture's update rule, and it has less noise than using samples.
One training image per step.
$l(\theta)$ is the log-likelihood of the single image $x^t$; for a mini-batch, average the increments.
The lecture writes the update for one sample drawn from the training set.
Natural logarithms and rounding.
$\log$ is the natural logarithm. Numbers are computed from unrounded values and printed to 4 decimals.
Rounded intermediate values would drift in the last digit.
Z only for tiny machines.
$Z$, $p(x)$ and exact gradients are computed only for machines with at most 7 units, where every configuration can be listed.
They are the exact answers that CD approximates; real machines never compute them.
13.1The RBM: one energy for pixels and hidden units
Scores every joint pattern of pixels and hidden units by an energy; summing out the hidden units gives each image's probability.
The denoising model of the graphical models section put an energy on pixels alone; now a second layer of binary units joins the energy, wired only to the pixels.
Solvable with what we have
Put an energy on the pixels alone and find the likeliest clean image, as in denoising.
Classify with naive Bayes when every training image carries its label.
Fit one hidden cause per point by EM, as for a mixture of Gaussians.
Train a network by backpropagation when every input has a target.
Not solvable yet
Capture a rule that involves three pixels at once, such as an even number of ink pixels.
Learn several hidden causes that can be on together, from images without labels.
Say how probable an image is when its hidden causes are never observed.
Data: the four images with an even number of ink pixels, $000, \allowbreak 011, \allowbreak 101, \allowbreak 110$, a quarter each. A pairwise pixel model matches each pixel's rate and each pair's rate. Here every pixel is on half the time and every pair shows $00, 01, 10, 11$ equally often, as three fair coins do. So its fit is $p(x)=\tfrac18$ for all 8 images.
Why it fails
Half of that probability, $4\times\tfrac18$, sits on the odd images, which never occur. No pair of pixels shows the rule; only all three together do. A hidden unit that responds to a whole image can see it, and that is what the RBM adds.
Every joint pattern of pixels and hidden units gets an energy. A positive $w_{ij}$ lowers the energy when $h_i$ and $x_j$ are on together, which makes that pairing more likely. The probability is $e^{-E}$ divided by $Z$, a sum over all $2^{m+n}$ patterns. Summing out $h$ leaves $e^{-F(x)}/Z$; $F$ is the free energy.
Why the sum over h is a product, and Z is not
Fix the image. Write $a_i(x)=c_i+\sum_jw_{ij}x_j$ for the input of hidden unit $i$. Then $-E(x,h)=b^Tx+\sum_ih_ia_i(x)$, so $e^{-E(x,h)}=e^{b^Tx}\prod_ie^{h_ia_i(x)}$.
One unit at a time. Summing over $h\in\{0,1\}^n$ lets each $h_i$ be $0$ or $1$ on its own, and a sum of products of separate factors is the product of the sums: $\sum_he^{-E(x,h)}=e^{b^Tx}\prod_i\big(1+e^{a_i(x)}\big)$.
Logs. Minus the log of that product is $F(x)$: $n$ terms instead of $2^n$.
Z does not split. $Z=\sum_xe^{-F(x)}$ still runs over all $2^m$ images, because every $a_i(x)$ involves every pixel. For $m=784$ that is about $10^{236}$ terms.
The eight 3-pixel images, with the data's rate in $\textcolor{#1f6feb}{\text{blue}}$. The pairwise fit, dashed, gives every image $\tfrac18$, so half its probability lands on odd images. The RBM of the first worked example gives each even image $\textcolor{#d1690a}{0.213}$ and each odd one $\textcolor{#d1690a}{0.037}$.
Looks like this, but is not
The image whose best hidden pattern has the lowest energy is the most probable image.
$p(x)$ adds $e^{-E}$ over every hidden pattern; it does not keep the best one. In the table below, $000$ and $010$ have the same best energy, $0$, but $010$ has it for all four hidden patterns, so $p(010)=0.2017$ is more than twice $p(000)=0.0943$.
image x
E(x, 00)
E(x, 10)
E(x, 01)
E(x, 11)
sum over h of exp(−E)
p(x)
$000$
$0$
$1$
$1$
$2$
$1.8711$
$0.0943$
$001$
$1$
$3$
$0$
$2$
$1.5530$
$0.0783$
$010$
$0$
$0$
$0$
$0$
$4.0000$
$0.2017$
$011$
$1$
$2$
$-1$
$0$
$4.2215$
$0.2129$
$100$
$1$
$0$
$3$
$2$
$1.5530$
$0.0783$
$101$
$2$
$2$
$2$
$2$
$0.5413$
$0.0273$
$110$
$1$
$-1$
$2$
$0$
$4.2215$
$0.2129$
$111$
$2$
$1$
$1$
$0$
$1.8711$
$0.0943$
The strokes $110$ and $011$ and the middle pixel $010$ together take $0.6274$ of the probability; the gap $101$ gets the least, $0.0273$.
Four detector units make the even images likely
A machine has 3 pixels and 4 hidden units, one for each even image $v$. Unit $i$ has weight $+4$ on the pixels where $v_i$ has ink and $-4$ elsewhere, bias $c_i=2-4\lvert v_i\rvert$, where $\lvert v_i\rvert$ counts the ink pixels of $v_i$, and $b=0$. How much probability does it give the even images?
Find$p(000)$, $p(001)$ and the total probability of the four even images.
Given
rows of $W$: $(-4,-4,-4)$, $(-4,4,4)$, $(4,-4,4)$, $(4,4,-4)$ for $v=000, \allowbreak 011, \allowbreak 101, \allowbreak 110$
$c=(2,-6,-6,-6)$, $b=(0,0,0)$
Solution
Summing $e^{-E}$ over all $2^4=16$ hidden patterns of every image is slow; the product form of the box needs one factor per hidden unit.
Inputs to the four units
$$a_i(x)=c_i+\sum_jw_{ij}x_j=2-4\,d(x,v_i)$$
At $x=v_i$ the input is $c_i+4\lvert v_i\rvert=2$; each pixel where $x$ and $v_i$ disagree then costs $4$, and $d$ counts those pixels.
Limits bracket the answer: with all weights and biases $0$ every image gets $\tfrac18=0.125$, and as the weights grow each even image tends to $\tfrac14=0.25$. The value 0.2131 lies between, and $4(0.2131)+4(0.0369)=1$.
This closes the opening problem: pairs of pixels cannot see the even-ink rule, hidden units that each respond to a whole image can. With weights $\pm6$ and the biases scaled alike, the even images already hold $0.948$ of the probability.
Energies, Z and p(110) for the running machine
The running machine of this page has 3 pixels and 2 hidden units: $h_1$ is wired to like the left stroke $110$ and $h_2$ the right stroke $011$. List the four energies of the image $110$, then find $Z$ and $p(110)$.
Find$E(110,h)$ for the four hidden patterns, $Z$, and $p(110)$.
Given
$W=\begin{bmatrix}2&1&-1\\-1&1&2\end{bmatrix}$
$b=(-1,0,-1)$, $c=(-1,-1)$
Solution
Energies first, because the definition gives them directly; the product form then checks the sum and gives the other seven images with little work.
The eight probabilities in the table add up to $1.0000$, and the mirror image $011$ also gets 0.2129: swapping $h_1\leftrightarrow h_2$ together with $x_1\leftrightarrow x_3$ maps the machine onto itself.
Energies are local and cheap; $Z$ is the one global number, and the rest of this page is built to avoid it.
Checkpoint
§13.1 — one energy of the running machine
The running machine has $W=\begin{bmatrix}2&1&-1\\-1&1&2\end{bmatrix}$, $b=(-1,0,-1)$ and $c=(-1,-1)$. Only the second hidden unit is on.
Find(a) What is $E(011,01)$?
Given
$x=011$, $h=01$
$E(x,h)=-h^TWx-b^Tx-c^Th$
Hint 1/4
You need three separate pieces of the energy: the weights between units that are on, and the two bias terms.
Given the image, every hidden unit flips its own coin: it adds its weights to the ink pixels, adds its bias, and passes the sum through the sigmoid. The units do not consult each other. Given the hidden units, every pixel flips its own coin the same way, using its column of $W$ and its bias $b_j$.
Z cancels, and the other hidden units drop out
Split off one unit. Write $h_{-i}$ for the other hidden units. Then $E(x,h)=\Phi(x,h_{-i})-h_i\big(\sum_jw_{ij}x_j+c_i\big)$, where $\Phi$ collects every term without $h_i$.
Take the ratio.$p(h_i=1\mid h_{-i},x)=\dfrac{e^{-E(x,h_{-i},1)}}{e^{-E(x,h_{-i},1)}+e^{-E(x,h_{-i},0)}}$. $Z$ and $e^{-\Phi}$ appear in every term and cancel, leaving $\dfrac{e^{a_i}}{e^{a_i}+1}=\sigma(a_i)$.
Independence. The result does not involve $h_{-i}$, so given $x$ the unit $h_i$ is independent of the other hidden units, and $p(h\mid x)=\prod_ip(h_i\mid x)$. In graph terms, no edge joins two hidden units, so the observed pixels separate them.
Other direction. The energy is also linear in each $x_j$, with slope $\sum_iw_{ij}h_i+b_j$, and the same ratio gives $p(x_j=1\mid h)$.
The running machine with the image $\textcolor{#1f6feb}{110}$ observed. Every path from $h_1$ to $h_2$ passes through a pixel, so given the pixels the two hidden units are separate coin flips: $\textcolor{#8250df}{0.881}$ and $\textcolor{#8250df}{0.269}$.
Looks like this, but is not
Given the pixels the hidden units are independent, so they are also independent when the pixels are not observed.
Summing the pixels out couples them. In the running machine $p(h_1=1)=p(h_2=1)=0.5201$, yet $p(h_1=1,h_2=1)=0.2290$, well below the product $0.2706$ that independence would give. Separation needs the separating layer observed.
image x
a1
a2
p(h1 = 1 | x)
p(h2 = 1 | x)
$000$
$-1$
$-1$
$0.2689$
$0.2689$
$001$
$-2$
$1$
$0.1192$
$0.7311$
$010$
$0$
$0$
$0.5000$
$0.5000$
$011$
$-1$
$2$
$0.2689$
$0.8808$
$100$
$1$
$-2$
$0.7311$
$0.1192$
$101$
$0$
$0$
$0.5000$
$0.5000$
$110$
$2$
$-1$
$0.8808$
$0.2689$
$111$
$1$
$1$
$0.7311$
$0.7311$
Each detector is most likely on for its own stroke; the gap $101$ and the middle pixel $010$ leave both units at a coin flip.
Hidden probabilities for the left stroke 110
In the running machine the image $110$ is observed. Find $p(h_1=1\mid x)$, $p(h_2=1\mid x)$ and the probability of each of the four hidden patterns.
FindThe two hidden probabilities and $p(h\mid x)$ for $h=00,10,01,11$.
From the energies of $110$ in the previous table, $p(10\mid x)=e^{1}/4.2215=0.6439$: the same number by way of the joint.
Row $i$ of $W$ and $c_i$ give hidden unit $i$; the other hidden units never enter.
Pixel probabilities when only h1 is on
In the running machine the hidden pattern is $h=10$. Find $p(x_j=1\mid h)$ for the three pixels, and the probability that the machine then draws the image $110$.
Find$p(x_j=1\mid h)$ for $j=1,2,3$ and $p(110\mid h)$.
The gradient of $w_{ij}$ is how often $h_i$ and $x_j$ are on together with the training image clamped, minus how often they are on together when the model runs freely. The first part is one sigmoid. The second is an average over all $2^m$ images weighted by $p(x)$, and $p(x)$ needs $Z$.
Two logs, two averages
First log. $$\frac{\partial}{\partial\theta}\log\sum_he^{-E(x^t,h)}=\sum_h\frac{e^{-E(x^t,h)}}{\sum_{h'}e^{-E(x^t,h')}}\Big(-\frac{\partial E(x^t,h)}{\partial\theta}\Big)$$ and the fraction is $p(h\mid x^t)$.
Second log. $$\frac{\partial\log Z}{\partial\theta}=\frac1Z\sum_{x,h}e^{-E(x,h)}\Big(-\frac{\partial E}{\partial\theta}\Big)=-\mathbb E_{x,h}\Big[\frac{\partial E}{\partial\theta}\Big]$$ It enters $l$ with a minus sign.
One weight. $\partial E/\partial w_{ij}=-h_ix_j$, and given $x$ the average of $h_i$ is $p(h_i=1\mid x)$. So the data average is $p(h_i=1\mid x^t)x_j^t$ and the model average is $\sum_xp(x)p(h_i=1\mid x)x_j$.
Biases. $\partial E/\partial b_j=-x_j$ and $\partial E/\partial c_i=-h_i$ give the other two lines the same way.
The six weights of the running machine at the training image $110$: the $\textcolor{#1f6feb}{\text{data term}}$ next to the $\textcolor{#d1690a}{\text{model term}}$, an average over all 8 images. The number over each pair is the gradient; $w_{22}$ goes down although pixel 2 is on.
Looks like this, but is not
Pixel 2 is on in the training image $110$ and $h_2$ is on with probability $0.2689$, so the gradient must raise $w_{22}$.
It is $0.2689-0.4145=-0.1456$. The model already turns $x_2$ and $h_2$ on together $0.4145$ of the time, more than this image asks for, so $w_{22}$ goes down.
parameter
data term
model term
gradient
$w_{11}$
$0.8808$
$0.3273$
$0.5534$
$w_{12}$
$0.8808$
$0.4145$
$0.4663$
$w_{13}$
$0.0000$
$0.1492$
$-0.1492$
$w_{21}$
$0.2689$
$0.1492$
$0.1197$
$w_{22}$
$0.2689$
$0.4145$
$-0.1456$
$w_{23}$
$0.0000$
$0.3273$
$-0.3273$
$b_{1}$
$1.0000$
$0.4128$
$0.5872$
$b_{2}$
$1.0000$
$0.7217$
$0.2783$
$b_{3}$
$0.0000$
$0.4128$
$-0.4128$
$c_{1}$
$0.8808$
$0.5201$
$0.3606$
$c_{2}$
$0.2689$
$0.5201$
$-0.2512$
Everything that ties $h_1$ to the left stroke goes up and everything that involves pixel 3, which is off, goes down; the parameters of $h_2$ go both ways.
The exact gradient of the running machine at the image 110
Train the running machine on $x^t=110$. With $p(x)$ from the first table, find $\partial l/\partial w_{11}$, $\partial l/\partial b_1$ and $\partial l/\partial c_1$.
The training image is clamped, so the data term is one sigmoid and no sum.
$$x_1^t=1,\qquad p(h_1=1\mid 110)=0.8808$$
For $b_1$ the data term is the pixel itself and for $c_1$ the hidden probability alone, since $\partial E/\partial b_1=-x_1$ and $\partial E/\partial c_1=-h_1$.
The log-likelihood of the training image went up, as ascent should.
Answer $$\boxed{\Delta\log p(110)=0.1428}$$
Check
First-order prediction: the gain is about $\eta\lVert\nabla l\rVert^2=0.1\times1.4745=0.1474$, close to the exact gain, as it should be for a small step.
A small exact step raises the training image's log-probability; the catch is that the exact gradient was computable only because this machine is tiny.
Checkpoint
§13.3 — gradient of a visible bias
The running machine is trained on $x^t=110$. Its image probabilities are $p(001)=0.0783$, $p(011)=0.2129$, $p(101)=0.0273$, $p(111)=0.0943$, and the other four images have $x_3=0$.
right$$\text{model term}=\textstyle\sum_xp(x)\,p(h_i=1\mid x)\,x_j\ \text{ over all }2^m\text{ images}$$
⚠ Dropping the pixel factor from the data term
$p(h_i=1\mid x^t)$ is the visible part of the computation; the factor $x^t_j$ quietly zeroes some terms.
wrong$$\text{data term of }w_{13}=p(h_1=1\mid110)=0.8808$$
right$$\text{data term of }w_{13}=p(h_1=1\mid110)\,x^t_3=0$$
13.4Contrastive divergence: a short Gibbs chain stands in for the model
Start at the training image, sample hidden units and pixels back and forth $k$ times, and use the chain's end for the model term.
The data term is exact and cheap; only the average over all images needs a stand-in, and the conditionals give a cheap way to draw images from the model.
MethodMethod 13.4: Contrastive divergence, CD-k
Conditions
a training image $x^t$, a chain length $k\ge1$ and a step size $\eta$
to sample a binary unit that is on with probability $q$, draw $u$ uniform on $[0,1)$ and set the unit to $1$ if $u<q$
Clamp the chain at the training image and record how strongly each hidden unit and pixel fire together: that is what the data implies. Let the machine run $k$ back-and-forth steps on its own and record the same thing: that is what the network believes. Raise the weights the data implies, lower the ones the network implies.
Where the approximation sits
Model term. Theorem 13.3 needs $\mathbb E_{x,h}[\partial E/\partial\theta]$; CD-k replaces it by its value at the late sample $(\tilde x^{(k)},\tilde h^{(k)})$ of the chain.
Hidden sample averaged out. For a weight, $-\partial E/\partial w_{ij}=h_ix_j$, and given $\tilde x^{(k)}$ the unit $h_i$ averages to $p(h_i=1\mid\tilde x^{(k)})$. The rule uses that probability instead of the 0/1 sample: same average, less noise.
Data term. At $\tilde x^{(0)}=x^t$ the same averaging is exact: $p(h_i=1\mid x^t)\,x^t_j$ is the data term of Theorem 13.3.
What is left. The only approximation is that $\tilde x^{(k)}$ is drawn from wherever $k$ steps from $x^t$ lead, not from $p(x)$. The next block measures the gap.
The CD-1 step of the worked example: $\textcolor{#1f6feb}{\text{data}}$ on the left, the $\textcolor{#d1690a}{\text{reconstruction}}$ on the right, the sampled $\textcolor{#8250df}{\text{hidden units}}$ between. Each weight moves by its left statistic minus its right one.
Looks like this, but is not
CD-1 is a noisy copy of the gradient, so on average it moves every weight the right way.
Not always. Take 2 pixels, one hidden unit, $w=(2,-2)$, $b=(0,1)$, $c=1$, trained on $x^t=01$. The gradient of $w_{12}$ is $0.0518$, but the average CD-1 step is $-0.0472$. Both were computed exactly, over all states; CD-2 already gets the sign right.
parameter
data statistic
reconstruction statistic
increment
new value
$w_{11}$
$0.8808$
$0.7311$
$0.1497$
$2.0150$
$w_{12}$
$0.8808$
$0.0000$
$0.8808$
$1.0881$
$w_{13}$
$0.0000$
$0.0000$
$0.0000$
$-1.0000$
$w_{21}$
$0.2689$
$0.1192$
$0.1497$
$-0.9850$
$w_{22}$
$0.2689$
$0.0000$
$0.2689$
$1.0269$
$w_{23}$
$0.0000$
$0.0000$
$0.0000$
$2.0000$
$b_{1}$
$1$
$1$
$0$
$-1.0000$
$b_{2}$
$1$
$0$
$1$
$0.1000$
$b_{3}$
$0$
$0$
$0$
$-1.0000$
$c_{1}$
$0.8808$
$0.7311$
$0.1497$
$-0.9850$
$c_{2}$
$0.2689$
$0.1192$
$0.1497$
$-0.9850$
Nothing that touches pixel 3 moves, because pixel 3 is off in both images; everything that touches pixel 2 rises.
One CD-1 update of the running machine on the image 110
Train the running machine on $x^t=110$ with CD-1 and $\eta=0.1$. The uniform numbers are $u=(0.42,\ 0.63)$ for $\tilde h^{(0)}$ and $u=(0.35,\ 0.87,\ 0.64)$ for $\tilde x^{(1)}$. Find all eleven increments and the new $w_{12}$, $b_2$ and $c_1$.
Find$\Delta W$, $\Delta b$, $\Delta c$ and three updated parameters.
Two structural checks: column 3 of $\Delta W$ is zero because pixel 3 is off in both images, and $\Delta c_i=\Delta w_{i1}$ because pixel 1 is on in both images.
The data had pixel 2 on and the reconstruction dropped it, so every parameter that touches pixel 2 went up. No step needed $Z$, which is how the 1284-unit machine of the opening is trained.
What the CD-1 update did to the two images
After the update of the previous example, compare $p(110)$ and $p(100)$ with their values before, and the free-energy gap $F(100)-F(110)$.
FindThe two probabilities before and after, and the change in their ratio.
Consistency: $e^{-F(110)}/Z$ after the step is $e^{1.6605}/22.9688=0.2291$, and the ratio 0.2291/0.0694 equals 3.3025.
Before the step the ratio was exactly $e$, by the machine's symmetry. CD raised the data image and lowered the reconstruction, which is the whole idea of contrasting them.
Checkpoint
§13.4 — one hidden-bias increment
A CD-1 step on the running machine, $c=(-1,-1)$ and $W=\begin{bmatrix}2&1&-1\\-1&1&2\end{bmatrix}$, starts at the data image $110$ and its reconstruction comes out as $111$.
Find(a) What is $\Delta c_2$?
Given
$\tilde x^{(0)}=110$, $\tilde x^{(1)}=111$
row 2 of $W$: $(-1,1,2)$, $c_2=-1$
Hint 1/4
The increment compares hidden unit 2 on the data image with hidden unit 2 on the reconstruction.
Sign check: the reconstruction added pixel 3, the right-stroke detector's favourite pixel, so $h_2$ is likelier on the reconstruction and $c_2$ must fall.
When the reconstruction wakes a hidden unit more than the data does, that unit's bias goes down.
⚠ Using the training image in the model statistic
The data image is the one in front of you, and its pixels slip into the second term.
One back-and-forth step takes the image from $x$ to $x'$ with probability $T(x'\mid x)$. An image already distributed as $p(x)$ stays so: $p$ is stationary. From any start the chain forgets where it began, so for large $k$ its end is a fair draw from the model and CD-k is the gradient on average. The lecture uses $k=1$.
Stationary, forgetful, and unbiased in the limit
Stationary.$\sum_xp(x)\sum_hp(h\mid x)\,p(x'\mid h)=\sum_hp(h)\,p(x'\mid h)=p(x')$, because summing $p(x)p(h\mid x)=p(x,h)$ over $x$ leaves $p(h)$.
Forgetful. With every $T(x'\mid x)>0$ each image can reach every image in one step, and the influence of the start fades geometrically; the one-pixel example below shows the rate.
Unbiased in the limit. At $k=\infty$ the pair $(\tilde x^{(\infty)},\tilde h^{(\infty)})$ is a sample from $p(x,h)$, so the model statistic averages exactly to the model term of Theorem 13.3.
Why k = 1. Each extra step costs two more layers of sigmoids and samples; the lecture takes $k=1$ as a fast heuristic and accepts the bias.
The average CD-k step for $w_{11}$ and $w_{23}$ of the running machine at $110$, against $k$. $\textcolor{#d1690a}{\text{CD-1}}$ has the right sign here but only 69% and 56% of the size; by $k=4$ both are within $0.01$ of the exact gradient, dashed.
Looks like this, but is not
The chain starts at a training image, so after many steps its samples come from the training data.
The start is forgotten: after many steps the image is a draw from the model's $p(x)$, for example $0.2129$ for $110$ in the running machine, whatever the start. That is exactly why the end of the chain can stand in for the model term.
k
total variation to p(x)
average step, w11
average step, w23
$1$
$0.2049$
$0.3816$
$-0.1846$
$2$
$0.0724$
$0.4927$
$-0.2703$
$3$
$0.0265$
$0.5312$
$-0.3055$
$4$
$0.0099$
$0.5452$
$-0.3191$
$6$
$0.0014$
$0.5523$
$-0.3262$
exact
$0$
$0.5534$
$-0.3273$
The distance shrinks by a factor of about 2.7 per step, and the average steps close in on the gradient at the same pace.
One Gibbs step from the left stroke to the right stroke
In the running machine, start the chain at $110$. What is the probability that one back-and-forth step lands on $011$?
Find$T(011\mid110)$.
Given
$p(h\mid110)$ for $h=00,10,01,11$: $0.0871,\ \allowbreak 0.6439,\ \allowbreak 0.0321,\ \allowbreak 0.2369$
Each route's weight is the probability of its hidden pattern given $110$.
Answer $$\boxed{T(011\mid110)=0.0909}$$
Check
The same four routes into each of the eight images give eight probabilities that add up to $1$, and staying at $110$ is the most likely move, 0.3646. The route $h=01$, which favours $011$ most, adds only 0.0151 because it is rare given $110$.
A transition probability is a sum over hidden routes; never plug hidden probabilities straight into $p(x\mid h)$.
The chain of a one-pixel machine, and the bias of CD-1
A machine has one pixel and one hidden unit with $w=2$, $b=0$ and $c=-1$. Find the chain's two transition probabilities, check that $p(x=1)$ is stationary, and compare the average CD-k step for $w$ at $x^t=1$ with the exact gradient.
Find$T(1\mid0)$, $T(0\mid1)$, the stationary $p(x=1)$, and the average CD-k step for $k=1,2,3$.
Given
$w=2$, $b=0$, $c=-1$
$x^t=1$
Solution
With two images the chain is a two-state Markov chain, so every quantity has a closed form and the bias of CD-k can be seen exactly.
Answer $$\boxed{T(1\mid0)=0.6024,\ T(0\mid1)=0.2216,\ p(x=1)=0.7311,\ \mathbb E[\text{CD-1}]=0.1620\text{ vs }0.1966}$$
Check
Direct CD-1 check: the model statistic is $\sigma(1)$ times the chance of staying at $1$, so the step is $\sigma(1)\,T(0\mid1)=0.7311\times0.2216=0.1620$, the formula's value.
CD-k's bias falls like $\lambda^k$: a chain that forgets slowly, with $\lambda$ near $1$, needs a longer chain for the same accuracy.
Checkpoint
§13.5 — two steps of a two-state chain
The one-pixel machine with $w=2$, $b=0$ and $c=-1$ has transition probabilities $T(1\mid0)=0.6024$ and $T(0\mid1)=0.2216$. A chain starts at $x=0$.
Find(a) What is the probability that the chain is at $x=1$ after two steps?
Given
$T(1\mid0)=0.6024$, $T(0\mid1)=0.2216$
start: $x=0$
Hint 1/4
After two steps the chain can be at $1$ along two different paths; list them first.
Hint 2/4
The probability of a path is the product of its transition probabilities, and the paths add.
Hint 3/4
Here the paths are $0\to1\to1$ with $T(1\mid0)\,(1-T(0\mid1))=0.6024\times0.7784$ and $0\to0\to1$ with $(1-T(1\mid0))\,T(1\mid0)=0.3976\times0.6024$.
Hint 4/4
They add up to 0.7084.
Show solution
Listing paths is shorter than squaring a matrix when there are only two states.
right$$\mathbb E[\text{CD-}k\text{ step}]\to\nabla_\theta\,l\ \text{only as }k\to\infty$$
Step through the chain started at $110$: orange bars show where the image is after $k$ steps, dashed outlines show $p(x)$. By $k=6$ the total variation is 0.0014.
At the edges
k = 0 all mass on 110
The chain has not moved; the model statistic would equal the data statistic and every step would be $0$.
k → ∞ p(x)
The start is forgotten and the average step is the exact gradient.
13.6Feature learning: each hidden unit becomes a detector, read off its row of W
Row $i$ of $W$, drawn on the pixel grid, is the pattern hidden unit $i$ answers to; together the units reconstruct what they see.
Trained by CD on many images, a row of weights stops being a list of numbers and becomes a picture.
RuleFact 13.6: Reading an RBM's features
Conditions
the pixels form a grid: $x_{r,s}$ is the pixel in row $r$ and column $s$, and $w_{i,(r,s)}$ its weight to $h_i$
the lecture's example: 50 hidden units on $16\times16=256$ pixels, trained on images of the digit 2
reconstruction of an image $x$: sample $\tilde h\sim p(h\mid x)$, then read off $p(x\mid\tilde h)$
$$\boxed{\begin{aligned}a_i(x)&=c_i+\sum_{r,s}w_{i,(r,s)}\,x_{r,s}\ \text{ is largest for }x_{r,s}=1\iff w_{i,(r,s)}>0\\\hat x_j&=p(x_j=1\mid\tilde h)=\sigma\Big(b_j+\sum_iw_{ij}\tilde h_i\Big)\\&\text{rows }i,k\text{ of }W\text{ and biases }c_i=c_k\text{ equal at the start}\ \Rightarrow\ \text{equal CD updates at every step}\end{aligned}}$$
A hidden unit adds up the weights of the ink pixels, so it fires hardest for the image with ink exactly where its weights are positive: the row, drawn on the grid, is the feature. Two units that start with equal weights and equal biases get equal updates forever, which is why training starts from small random weights.
Why equal units stay equal
If rows $i$ and $k$ of $W$ are equal and $c_i=c_k$, then $p(h_i=1\mid x)=p(h_k=1\mid x)$ for every image $x$.
The CD increments of the two rows use only these probabilities and the images $\tilde x^{(0)}$ and $\tilde x^{(k)}$, so they are equal, and the rows are still equal after the step.
By induction they stay equal: two units doing one job. Small random starting weights make the rows differ, and training then pushes them towards different features.
A small run in the spirit of the lecture's digit example: six hidden units trained by CD-1 on six shapes of the digit 2, weights drawn as images with white large. $\textcolor{#8250df}{h_1}$ and $\textcolor{#8250df}{h_6}$ look like the 2s that touch the top edge; $h_2$, $h_3$ and $h_5$ like those moved down a row.
Looks like this, but is not
A hidden unit with a large positive weight on a pixel turns that pixel on whenever the unit is on.
It adds $w_{ij}$ to the pixel's input, but the bias and the other units add theirs. In the running machine, $h_1$ alone gives pixel 1 probability $0.7311$; with $h_2$ also on, $w_{21}=-1$ pulls it down to $0.5000$.
image x
pixel 1
pixel 2
pixel 3
$000$
$0.3471$
$0.6184$
$0.3471$
$001$
$0.2075$
$0.6894$
$0.5818$
$010$
$0.4048$
$0.7107$
$0.4048$
$011$
$0.2421$
$0.7464$
$0.6164$
$100$
$0.5818$
$0.6894$
$0.2075$
$101$
$0.4048$
$0.7107$
$0.4048$
$110$
$0.6164$
$0.7464$
$0.2421$
$111$
$0.4538$
$0.7944$
$0.4538$
Whatever goes in, pixel 2 comes back likely on, and the end pixels follow the stroke the image resembles most.
The image each hidden unit of the running machine likes best
In the running machine, which image makes $h_1$ most likely to be on, and with what probability? Which image does $h_2$ prefer?
FindThe best image for each unit and its probability.
Given
row 1 of $W$: $(2,1,-1)$, $c_1=-1$
row 2 of $W$: $(-1,1,2)$, $c_2=-1$
Solution
The input is a sum of separate terms, one per pixel, so each pixel can be decided on its own: no search over the 8 images is needed.
Decide pixel by pixel for h1
$$a_1(x)=-1+2x_1+x_2-x_3$$
Pixel $j$ adds $w_{1j}$ if it is on and nothing if it is off.
$$x_1=1,\ x_2=1,\ x_3=0\ \Rightarrow\ a_1=2$$
Turn on the pixels with positive weight and leave off the one with negative weight.
Symmetry check: the gap is its own mirror image, and its reconstruction is symmetric, $0.4048$ at both ends.
The stroke keeps its shape, with pixel 3 low, but the gap is filled in: its missing middle pixel comes back at 0.71 and its ends fade to 0.40. An image close to one stroke comes back as that stroke; one that favours neither, like the gap, comes back as an even blend with only the middle pixel likely on.
Checkpoint
§13.6 — the image a unit likes best
A hidden unit of an RBM trained on $3\times3$ images has the weights below, row by row, and bias $c_i=-9$.
Find(a) Which image makes $h_i$ most likely to fire, and with what probability?
Given
$w_{i,(r,s)}$ by rows: $(2,-1,2)$, $(-1,3,-1)$, $(2,-1,2)$
$c_i=-9$
Hint 1/4
Each pixel adds its own weight when it is on, so decide pixel by pixel.
Hint 2/4
$a_i(x)=c_i+\sum_{r,s}w_{i,(r,s)}x_{r,s}$ is largest when exactly the pixels with positive weight are on.
Hint 3/4
Here the positive weights are the four corners, $2$ each, and the centre, $3$; with $c_i=-9$ the input is $-9+8+3$.
Hint 4/4
So the best image is the X of corners and centre, with $\sigma(2)=0.8808$.
Show solution
The input splits into one term per pixel, so the signs of the weights decide.
Pick the pixels
$$x_{r,s}=1\iff w_{i,(r,s)}>0:\ \text{corners and centre}$$
A pixel with a negative weight can only lower the input.
Input and probability
$$a_i=-9+4(2)+3=2,\quad\sigma(2)=0.8808$$
Sum of the kept weights plus the bias.
Answer $$\boxed{\text{X},\ \ 0.8808}$$
Check
Neighbouring images do worse: all four corners without the centre give $\sigma(-1)=0.2689$, all nine pixels $\sigma(-2)=0.1192$.
The feature image of a unit is the sign pattern of its weights.
⚠ Reading a column of W as a feature image
A column is also a list of weights, but it belongs to one pixel and runs over the hidden units.
wrong$$\text{feature of }h_1=(w_{11},w_{21})=(2,-1)$$
right$$\text{feature of }h_1=(w_{11},w_{12},w_{13})=(2,1,-1)$$
⚠ Starting all weights at the same value
Zero looks like the neutral, fair start, favouring no unit.
wrong$$W^{(0)}=0\ \Rightarrow\ \text{the units specialize during training}$$
right$$\text{equal rows at the start stay equal: start small and random}$$
Step through: a 3, never seen in training, switches on $h_1$ and $h_6$, and the reconstruction from those two units is a 2: 5 of the 30 pixels change.
At the edges
a training 2 28 of 30 pixels kept
The top-aligned square 2 switches on the same two units and comes back almost unchanged.
a 3 25 of 30 pixels kept
The right-hand stroke of the lower half goes and a left-hand one appears: the network sees every image as a 2, as in the lecture.
13.7Deep networks: stack RBMs and train them one layer at a time
Train an RBM on the pixels, feed its hidden activations to the next RBM as data, and repeat; the stack classifies and generates.
The hidden layer of one RBM is itself a vector of binary units, so it can serve as the visible layer of another.
MethodMethod 13.7: Deep network and layer-by-layer training
Conditions
layers $x$, $\boldsymbol h_1$, $\boldsymbol h_2$, $\boldsymbol h_3$; a bold $\boldsymbol h$ is a whole layer, an italic $h_i$ one unit
each pair of neighbouring layers has its own weights, trained as an RBM by contrastive divergence
$$\boxed{\begin{aligned}&p(x,\boldsymbol h_1,\boldsymbol h_2,\boldsymbol h_3)=p(\boldsymbol h_3,\boldsymbol h_2)\,p(\boldsymbol h_1\mid\boldsymbol h_2)\,p(x\mid\boldsymbol h_1)\\&\text{(1) CD on }(x,\boldsymbol h_1)\text{, then fix these weights}\\&\text{(2) data for layer 2: }p(\boldsymbol h_1\mid x)\text{ or samples of it}\\&\text{(3) CD on }(\boldsymbol h_1,\boldsymbol h_2)\text{, then fix}\\&\text{(4) repeat up to the top pair}\end{aligned}}$$
The top two layers form an ordinary RBM; below it each layer is generated from the layer above by sigmoid conditionals. Training runs bottom up: an RBM on the pixels first, then its activations, or samples of them, become the training images of the next RBM, and so on. Each RBM only ever sees the layer below it.
The lecture's digit network: $\textcolor{#1f6feb}{784}$ pixels, two layers of 500 units, and a top RBM of 2000 units joined to the second layer and to $\textcolor{#d1690a}{10}$ label units. The numbers beside the links count the weights.
Looks like this, but is not
The stack's joint is the product of its RBMs' joints: $p(x,\boldsymbol h_1)\,p(\boldsymbol h_1,\boldsymbol h_2)\,p(\boldsymbol h_2,\boldsymbol h_3)$.
That counts $\boldsymbol h_1$ and $\boldsymbol h_2$ twice and does not even add up to $1$. The lecture keeps one RBM at the top and only downward conditionals below: $p(\boldsymbol h_3,\boldsymbol h_2)\,p(\boldsymbol h_1\mid\boldsymbol h_2)\,p(x\mid\boldsymbol h_1)$.
link
trained as
weights
pixels to layer 1
RBM 1, first
$392\,000$
layer 1 to layer 2
RBM 2, on the activations of RBM 1
$250\,000$
layer 2 and labels to layer 3
RBM 3, the top RBM, last
$1\,020\,000$
total
$1\,662\,000$
The top RBM holds 61% of the weights, and it is the only link that stays undirected.
Counting the weights of the lecture's digit network
The lecture's network reads $28\times28$ pixel images and has layers of 500, 500 and 2000 units; the top layer is also joined to 10 label units. How many weights does it have, and which link holds most of them?
Every link joins every unit of one layer to every unit of the next, so each link holds a product of two layer sizes.
Link by link
$$x\text{ to }\boldsymbol h_1:\ 784\times500=392\,000$$
One weight per pixel and first-layer unit.
$$\boldsymbol h_1\text{ to }\boldsymbol h_2:\ 500\times500=250\,000$$
Same count for the second RBM.
$$(\boldsymbol h_2,\text{labels})\text{ to }\boldsymbol h_3:\ (500+10)\times2000=1\,020\,000$$
The top RBM's visible layer is the 500 units of $\boldsymbol h_2$ plus the 10 labels.
Total
$$392\,000+250\,000+1\,020\,000=1\,662\,000$$
Plus one bias per unit, $784+500+500+10+2000=3\,794$.
Answer $$\boxed{1\,662\,000\text{ weights, }61\%\text{ in the top RBM}}$$
Check
Rough count: about $0.4+0.25+1.0\approx1.7$ million, the same size. The top link is the largest because it is the only one with 2000 units on one side.
Counting weights is layer size times layer size, link by link; do not forget the labels in the top RBM.
Generating an image from a two-layer stack
Stack the running machine under a top RBM whose layer $\boldsymbol h_2$ has a single unit, joined to the two units of $\boldsymbol h_1$ by weights $(2,-2)$, all top biases $0$. Start the top chain at $\boldsymbol h_1=10$, run one top Gibbs step, then generate the pixels.
FindThe sampled $\boldsymbol h_2$, the new $\boldsymbol h_1$ and the generated image.
Given
top RBM: weights $(2,-2)$ between $\boldsymbol h_2$ and the two units of $\boldsymbol h_1$, biases $0$
bottom: the running machine, $W=\begin{bmatrix}2&1&-1\\-1&1&2\end{bmatrix}$ and $b=(-1,0,-1)$
uniforms: $0.95$ for $\boldsymbol h_2$, $(0.70,\ 0.20)$ for $\boldsymbol h_1$, $(0.40,\ 0.15,\ 0.60)$ for $x$
Solution
Generation follows the factorization from the top: the top RBM is sampled by its own Gibbs chain, and then each lower layer is drawn from its conditional.
Consistency: $011$ is also the single most likely image given $\boldsymbol h_1=01$, with probability $0.7311^2\times0.8808=0.4707$: the unit that is on draws its own feature.
Generation runs top down: sample the top RBM, then one conditional per layer below it.
Checkpoint
§13.7 — the training data of the second RBM
A deep network is trained layer by layer. The first RBM, between the pixels $x$ and $\boldsymbol h_1$, has been trained by CD and its weights are now fixed.
Find(a) What does the RBM between $\boldsymbol h_1$ and $\boldsymbol h_2$ use as its training data?
Given
training images $x^1,\dots,x^N$
the first RBM's weights, fixed
Hint 1/4
Ask which layer plays the role of the visible layer for the second RBM.
Hint 2/4
Step (2) of Method 13.7: the second RBM's data come from the first RBM's hidden layer.
Hint 3/4
Here the first RBM is fixed, so for each training image $x^n$ it gives $p(\boldsymbol h_1\mid x^n)$, or a 0/1 sample of it.
Hint 4/4
The second RBM trains on these $N$ vectors of layer 1.
Show solution
The second RBM's visible layer is $\boldsymbol h_1$, so its data must be values of $\boldsymbol h_1$.
Push the images up
$$x^n\ \mapsto\ p(\boldsymbol h_1\mid x^n)\ \text{ or a sample of it}$$
The first RBM's conditional turns each image into a layer-1 vector.
Train
$$\text{CD on }(\boldsymbol h_1,\boldsymbol h_2)\text{ with these }N\text{ vectors}$$
Exactly Method 13.4, one layer higher.
Answer $$\boxed{p(\boldsymbol h_1\mid x^n)\text{ or samples of it}}$$
Check
Dimension check: the second RBM has as many visible units as $\boldsymbol h_1$ has units, 500 in the lecture's network, not 784.
Each RBM in the stack is trained on the layer directly below it.
⚠ Training every layer on the pixels
The pixels are the only data we were given, so it seems every RBM must see them.
wrong$$\text{RBM 2 trained on the images }x$$
right$$\text{RBM 2 trained on }p(\boldsymbol h_1\mid x)\text{ or samples of it}$$
⚠ Leaving the labels out of the top count
The labels sit beside $\boldsymbol h_2$ in the drawing and look like a separate part.
wrong$$500\times2000=1\,000\,000$$
right$$(500+10)\times2000=1\,020\,000$$
Conditionals by hand
A question gives $W$, $b$, $c$ and one layer's values and asks for the other layer's probabilities or a sample.
Pick the line of W
Hidden unit $i$: row $i$ of $W$ and $c_i$. Pixel $j$: column $j$ of $W$ and $b_j$.
Add
The bias plus the weights of the units that are on; units that are off contribute nothing.
Squash
$\sigma(a)=1/(1+e^{-a})$; use $\sigma(-a)=1-\sigma(a)$ to halve the table you need.
Combine or sample
Multiply across units for a whole pattern; set a unit to $1$ when its uniform number is below its probability.
Where it goes wrong
A row read as a column, or the other way round.
The visible bias added to a hidden unit.
The probability of $0$ reported instead of the probability of $1$.
One CD-1 update by hand
A question gives a machine, a training image, uniform numbers and a step size, and asks for the update.
Positive phase
$p(h_i=1\mid x^t)$ for every hidden unit; keep these numbers.
Hidden sample
Turn them into $\tilde h^{(0)}$ with the first uniforms.
Reconstruction
$p(x_j=1\mid\tilde h^{(0)})$ for every pixel, then $\tilde x^{(1)}$ with the next uniforms.
Negative phase
$p(h_i=1\mid\tilde x^{(1)})$ for every hidden unit.
The training image used in the negative statistic.
Hidden probabilities fed into $p(x\mid h)$ in place of the 0/1 sample.
Reconstruction minus data instead of data minus reconstruction.
Comparing two images without Z
A question asks which of two images is more probable, or by what factor.
Inputs
$a_i(x)=c_i+\sum_jw_{ij}x_j$ for both images.
Free energies
$F(x)=-b^Tx-\sum_i\log\big(1+e^{a_i(x)}\big)$.
Ratio
$p(x)/p(x')=e^{F(x')-F(x)}$: the image with the lower free energy is the more probable one.
Where it goes wrong
The $1$ inside $\log(1+e^{a})$ dropped.
The sign of $-b^Tx$ lost.
The exponent written as $F(x)-F(x')$, which inverts the ratio.
A two-class naive Bayes posterior is a sigmoid
A naive Bayes classifier on 3 binary pixels has two classes with prior $\tfrac12$ each and the feature rates below. Find $p(y=1\mid110)$ by Bayes' rule and as a sigmoid of the log-odds.
Find$p(y=1\mid110)$.
Given
$\theta_{j1}=p(x_j=1\mid y=1)=(0.75,\ 0.6,\ 0.4)$
$\theta_{j0}=p(x_j=1\mid y=0)=(0.25,\ 0.4,\ 0.6)$
Solution
Bayes' rule gives the number; writing it as a log-odds shows its shape.
Odds check: class 1 is favoured $0.2700/0.0400=6.75$ to 1, and $6.75/7.75=0.8710$.
A two-class naive Bayes posterior is a sigmoid of a weighted sum of the pixels.
One RBM hidden unit's probability is a sigmoid
In the running machine, find $p(h_1=1\mid110)$.
Find$p(h_1=1\mid110)$.
Given
row 1 of $W$: $(2,1,-1)$
$c_1=-1$
Solution
Theorem 13.2 applies directly: one row, one bias, one sigmoid.
Input
$$a_1=-1+2+1=2$$
Row 1 at the pixels that are on.
Sigmoid
$$\sigma(2)=0.8808$$
The logistic function of the input.
Answer $$\boxed{p(h_1=1\mid110)=0.8808}$$
Check
The conditionals table lists the same value for $110$.
An RBM hidden unit's probability is a sigmoid of a weighted sum of the pixels.
Both answers are a sigmoid of a bias plus weights on the ink pixels. Naive Bayes gets its weights by counting labelled images and has one label; the RBM learns its weights without labels and has many hidden units reading the same pixels without talking to each other.
How to tell them apart
Ask whether the variable on the other side is observed in training. An observed class label, one variable: naive Bayes, posterior by Bayes' rule. Never observed, many binary units: an RBM, one sigmoid per unit.
Layer-2 data as activation probabilities
Use the running machine as the first layer of a deep network. Build the second layer's training data from the images $110$, $011$ and $111$ using activations.
FindThree vectors of $\boldsymbol h_1$.
Given
the running machine: rows $(2,1,-1)$ and $(-1,1,2)$, $c=(-1,-1)$
images $110,\ 011,\ 111$
Solution
Step (2) of Method 13.7 allows the activations $p(\boldsymbol h_1\mid x)$ directly.
The values for $110$ and $011$ are mirror images, as the machine is.
Activations keep the first layer's uncertainty, but they are not binary.
Layer-2 data as samples
Use the running machine, rows $(2,1,-1)$ and $(-1,1,2)$ with $c=(-1,-1)$, as the first layer of a deep network. Build the second layer's training data from the images $110$, $011$ and $111$ by sampling, with the uniforms $(0.30,\ 0.55)$, $(0.80,\ 0.10)$ and $(0.20,\ 0.90)$, one pair per image.
FindThree binary vectors of $\boldsymbol h_1$.
Given
the running machine: rows $(2,1,-1)$ and $(-1,1,2)$, $c=(-1,-1)$
On average the samples track the activations: over the three images unit 1 is on 0.67 of the time against a mean activation of 0.63.
Samples are binary like real data, at the price of noise.
Both build the second RBM's training set from the first RBM's view of the images; activations are smooth numbers between 0 and 1, samples are 0/1 vectors whose average is the activation.
How to tell them apart
The lecture allows either. Activations give a less noisy training set; samples keep the next layer's data binary, which is what an RBM's visible units are.
Scaffolding comes off
The common skeleton
Positive phase: $p(h_i=1\mid\tilde x^{(0)})=\sigma\big(c_i+\sum_jw_{ij}\tilde x^{(0)}_j\big)$ for every hidden unit.
Hidden sample: unit $i$ is $1$ if its uniform number is below $p(h_i=1\mid\tilde x^{(0)})$.
Reconstruction: $p(x_j=1\mid\tilde h^{(0)})=\sigma\big(b_j+\sum_iw_{ij}\tilde h^{(0)}_i\big)$, then sample $\tilde x^{(1)}$ the same way.
Negative phase: $p(h_i=1\mid\tilde x^{(1)})$ for every hidden unit.
Increments: data statistic minus reconstruction statistic for every $w_{ij}$, $b_j$ and $c_i$; then add $\eta$ times each.
1 · fully worked
CD-1 on a two-pixel, two-unit machine
Train the machine below on $x^t=10$ with CD-1 and $\eta=0.5$. The uniforms are $(0.6,\ 0.3)$ for the hidden sample and $(0.2,\ 0.05)$ for the pixels.
Signs agree with the story: the reconstruction added pixel 2, which the data lacked, so $b_2$ and both weights into pixel 2 fall.
Every parameter tied to a pixel the reconstruction added and the data lacked goes down.
2 · you write the reasoning
Easier: one hidden unit, and this time you write the reasons. Machine $w=(2,-1)$, $b=(0,0)$, $c=-1$, trained on $x^t=10$ with CD-1 and $\eta=0.1$; uniforms $0.5$ for $h$ and $(0.4,\ 0.2)$ for the pixels. For each line, write in the empty column why it is allowed.
reasoning
The positive phase: the hidden input is $c$ plus the weights of the pixels that are on, here only $w_1=2$.
reasoning
Sampling rule: the unit is on because its uniform number is below its probability.
reasoning
With $h=1$ each pixel gets its bias plus its weight to $h$: $0+2$ and $0-1$.
reasoning
Both uniforms fall below their probabilities, so both pixels come out on.
reasoning
The negative phase uses the reconstruction $11$: $-1+2-1=0$.
reasoning
Data statistic minus reconstruction statistic: $0.7311\cdot1-0.5\cdot1$ and $0.7311\cdot0-0.5\cdot1$ for the weights, pixel values for $b$, hidden probabilities for $c$.
3 · find the buried error
Harder, with two errors buried in the solution. A student runs CD-1 on the machine $W=\begin{bmatrix}1&2&-1\\-2&1&1\end{bmatrix}$, $b=(0,-1,0)$, $c=(-1,0)$, with $x^t=011$, uniforms $(0.3,\ 0.5)$ for the hidden sample and $(0.6,\ 0.2,\ 0.9)$ for the pixels. Which two steps are wrong?
The input of $h_2$ uses the visible bias $b_2=-1$ instead of the hidden bias $c_2=0$, so $p(h_2=1\mid011)$ comes out 0.7311 instead of $\sigma(2)=0.8808$.
$b$ and $c$ sit side by side in the question, and $b_2$ has the same index as the unit.
right
With $\sigma(2)=0.8808$ the sample is still $h_2=1$, but row 2 of $\Delta W$ becomes $(0.0000,\ 0.1497,\ 0.8808)$ and $\Delta c_2=0.1497$.
⚠ step 5
The visible increments are reversed: $\Delta b=\tilde x^{(1)}-\tilde x^{(0)}$ was used.
The weights were done in the right order, and the short bias line is written in the order the chain produced the images.
right
$\Delta b=\tilde x^{(0)}-\tilde x^{(1)}=(0,0,1)$: pixel 3 was on in the data and off in the reconstruction, so $b_3$ rises. With both errors fixed, $\Delta W=\begin{bmatrix}0.0000&-0.2311&0.5000\\0.0000&0.1497&0.8808\end{bmatrix}$ and $\Delta c=(-0.2311,\ 0.1497)$.
4 · the bare problem
§13.4 — a CD-1 update from scratch
An RBM with 2 pixels and 2 hidden units is trained on the image $x^t=11$ with CD-1 and step size $\eta=0.2$.
uniforms: $(0.8,\ 0.4)$ for the hidden sample, $(0.3,\ 0.7)$ for the pixels
Hint 1/4
You need the data statistics, then one sampled round trip to a reconstruction, then the reconstruction statistics.
Hint 2/4
$\Delta w_{ij}=p(h_i=1\mid\tilde x^{(0)})\tilde x^{(0)}_j-p(h_i=1\mid\tilde x^{(1)})\tilde x^{(1)}_j$, with $\Delta b$ and $\Delta c$ the same differences; sample a unit as $1$ when $u<p$.
Hint 3/4
Here $p(h\mid11)=(\sigma(2),\sigma(0))=(0.8808,\ 0.5)$, so with $(0.8,\ 0.4)$ the sample is $11$; then $p(x\mid11)=(\sigma(-1),\sigma(3))=(0.2689,\ 0.9526)$ and $(0.3,\ 0.7)$ give $\tilde x^{(1)}=01$, with $p(h\mid01)=(0.7311,\ 0.7311)$.
Hint 4/4
So $\Delta W=\begin{bmatrix}0.8808&0.1497\\0.5000&-0.2311\end{bmatrix}$, $\Delta b=(1,0)$, $\Delta c=(0.1497,\ -0.2311)$, and the parameters move by $0.2$ times these.
Show solution
Method 13.4 with $k=1$; all probabilities are single sigmoids, so no $Z$ is needed.
Column 2 of $\Delta W$ holds the only negative entry, $\Delta w_{22}$: pixel 2 is on in both images, so its column compares the two hidden probabilities, and only $h_2$ was likelier on the reconstruction.
When a pixel is on in both images, its weights move by the change in the hidden probabilities alone.
Full exam-style question
RBM exam question: energy, conditionals, free energy and one CD-1 stepexam format
An RBM has 3 pixels and 2 hidden units, with the parameters below. (a) Compute $E(101,11)$. (b) Compute $p(h\mid101)$. (c) Which of $101$ and $110$ is more probable, and by what factor? (d) Carry out one CD-1 step on $x^t=101$. (e) Why is the exact gradient not used for $784$-pixel images?
FindThe energy, two hidden probabilities, a probability ratio, the CD-1 increments and a one-line reason.
This machine is small enough to list: $p(110)=0.3657$ and $p(101)=0.1455$, whose ratio is 2.5135, as in (c); and $110$, where the chain landed in (d), is the machine's most probable image.
A full RBM question is four one-line computations and one sentence; the only trap is the bookkeeping of rows, columns and biases.
Practice
A · concept 4 questions
1§13.2 — independent hidden units
A classmate reasons: no edge joins two hidden units of an RBM, so the hidden units are independent and $p(h)=\prod_ip(h_i)$.
Find(a) True or false: $p(h)=\prod_ip(h_i)$ in every RBM.
Givenan RBM: edges only between the two layers
Hint 1/4
Separate two claims: independence given the pixels, and independence with the pixels summed out.
Hint 2/4
Separation gives $p(h\mid x)=\prod_ip(h_i\mid x)$; the marginal $p(h)=\sum_xp(x)\,p(h\mid x)$ is a mixture of such products.
Hint 3/4
Here, in the running machine, $p(h_1=1)=p(h_2=1)=0.5201$ while $p(h_1=1,h_2=1)=0.2290$.
Hint 4/4
The product would be $0.2706$, so the statement is false.
Show solution
One machine where the product fails refutes a claim about every RBM.
Marginals
$$p(h_1=1)=0.2912+0.2290=0.5201$$
Add the patterns with $h_1=1$; $h_2$ is the same by symmetry.
The two units are less often on together than independence predicts.
Answer $$\boxed{\text{False}}$$
Check
The four values of $p(h)$ add up to $1$, and they come from $e^{c^Th}\prod_j(1+e^{b_j+\sum_iw_{ij}h_i})/Z$, a route that never uses the product rule.
Independence given the other layer is all an RBM promises.
2§13.3 — what is cheap in a large RBM
An RBM has 784 pixels and 500 hidden units, and one training image is given.
Find(a) Which of these can be computed exactly in a fraction of a second?
Given
$m=784$, $n=500$
one training image $x^t$
Hint 1/4
For each option, count how many configurations the computation has to visit.
Hint 2/4
Anything that needs $Z$ visits all $2^{m+n}$ configurations; conditionals given one layer need one sigmoid per unit.
Hint 3/4
Here $2^{1284}$ configurations for $Z$ against $500$ sigmoids for $p(h\mid x^t)$.
Hint 4/4
Only the hidden probabilities of the given image are cheap.
Show solution
The cost of a quantity is the number of configurations it sums over.
Conditionals
$$p(h_i=1\mid x^t)=\sigma(a_i(x^t)):\ 500\text{ sigmoids of }784\text{ terms}$$
No $Z$: it cancels in the ratio.
Everything with Z
$$Z,\ p(x^t),\ \nabla l:\ \text{sums over }2^{784}\approx10^{236}\text{ images}$$
Even with the free energy trick, the sum over $x$ remains.
Answer $$\boxed{p(h\mid x^t)}$$
Check
At a billion terms per second, $10^{236}$ terms take about $10^{227}$ seconds, against $500\times784$ multiplications for the conditionals.
In an RBM, whatever needs $Z$ is out of reach and whatever conditions on a layer is cheap.
3§13.5 — the average CD-1 step
A student claims that contrastive divergence with $k=1$ is an unbiased stochastic gradient: its step is random, but on average it equals the gradient of $\log p(x^t)$.
Find(a) True or false: the average CD-1 step equals the gradient.
GivenCD-1: $\tilde x^{(1)}$ one Gibbs step from $x^t$
Hint 1/4
Ask from which distribution the reconstruction is drawn, and from which one the gradient's model term averages.
Hint 2/4
The model term averages under $p(x)$; CD-1's reconstruction is drawn one step from $x^t$, which equals $p(x)$ only as $k\to\infty$.
Hint 3/4
Here, in the running machine at $110$, the average CD-1 step for $w_{11}$ is $0.3816$ while the gradient is $0.5534$.
Hint 4/4
The two differ, so the statement is false.
Show solution
Fact 13.5 says they agree only in the limit; one exact comparison shows the gap.
Term by term: the model turns pixel 1 on only 0.6727 of the time against always in the data, and it has $h$ and pixel 1 on together 0.3995 of the time against 0.7311 in the data, so both gradients must be positive.
Write the model term as a short sum over the images with the pixel on.
5§13.4 — a CD-1 step with one hidden unit
An RBM with 2 pixels and one hidden unit takes one CD-1 step on the image $x^t=01$, with $\eta=0.1$.
Find
(a) Find $\tilde h^{(0)}$ and $\tilde x^{(1)}$.
(b) Find $\Delta w$, $\Delta b$, $\Delta c$ and the new $w_{12}$.
Given
$w=(1,2)$, $b=(-1,0)$, $c=0$
$x^t=01$, $\eta=0.1$
uniforms: $0.3$ for $h$, $(0.6,\ 0.9)$ for the pixels
Hint 1/4
Run the chain once, data to hidden to pixels to hidden, keeping every probability.
Hint 2/4
Unit on when $u<p$; $\Delta w_j=p(h=1\mid\tilde x^{(0)})\tilde x^{(0)}_j-p(h=1\mid\tilde x^{(1)})\tilde x^{(1)}_j$.
Hint 3/4
Here $p(h=1\mid01)=\sigma(2)=0.8808$ gives $h=1$ with $u=0.3$; then $p(x\mid h=1)=(\sigma(0),\sigma(2))=(0.5,\ 0.8808)$ and $(0.6,\ 0.9)$ give $00$; and $p(h=1\mid00)=0.5$.
Hint 4/4
So $\Delta w=(0,\ 0.8808)$, $\Delta b=(0,1)$, $\Delta c=0.3808$ and $w_{12}\to2.0881$.
Show solution
Method 13.4 with one hidden unit: four sigmoids in all.
The four transitions out of $10$ add up to $1$: $0.1309+0.0907+0.5380+0.2404=1$.
Most of this chance comes through $h=0$, the route that forgets the image.
7§13.7 — sizing a smaller deep network
A deep network in the style of the lecture's reads $16\times16$ binary images, has layers of 100 and 50 units, and a top RBM of 200 units joined to layer 2 and to 10 label units.
Find
(a) How many weights does each link have, and how many in total?
(b) How many visible units does the second RBM have, and what are its training data?
Counted from the other side: each of the 100 first-layer units has 256 weights, each of the 50 second-layer units 100, and each of the 200 top units $50+10$: $25\,600$, $5\,000$ and $12\,000$ again.
Every link is a product of two layer sizes, and every RBM's data are the layer below.
C · exam level 4 questions
1§13.2 — pixels given the hidden layer
The lecture derives $p(h_i=1\mid x)$ from the energy. Derive the other conditional in the same way.
Find
(a) Show that $p(x_j=1\mid h)=\sigma\big(b_j+\sum_iw_{ij}h_i\big)$.
(b) Show that the pixels are independent given $h$.
Given
$E(x,h)=-h^TWx-b^Tx-c^Th$
$x_j,h_i\in\{0,1\}$
Hint 1/4
Fix $h$ and all pixels but one, and look at how the energy depends on that one pixel.
Hint 2/4
A conditional is a ratio of joint probabilities, so $Z$ cancels: $p(x_j=1\mid h,x_{-j})=\dfrac{e^{-E(x_j=1)}}{e^{-E(x_j=1)}+e^{-E(x_j=0)}}$.
Hint 3/4
Here the terms of $-E$ with $x_j$ are $x_j\big(b_j+\sum_iw_{ij}h_i\big)$; every other term is the same in the numerator and the denominator.
Hint 4/4
So the ratio is $\sigma\big(b_j+\sum_iw_{ij}h_i\big)$, which does not involve $x_{-j}$: the pixels are independent given $h$.
Show solution
Mirroring Theorem 13.2's proof with the layers swapped is shorter than summing over images.
Numerical check on the running machine: for $h=10$ the formula gives $(\sigma(1),\sigma(1),\sigma(-2))$, and the joint route gave the same $p(110\mid h)$ in the conditionals block.
Linearity of the energy in each unit is what turns every conditional into a sigmoid.
2§13.4 — reading a CD-1 update
One CD-1 step on the running machine starts at the data image $011$ and produces the reconstruction $010$. The hidden probabilities are listed below.
A parameter decreases when its reconstruction statistic exceeds its data statistic; go through the pixels one at a time.
Hint 2/4
$\Delta w_{ij}=p(h_i=1\mid011)\tilde x^{(0)}_j-p(h_i=1\mid010)\tilde x^{(1)}_j$, $\Delta b_j=\tilde x^{(0)}_j-\tilde x^{(1)}_j$, $\Delta c_i$ the difference of the hidden probabilities.
Hint 3/4
Here pixel 1 is off in both images; pixel 2 is on in both, so $\Delta w_{12}=0.2689-0.5$ and $\Delta w_{22}=0.8808-0.5$; pixel 3 is on only in the data; and $\Delta c=(-0.2311,\ 0.3808)$.
Hint 4/4
Only $w_{12}$ and $c_1$ come out negative.
Show solution
Sorting pixels into on in both, on in one, off in both settles most signs without arithmetic.
Story check: the data is the right stroke; the reconstruction dropped its right end, so the right-stroke unit's parameters rise and the left-stroke unit loses its hold on the middle pixel.
In a CD step, a pixel that is on in both images moves its weights by the change in hidden probabilities alone.
3§13.7 — training and generating with a deep network
A deep network reads $20\times20$ images and has hidden layers of 300 and 300 units and a top RBM of 1000 units joined to layer 2 and to 10 label units.
Find
(a) Count the weights of each link and the total.
(b) In what order are the RBMs trained, and on what data?
(c) Once the top RBM has produced a sample of $\boldsymbol h_2$, which conditionals produce an image, in what order?
Treat the stack as three RBMs, each seeing only the layer below it, and read generation off the factorization.
Hint 2/4
The factorization $$p(x,\boldsymbol h_1,\boldsymbol h_2,\boldsymbol h_3)=p(\boldsymbol h_3,\boldsymbol h_2)\,p(\boldsymbol h_1\mid\boldsymbol h_2)\,p(x\mid\boldsymbol h_1)$$ and, for the counts, weights per link are products of layer sizes.
Hint 3/4
Here $400\times300$, $300\times300$ and $(300+10)\times1000$.
Hint 4/4
So $120\,000+90\,000+310\,000=520\,000$ weights; train bottom up; generate top down with $p(\boldsymbol h_1\mid\boldsymbol h_2)$ then $p(x\mid\boldsymbol h_1)$.
Show solution
Method 13.7 gives the training order; the factorization gives the generation order.
Answer $$\boxed{520\,000\text{ weights};\ \text{train bottom up; generate top down}}$$
Check
Count the top link from the other side: each of the 1000 top units connects to $300+10$ units below, $310\,000$ in all, the same number.
Training climbs the stack, generation descends it.
4§13.5 — the bias of CD-2 on a one-pixel machine
A machine has one pixel and one hidden unit with $w=3$, $b=-1$ and $c=-1$, and is trained on $x^t=1$.
Find
(a) Find $T(1\mid0)$ and $T(0\mid1)$.
(b) Find the stationary $\pi(1)$ and check it against $p(x=1)$ from the free energy.
(c) Find the exact gradient $\partial l/\partial w$ and the average CD-2 step.
Given
$w=3$, $b=-1$, $c=-1$
$x^t=1$
Hint 1/4
Treat the chain on the single pixel as a two-state Markov chain and use the closed forms of the one-pixel example.
Hint 2/4
$T(1\mid0)=\sum_hp(h\mid0)p(x=1\mid h)$; $\pi(1)=\frac{T(1\mid0)}{T(1\mid0)+T(0\mid1)}$; $\mathbb E[\text{CD-}k]=\nabla l\,(1-\lambda^k)$ with $\lambda=1-T(1\mid0)-T(0\mid1)$.
Hint 3/4
Here $p(h=1\mid0)=\sigma(-1)$, $p(h=1\mid1)=\sigma(2)$, $p(x=1\mid h=0)=\sigma(-1)$, $p(x=1\mid h=1)=\sigma(2)$, which give $T(1\mid0)=0.4335$ and $T(0\mid1)=0.1921$.
Hint 4/4
So $\pi(1)=0.6929$, $\nabla l=0.2705$, $\lambda=0.3744$ and the average CD-2 step is $0.2326$.
Show solution
Two states make every quantity a closed form, exactly as in the one-pixel worked example.
The responsibility of component 1 for the image $11$, from Theorem 13.2.
Answer $$\boxed{p(h=1)=0.5000,\ \text{rates }0.2689\text{ and }0.7311,\ p(11)=0.3034,\ p(h=1\mid11)=0.8808}$$
Check
Through the free energy, $p(11)=e^{-F(11)}/Z=0.3034$, and Bayes' rule, $\frac{0.5\cdot0.7311^2}{0.3034}=0.8808$, matches the sigmoid.
An RBM with $n$ hidden units is a mixture of $2^n$ product distributions whose weights and rates share parameters.
3§13.5 — how many samples for one average
To check CD's model statistic for one weight, a student averages $p(h_i=1\mid x)\,x_j$ over $N$ images drawn independently from the model by long Gibbs chains.
Find(a) How large must $N$ be by Hoeffding's inequality?
Given
each term lies in $[0,1]$
target: within $0.05$ of the true average with probability at least $0.95$
Hint 1/4
You need a bound on the chance that an average of bounded independent terms misses its mean.
Hint 2/4
Hoeffding: for $N$ independent terms in $[0,1]$, $P(\lvert\bar Y-\mu\rvert\ge\varepsilon)\le2e^{-2N\varepsilon^2}$.
Hint 3/4
Here $\varepsilon=0.05$ and the allowed failure probability is $0.05$: solve $2e^{-2N(0.05)^2}\le0.05$.
Hint 4/4
So $N\ge\ln(40)/0.005=737.78$, that is $N=738$.
Show solution
Hoeffding needs only boundedness and independence, both of which hold here.
Divide $\ln(2/0.05)=\ln40$ by $2\varepsilon^2=0.005$.
Answer $$\boxed{N=738}$$
Check
Plug back: $2e^{-2(738)(0.0025)}=0.0499\le0.05$, while $N=737$ gives 0.0502.
CD-1 uses a single sample per training image, so its model statistic is far noisier than this; it relies on many small steps averaging out.
4§13.3 — observed minus predicted, twice
A logistic regression with $P(Y=1\mid x)=\sigma(\beta_0+\beta_1x)$ and an RBM are both trained by gradient ascent on a log-likelihood. Compare one gradient of each.
Find
(a) Compute the gradient of the logistic log-likelihood with respect to $\beta_1$.
(b) Compute $\partial l/\partial b_1$ for the RBM.
(c) Which of the two predicted terms needs a sum over all inputs, and why?
Given
logistic model: $\beta=(-1,\ 2)$, one example $x=1$, $y=1$
RBM: the running machine at $x^t=110$, where $\sum_xp(x)x_1=0.4128$
Hint 1/4
Both gradients have the shape observed minus predicted; find what plays each role in each model.
An undirected model of binary visible and hidden units with edges only between the two layers; $p(x,h)=e^{-E(x,h)}/Z$.
visible unitgörünür birim
A unit whose value is observed, such as a pixel; its bias is $b_j$.
hidden unitgizli birim
A binary unit that is never observed; given the visible units it is on with probability $\sigma(c_i+\sum_jw_{ij}x_j)$.
iki parçalı çizge
A graph whose nodes split into two groups with edges only between the groups, never inside one.
free energyserbest enerji
$F(x)=-b^Tx-\sum_i\log(1+e^{a_i(x)})$, with $p(x)=e^{-F(x)}/Z$; lower free energy, more probable image.
stochastic gradient ascent
Updating the parameters along the gradient of the log-likelihood of one randomly chosen example: $\theta\leftarrow\theta+\eta\nabla l$.
positive phase
The data half of the gradient: statistics such as $p(h_i=1\mid x^t)\,x^t_j$ with the training image clamped.
negative phase
The model half of the gradient: the same statistics averaged under the model, or at the end of CD's chain.
contrastive divergence
Training that replaces the model average of the gradient by the statistics of a $k$-step Gibbs chain started at the training image; CD-k.
Gibbs örneklemesi
Drawing from a joint distribution by resampling variables from their conditionals in turn; in an RBM, a whole layer at a time.
Markov chainMarkov zinciri
A sequence of random states in which each state depends only on the one before it, through fixed transition probabilities.
transition probabilitygeçiş olasılığı
$T(x'\mid x)$, the probability that one step of the chain moves from $x$ to $x'$.
stationary distributiondurağan dağılım
A distribution that one step of the chain leaves unchanged; for the Gibbs chain of an RBM it is $p(x,h)$.
feature detector
A hidden unit whose weights, drawn on the pixel grid, form the pattern that turns it on.
simetri kırılması
Starting units with different, small random weights so that training can make them learn different features.
derin inanç ağı
A stack of layers with an RBM on top and downward sigmoid conditionals below, trained one layer at a time; the lecture's deep network.
Training a deep network one RBM at a time from the bottom, each on the activations of the layer below, with lower weights fixed.
activationaktivasyon
Here the probability $p(h_i=1\mid x)$ that a hidden unit is on, used as data for the next layer.
What comes next
§14 · Reinforcement learning
Here a model learned what images look like from the images alone. Next, a learner acts, and the only signal it gets is a reward for what it did.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, so no section numbers are cited here.
course materialEEE 485 lecture slides and lecture notes, chapter 13: Restricted Boltzmann Machine and Deep Learning Scope, order and notation (x, h, W, b, c, E, Z, F, the CD chain, the increments, the layers h1 to h3) follow these materials; the explanations, machines, numbers, figures and exercises here are original.
course materialEEE 485 lecture slides, chapter 12: naive Bayes classifier The naive Bayes model recalled in the comparison with the RBM.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights and the weekly topic list.
standard resultLogistic function, Gibbs sampling, two-state Markov chains, Hoeffding's inequality Standard results used in the derivations. All machines, numbers and figures were computed for this page by exact enumeration.