6  The restricted Boltzmann machine: one wall falls, one we walk around

Recommended reading

Core (~1 h). Hinton (2002) — the contrastive-divergence paper and the products-of-experts framing (an RBM is a product of experts, one per hidden unit). Read the CD section, which this lecture makes precise. Alongside it, Mehta et al. (2019), §VII — the physicist’s account of the RBM, the factorized conditionals, and CD, in the course’s notation; our derivation follows its logic.

Optional background. Smolensky (1986) — the original “harmonium,” the RBM before it had the name, worth reading for the bipartite idea in its birthplace; Hinton (2012) — the engineering companion, CD-\(k\) in practice and the gap between clean theory and what actually trains; Hinton and Salakhutdinov (2006) — the stacked-RBM result in Science that reignited deep learning, the historical culmination of today’s machinery; MacKay (2003), Ch. 43, for the maximum-likelihood gradient done carefully.

Prerequisite reminder. All of Chapter 5 — the model, the two-phase gradient Equation 5.4, hidden units and the two-expectation problem, and the \(2^N\) ledger — plus the logistic-conditional fact from Section 5.3 and the free energy \(F = -T\log Z\) from Week 1. New today: conditional independence from graph structure, block Gibbs sampling, a closed-form marginal free energy, and the CD-\(k\) approximation with a quantitative account of its bias.

6.1 Two walls, one already read

The previous lecture ended with a learning rule and two walls. ① The learning rule: \(\Delta \theta \propto \langle \cdot \rangle_\text{data} - \langle \cdot \rangle_\text{model}\), transparent and exact. ② With hidden units, the positive phase is no longer a lookup: it clamps the visibles and averages over \(p(h \mid v)\) — intractable for a general graph. ③ The negative phase is \(\nabla_\theta \log Z\), a sum over \(2^N\) configurations — intractable regardless of architecture. One wall falls to a theorem; the other we walk around by approximation, and a central question of the lecture is why a short chain is allowed at all.

Smolensky (1986) built the bipartite machine first, inside the connectionist collection that named the era, and called it the harmonium — the restricted Boltzmann machine before it had the name. Hinton (2002) gave it a fast training rule, contrastive divergence, as a by-product of a more general framework (products of experts: the RBM’s hidden units multiply together like independent critics, one constraint each). And in 2006 the combination broke through: Hinton and Salakhutdinov (2006) stacked RBMs, trained them greedily layer by layer with CD, and used the stack to initialize a deep autoencoder that outperformed PCA, published in Science. That result, with its companion deep-belief-net paper (Hinton, Osindero, and Teh 2006), is widely credited with reigniting deep learning, and the architecture we derive today is where it started.

Forbidding within-layer connections makes inference exact and sampling fast; computing \(Z\) remains intractable, so we approximate the one average we cannot take and accept a known bias for a workable algorithm.

Take-home 1

An RBM is a Boltzmann machine with the within-layer couplings removed. The restriction makes \(p(h \mid v)\) factorize, giving an exact positive phase and layer-parallel sampling, while \(Z\) remains as intractable as in the previous lecture.

6.2 Restrict versus approximate

The two moves are independent ideas of opposite character: one exact, one approximate.

The first move is architectural, and exact. Remove the visible–visible and hidden–hidden couplings, and — as we prove in a moment — given one layer, the units of the other become conditionally independent: the clamped positive phase collapses to a formula, and a whole layer can be resampled in a single parallel step. This costs expressivity at a fixed number of hidden units — with enough of them a single RBM can approximate any distribution over binary vectors (Le Roux and Bengio 2008) — and it is exact. Stacking, historically, bought hierarchical features more efficiently than width.

The second move is algorithmic, and biased. No architecture computes \(Z\) — the negative phase still demands equilibrium samples from the model. Contrastive divergence does not wait for equilibrium: it runs the sampler a few steps from the data and uses whatever it reaches. That is a workaround, and its bias is real; we will quantify it below. Note the independence of the two ideas: CD would apply to any Boltzmann machine; the bipartite structure is what makes CD’s Gibbs steps inexpensive and the positive phase exact. The two ideas combine well, but neither requires the other.

