% ============================================================================
%  Artificial Neural Networks — Methods, Equations and Graphical
%  Representations
%  Author  : Simon-Pierre Boucher — contact@spboucher.ai
%  Chapter 9 : Energy-Based and Associative-Memory Networks
%              (chapters/09-energy.tex)
% ============================================================================
\chapter{Energy-Based and Associative-Memory Networks}\label{chap:energy}

The architectures of the preceding chapters compute by \emph{propagating}
signals through a directed graph. This chapter studies a different
computational metaphor, imported from statistical physics: a network is
assigned a scalar \emph{energy} for every joint configuration of its units,
and computation proceeds by \emph{relaxation} — the state slides downhill
on the energy surface until it settles in a minimum. Memories are not
stored at addresses; they are sculpted into the landscape as attractors,
and retrieval is descent. The deterministic version of this idea is the
Hopfield network \cite{hopfield1982}; its stochastic generalization, the
Boltzmann machine \cite{ackley1985}, turns the energy into a probability
distribution and thereby becomes a trainable generative model. The
restricted Boltzmann machine and its stack, the deep belief network
\cite{hinton2006}, converted these physical ideas into the first practical
recipe for training deep architectures — the spark of the modern deep
learning era.

\section{The Classical Hopfield Network}

\begin{definition}[Hopfield network]\label{def:en-hopfield}
A Hopfield network is a fully connected recurrent network of $N$ binary
units with states $s_i \in \{-1,+1\}$, symmetric coupling weights
$w_{ij} = w_{ji}$, no self-connections ($w_{ii}=0$), and thresholds
$\theta_i$. The network state is the vector
$\vect{s} = (s_1,\dots,s_N)\transp \in \{-1,+1\}^N$.
\end{definition}

Every configuration $\vect{s}$ is scored by the energy function
\begin{equation}
  E(\vect{s})
  \;=\;
  -\frac{1}{2}\sum_{i,j} w_{ij}\, s_i s_j \;+\; \sum_i \theta_i s_i .
  \label{eq:en-hopfield-energy}
\end{equation}
The dynamics are \emph{asynchronous}: at each step a single unit $i$ is
selected (in random or cyclic order) and set to the sign of its local
field,
\begin{equation}
  s_i \;\leftarrow\;
  \operatorname{sign}\!\Bigl(\sum_j w_{ij}\, s_j - \theta_i\Bigr).
  \label{eq:en-hopfield-update}
\end{equation}
The central fact — and the reason the network computes anything at all —
is that this update can only lower the energy.

\begin{theorem}[Energy descent]\label{thm:en-descent}
Under the asynchronous update \eqref{eq:en-hopfield-update} with symmetric
weights and $w_{ii}=0$, the energy \eqref{eq:en-hopfield-energy} never
increases. Since $E$ is bounded below on the finite state space, the
dynamics converge in finitely many steps to a fixed point — a local
minimum of $E$.
\end{theorem}

