spb/artificial-neural-networks-book Public
Artificial Neural Networks — Methods, Equations and Graphical Representations: a complete book, every method with rigorous equations, pseudocode and native TikZ figures.
TeX 100%
1% ============================================================================2% Artificial Neural Networks — Methods, Equations and Graphical3% Representations4% Author : Simon-Pierre Boucher — contact@spboucher.ai5% Chapter 1 : Foundations of Neural Networks (chapters/01-foundations.tex)6% ============================================================================78\chapter{Foundations of Neural Networks}\label{chap:foundations}910Artificial neural networks rest on a small number of ideas of remarkable11economy: a neuron is an affine map followed by a nonlinearity, a network is12a composition of such maps, and learning is the adjustment of the affine13parameters from examples. This chapter develops these ideas in their14historical and mathematical order. We begin with the artificial neuron as a15radical abstraction of its biological counterpart, formalize the perceptron16of Rosenblatt~\cite{rosenblatt1958} together with its learning rule and17convergence guarantee, examine the activation functions that give networks18their expressive power, and assemble these components into the multilayer19perceptron (MLP). The chapter closes with the universal approximation20theorem, which explains \emph{why} such compositions can, in principle,21represent essentially any continuous function.2223Throughout the book, vectors are bold lowercase ($\vect{x} \in \R^n$),24matrices bold uppercase ($\mat{W} \in \R^{m \times n}$), scalars italic,25and the Hadamard (elementwise) product is written $\odot$. The loss is26$\Loss$ and expectation is $\E$.2728% ----------------------------------------------------------------------------29\section{From the Biological Neuron to the Artificial Neuron}30% ----------------------------------------------------------------------------3132A biological neuron receives electrochemical signals through its33\emph{dendrites}, integrates them in the cell body, and — if the aggregated34membrane depolarization crosses a threshold — emits an action potential35that propagates along the axon to synapses connecting to downstream36neurons. Two properties of this system survive in the mathematical37abstraction: synaptic transmission is \emph{weighted} (a synapse may be38excitatory or inhibitory, strong or weak), and firing is \emph{nonlinear39and threshold-based}. Everything else — spike timing, refractory periods,40dendritic compartmentalization, neuromodulation — is discarded. The41artificial neuron is therefore best understood as a computational primitive42\emph{inspired by}, not a model of, neurophysiology.4344The founding formalization is due to McCulloch and Pitts (1943). Their45neuron takes Boolean inputs $x_i \in \{0,1\}$ and produces a Boolean output46through a threshold (Heaviside) function:47\begin{equation}48 y \;=\; \Theta\!\left(\sum_{i=1}^{n} w_i x_i - \theta\right),49 \qquad50 \Theta(u) \;=\;51 \begin{cases}52 1 & \text{if } u \geq 0,\\53 0 & \text{if } u < 0.54 \end{cases}55 \label{eq:found-mp}56\end{equation}57Networks of such units can implement any Boolean function — AND is obtained58with $\theta = n$, OR with $\theta = 1$, NOT via inhibition — and, when59cycles are allowed, any finite-state automaton. The decisive limitation of60the McCulloch--Pitts unit is that it does not \emph{learn}: the weights61$w_i$ and the threshold $\theta$ must be set by the designer. The history62of neural networks is, in large part, the history of removing this63limitation.6465% ----------------------------------------------------------------------------66\section{The Artificial Neuron}67% ----------------------------------------------------------------------------6869\begin{definition}[Artificial neuron]\label{def:found-neuron}70An \emph{artificial neuron} with weights $\vect{w} \in \R^n$, bias71$b \in \R$ and activation function72$\varphi : \R \to \R$ is the map that assigns to an input73$\vect{x} \in \R^n$ the \emph{pre-activation} $z$ and the74\emph{activation} $a$ defined by75\begin{equation}76 z \;=\; \vect{w}\transp \vect{x} + b \;=\; \sum_{i=1}^{n} w_i x_i + b,77 \qquad78 a \;=\; \varphi(z).79 \label{eq:found-neuron}80\end{equation}81\end{definition}8283The computation~\eqref{eq:found-neuron} decomposes into three stages,84represented graphically in Figure~\ref{fig:found-neuron}: a weighted85aggregation of the inputs, the addition of a bias, and a pointwise86nonlinearity. The bias can be absorbed into the weights by augmenting the87input, $\vect{x} \leftarrow (\vect{x}, 1)$ and88$\vect{w} \leftarrow (\vect{w}, b)$, a convention we use freely whenever it89lightens notation.9091\begin{figure}[htbp]92 \centering93 \begin{tikzpicture}94 % --- inputs -------------------------------------------------------------95 \node[ninput] (x1) at (0, 2.2) {$x_1$};96 \node[ninput] (x2) at (0, 1.1) {$x_2$};97 \node[ninput] (x3) at (0, 0.0) {$x_3$};98 \node (xd) at (0,-0.85) {$\vdots$};99 \node[ninput] (xn) at (0,-1.7) {$x_n$};100 % --- bias ---------------------------------------------------------------101 \node[neuron, fill=black!8] (bias) at (3.2, 2.3) {$1$};102 % --- sum and activation ---------------------------------------------------103 \node[op, minimum size=9mm] (sum) at (3.2, 0.25) {$\Sigma$};104 \node[nhidden, minimum size=9mm] (phi) at (5.5, 0.25) {$\varphi$};105 % --- output ---------------------------------------------------------------106 \node (out) at (7.9, 0.25) {$a = \varphi(z)$};107 % --- edges with weight labels ---------------------------------------------108 \draw[fleche] (x1) -- node[etiquette, above, pos=0.40] {$w_1$} (sum);109 \draw[fleche] (x2) -- node[etiquette, above, pos=0.45] {$w_2$} (sum);110 \draw[fleche] (x3) -- node[etiquette, above, pos=0.50] {$w_3$} (sum);111 \draw[fleche] (xn) -- node[etiquette, below, pos=0.45] {$w_n$} (sum);112 \draw[fleche] (bias) -- node[etiquette, right, pos=0.45] {$b$} (sum);113 \draw[fleche] (sum) -- node[etiquette, above] {$z$} (phi);114 \draw[fleche] (phi) -- (out);115 \end{tikzpicture}116 \caption{The artificial neuron of117 Definition~\ref{def:found-neuron}. Inputs $x_1, \dots, x_n$ are118 weighted by $w_1, \dots, w_n$ and aggregated by the summation node119 $\Sigma$ together with the bias $b$; the pre-activation120 $z = \vect{w}\transp\vect{x} + b$ then passes through the activation121 function $\varphi$ to produce the output $a = \varphi(z)$.}122 \label{fig:found-neuron}123\end{figure}124125\begin{remark}[Geometry of a single neuron]126The level set $\{\vect{x} : \vect{w}\transp\vect{x} + b = 0\}$ is a127hyperplane with normal vector $\vect{w}$, at signed distance128$-b/\lVert\vect{w}\rVert$ from the origin. A single neuron with a monotone129activation therefore responds along one direction of input space only: it130is a \emph{linear feature detector} followed by a nonlinear read-out.131Everything a deep network does can be traced back to compositions of these132elementary half-space responses.133\end{remark}134135% ----------------------------------------------------------------------------136\section{The Rosenblatt Perceptron}137% ----------------------------------------------------------------------------138139Rosenblatt's perceptron~\cite{rosenblatt1958} is historically the first140neuron that \emph{learns}: its weights are adjusted from labelled examples141rather than hand-designed. For binary classification with labels142$y \in \{-1, +1\}$, the perceptron predicts with the sign of the143pre-activation,144\begin{equation}145 \hat{y} \;=\; \operatorname{sign}\!\left(\vect{w}\transp\vect{x} + b\right)146 \;=\;147 \begin{cases}148 +1 & \text{if } \vect{w}\transp\vect{x} + b \geq 0,\\149 -1 & \text{otherwise,}150 \end{cases}151 \label{eq:found-perceptron-decision}152\end{equation}153so that the decision boundary is the hyperplane154$\vect{w}\transp\vect{x} + b = 0$. Learning proceeds \emph{online}: the155examples $(\vect{x}^{(k)}, y^{(k)})$ are presented one at a time, and each156misclassified example triggers the update157\begin{equation}158 \vect{w} \;\leftarrow\; \vect{w} + \eta\, y^{(k)} \vect{x}^{(k)},159 \qquad160 b \;\leftarrow\; b + \eta\, y^{(k)},161 \label{eq:found-perceptron-update}162\end{equation}163with learning rate $\eta > 0$; correctly classified examples produce no164update. Rule~\eqref{eq:found-perceptron-update} is intuitive — it rotates165the hyperplane toward each mistake — and it requires no differentiability.166Indeed, the step function of~\eqref{eq:found-perceptron-decision} has zero167derivative almost everywhere, so the perceptron rule is \emph{not}168gradient descent on the misclassification error. It is, however,169exactly stochastic subgradient descent on the \emph{perceptron criterion}170\begin{equation}171 \Loss(\vect{w}, b)172 \;=\;173 \max\!\left(0,\; -y\left(\vect{w}\transp\vect{x} + b\right)\right),174 \label{eq:found-perceptron-criterion}175\end{equation}176which vanishes on correct classifications and grows linearly with the177margin of error otherwise — an early ancestor of the hinge loss. The178complete estimation procedure, which simply cycles through the data179applying~\eqref{eq:found-perceptron-update} until an error-free pass,180is summarized in Algorithm~\ref{alg:found-perceptron}.181182\begin{algorithm}[htbp]183 \caption{Perceptron learning (Rosenblatt)}184 \label{alg:found-perceptron}185 \begin{algorithmic}[1]186 \Require training set $\{(\vect{x}^{(k)}, y^{(k)})\}_{k=1}^{m}$ with187 $y^{(k)} \in \{-1,+1\}$, learning rate $\eta > 0$188 \State $\vect{w} \gets \vect{0}$, \quad $b \gets 0$189 \Repeat190 \State $\mathit{errors} \gets 0$191 \For{$k = 1, \dots, m$}192 \If{$y^{(k)}\bigl(\vect{w}\transp\vect{x}^{(k)} + b\bigr) \leq 0$}193 \Comment{misclassified example}194 \State $\vect{w} \gets \vect{w} + \eta\, y^{(k)}\vect{x}^{(k)}$195 \State $b \gets b + \eta\, y^{(k)}$196 \State $\mathit{errors} \gets \mathit{errors} + 1$197 \EndIf198 \EndFor199 \Until{$\mathit{errors} = 0$}200 \State \Return $\vect{w},\, b$201 \end{algorithmic}202\end{algorithm}203204The perceptron admits one of the cleanest guarantees in machine learning,205formalized by Novikoff (1962).206207\begin{theorem}[Perceptron convergence]\label{thm:found-convergence}208Suppose the training set209$\{(\vect{x}^{(k)}, y^{(k)})\}_{k=1}^{m}$ is linearly separable with210margin $\gamma > 0$: there exists a unit vector $\vect{w}^{\star}$,211$\lVert\vect{w}^{\star}\rVert = 1$, such that212$y^{(k)}\,\vect{w}^{\star\top}\vect{x}^{(k)} \geq \gamma$ for all $k$.213Let $R = \max_k \lVert\vect{x}^{(k)}\rVert$. Then the perceptron214algorithm~\eqref{eq:found-perceptron-update}, started from215$\vect{w} = \vect{0}$, makes at most216\begin{equation}217 T \;\leq\; \left(\frac{R}{\gamma}\right)^{2}218 \label{eq:found-novikoff}219\end{equation}220updates before finding a separating hyperplane.221\end{theorem}222223\begin{remark}224The bound~\eqref{eq:found-novikoff} is independent of the input dimension225$n$ and of the number of examples $m$: only the \emph{normalized margin}226$\gamma / R$ matters. This is an early instance of a recurring theme —227the difficulty of a learning problem is governed by geometric quantities,228not by raw dimensionality.229\end{remark}230231Shortly after the perceptron, Widrow and Hoff (1960) introduced ADALINE,232which differs in one crucial respect: the error is computed on the233\emph{linear} pre-activation $z = \vect{w}\transp\vect{x} + b$ rather than234on the thresholded output. Minimizing the squared error235$\tfrac{1}{2}(d - z)^2$ against a target $d$ gives the \emph{delta rule}236(or LMS, least-mean-squares, rule)237\begin{equation}238 \vect{w} \;\leftarrow\; \vect{w} + \eta\,(d - z)\,\vect{x},239 \label{eq:found-adaline}240\end{equation}241which, unlike~\eqref{eq:found-perceptron-update}, \emph{is} genuine242stochastic gradient descent on a differentiable objective. The delta rule243keeps improving even after the data are separated, driving the weights244toward the minimum mean-squared-error solution, and it does not diverge on245non-separable data. Gradient-based learning of exactly this kind — extended246to many layers — is the subject of the next chapter.247248% ----------------------------------------------------------------------------249\subsection{The Limits of Linear Separation: XOR}250% ----------------------------------------------------------------------------251252The perceptron can only realize decision boundaries that are hyperplanes.253Minsky and Papert (1969) analyzed this restriction with mathematical254precision, and their canonical counterexample is the exclusive-or function255XOR, shown in Figure~\ref{fig:found-xor}: the positive examples256$(0,1)$ and $(1,0)$ sit on one diagonal of the unit square, the negative257examples $(0,0)$ and $(1,1)$ on the other, and no straight line separates258two diagonals. The proof is elementary. If a separating line259$w_1 x_1 + w_2 x_2 + b = 0$ existed, then $(0,0) \mapsto 0$ forces260$b < 0$, while the positive cases force $w_1 + b \geq 0$ and261$w_2 + b \geq 0$; adding these, $w_1 + w_2 + 2b \geq 0$, hence262$w_1 + w_2 + b \geq -b > 0$, which would classify $(1,1)$ as positive — a263contradiction.264265\begin{figure}[htbp]266 \centering267 \begin{tikzpicture}[scale=2.6]268 % axes269 \draw[fleche, black!60] (-0.30, 0) -- (1.55, 0)270 node[below, font=\small] {$x_1$};271 \draw[fleche, black!60] (0, -0.30) -- (0, 1.55)272 node[left, font=\small] {$x_2$};273 % the two hidden-unit hyperplanes274 \draw[cgate, dashed, thick] (-0.15, 0.65) -- (0.65, -0.15)275 node[etiquette, below, text=cgate!60!black]276 {$x_1 + x_2 = \tfrac{1}{2}$};277 \draw[cgate, dashed, thick] (0.38, 1.18) -- (1.18, 0.38)278 node[etiquette, below right, text=cgate!60!black]279 {$x_1 + x_2 = \tfrac{3}{2}$};280 % class 0 (blue) and class 1 (red) points281 \node[circle, fill=cinput, draw=cinput!60!black, inner sep=2.4pt,282 label={[etiquette]below left:$(0,0)$}] at (0,0) {};283 \node[circle, fill=cinput, draw=cinput!60!black, inner sep=2.4pt,284 label={[etiquette]above right:$(1,1)$}] at (1,1) {};285 \node[circle, fill=coutput, draw=coutput!60!black, inner sep=2.4pt,286 label={[etiquette]above left:$(0,1)$}] at (0,1) {};287 \node[circle, fill=coutput, draw=coutput!60!black, inner sep=2.4pt,288 label={[etiquette]below right:$(1,0)$}] at (1,0) {};289 \end{tikzpicture}290 \caption{The XOR problem. Negative examples (blue) occupy one diagonal291 of the unit square, positive examples (red) the other; no single line292 separates the two classes. The two dashed lines show the resolution by293 a hidden layer: two threshold units implementing294 $x_1 + x_2 \geq \tfrac{1}{2}$ (OR) and $x_1 + x_2 \leq \tfrac{3}{2}$295 (NAND) carve out the strip between the lines, and an AND unit on top296 of them computes XOR exactly.}297 \label{fig:found-xor}298\end{figure}299300Crucially, XOR \emph{is} solvable with one hidden layer:301$\mathrm{XOR}(x_1, x_2) = \mathrm{OR}(x_1, x_2) \wedge302\neg\,\mathrm{AND}(x_1, x_2)$, i.e.\ two threshold units feeding a third.303Minsky and Papert's pessimism about such multilayer extensions — for which304no training algorithm was then known — is commonly cited as a trigger of305the first connectionist winter, which lasted until the mid-1980s. The306missing algorithm, backpropagation, is derived in the next chapter; the307representational question of what multilayer networks \emph{can} express308is answered at the end of this one.309310% ----------------------------------------------------------------------------311\section{Activation Functions}312% ----------------------------------------------------------------------------313314The nonlinearity $\varphi$ is not a detail: without it, a network of any315depth collapses. If every layer applied only an affine map, their316composition would again be affine, and the deepest network would be317exactly as expressive as a single linear layer. The choice of $\varphi$318also governs how gradients flow backward through the network — as we will319see in the next chapter, training multiplies derivatives $\varphi'$ across320layers, so activations that \emph{saturate} (have near-zero derivative321over most of their domain) starve deep networks of learning signal. We now322review the five activations that dominate practice, giving for each the323definition and the derivative; Figure~\ref{fig:found-activations} plots324them side by side.325326\paragraph{Sigmoid.} The logistic sigmoid maps $\R$ onto $(0,1)$ and was327historically the default choice:328\begin{equation}329 \sigma(z) \;=\; \frac{1}{1 + e^{-z}},330 \qquad331 \sigma'(z) \;=\; \sigma(z)\bigl(1 - \sigma(z)\bigr).332 \label{eq:found-sigmoid}333\end{equation}334Its derivative is bounded by $\sigma'(0) = \tfrac{1}{4}$ and decays335exponentially for $\lvert z \rvert \gtrsim 5$: the function336\emph{saturates}, and its outputs are not zero-centred, which induces337correlated gradient signs within a layer. It survives today mainly in338gates and binary output units.339340\paragraph{Hyperbolic tangent.} A rescaled sigmoid,341$\tanh(z) = 2\sigma(2z) - 1$, with range $(-1, 1)$:342\begin{equation}343 \tanh(z) \;=\; \frac{e^{z} - e^{-z}}{e^{z} + e^{-z}},344 \qquad345 \frac{d}{dz}\tanh(z) \;=\; 1 - \tanh^{2}(z).346 \label{eq:found-tanh}347\end{equation}348Zero-centred and with maximal derivative $1$ at the origin, it is better349conditioned than the sigmoid for hidden layers, though still saturating;350it remains standard inside recurrent cells.351352\paragraph{ReLU.} The rectified linear unit, repopularized around3532010--2012, is the piecewise-linear map354\begin{equation}355 \mathrm{ReLU}(z) \;=\; \max(0, z),356 \qquad357 \mathrm{ReLU}'(z) \;=\;358 \begin{cases}359 1 & z > 0,\\360 0 & z < 0,361 \end{cases}362 \label{eq:found-relu}363\end{equation}364with the convention $\mathrm{ReLU}'(0) = 0$ at the (measure-zero)365non-differentiable point. For positive inputs the gradient is exactly $1$,366so ReLU does not saturate on its active half — the property that unlocked367the training of genuinely deep networks. Its failure mode is the368\emph{dying ReLU}: a unit pushed into the negative regime for every input369receives zero gradient forever and never recovers.370371\paragraph{Leaky ReLU.} A minimal repair of the dying-unit problem replaces372the zero slope with a small $\alpha > 0$ (typically $\alpha = 0.01$):373\begin{equation}374 \mathrm{LReLU}(z) \;=\; \max(\alpha z,\, z)375 \;=\;376 \begin{cases}377 z & z \geq 0,\\378 \alpha z & z < 0,379 \end{cases}380 \qquad381 \mathrm{LReLU}'(z) \;=\;382 \begin{cases}383 1 & z > 0,\\384 \alpha & z < 0.385 \end{cases}386 \label{eq:found-leaky}387\end{equation}388The parametric variant (PReLU) learns $\alpha$ per channel at negligible389cost.390391\paragraph{GELU.} The Gaussian error linear unit weights its input by the392probability that a standard Gaussian falls below it. With $\Phi$ and393$\phi$ the standard normal cumulative distribution function and density,394\begin{equation}395 \mathrm{GELU}(z) \;=\; z\,\Phi(z)396 \;=\; \frac{z}{2}\left[1 + \operatorname{erf}\!\left(397 \frac{z}{\sqrt{2}}\right)\right],398 \qquad399 \frac{d}{dz}\mathrm{GELU}(z) \;=\; \Phi(z) + z\,\phi(z).400 \label{eq:found-gelu}401\end{equation}402GELU can be read as a deterministic version of stochastic gating: instead403of dropping a unit with probability $1 - \Phi(z)$, it scales the unit by404the expected mask. It is smooth, non-monotonic (a shallow negative dip405near $z \approx -0.75$), and is the default activation in Transformer406architectures. Implementations commonly use the tanh approximation407\begin{equation}408 \mathrm{GELU}(z) \;\approx\; \tfrac{1}{2}\, z \left(1 + \tanh\!\left[409 \sqrt{\tfrac{2}{\pi}}\left(z + 0.044715\, z^{3}\right)410 \right]\right).411 \label{eq:found-gelu-approx}412\end{equation}413414\begin{figure}[htbp]415 \centering416 \begin{tikzpicture}417 \begin{axis}[418 width=0.50\textwidth, height=6.2cm,419 title={\small (a) Activation functions},420 xlabel={$z$}, ylabel={$\varphi(z)$},421 xmin=-4, xmax=4, ymin=-1.6, ymax=4,422 grid=major, grid style={black!12},423 legend pos=north west,424 legend style={font=\scriptsize, fill=white, fill opacity=0.85,425 text opacity=1, draw=black!30},426 every axis plot/.append style={thick},427 samples=200, domain=-4:4,428 ]429 \addplot[cinput] {1/(1+exp(-x))};430 \addlegendentry{sigmoid}431 \addplot[chidden] {tanh(x)};432 \addlegendentry{$\tanh$}433 \addplot[coutput] {max(0,x)};434 \addlegendentry{ReLU}435 \addplot[cgate, dashed] {max(0,x) + 0.1*min(0,x)};436 \addlegendentry{Leaky ReLU}437 \addplot[cmem]438 {0.5*x*(1 + tanh(0.7978845608*(x + 0.044715*x^3)))};439 \addlegendentry{GELU}440 \end{axis}441 \end{tikzpicture}\hfill442 \begin{tikzpicture}443 \begin{axis}[444 width=0.50\textwidth, height=6.2cm,445 title={\small (b) Derivatives},446 xlabel={$z$}, ylabel={$\varphi'(z)$},447 xmin=-4, xmax=4, ymin=-0.25, ymax=1.35,448 grid=major, grid style={black!12},449 legend pos=north west,450 legend style={font=\scriptsize, fill=white, fill opacity=0.85,451 text opacity=1, draw=black!30},452 every axis plot/.append style={thick},453 samples=200, domain=-4:4,454 ]455 \addplot[cinput] {exp(-x)/((1+exp(-x))^2)};456 \addlegendentry{sigmoid$'$}457 \addplot[chidden] {1 - tanh(x)^2};458 \addlegendentry{$\tanh'$}459 \addplot[coutput] coordinates {(-4,0) (0,0)};460 \addlegendentry{ReLU$'$}461 \addplot[coutput, forget plot] coordinates {(0,1) (4,1)};462 \addplot[cgate, dashed] coordinates {(-4,0.1) (0,0.1)};463 \addlegendentry{Leaky ReLU$'$}464 \addplot[cgate, dashed, forget plot] coordinates {(0,1) (4,1)};465 \addplot[cmem]466 {0.5*(1 + tanh(0.7978845608*(x + 0.044715*x^3)))467 + x*0.3989422804*exp(-x^2/2)};468 \addlegendentry{GELU$'$}469 \end{axis}470 \end{tikzpicture}471 \caption{The five standard activation functions472 \eqref{eq:found-sigmoid}--\eqref{eq:found-gelu} (left) and their473 derivatives (right). Leaky ReLU is drawn with $\alpha = 0.1$ for474 visibility (in practice $\alpha = 0.01$ is typical). Note the475 saturation of sigmoid and $\tanh$ — their derivatives vanish for476 $\lvert z\rvert \gtrsim 4$ — against the constant unit slope of the477 ReLU family on the positive half-line, and the smooth non-monotonic478 profile of GELU.}479 \label{fig:found-activations}480\end{figure}481482% ----------------------------------------------------------------------------483\subsection{The Softmax Function}484% ----------------------------------------------------------------------------485486Multiclass classification requires a vector-valued output layer that maps487$K$ real \emph{logits} to a probability distribution over $K$ classes.488This is the role of the softmax:489\begin{equation}490 \softmax(\vect{z})_i \;=\; \frac{e^{z_i}}{\sum_{j=1}^{K} e^{z_j}},491 \qquad i = 1, \dots, K,492 \label{eq:found-softmax}493\end{equation}494whose outputs are positive and sum to one. Its Jacobian has the compact495form496\begin{equation}497 \frac{\partial\, \softmax(\vect{z})_i}{\partial z_j}498 \;=\;499 \softmax(\vect{z})_i \left(\delta_{ij} - \softmax(\vect{z})_j\right),500 \label{eq:found-softmax-jacobian}501\end{equation}502with $\delta_{ij}$ the Kronecker delta — an expression that will combine503particularly gracefully with the cross-entropy loss in the next chapter.504505\begin{remark}[Shift invariance and temperature]506Softmax is invariant to adding a constant to every logit,507$\softmax(\vect{z} + c\vect{1}) = \softmax(\vect{z})$; numerically stable508implementations exploit this by subtracting $\max_j z_j$ before509exponentiating. Dividing the logits by a \emph{temperature} $T > 0$510interpolates between a hard maximum ($T \to 0$) and the uniform511distribution ($T \to \infty$).512\end{remark}513514% ----------------------------------------------------------------------------515\section{The Multilayer Perceptron}516% ----------------------------------------------------------------------------517518A single neuron detects one linear feature; the multilayer perceptron519composes entire \emph{layers} of them, each layer feeding the next.520521\begin{definition}[Multilayer perceptron]\label{def:found-mlp}522An MLP with $L$ layers of widths $n_1, \dots, n_L$ on inputs of dimension523$n_0$ is defined by weight matrices524$\mat{W}^{(\ell)} \in \R^{n_\ell \times n_{\ell-1}}$ and bias vectors525$\vect{b}^{(\ell)} \in \R^{n_\ell}$, $\ell = 1, \dots, L$. Setting526$\vect{a}^{(0)} = \vect{x}$, the \emph{forward propagation} computes, for527$\ell = 1, \dots, L$,528\begin{align}529 \vect{z}^{(\ell)} &= \mat{W}^{(\ell)} \vect{a}^{(\ell-1)}530 + \vect{b}^{(\ell)},531 \label{eq:found-mlp-z}\\532 \vect{a}^{(\ell)} &= \varphi^{(\ell)}\!\left(\vect{z}^{(\ell)}\right),533 \label{eq:found-mlp-a}534\end{align}535where $\varphi^{(\ell)}$ acts componentwise, and the network output is536$\hat{\vect{y}} = \vect{a}^{(L)}$.537\end{definition}538539Componentwise, \eqref{eq:found-mlp-z} reads540\begin{equation}541 z^{(\ell)}_j \;=\; \sum_{i=1}^{n_{\ell-1}}542 W^{(\ell)}_{ji}\, a^{(\ell-1)}_i + b^{(\ell)}_j,543 \label{eq:found-mlp-component}544\end{equation}545so that each unit of layer $\ell$ is exactly an artificial neuron in the546sense of Definition~\ref{def:found-neuron}, whose inputs are the547activations of the previous layer. The final activation548$\varphi^{(L)}$ is chosen to match the task: identity for regression,549sigmoid for binary classification, softmax~\eqref{eq:found-softmax} for550multiclass classification, while hidden layers use one of the551nonlinearities of Figure~\ref{fig:found-activations}. A network with two552hidden layers is drawn in Figure~\ref{fig:found-mlp}.553554\begin{figure}[htbp]555 \centering556 \begin{tikzpicture}557 % --- input layer --------------------------------------------------------558 \foreach \i in {1,2,3}559 \node[ninput] (x\i) at (0, 2.2-\i*1.1) {$x_{\i}$};560 % --- hidden layer 1 -----------------------------------------------------561 \foreach \j in {1,...,4}562 \node[nhidden] (h1\j) at (2.7, 2.75-\j*1.1) {};563 % --- hidden layer 2 -----------------------------------------------------564 \foreach \j in {1,...,4}565 \node[nhidden] (h2\j) at (5.4, 2.75-\j*1.1) {};566 % --- output layer -------------------------------------------------------567 \foreach \k in {1,2}568 \node[noutput] (o\k) at (8.1, 1.1-\k*1.1) {};569 % --- connections ----------------------------------------------------------570 \foreach \i in {1,2,3} \foreach \j in {1,...,4}571 \draw[black!35, semithick] (x\i) -- (h1\j);572 \foreach \i in {1,...,4} \foreach \j in {1,...,4}573 \draw[black!35, semithick] (h1\i) -- (h2\j);574 \foreach \i in {1,...,4} \foreach \k in {1,2}575 \draw[black!35, semithick] (h2\i) -- (o\k);576 % --- outputs ---------------------------------------------------------------577 \draw[fleche] (o1) -- ++(1.3,0) node[right] {$\hat{y}_1$};578 \draw[fleche] (o2) -- ++(1.3,0) node[right] {$\hat{y}_2$};579 % --- weight-matrix labels ---------------------------------------------------580 \node[etiquette] at (1.35, 2.55) {$\mat{W}^{(1)}, \vect{b}^{(1)}$};581 \node[etiquette] at (4.05, 2.55) {$\mat{W}^{(2)}, \vect{b}^{(2)}$};582 \node[etiquette] at (6.75, 2.55) {$\mat{W}^{(3)}, \vect{b}^{(3)}$};583 % --- layer labels ---------------------------------------------------------584 \node[etiquette, align=center] at (0, -2.6)585 {input layer\\ $\vect{a}^{(0)} = \vect{x}$};586 \node[etiquette, align=center] at (2.7, -2.6)587 {hidden layer 1\\ $\vect{a}^{(1)}$};588 \node[etiquette, align=center] at (5.4, -2.6)589 {hidden layer 2\\ $\vect{a}^{(2)}$};590 \node[etiquette, align=center] at (8.1, -2.6)591 {output layer\\ $\hat{\vect{y}} = \vect{a}^{(3)}$};592 \end{tikzpicture}593 \caption{A fully connected network with two hidden layers594 ($n_0 = 3$, $n_1 = n_2 = 4$, $n_3 = 2$). Each edge carries one entry595 of a weight matrix $\mat{W}^{(\ell)}$; each column of neurons applies596 the affine map~\eqref{eq:found-mlp-z} followed by the pointwise597 nonlinearity~\eqref{eq:found-mlp-a}.}598 \label{fig:found-mlp}599\end{figure}600601\begin{remark}[Batched computation]602For a mini-batch of $m$ examples stacked as rows of603$\mat{X} \in \R^{m \times n_0}$, forward propagation becomes604$\mat{Z}^{(\ell)} = \mat{A}^{(\ell-1)} \mat{W}^{(\ell)\top}605+ \vect{1}_m \vect{b}^{(\ell)\top}$ — a chain of dense matrix products.606This is why MLPs map so efficiently onto modern hardware: the entire607network is a sequence of GEMM primitives.608\end{remark}609610\begin{remark}[Why the nonlinearity is essential]611If $\varphi^{(\ell)} = \mathrm{id}$ for all $\ell$, then612$\hat{\vect{y}} = \mat{W}^{(L)} \cdots \mat{W}^{(1)} \vect{x} + \vect{c}$613for some constant $\vect{c}$: the composition of affine maps is affine,614and depth buys nothing. All the expressive power of the MLP resides in the615interleaving of~\eqref{eq:found-mlp-z} with the616nonlinearity~\eqref{eq:found-mlp-a}.617\end{remark}618619% ----------------------------------------------------------------------------620\subsection{Universal Approximation}621% ----------------------------------------------------------------------------622623How expressive is the MLP? The classical answer, due independently to624Cybenko (1989) and to Hornik, Stinchcombe and White (1989), is that625\emph{one} hidden layer already suffices, provided it is wide enough.626627\begin{property}[Universal approximation]\label{prop:found-uat}628Let $\varphi$ be a continuous sigmoidal function629($\varphi(t) \to 1$ as $t \to +\infty$ and $\varphi(t) \to 0$ as630$t \to -\infty$). Then finite sums of the form631\begin{equation}632 G(\vect{x}) \;=\; \sum_{j=1}^{N} \alpha_j\,633 \varphi\!\left(\vect{w}_j\transp \vect{x} + \theta_j\right)634 \label{eq:found-uat}635\end{equation}636are dense in $C([0,1]^{n})$ for the uniform norm: for every continuous637$f : [0,1]^n \to \R$ and every $\varepsilon > 0$, there exist $N$ and638parameters $\{\alpha_j, \vect{w}_j, \theta_j\}$ such that639$\lvert G(\vect{x}) - f(\vect{x})\rvert < \varepsilon$ for all640$\vect{x} \in [0,1]^n$. More generally (Leshno et al., 1993), a641one-hidden-layer network with a locally bounded, piecewise-continuous642activation is a universal approximator \emph{if and only if} the643activation is not a polynomial.644\end{property}645646The ``if and only if'' clause explains why ReLU — which is not sigmoidal —647is nevertheless universal, and why a purely linear network is not. Two648caveats temper the theorem's optimism, and both shape the rest of this649book~\cite{goodfellow2016book}. First,650Property~\ref{prop:found-uat} is an \emph{existence} result: it is silent651on how many hidden units are required (the width $N$ may grow652exponentially with the input dimension $n$) and on whether any learning653algorithm will \emph{find} the approximating weights. Second, it concerns654shallow networks only; depth-separation results show that certain655functions computable by a deep network with polynomially many units656require exponentially many units at bounded depth. Approximation theory657thus motivates depth, but it is the training machinery of the next658chapter — loss functions, backpropagation, and stochastic optimization —659that makes depth usable in practice.660661% ----------------------------------------------------------------------------662\section{A Contrast: Radial Basis Function Networks}663% ----------------------------------------------------------------------------664665The MLP is not the only way to combine simple units into a universal666approximator, and a brief look at its classical alternative sharpens our667understanding of what makes the MLP distinctive. A \emph{radial basis668function} (RBF) network, introduced by Broomhead and Lowe (1988) and669refined by Moody and Darken (1989), has exactly one hidden layer of $J$670\emph{locally tuned} units, each defined by a centre671$\vect{\mu}_j \in \R^n$ and a width $\sigma_j > 0$, followed by a linear672output layer:673\begin{equation}674 f(\vect{x}) \;=\; \sum_{j=1}^{J} w_j\,675 \varphi_j(\vect{x}) + b,676 \qquad677 \varphi_j(\vect{x}) \;=\;678 \exp\!\left(679 -\frac{\lVert \vect{x} - \vect{\mu}_j \rVert^{2}}{2\sigma_j^{2}}680 \right).681 \label{eq:found-rbf}682\end{equation}683The contrast with Definition~\ref{def:found-neuron} is fundamental. An684MLP unit computes an \emph{inner product} $\vect{w}\transp\vect{x}$ and685responds along a hyperplane — a global, distributed representation. An686RBF unit computes a \emph{distance} $\lVert\vect{x} - \vect{\mu}_j\rVert$687and responds only in a localized neighbourhood of its centre — a local,688spherical receptive field. Locality makes RBF networks fast to train:689once the centres are placed (by random subsampling or $k$-means690clustering), the model is \emph{linear} in the output weights, and with691the design matrix $\Phi_{ij} = \varphi_j(\vect{x}^{(i)})$ and targets692$\vect{y}$, the ridge-regularized least-squares solution is closed-form,693\begin{equation}694 \vect{w} \;=\;695 \left(\mat{\Phi}\transp \mat{\Phi} + \lambda \mat{I}\right)^{-1}696 \mat{\Phi}\transp \vect{y}.697 \label{eq:found-rbf-ls}698\end{equation}699The price of locality is the curse of dimensionality: covering a700high-dimensional input space with local bumps requires exponentially many701centres, whereas the global half-space features of the MLP can be shared702and composed. This trade-off — local interpolation versus global,703composable features — anticipates a pattern that recurs throughout the704book, and it is the composable option that deep learning has embraced.705Everything now hinges on one question: how are the weights of a706multilayer network actually learned? The next chapter answers it.707