Figure 6.1 draws both moves. On the left, the bipartite graph: a visible layer \(v\) carrying the data, a hidden layer \(h\), couplings \(W_{ij}\) only between the layers, and the forbidden within-layer edges crossed out; those crosses define the restriction. On the right, the consequence: the block-Gibbs ladder \(v^{(0)} \to h^{(0)} \to v^{(1)} \to h^{(1)} \to \cdots\), each arrow resampling one full layer from its factorized conditional. Factorization is a statement about the left half; contrastive divergence is a statement about the right half, namely how far up the ladder the chain is run.

Figure 6.1: Left: the bipartite cut — visible units \(v\) (biases \(a_i\)), hidden units \(h\) (biases \(b_j\)), weights \(W_{ij}\) only between the layers; the crossed-out within-layer edges are the restriction that gives the RBM its name and all of its tractability. Right: the block-Gibbs ladder — because each layer is conditionally independent given the other, the alternating chain \(v^{(0)} \to h^{(0)} \to v^{(1)} \to \cdots\) resamples a whole layer per arrow. The data sit at \(v^{(0)}\); the one-step reconstruction is \(v^{(1)}\); the true negative phase lives at the far, equilibrium end of the ladder — and CD-\(k\) stops climbing after \(k\) rungs.

6.3 Bipartite structure and its consequences

The previous lecture’s obstacle: the hidden-unit positive phase needed \(p(h \mid v)\), intractable on a general graph. The least structure we can remove to make that conditional trivial is the set of within-layer edges, for the following reason.

Setup, with a convention shift flagged. RBM units are binary \(\{0, 1\}\) — active or silent — rather than the \(\pm 1\) spins of Weeks 2–3. This is the convention of the entire RBM literature, so we adopt it; the affine map \(s = 2v - 1\) converts one convention to the other, renormalizing couplings and shuffling constants into the biases (mix the two silently and it is precisely the biases that get corrupted). With visible biases \(a_i\), hidden biases \(b_j\), and a weight matrix \(W_{ij}\), the energy is

\[ E(v, h) \;=\; -\sum_i a_i v_i \;-\; \sum_j b_j h_j \;-\; \sum_{ij} v_i\, W_{ij}\, h_j \tag{6.1}\]

RBM energy

— no \(v_i v_{i'}\) terms, no \(h_j h_{j'}\) terms. The key observation is immediate: for fixed \(v\), this energy is linear in \(h\) (and symmetrically, for fixed \(h\), linear in \(v\)). Group the \(h\)-dependent terms accordingly,

\[ E(v, h) \;=\; -\sum_i a_i v_i \;-\; \sum_j c_j(v)\, h_j, \qquad c_j(v) \;=\; b_j + \sum_i v_i W_{ij}, \]

\(c_j(v)\): the effective field on hidden unit \(j\)

where \(c_j(v)\) collects everything hidden unit \(j\) feels — its bias plus the weighted activity of the visible layer.

The conditional factorizes. Compute \(p(h \mid v)\) head-on. The factor \(e^{\sum_i a_i v_i}\) is common to numerator and denominator and cancels; what remains splits per hidden unit, because both the exponential of a sum and the sum over \(h \in \{0,1\}^{n_h}\) factorize:

\[ p(h \mid v) \;=\; \frac{e^{\sum_j c_j h_j}}{\sum_{h'} e^{\sum_j c_j h_j'}} \;=\; \prod_j \frac{e^{c_j h_j}}{\underbrace{\textstyle\sum_{h_j' \in \{0,1\}} e^{c_j h_j'}}_{=\; 1 + e^{c_j}}} \;=\; \prod_j p(h_j \mid v). \]

Reading off the \(h_j = 1\) entry, and running the identical algebra with the roles of the layers exchanged:

\[ \boxed{\; p(h_j = 1 \mid v) \;=\; \sigma\Big( b_j + \sum_i v_i W_{ij} \Big), \qquad p(v_i = 1 \mid h) \;=\; \sigma\Big( a_i + \sum_j W_{ij} h_j \Big). \;} \tag{6.2}\]

RBM conditionals