\begin{proof}
Suppose unit $i$ flips from $s_i$ to $s_i' = -s_i$; all other units are
frozen. Writing $h_i = \sum_j w_{ij}s_j - \theta_i$ for the local field,
the energy change collects exactly the terms involving $s_i$ (symmetry
counts each pair once, and $w_{ii}=0$ removes the diagonal):
$\Delta E = E(\vect{s}') - E(\vect{s}) = -(s_i' - s_i)\,h_i$.
The rule \eqref{eq:en-hopfield-update} flips $s_i$ only when $s_i$ and
$h_i$ disagree, i.e.\ when $s_i' = \operatorname{sign}(h_i)$, so
$(s_i' - s_i)\,h_i = 2\,|h_i| \ge 0$ and $\Delta E \le 0$. A strict flip
with $h_i \neq 0$ strictly decreases $E$; as the state space is finite,
only finitely many strict decreases can occur.
\end{proof}

\subsection{Hebbian storage and capacity}

To turn descent into \emph{recall}, one shapes the landscape so that the
desired memories $\{\vect{\xi}^\mu\}_{\mu=1}^{P}$,
$\vect{\xi}^\mu \in \{-1,+1\}^N$, sit at the bottoms of basins. The
Hebbian (outer-product) prescription is
\begin{equation}
  w_{ij} \;=\; \frac{1}{N}\sum_{\mu=1}^{P} \xi_i^\mu\, \xi_j^\mu ,
  \qquad w_{ii}=0,
  \label{eq:en-hebb}
\end{equation}
which makes each $\vect{\xi}^\mu$ (approximately) a fixed point of
\eqref{eq:en-hopfield-update}: units that fire together are wired
together, so a corrupted probe within a basin is pulled back to the
stored pattern. This is \emph{content-addressable} memory — the query is
a partial or noisy version of the content itself.

\begin{remark}[Capacity and spurious states]\label{rem:en-capacity}
Statistical-mechanics analysis of \eqref{eq:en-hebb} shows that reliable
retrieval survives only up to
\begin{equation}
  P_{\max} \;\approx\; 0.138\, N
  \label{eq:en-capacity}
\end{equation}
stored patterns; for essentially error-free recall the bound tightens to
$N/(2\ln N)$. Beyond capacity, crosstalk between patterns proliferates
\emph{spurious attractors} — mixture states and inverted patterns that
were never stored — and retrieval degrades abruptly (catastrophic
interference).
\end{remark}

\begin{algorithm}[htbp]
\caption{Hopfield network: Hebbian storage and asynchronous recall}
\label{alg:en-hopfield}
\begin{algorithmic}[1]
\Require patterns $\vect{\xi}^1,\dots,\vect{\xi}^P \in \{-1,+1\}^N$;
         probe $\vect{x} \in \{-1,+1\}^N$
\State $w_{ij} \gets \frac{1}{N}\sum_{\mu=1}^{P}\xi_i^\mu \xi_j^\mu$
       for all $i \neq j$; \quad $w_{ii} \gets 0$
       \Comment{storage \eqref{eq:en-hebb}}
\State $\vect{s} \gets \vect{x}$ \Comment{initialize at the probe}
\Repeat
  \State draw a unit index $i$ (random or cyclic sweep)
  \State $h_i \gets \sum_j w_{ij} s_j - \theta_i$
  \State $s_i \gets \operatorname{sign}(h_i)$
         \Comment{energy never increases (Theorem~\ref{thm:en-descent})}
\Until{no unit changed during a full sweep}
\State \Return $\vect{s}$ \Comment{an attractor: ideally the stored
       pattern nearest $\vect{x}$}
\end{algorithmic}
\end{algorithm}

Figure~\ref{fig:en-hopfield} shows the two complementary views of the same
object: the fully connected graph of units, and the energy landscape over
the state space in which the stored patterns are the basins.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
    % ---- left: fully connected 6-unit Hopfield graph (hexagon) ----
    \begin{scope}[local bounding box=graph]
      \foreach \i in {1,...,6}
        \node[nhidden] (s\i) at ({90-(\i-1)*60}:1.9) {$s_{\i}$};
      \foreach \i [evaluate=\i as \nexti using int(\i+1)] in {1,...,5}
        \foreach \j in {\nexti,...,6}
          \draw[black!45, semithick] (s\i) -- (s\j);
      \node[etiquette, sloped, above] at ($(s1)!0.5!(s2)$) {$w_{12}$};
      \node[etiquette, sloped, above] at ($(s2)!0.5!(s3)$) {$w_{23}$};
      \node[etiquette, sloped, below] at ($(s4)!0.5!(s5)$) {$w_{45}$};
    \end{scope}
    \node[etiquette, align=center] at ($(graph.south)+(0,-0.5)$)
      {fully connected, symmetric $w_{ij}=w_{ji}$,\\ no self-loops};

    % ---- right: 1D energy landscape with two basins ----
    \begin{scope}[xshift=6.4cm, yshift=-2.2cm]
      \begin{axis}[
          width=7.2cm, height=5.6cm,
          axis lines=left,
          xlabel={state space (schematic)},
          ylabel={$E(\vect{s})$},
          xtick=\empty, ytick=\empty,
          domain=-2.35:2.45, samples=120,
          ymin=-1.9, ymax=1.4,
          clip=false,
        ]
        \addplot[cmem, very thick] {0.25*x^4 - x^2 + 0.15*x};
        % basin minima near x=-1.49 and x=+1.34
        \node[etiquette, align=center] at (axis cs:-1.49,-1.55)
          {stored pattern $\vect{\xi}^1$};
        \node[etiquette, align=center] at (axis cs:1.34,-1.35)
          {stored pattern $\vect{\xi}^2$};
        % descending ball
        \fill[coutput] (axis cs:-2.18,0.57) circle (2.2pt);
        \node[etiquette, anchor=west] at (axis cs:-1.98,0.85)
          {probe $\vect{x}$};
        \draw[fleche, coutput]
          (axis cs:-2.1,0.32) to[bend left=25] (axis cs:-1.62,-0.85);
      \end{axis}
    \end{scope}
  \end{tikzpicture}
  \caption{The Hopfield network \cite{hopfield1982}. Left: six binary
    units with symmetric all-to-all couplings (a few weights labeled).
    Right: the energy \eqref{eq:en-hopfield-energy} as a landscape over
    the state space; Hebbian storage \eqref{eq:en-hebb} carves one basin
    per memory, and asynchronous updates
    \eqref{eq:en-hopfield-update} roll a noisy probe downhill into the
    nearest attractor.}
  \label{fig:en-hopfield}
\end{figure}

\section{Modern Hopfield Networks}

The classical construction is limited by its $O(N)$ capacity
\eqref{eq:en-capacity}. Modern Hopfield networks \cite{ramsauer2021}
replace binary states by continuous queries $\vect{q} \in \R^{d}$ and the
quadratic energy by a \emph{log-sum-exp} energy over stored patterns
$\mat{X} = [\vect{x}_1,\dots,\vect{x}_P] \in \R^{d\times P}$:
\begin{equation}
  E(\vect{q})
  \;=\;
  -\frac{1}{\beta}\,
  \log \sum_{i=1}^{P} \exp\bigl(\beta\, \vect{x}_i\transp \vect{q}\bigr)
  \;+\; \frac{1}{2}\,\lVert \vect{q}\rVert^2 \;+\; \text{const},
  \label{eq:en-mhn-energy}
\end{equation}
where $\beta > 0$ is an inverse temperature. Minimizing
\eqref{eq:en-mhn-energy} by a concave--convex procedure yields the
strikingly simple fixed-point iteration
\begin{equation}
  \vect{q}^{\mathrm{new}}
  \;=\;
  \mat{X}\,\softmax\bigl(\beta\, \mat{X}\transp \vect{q}\bigr),
  \label{eq:en-mhn-update}
\end{equation}
a convex combination of the stored patterns weighted by their similarity
to the query.

\begin{property}[Exponential capacity, one-step retrieval]
\label{prop:en-mhn}
For patterns placed on a sphere in $\R^d$, the energy
\eqref{eq:en-mhn-energy} admits on the order of $\exp(c\,d)$
well-separated attractors (for a constant $c$ depending on the required
separation), and for well-separated patterns the update
\eqref{eq:en-mhn-update} retrieves the correct pattern to exponentially
small error in a \emph{single} step \cite{ramsauer2021}.
\end{property}

\begin{remark}[Associative memory is attention]\label{rem:en-attention}
Read \eqref{eq:en-mhn-update} with $\vect{q}$ as a query and the columns
of $\mat{X}$ as keys and values: it is exactly the scaled dot-product
attention update of the Transformer, with $\beta = 1/\sqrt{d_k}$.
Retrieval from an associative memory and an attention head are the same
computation — a result that unifies one of the oldest ideas in the field
with one of the newest.
\end{remark}

\section{Boltzmann Machines}

The Hopfield network is deterministic: it can only descend, so it settles
in whichever basin it starts in, and it has no principled notion of
\emph{learning} a data distribution. The Boltzmann machine
\cite{ackley1985} makes two moves. First, units become stochastic, and
the network is augmented with \emph{hidden} units $\vect{h}$ alongside
the \emph{visible} units $\vect{v}$ that carry the data; the energy
$E(\vect{v},\vect{h})$ keeps the quadratic form of
\eqref{eq:en-hopfield-energy} over the concatenated state. Second, the
energy is exponentiated into a Gibbs (Boltzmann) distribution at
temperature $T$:
\begin{equation}
  p(\vect{v},\vect{h})
  \;=\;
  \frac{e^{-E(\vect{v},\vect{h})/T}}{Z},
  \qquad
  Z \;=\; \sum_{\vect{v}',\vect{h}'} e^{-E(\vect{v}',\vect{h}')/T},
  \label{eq:en-bm-gibbs}
\end{equation}
so that low-energy configurations are exponentially more probable. The
network is now a latent-variable generative model, and maximum-likelihood
learning has a beautifully symmetric gradient: for a coupling $w_{ij}$
between any two units $s_i$ and $s_j$,
\begin{equation}
  \frac{\partial \log p(\vect{v})}{\partial w_{ij}}
  \;=\;
  \E\bigl[s_i s_j\bigr]_{\text{data}}
  \;-\;
  \E\bigl[s_i s_j\bigr]_{\text{model}},
  \label{eq:en-bm-grad}
\end{equation}
a \emph{positive phase} that measures correlations with the visibles
clamped to data, minus a \emph{negative phase} that measures the same
correlations under the model's own equilibrium distribution
\eqref{eq:en-bm-gibbs}. Learning stops when the model dreams what it
sees. The catch is the negative phase: equilibrium expectations require
Markov chains run to convergence under an intractable $Z$, which made
general Boltzmann machines impractical for two decades.

\section{Restricted Boltzmann Machines and Contrastive Divergence}

\begin{definition}[Restricted Boltzmann machine]\label{def:en-rbm}
An RBM is a Boltzmann machine whose connectivity graph is
\emph{bipartite}: $n_v$ visible units $\vect{v} \in \{0,1\}^{n_v}$ and
$n_h$ hidden units $\vect{h} \in \{0,1\}^{n_h}$ interact through
$\mat{W} \in \R^{n_v \times n_h}$, with biases $\vect{a}, \vect{b}$ and
\emph{no} intra-layer connections. Its energy is
\begin{equation}
  E(\vect{v},\vect{h})
  \;=\;
  -\vect{a}\transp \vect{v}
  \;-\; \vect{b}\transp \vect{h}
  \;-\; \vect{v}\transp \mat{W}\, \vect{h},
  \label{eq:en-rbm-energy}
\end{equation}
with joint distribution
$p(\vect{v},\vect{h}) = e^{-E(\vect{v},\vect{h})}/Z$ as in
\eqref{eq:en-bm-gibbs} (absorbing $T$ into the parameters).
\end{definition}

Bipartiteness (Figure~\ref{fig:en-rbm}) is precisely what makes the model
usable: conditioned on one layer, the units of the other layer are
independent, and the conditionals factorize into sigmoids,
\begin{align}
  p(h_j = 1 \mid \vect{v})
  &\;=\;
  \sigma\Bigl(b_j + \sum_i v_i\, w_{ij}\Bigr),
  \label{eq:en-rbm-condh}\\
  p(v_i = 1 \mid \vect{h})
  &\;=\;
  \sigma\Bigl(a_i + \sum_j w_{ij}\, h_j\Bigr),
  \label{eq:en-rbm-condv}
\end{align}
with $\sigma(x) = 1/(1+e^{-x})$. An entire layer can therefore be sampled
in one parallel \emph{block Gibbs} step. Marginalizing the hiddens also
gives a closed-form \emph{free energy} for a visible vector,
\begin{equation}
  F(\vect{v})
  \;=\;
  -\vect{a}\transp\vect{v}
  \;-\;
  \sum_{j=1}^{n_h}
  \log\Bigl(1 + e^{\,b_j + \vect{v}\transp \mat{W}_{:j}}\Bigr),
  \qquad
  p(\vect{v}) = \frac{e^{-F(\vect{v})}}{Z},
  \label{eq:en-rbm-free}
\end{equation}
useful for monitoring training. The exact likelihood gradient specializes
\eqref{eq:en-bm-grad} to
\begin{equation}
  \frac{\partial \log p(\vect{v})}{\partial w_{ij}}
  \;=\;
  \E\bigl[v_i h_j\bigr]_{\text{data}}
  \;-\;
  \E\bigl[v_i h_j\bigr]_{\text{model}} .
  \label{eq:en-rbm-grad}
\end{equation}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
    \foreach \j in {1,...,3}
      \node[nhidden] (h\j) at (1.1+\j*1.7, 2.1) {$h_{\j}$};
    \foreach \i in {1,...,4}
      \node[ninput]  (v\i) at (0.25+\i*1.7, 0)   {$v_{\i}$};
    \foreach \i in {1,...,4}
      \foreach \j in {1,...,3}
        \draw[black!45, semithick] (v\i) -- (h\j);
    \node[etiquette, left=3mm of h1] {hidden layer $\vect{h}$};
    \node[etiquette, left=3mm of v1] {visible layer $\vect{v}$};
    \node[etiquette, right=2mm of h3, yshift=-9mm] {$\mat{W}$};
    \node[etiquette, align=center] at (4.2,-0.95)
      {bipartite: no intra-layer connections};
  \end{tikzpicture}
  \caption{The restricted Boltzmann machine
    (Definition~\ref{def:en-rbm}). Visible and hidden units interact
    through $\mat{W}$ only across layers; the missing intra-layer edges
    are what make the conditionals
    \eqref{eq:en-rbm-condh}--\eqref{eq:en-rbm-condv} factorize and block
    Gibbs sampling efficient.}
  \label{fig:en-rbm}
\end{figure}

\subsection{Contrastive divergence}

The negative phase of \eqref{eq:en-rbm-grad} still asks for equilibrium
samples. Contrastive divergence \cite{hinton2002} replaces equilibrium
with \emph{proximity}: run the block Gibbs chain
\begin{equation}
  \vect{v}^{(0)} \xrightarrow{\;p(\vect{h}\mid\vect{v})\;} \vect{h}^{(0)}
  \xrightarrow{\;p(\vect{v}\mid\vect{h})\;} \vect{v}^{(1)}
  \xrightarrow{\;\cdots\;} \vect{v}^{(k)}
  \xrightarrow{\;p(\vect{h}\mid\vect{v})\;} \vect{h}^{(k)}
  \label{eq:en-gibbs-chain}
\end{equation}
for only $k$ steps (typically $k=1$), \emph{started at the data}
$\vect{v}^{(0)}$, and contrast the correlations at both ends:
\begin{equation}
  \Delta w_{ij}
  \;\propto\;
  \bigl\langle v_i h_j \bigr\rangle_{0}
  \;-\;
  \bigl\langle v_i h_j \bigr\rangle_{k}
  \qquad \text{(CD-}k\text{)}.
  \label{eq:en-cdk}
\end{equation}
The estimator is biased — the chain has not mixed — but the bias is small
near the data manifold and the signal is strong enough to train excellent
features; persistent CD further improves the negative samples by never
restarting the chain. Algorithm~\ref{alg:en-cdk} is the chapter's
estimation centerpiece, and Figure~\ref{fig:en-cdk} traces the chain
\eqref{eq:en-gibbs-chain}.

\begin{algorithm}[htbp]
\caption{Contrastive divergence CD-$k$ for one mini-batch (RBM)}
\label{alg:en-cdk}
\begin{algorithmic}[1]
\Require mini-batch $\{\vect{v}_1,\dots,\vect{v}_m\}$, parameters
         $(\mat{W},\vect{a},\vect{b})$, learning rate $\eta$,
         Gibbs steps $k$
\For{$n = 1,\dots,m$}
  \State $\vect{v}^{(0)} \gets \vect{v}_n$
  \State $\hat{\vect{h}}^{(0)} \gets
         \sigma\bigl(\vect{b} + \mat{W}\transp \vect{v}^{(0)}\bigr)$
         \Comment{positive phase, \eqref{eq:en-rbm-condh}}
  \For{$t = 0,\dots,k-1$}
    \State sample $\vect{h}^{(t)} \sim
           p(\vect{h}\mid \vect{v}^{(t)})$
           \Comment{block Gibbs step, \eqref{eq:en-rbm-condh}}
    \State sample $\vect{v}^{(t+1)} \sim
           p(\vect{v}\mid \vect{h}^{(t)})$
           \Comment{block Gibbs step, \eqref{eq:en-rbm-condv}}
  \EndFor
  \State $\hat{\vect{h}}^{(k)} \gets
         \sigma\bigl(\vect{b} + \mat{W}\transp \vect{v}^{(k)}\bigr)$
  \State $\Delta\mat{W}_n \gets
         \vect{v}^{(0)}\hat{\vect{h}}^{(0)\top}
         - \vect{v}^{(k)}\hat{\vect{h}}^{(k)\top}$
         \Comment{contrast \eqref{eq:en-cdk}}
  \State $\Delta\vect{a}_n \gets \vect{v}^{(0)} - \vect{v}^{(k)}$;
         \quad
         $\Delta\vect{b}_n \gets
         \hat{\vect{h}}^{(0)} - \hat{\vect{h}}^{(k)}$
\EndFor
\State $\mat{W} \gets \mat{W} + \frac{\eta}{m}\sum_n \Delta\mat{W}_n$;
       \quad
       $\vect{a} \gets \vect{a} + \frac{\eta}{m}\sum_n \Delta\vect{a}_n$;
       \quad
       $\vect{b} \gets \vect{b} + \frac{\eta}{m}\sum_n \Delta\vect{b}_n$
\end{algorithmic}
\end{algorithm}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[node distance=6mm and 13mm]
    \node[blocinput, minimum width=1.35cm]  (v0) {$\vect{v}^{(0)}$};
    \node[blochidden, minimum width=1.35cm, right=of v0] (h0)
      {$\vect{h}^{(0)}$};
    \node[blocinput, minimum width=1.35cm, right=of h0]  (v1)
      {$\vect{v}^{(1)}$};
    \node[blochidden, minimum width=1.35cm, right=9mm of v1] (h1)
      {$\vect{h}^{(1)}$};
    \node[right=5mm of h1] (dots) {$\cdots$};
    \node[blocinput, minimum width=1.35cm, right=5mm of dots]  (vk)
      {$\vect{v}^{(k)}$};
    \node[blochidden, minimum width=1.35cm, right=of vk] (hk)
      {$\vect{h}^{(k)}$};
    \draw[fleche] (v0) -- node[etiquette, above]
      {$p(\vect{h}\!\mid\!\vect{v})$} (h0);
    \draw[fleche] (h0) -- node[etiquette, above]
      {$p(\vect{v}\!\mid\!\vect{h})$} (v1);
    \draw[fleche] (v1) -- (h1);
    \draw[fleche] (h1) -- (dots);
    \draw[fleche] (dots) -- (vk);
    \draw[fleche] (vk) -- node[etiquette, above]
      {$p(\vect{h}\!\mid\!\vect{v})$} (hk);
    \node[etiquette, below=2.5mm of v0] {data (clamped)};
    \node[etiquette, below=2.5mm of hk] {negative phase};
    \draw[flechep, coutput]
      ($(v0.south)+(0,-9mm)$) -- node[etiquette, below]
      {contrast
       $\langle v_i h_j\rangle_0 - \langle v_i h_j\rangle_k$
       \ \eqref{eq:en-cdk}}
      ($(hk.south)+(0,-9mm)$);
  \end{tikzpicture}
  \caption{The CD-$k$ Gibbs chain \eqref{eq:en-gibbs-chain}
    \cite{hinton2002}. The chain starts at the data, alternates the
    factorized conditionals
    \eqref{eq:en-rbm-condh}--\eqref{eq:en-rbm-condv} for $k$ block
    steps, and the weight update contrasts correlations at the two ends
    of the chain.}
  \label{fig:en-cdk}
\end{figure}

\section{Deep Belief Networks}

A single RBM learns one layer of features. Deep belief networks
\cite{hinton2006} stack RBMs: train an RBM on the data, freeze it, feed
its hidden activations as ``data'' to a second RBM, and repeat. The
resulting generative model is a hybrid — the top two layers keep an
undirected RBM joint, while the lower layers become a directed belief
network:
\begin{equation}
  p\bigl(\vect{v}, \vect{h}^{(1)}, \dots, \vect{h}^{(L)}\bigr)
  \;=\;
  p\bigl(\vect{h}^{(L-1)}, \vect{h}^{(L)}\bigr)
  \prod_{\ell=L-2}^{0}
  p\bigl(\vect{h}^{(\ell)} \mid \vect{h}^{(\ell+1)}\bigr),
  \label{eq:en-dbn-joint}
\end{equation}
with $\vect{h}^{(0)} \equiv \vect{v}$. Greediness is not a mere
heuristic: each newly stacked RBM, initialized as the transpose of the
one below, starts from an equivalent model and can only improve a
variational lower bound on the data log-likelihood,
\begin{equation}
  \log p(\vect{v})
  \;\ge\;
  \E_{q(\vect{h}^{(1)}\mid\vect{v})}
  \Bigl[\log p\bigl(\vect{v}\mid\vect{h}^{(1)}\bigr)
        + \log p\bigl(\vect{h}^{(1)}\bigr)\Bigr]
  \;+\;
  \mathcal{H}\bigl[q(\vect{h}^{(1)}\mid\vect{v})\bigr],
  \label{eq:en-dbn-bound}
\end{equation}
where $q$ is the first RBM's posterior, $\mathcal{H}[\cdot]$ denotes the
entropy, and training the upper stack improves the prior term
$\log p(\vect{h}^{(1)})$. After pretraining, the stack is optionally
\emph{fine-tuned} — generatively by the wake--sleep procedure, or
discriminatively by appending a classifier head and running
backpropagation through the unrolled weights
(Algorithm~\ref{alg:en-dbn}, Figure~\ref{fig:en-dbn}).

\begin{algorithm}[htbp]
\caption{Greedy layer-wise pretraining of a deep belief network}
\label{alg:en-dbn}
\begin{algorithmic}[1]
\Require dataset $\mathcal{D} = \{\vect{v}_n\}$, layer sizes
         $n_1,\dots,n_L$, Gibbs steps $k$
\State $\mathcal{D}^{(0)} \gets \mathcal{D}$
\For{$\ell = 1,\dots,L$}
  \State train RBM$_\ell$ with parameters $(\mat{W}^{(\ell)},
         \vect{a}^{(\ell)}, \vect{b}^{(\ell)})$ on
         $\mathcal{D}^{(\ell-1)}$ by CD-$k$
         (Algorithm~\ref{alg:en-cdk})
  \State $\mathcal{D}^{(\ell)} \gets
         \bigl\{\, \sigma\bigl(\vect{b}^{(\ell)} +
         \mat{W}^{(\ell)\top}\vect{x}\bigr)
         \;:\; \vect{x} \in \mathcal{D}^{(\ell-1)} \bigr\}$
         \Comment{propagate features upward}
\EndFor
\State \Return stack $\{\mat{W}^{(\ell)}\}_{\ell=1}^{L}$; optionally
       fine-tune (wake--sleep, or backpropagation with a supervised
       head)
\end{algorithmic}
\end{algorithm}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[node distance=9mm]
    \node[blocinput,  minimum width=3.4cm] (v)  {$\vect{v}$};
    \node[blochidden, minimum width=3.4cm, above=of v]  (h1)
      {$\vect{h}^{(1)}$};
    \node[blochidden, minimum width=3.4cm, above=of h1] (h2)
      {$\vect{h}^{(2)}$};
    \node[mem,        minimum width=3.4cm, above=of h2] (h3)
      {$\vect{h}^{(3)}$};
    % upward recognition / pretraining arrows
    \draw[fleche, cgate!70!black]
      ([xshift=-9mm]v.north)  -- ([xshift=-9mm]h1.south)
      node[etiquette, midway, left=1.5mm] {$\mat{W}^{(1)\top}$};
    \draw[fleche, cgate!70!black]
      ([xshift=-9mm]h1.north) -- ([xshift=-9mm]h2.south)
      node[etiquette, midway, left=1.5mm] {$\mat{W}^{(2)\top}$};
    \draw[fleche, cgate!70!black]
      ([xshift=-9mm]h2.north) -- ([xshift=-9mm]h3.south)
      node[etiquette, midway, left=1.5mm] {$\mat{W}^{(3)\top}$};
    % downward generative arrows
    \draw[flechep, cmem!80!black]
      ([xshift=9mm]h3.south) -- ([xshift=9mm]h2.north)
      node[etiquette, midway, right=1.5mm] {$\mat{W}^{(3)}$};
    \draw[flechep, cmem!80!black]
      ([xshift=9mm]h2.south) -- ([xshift=9mm]h1.north)
      node[etiquette, midway, right=1.5mm] {$\mat{W}^{(2)}$};
    \draw[flechep, cmem!80!black]
      ([xshift=9mm]h1.south) -- ([xshift=9mm]v.north)
      node[etiquette, midway, right=1.5mm] {$\mat{W}^{(1)}$};
    % RBM braces on the left
    \draw[decorate, decoration={brace, amplitude=5pt}, black!60]
      ($(h1.west)+(-1.65,0.12)$) -- ($(v.west)+(-1.65,-0.12)$)
      node[etiquette, midway, left=7pt] {RBM 1};
    \draw[decorate, decoration={brace, amplitude=5pt}, black!60]
      ($(h2.west)+(-2.5,0.12)$) -- ($(h1.west)+(-2.5,-0.12)$)
      node[etiquette, midway, left=7pt] {RBM 2};
    \draw[decorate, decoration={brace, amplitude=5pt}, black!60]
      ($(h3.west)+(-1.65,0.12)$) -- ($(h2.west)+(-1.65,-0.12)$)
      node[etiquette, midway, left=7pt] {RBM 3};
    % legend
    \node[etiquette, align=left, anchor=west]
      at ($(v.east)+(0.75,0.7)$)
      {\textcolor{cgate!70!black}{$\longrightarrow$}\ pretraining
       (recognition)\\[1pt]
       \textcolor{cmem!80!black}{$\dashrightarrow$}\ generation};
    % top RBM annotation
    \node[etiquette, above=2.5mm of h3]
      {top pair: undirected joint
       $p(\vect{h}^{(2)},\vect{h}^{(3)})$};
  \end{tikzpicture}
  \caption{A three-layer deep belief network \cite{hinton2006}. Each
    RBM (braces) is trained greedily on the features of the layer below
    (Algorithm~\ref{alg:en-dbn}); the trained stack generates by
    sampling the top RBM and propagating down the dashed directed
    connections, as in \eqref{eq:en-dbn-joint}.}
  \label{fig:en-dbn}
\end{figure}

\begin{remark}[Historical impact]\label{rem:en-history}
Greedy DBN pretraining was the first broadly reliable method for
initializing deep networks, at a time when random initialization plus
backpropagation stalled. Modern practice — rectified activations,
normalization, residual connections and large datasets — later made
unsupervised pretraining unnecessary for most supervised tasks, but the
energy-based view survives: contrastive objectives, score matching, and
the attention--Hopfield correspondence of
Remark~\ref{rem:en-attention} are all its descendants.
\end{remark}