In words: given the other layer, each unit is an independent logistic neuron — the sigmoid of Section 5.3, a conditional Boltzmann probability for one two-state degree of freedom in the field of its neighbors, now sitting inside a learning machine. Conditional independence follows from the bipartite cut, and the next three paragraphs use it.

The positive phase is exact. Clamp \(v\) to a data point. Because the \(h_j\) are independent given \(v\), the conditional expectation needs no sum over hidden configurations at all: \(\langle v_i h_j \rangle_{h \mid v} = v_i\, \sigma(c_j(v))\), a number. Averaging it over the training set gives the clamped average of Section 5.6, an expectation under \(p_\text{data}(v)\, p(h \mid v)\): each data point supplies the visibles, and the model’s conditional supplies the hidden units, which the data do not contain. It is therefore not a plain data average, and we keep the subscript clamped to say so:

\[ \langle v_i h_j \rangle_\text{clamped} \;=\; \frac{1}{D} \sum_{d} v_i^{(d)}\, \sigma\big( c_j(v^{(d)}) \big) \tag{6.3}\]

exact positive phase

— no sampling, no \(Z\), cost linear in the dataset. The wall the previous lecture raised for the general graph is gone, by structure. (This is also the general two-phase gradient of Section 5.6 specialized to the RBM: \(\partial L/\partial W_{ij} = \langle v_i h_j \rangle_\text{clamped} - \langle v_i h_j \rangle_\text{model}\), with the first bracket now a formula. Much of the RBM literature writes this bracket \(\langle v_i h_j \rangle_\text{data}\); it is the same quantity.)

Block Gibbs sampling. The same independence makes the sampler fast: draw all of \(h\) from \(p(h \mid v)\) in one parallel step (\(n_h\) independent coin flips with probabilities \(\sigma(c_j)\)), then all of \(v\) from \(p(v \mid h)\), and alternate — the ladder of Figure 6.1. Each half-update resamples a block of variables from its exact conditional, which leaves the joint \(p(v, h) = e^{-E}/Z\) invariant (resampling \(h\) from \(p(h \mid v)\) cannot change a distribution that already factorizes as \(p(v)\,p(h \mid v)\) — the one-line stationarity argument; irreducibility and aperiodicity hold as in Section 5.3 since every conditional probability is strictly positive). This is Glauber’s dynamics (Glauber 1963) upgraded from one spin per move to one layer per move — the sampler that every downstream method, starting with CD, relies on.

Tracing out the hidden layer. The factorized sum that gave the conditionals also yields a result of directly statistical-mechanical character. Sum the joint weight over all hidden configurations — the same per-unit split as before:

\[ \sum_h e^{-E(v, h)} \;=\; e^{\sum_i a_i v_i} \prod_j \sum_{h_j \in \{0,1\}} e^{c_j(v)\, h_j} \;=\; e^{\sum_i a_i v_i} \prod_j \big( 1 + e^{c_j(v)} \big), \]

so the marginal distribution of the visibles is exactly Boltzmann in an effective energy, \(p(v) = e^{-F(v)}/Z\), with

\[ F(v) \;=\; -\sum_i a_i v_i \;-\; \sum_j \operatorname{softplus}\Big( b_j + \sum_i v_i W_{ij} \Big), \qquad \operatorname{softplus}(x) = \log(1 + e^x). \tag{6.4}\]

RBM free energy

Physically, \(F(v) = -\log \sum_h e^{-E(v,h)}\) is a free energy — we integrated out the hidden (“fast”) degrees of freedom to obtain an effective theory over the visible (“slow”) ones, the same coarse-graining move statistical mechanics makes whenever it trades microscopic detail for an effective potential. Each hidden unit contributes one softplus term — Figure 6.2 draws the function and the landscape it builds — and the softplus realizes the claim of the previous lecture: \(c_j(v)\) is linear in \(v\), but \(\operatorname{softplus}\) is not, and expanding it generates products of visibles of every order up to \(n_v\). The effective higher-order interactions that motivated hidden units are now explicit and computable in one line.

The contrast is immediate. \(F(v)\) is a closed-form expression — evaluate it at any \(v\) in microseconds. The normalizer \(Z = \sum_v e^{-F(v)}\) is a sum over \(2^{n_v}\) visible configurations — as intractable as ever. Everything about this model is computable except its normalizer.

Show code 
fig, (a1, a2) = plt.subplots(1, 2, figsize=(10.4, 3.9), width_ratios=[1, 1.25])
xx = np.linspace(-6, 6, 400)
a1.plot(xx, np.log1p(np.exp(xx)), color=NAVY, lw=2.5)
a1.plot(xx, np.where(xx > 0, xx, 0), color=GRAY, ls="--", lw=1.2)
a1.text(-5.4, 0.55, "asymptote $0$:\nunit silent", color=GRAY, fontsize=10)
a1.text(3.4, 1.2, "asymptote $x$:\nunit active", color=GRAY, fontsize=10)
a1.annotate("the crossover carries\nthe nonlinearity and the\ninduced interactions",
            xy=(0, 0.69), xytext=(-5.4, 3.0), color=ORANGE, fontsize=10,
            arrowprops=dict(arrowstyle="->", color=ORANGE, lw=1))
a1.set_xlabel(r"input $c_j(v)$"); a1.set_ylabel(r"$\operatorname{softplus}(c_j)$")

order = np.argsort(F)
lbl = ["".join(str(int(x)) for x in V[c]) for c in order]
colors = [ORANGE if l in ("1100", "0011") else NAVY for l in lbl]
a2.bar(range(16), F[order], color=colors)
a2.set_xticks(range(16), lbl, rotation=90, fontsize=8.5)
a2.axhline(0, color="k", lw=0.8)
a2.annotate("the two data patterns:\ndeepest free energy, $F=-3.15$",
            xy=(0.5, -3.05), xytext=(3.2, -2.75), color=ORANGE, fontsize=10.5,
            arrowprops=dict(arrowstyle="->", color=ORANGE, lw=1))
a2.set_xlabel(r"visible state $v$ (sorted by $F$)"); a2.set_ylabel(r"$F(v)$")
fig.tight_layout(); plt.show()
Figure 6.2: The coarse-graining, drawn. Left: \(\operatorname{softplus}(x) = \log(1+e^x)\), the effective potential a single hidden unit contributes to \(F(v)\) once traced out — flat (\(\approx 0\)) when its input is strongly negative, linear (\(\approx x\)) when strongly positive, with the crossover at \(c_j = 0\) carrying all the nonlinearity (and hence all the induced higher-order interactions among the visibles). Right: the free energy Equation 6.4 of the small RBM of Section 6.6, evaluated in closed form at all \(2^4 = 16\) visible states: the two data patterns \((1100)\) and \((0011)\) are the two deepest states at \(F = -3.15\). Every bar is a microsecond’s arithmetic; the sum \(Z = \sum_v e^{-F(v)}\) over the bars is what remains intractable at scale.
Trap

Conditional independence is not marginal independence. \(p(h \mid v)\) factorizes; \(p(v)\), \(p(v, h)\), and above all \(Z\) do not — the visibles are strongly coupled through the hidden units they share (that coupling is the model’s entire expressive power), and \(Z\) is still a sum over exponentially many states. A common error is to claim that the RBM’s partition function factorizes.

6.4 Contrastive divergence: approximating the negative phase

The RBM’s structure fixed the positive phase; the negative phase \(\langle v_i h_j \rangle_\text{model}\) is untouched — it wants an average over the free-running model, which means block Gibbs run to equilibrium, at every gradient step, on a landscape that (Week 2) may mix exponentially slowly. The question Hinton (2002) asked is what happens if we run the ladder only a little?

The CD-\(k\) rule. Start the Gibbs chain at a data point — not at a random state — and climb \(k\) rungs of the ladder: \(v^{(0)} = v_\text{data} \to h^{(0)} \to v^{(1)} \to \cdots \to v^{(k)}\). Then estimate the negative phase from where the chain got to:

\[ \boxed{\; \Delta W_{ij} \;\propto\; \big\langle v_i\, h_j \big\rangle_\text{clamped} \;-\; \big\langle v_i\, h_j \big\rangle_{v^{(k)}} \;} \tag{6.5}\]

contrastive-divergence (CD-\(k\)) update

with both brackets evaluated by the exact formula Equation 6.3 (using the hidden probabilities \(\sigma(c_j)\) rather than sampled \(h_j\) cuts variance at no cost in expectation — standard practice (Hinton 2012)). CD-1 — one up–down–up pass — is the workhorse: the negative sample is the model’s one-step reconstruction of the data, and the update pushes energy down at the data and up at the reconstruction. Figure 6.3 places the move on the free-energy landscape, and against the previous lecture’s global picture.

Figure 6.3: What CD-1 actually does, drawn on the visible free-energy landscape \(F(v)\) — compare Figure 5.2, where the negative phase pushed up at all the model’s modes. CD starts at the data, takes one Gibbs step, and pushes up at the resulting reconstruction: a local negative phase, applied where the model’s probability mass sits near the data. If the model is right, the step doesn’t move (\(v^{(1)} \approx v^{(0)}\)) and the two arrows cancel. The bias is drawn in gray: a distant spurious mode that equilibrium sampling would find and suppress is never visited by a short chain — CD’s bias lives exactly there.

Why the chain starts at the data. Two arguments support the choice. The first is practical: a chain started at the data begins in a high-probability region of a reasonable model, so \(k\) Gibbs steps produce a locally equilibrated sample, far better than \(k\) steps from a random state, which would still be essentially noise. The second is structural: if the model reproduced the data distribution exactly, the data would already be an equilibrium sample, one Gibbs step would leave its distribution unchanged, the two brackets in Equation 6.5 would agree in expectation, and the update would vanish. This needs a condition: the model class must contain \(p_\text{data}\), so that the maximum-likelihood solution is \(p_\text{data}\) itself; only then is it a fixed point of CD. At a generic maximum-likelihood optimum the model matches only the statistics its energy can express, the moment matching of Equation 5.6, so the data are not an equilibrium sample of it. The exact gradient vanishes there, but the one-step negative phase of Equation 6.5 need not equal the model average, and the CD update does not vanish; this residual is the bias discussed next. When the model is wrong, one step moves the data toward the model’s nearby samples, and CD raises the energy precisely there: the negative phase is sampled near the data rather than over the model’s whole support.

The bias. CD is biased, and the bias is structural; three results make this precise. First, the CD-\(k\) update is not the gradient of the log-likelihood: the true negative phase averages over the model everywhere; CD’s averages only over what a \(k\)-step chain reaches (the gray mode of Figure 6.3 is real, and a landscape’s distant spurious modes are exactly the states a short chain does not reach). Hinton’s own motivation — that CD-\(k\) approximately descends the contrastive objective \(D_\mathrm{KL}(p_0 \| p_\infty) - D_\mathrm{KL}(p_k \| p_\infty)\), the amount by which \(k\) Gibbs steps move the data distribution toward the model — is illuminating but heuristic, and he said so (Hinton 2002). Second, it is not the gradient of that objective either, nor of any objective: Sutskever and Tieleman (2010) showed the CD update is not the gradient of any function at all — there is no hidden loss being optimized. Third, the effect is measurable: the fixed points of CD learning differ from the maximum-likelihood solutions, an effect analyzed and quantified on exactly-solvable small models by Carreira-Perpiñán and Hinton (2005) — whose diagnosis is also the reassurance: the bias is usually small, shrinks as \(k\) grows (as \(k \to \infty\) the chain equilibrates and CD-\(k\) is maximum likelihood), and rarely matters for learning good features, though it does distort the learned distribution.

The standard modern mitigation is persistent CD (Tieleman 2008), which keeps a set of “fantasy” chains running across parameter updates — never resetting to the data — so the negative-phase samples track the slowly moving model far better than a freshly truncated chain, at essentially no extra cost. (The chains stay approximately equilibrated because each parameter update moves the model only slightly — an adiabatic argument a physicist will recognize.)

Trap

CD never computes \(Z\) — and never estimates it. It sidesteps the negative-phase expectation by sampling; the normalizer itself is untouched, unknown, and unknowable at scale. Corollary: you cannot evaluate the likelihood of a trained RBM either — training monitors proxies (reconstruction error, pseudo-likelihood), and a low reconstruction error is not a high likelihood: a model can reconstruct data beautifully while assigning most of its probability mass to configurations that never appear in its reconstructions. Mistaking the proxy for the objective is the standard failure mode of energy-based practice. (Estimating \(Z\) when it truly matters is typically done by annealed importance sampling, part of Week 11’s fluctuation-theorem machinery.)

Take-home 2

Contrastive divergence estimates the negative phase from a short Gibbs chain started at the data. It replaces an unbiased but intractable gradient with a biased but tractable one; the bias is real (CD is not maximum likelihood, not even the gradient of any objective, and its fixed points differ), shrinks with \(k\), and is reduced by persistent chains. CD never computes \(Z\).

6.5 From workaround to revival

RBM pretraining explains why a superseded model still occupies a week of the course.

Through the 1990s and early 2000s, deep fully connected networks proved very hard to train by backpropagation alone, because the gradient vanished through many layers (convolutional networks such as LeNet were the notable exception). The RBM + CD combination broke the deadlock from an unexpected side. Hinton and Salakhutdinov (2006) trained a stack of RBMs greedily — each layer learned, by CD, to model the hidden activities of the layer below — then unrolled the stack into a deep autoencoder and fine-tuned; the pretrained network compressed images and documents better than PCA, and, decisively, trained at all. The companion paper (Hinton, Osindero, and Teh 2006) built generative deep belief nets the same way. For roughly five years, greedy layer-wise unsupervised pretraining — with RBMs or, in parallel, with autoencoders (Bengio et al. 2007; Vincent et al. 2008) — was the standard way to train deep fully connected networks — until better activations, initializations, optimizers, and GPUs (circa 2012) made the scaffolding unnecessary, and the field moved on.

The current status, then: as production models, RBMs and CD are historical — you will not deploy one. We spend a week on them because they are the cleanest setting for ideas the course cannot do without: energy-based learning, the two-phase gradient, the \(Z\) obstruction, sampling as the consequence of normalization, and contrastive estimation — the move of pitting data against the model’s own samples, which echoes through noise-contrastive estimation, GAN discriminators, and the negative sampling of modern representation learning. The RBM is to energy-based learning what the Ising model is to phase transitions: nobody’s production system, everybody’s understanding.

In practice, for feature learning, CD-1 is usually enough — its bias barely touches the filters. For generation, use CD-\(k\) with \(k\) in the tens, or better, persistent CD. Sample the hidden states when they are driven by the data — the stochastic binary bottleneck is what stops each hidden unit from passing more than a bit, and all-probabilities chains collapse into deterministic mean-field fixed points — but use probabilities, not samples, for the visible reconstructions and for the hidden activities that enter the final gradient statistics. Monitor reconstruction error and pseudo-likelihood knowing they are proxies, and watch for the signature failure where reconstruction keeps improving while the model’s samples degrade. All of it is systematized in Hinton (2012). (Two asides: real-valued data uses Gaussian-visible RBMs, so binary units are a modelling choice; and the closed-form \(F(v)\) makes a trained RBM usable as a classifier by comparing free energies of label-conditioned configurations.)

6.6 Example: watching the bias

We take an RBM small enough to enumerate, so that the CD bias becomes visible; in any real application it is hidden, because seeing it requires the very sum CD exists to avoid. Take \(n_v = 4\) visible and \(n_h = 3\) hidden units: \(2^{4+3} = 128\) joint states, comfortably inside the enumerable region of the previous lecture’s ledger (Section 5.7). The machine is hand-built to be legible: hidden unit 1 is tuned to the pattern “left pair on” (\(W_{\cdot 1} = (2, 2, -2, -2)\)), hidden unit 2 to “right pair on” (\(W_{\cdot 2} = (-2, -2, 2, 2)\)), hidden unit 3 weakly coupled (\(W_{\cdot 3} = (0.5, -0.5, 0.5, -0.5)\)); biases \(a_i = -0.3\), \(b = (-1, -1, 0)\). The dataset is six points in two clusters — four copies of \((1,1,0,0)\), two of \((0,0,1,1)\). This is a machine already well adapted to its data: brute force gives \(Z = 98.9\), and the two data patterns are the two lowest-free-energy states of Figure 6.2, each carrying \(p(v) = 0.236\) of the model’s mass — though note the model splits its mass symmetrically while the data arrive 4 : 2, so there is still something to learn, and the exact gradient will point at it.

For the single weight \(W_{11}\) (first visible unit, first hidden unit), the table lists how each bracket of Equation 6.5 is obtained:

quantity how computed cost value
positive phase \(\langle v_1 h_1 \rangle_\text{clamped}\) formula Equation 6.3 exact, \(\mathcal{O}(D\, n_v n_h)\) \(0.635\)
negative phase \(\langle v_1 h_1 \rangle_\text{model}\) brute force, \(128\) states exact, \(\mathcal{O}(2^{n_v + n_h})\) \(0.352\)
CD-1 estimate \(\langle v_1 h_1 \rangle_{v^{(1)}}\) one Gibbs step from the data approximate, \(\mathcal{O}(D\, n_v n_h)\) \(0.490\)

(For the CD row we tabulate the expected CD-1 estimate — the data distribution propagated exactly through one block-Gibbs step, so the number is deterministic; a sampled run scatters around it.) Across the table, the positive phase is the truth — exact by Equation 6.3, at trivial cost; e.g. clamping \(v = (1,1,0,0)\) gives \(\sigma(c_1) = \sigma(3) = 0.95\), hidden unit 1 all but certainly on. The middle row is the quantity CD avoids: at \(128\) states we can enumerate it; at \(128\) units we cannot. And the CD-1 row approximates the middle row while leaning toward the first: one Gibbs step has not carried the data far into the model, and the reconstruction statistics remain close to the data. The resulting gradients: exact, \(0.635 - 0.352 = +0.283\); CD-1, \(0.635 - 0.490 = +0.145\). The CD-1 gradient has the right sign at half the size: it learns in the correct direction and undershoots, which is very much its general character.

As the chain climbs the ladder, the bias drains: Figure 6.4 plots the expected CD-\(k\) estimate against \(k\), sliding from the data value at \(k = 0\) (the estimate before any Gibbs step is the positive phase) to the exact negative phase as \(k \to \infty\):

\(k\) expected CD-\(k\) estimate bias
\(1\) \(0.490\) \(+0.138\)
\(2\) \(0.446\) \(+0.094\)
\(5\) \(0.394\) \(+0.042\)
\(10\) \(0.364\) \(+0.012\)
\(20\) \(0.353\) \(+0.001\)

The decay is controlled by the chain’s mixing: this machine’s couplings (\(|W| = 2\)) carve two well-separated modes, and a chain started in one takes many rungs to visit the other in fair proportion — the previous lecture’s second obstruction, sampling hardness, controlling the size of CD’s bias. Strengthen the couplings and the bias at fixed \(k\) grows; this is the toy version of why CD struggles precisely on the strongly structured models one most wants.

Show code 
# exact block-Gibbs transition matrix on the visibles: T[v, v'] = sum_h p(h|v) p(v'|h)
ph_v = np.prod(sig(C)[:, None, :] ** H[None, :, :]
               * (1 - sig(C))[:, None, :] ** (1 - H[None, :, :]), axis=2)   # 16 x 8
Ah = H @ W.T + a
pv_h = np.prod(sig(Ah)[:, None, :] ** V[None, :, :]
               * (1 - sig(Ah))[:, None, :] ** (1 - V[None, :, :]), axis=2)  # 8 x 16
T = ph_v @ pv_h

E = np.array([[-(v @ a) - (h @ b) - v @ W @ h for h in H] for v in V])
p_joint = np.exp(-E) / np.exp(-E).sum()
neg_exact = np.einsum("vh,vi,hj->ij", p_joint, V, H)[0, 0]                  # 0.352

p0 = np.zeros(2**nv)                                     # empirical data distribution
for d in data:
    p0[int(sum(int(x) << i for i, x in enumerate(d)))] += 1 / len(data)

ks = np.arange(0, 31)
est, pk = [], p0.copy()
for k in ks:
    est.append(np.einsum("v,v,v->", pk, V[:, 0], sig(C)[:, 0]))
    pk = pk @ T
est = np.array(est)

fig, ax = plt.subplots(figsize=(8.4, 4.3))
ax.plot(ks, est, "o-", color=ORANGE, lw=1.8, ms=5)
ax.axhline(neg_exact, color=NAVY, ls="--", lw=1.8)
ax.annotate(rf"true negative phase $\langle v_1 h_1\rangle_\mathrm{{model}} = {neg_exact:.3f}$"
            "\n(brute force, 128 states)", xy=(20, neg_exact), xytext=(13, 0.42),
            color=NAVY, fontsize=10.5,
            arrowprops=dict(arrowstyle="->", color=NAVY, lw=1))
ax.annotate(r"$k=0$: the positive phase itself, $0.635$", xy=(0, est[0]),
            xytext=(2.5, 0.64), color=GRAY, fontsize=10.5,
            arrowprops=dict(arrowstyle="->", color=GRAY, lw=1))
ax.annotate(rf"CD-1: ${est[1]:.3f}$ — right direction," "\nhalf the gradient",
            xy=(1, est[1]), xytext=(4.5, 0.53), color=ORANGE, fontsize=10.5,
            arrowprops=dict(arrowstyle="->", color=ORANGE, lw=1))
ax.set_xlabel(r"Gibbs steps $k$")
ax.set_ylabel(r"expected CD-$k$ estimate of $\langle v_1 h_1\rangle$")
ax.set_xlim(-0.8, 30.5); ax.set_ylim(0.33, 0.67)
fig.tight_layout(); plt.show()
Figure 6.4: The CD-\(k\) bias, exactly, on the enumerable RBM of this section (\(n_v = 4\), \(n_h = 3\); \(Z = 98.9\)). Orange: the expected CD-\(k\) estimate of the negative phase \(\langle v_1 h_1 \rangle\), computed by propagating the data distribution through \(k\) exact block-Gibbs steps (no sampling noise). At \(k = 0\) the estimate is the positive phase itself (\(0.635\)); as \(k \to \infty\) the chain equilibrates onto the true negative phase (\(0.352\), navy dashed). CD-1 stops one rung up the ladder at \(0.490\) — right direction, roughly half the true gradient — and the bias decays with \(k\) at a rate set by how fast the chain mixes between the machine’s two modes. On this toy the whole curve is accessible; on a real model, only the chosen \(k\).

The conditionals factorize; the partition function does not — that gap is exactly what we approximate.

Take-home 3

On a brute-forceable RBM all three rows are visible: the positive phase is exact by formula, the negative phase is exact by enumeration, and CD-1 approximates the latter with a bias that leans toward the data — right sign, wrong magnitude, decaying with \(k\) at the chain’s mixing rate. The bias is the measurable consequence of avoiding \(Z\), visible here only because the model is tiny.

6.7 Outlook: where the obstruction stands

The previous lecture derived the learning rule and the obstruction. Today the positive-phase wall fell — to a theorem, the bipartite factorization, at no cost in exactness — and the negative-phase wall was walked around — by contrastive divergence, at the cost of a real, quantified bias. The partition function itself is exactly as intractable as it was in the previous lecture: we have become good at avoiding \(Z\), and no better at computing it. That asymmetry reflects the state of the field, and every module until Week 10 is a better avoidance — mean-field and variational bounds in Module 2, smarter sampling in Module 3.

Next week the energy-based view scales to the present: modern Hopfield networks carry an energy whose capacity is exponential rather than \(0.138\,N\), and whose retrieval update turns out to be exactly the attention mechanism of the transformer. Week 2’s machine never went away; Week 4 makes the connection precise. And Week 10 returns to the point the previous lecture made precise: score matching trades \(\nabla_\theta \log Z\), which is intractable, for \(\nabla_x \log Z\), which is zero (Hyvärinen 2005), and the negative phase disappears.