% ============================================================================
%  Artificial Neural Networks — Methods, Equations and Graphical
%  Representations
%  Author  : Simon-Pierre Boucher — contact@spboucher.ai
%  Chapter 1 : Foundations of Neural Networks (chapters/01-foundations.tex)
% ============================================================================

\chapter{Foundations of Neural Networks}\label{chap:foundations}

Artificial neural networks rest on a small number of ideas of remarkable
economy: a neuron is an affine map followed by a nonlinearity, a network is
a composition of such maps, and learning is the adjustment of the affine
parameters from examples. This chapter develops these ideas in their
historical and mathematical order. We begin with the artificial neuron as a
radical abstraction of its biological counterpart, formalize the perceptron
of Rosenblatt~\cite{rosenblatt1958} together with its learning rule and
convergence guarantee, examine the activation functions that give networks
their expressive power, and assemble these components into the multilayer
perceptron (MLP). The chapter closes with the universal approximation
theorem, which explains \emph{why} such compositions can, in principle,
represent essentially any continuous function.

Throughout the book, vectors are bold lowercase ($\vect{x} \in \R^n$),
matrices bold uppercase ($\mat{W} \in \R^{m \times n}$), scalars italic,
and the Hadamard (elementwise) product is written $\odot$. The loss is
$\Loss$ and expectation is $\E$.

% ----------------------------------------------------------------------------
\section{From the Biological Neuron to the Artificial Neuron}
% ----------------------------------------------------------------------------

A biological neuron receives electrochemical signals through its
\emph{dendrites}, integrates them in the cell body, and — if the aggregated
membrane depolarization crosses a threshold — emits an action potential
that propagates along the axon to synapses connecting to downstream
neurons. Two properties of this system survive in the mathematical
abstraction: synaptic transmission is \emph{weighted} (a synapse may be
excitatory or inhibitory, strong or weak), and firing is \emph{nonlinear
and threshold-based}. Everything else — spike timing, refractory periods,
dendritic compartmentalization, neuromodulation — is discarded. The
artificial neuron is therefore best understood as a computational primitive
\emph{inspired by}, not a model of, neurophysiology.

The founding formalization is due to McCulloch and Pitts (1943). Their
neuron takes Boolean inputs $x_i \in \{0,1\}$ and produces a Boolean output
through a threshold (Heaviside) function:
\begin{equation}
  y \;=\; \Theta\!\left(\sum_{i=1}^{n} w_i x_i - \theta\right),
  \qquad
  \Theta(u) \;=\;
  \begin{cases}
    1 & \text{if } u \geq 0,\\
    0 & \text{if } u < 0.
  \end{cases}
  \label{eq:found-mp}
\end{equation}
Networks of such units can implement any Boolean function — AND is obtained
with $\theta = n$, OR with $\theta = 1$, NOT via inhibition — and, when
cycles are allowed, any finite-state automaton. The decisive limitation of
the McCulloch--Pitts unit is that it does not \emph{learn}: the weights
$w_i$ and the threshold $\theta$ must be set by the designer. The history
of neural networks is, in large part, the history of removing this
limitation.

% ----------------------------------------------------------------------------
\section{The Artificial Neuron}
% ----------------------------------------------------------------------------

\begin{definition}[Artificial neuron]\label{def:found-neuron}
An \emph{artificial neuron} with weights $\vect{w} \in \R^n$, bias
$b \in \R$ and activation function
$\varphi : \R \to \R$ is the map that assigns to an input
$\vect{x} \in \R^n$ the \emph{pre-activation} $z$ and the
\emph{activation} $a$ defined by
\begin{equation}
  z \;=\; \vect{w}\transp \vect{x} + b \;=\; \sum_{i=1}^{n} w_i x_i + b,
  \qquad
  a \;=\; \varphi(z).
  \label{eq:found-neuron}
\end{equation}
\end{definition}

The computation~\eqref{eq:found-neuron} decomposes into three stages,
represented graphically in Figure~\ref{fig:found-neuron}: a weighted
aggregation of the inputs, the addition of a bias, and a pointwise
nonlinearity. The bias can be absorbed into the weights by augmenting the
input, $\vect{x} \leftarrow (\vect{x}, 1)$ and
$\vect{w} \leftarrow (\vect{w}, b)$, a convention we use freely whenever it
lightens notation.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
    % --- inputs -------------------------------------------------------------
    \node[ninput] (x1) at (0, 2.2)  {$x_1$};
    \node[ninput] (x2) at (0, 1.1)  {$x_2$};
    \node[ninput] (x3) at (0, 0.0)  {$x_3$};
    \node         (xd) at (0,-0.85) {$\vdots$};
    \node[ninput] (xn) at (0,-1.7)  {$x_n$};
    % --- bias ---------------------------------------------------------------
    \node[neuron, fill=black!8] (bias) at (3.2, 2.3) {$1$};
    % --- sum and activation ---------------------------------------------------
    \node[op, minimum size=9mm]      (sum) at (3.2, 0.25) {$\Sigma$};
    \node[nhidden, minimum size=9mm] (phi) at (5.5, 0.25) {$\varphi$};
    % --- output ---------------------------------------------------------------
    \node (out) at (7.9, 0.25) {$a = \varphi(z)$};
    % --- edges with weight labels ---------------------------------------------
    \draw[fleche] (x1) -- node[etiquette, above, pos=0.40] {$w_1$} (sum);
    \draw[fleche] (x2) -- node[etiquette, above, pos=0.45] {$w_2$} (sum);
    \draw[fleche] (x3) -- node[etiquette, above, pos=0.50] {$w_3$} (sum);
    \draw[fleche] (xn) -- node[etiquette, below, pos=0.45] {$w_n$} (sum);
    \draw[fleche] (bias) -- node[etiquette, right, pos=0.45] {$b$} (sum);
    \draw[fleche] (sum) -- node[etiquette, above] {$z$} (phi);
    \draw[fleche] (phi) -- (out);
  \end{tikzpicture}
  \caption{The artificial neuron of
    Definition~\ref{def:found-neuron}. Inputs $x_1, \dots, x_n$ are
    weighted by $w_1, \dots, w_n$ and aggregated by the summation node
    $\Sigma$ together with the bias $b$; the pre-activation
    $z = \vect{w}\transp\vect{x} + b$ then passes through the activation
    function $\varphi$ to produce the output $a = \varphi(z)$.}
  \label{fig:found-neuron}
\end{figure}

\begin{remark}[Geometry of a single neuron]
The level set $\{\vect{x} : \vect{w}\transp\vect{x} + b = 0\}$ is a
hyperplane with normal vector $\vect{w}$, at signed distance
$-b/\lVert\vect{w}\rVert$ from the origin. A single neuron with a monotone
activation therefore responds along one direction of input space only: it
is a \emph{linear feature detector} followed by a nonlinear read-out.
Everything a deep network does can be traced back to compositions of these
elementary half-space responses.
\end{remark}

% ----------------------------------------------------------------------------
\section{The Rosenblatt Perceptron}
% ----------------------------------------------------------------------------

Rosenblatt's perceptron~\cite{rosenblatt1958} is historically the first
neuron that \emph{learns}: its weights are adjusted from labelled examples
rather than hand-designed. For binary classification with labels
$y \in \{-1, +1\}$, the perceptron predicts with the sign of the
pre-activation,
\begin{equation}
  \hat{y} \;=\; \operatorname{sign}\!\left(\vect{w}\transp\vect{x} + b\right)
  \;=\;
  \begin{cases}
    +1 & \text{if } \vect{w}\transp\vect{x} + b \geq 0,\\
    -1 & \text{otherwise,}
  \end{cases}
  \label{eq:found-perceptron-decision}
\end{equation}
so that the decision boundary is the hyperplane
$\vect{w}\transp\vect{x} + b = 0$. Learning proceeds \emph{online}: the
examples $(\vect{x}^{(k)}, y^{(k)})$ are presented one at a time, and each
misclassified example triggers the update
\begin{equation}
  \vect{w} \;\leftarrow\; \vect{w} + \eta\, y^{(k)} \vect{x}^{(k)},
  \qquad
  b \;\leftarrow\; b + \eta\, y^{(k)},
  \label{eq:found-perceptron-update}
\end{equation}
with learning rate $\eta > 0$; correctly classified examples produce no
update. Rule~\eqref{eq:found-perceptron-update} is intuitive — it rotates
the hyperplane toward each mistake — and it requires no differentiability.
Indeed, the step function of~\eqref{eq:found-perceptron-decision} has zero
derivative almost everywhere, so the perceptron rule is \emph{not}
gradient descent on the misclassification error. It is, however,
exactly stochastic subgradient descent on the \emph{perceptron criterion}
\begin{equation}
  \Loss(\vect{w}, b)
  \;=\;
  \max\!\left(0,\; -y\left(\vect{w}\transp\vect{x} + b\right)\right),
  \label{eq:found-perceptron-criterion}
\end{equation}
which vanishes on correct classifications and grows linearly with the
margin of error otherwise — an early ancestor of the hinge loss. The
complete estimation procedure, which simply cycles through the data
applying~\eqref{eq:found-perceptron-update} until an error-free pass,
is summarized in Algorithm~\ref{alg:found-perceptron}.

\begin{algorithm}[htbp]
  \caption{Perceptron learning (Rosenblatt)}
  \label{alg:found-perceptron}
  \begin{algorithmic}[1]
    \Require training set $\{(\vect{x}^{(k)}, y^{(k)})\}_{k=1}^{m}$ with
      $y^{(k)} \in \{-1,+1\}$, learning rate $\eta > 0$
    \State $\vect{w} \gets \vect{0}$, \quad $b \gets 0$
    \Repeat
      \State $\mathit{errors} \gets 0$
      \For{$k = 1, \dots, m$}
        \If{$y^{(k)}\bigl(\vect{w}\transp\vect{x}^{(k)} + b\bigr) \leq 0$}
          \Comment{misclassified example}
          \State $\vect{w} \gets \vect{w} + \eta\, y^{(k)}\vect{x}^{(k)}$
          \State $b \gets b + \eta\, y^{(k)}$
          \State $\mathit{errors} \gets \mathit{errors} + 1$
        \EndIf
      \EndFor
    \Until{$\mathit{errors} = 0$}
    \State \Return $\vect{w},\, b$
  \end{algorithmic}
\end{algorithm}

The perceptron admits one of the cleanest guarantees in machine learning,
formalized by Novikoff (1962).

\begin{theorem}[Perceptron convergence]\label{thm:found-convergence}
Suppose the training set
$\{(\vect{x}^{(k)}, y^{(k)})\}_{k=1}^{m}$ is linearly separable with
margin $\gamma > 0$: there exists a unit vector $\vect{w}^{\star}$,
$\lVert\vect{w}^{\star}\rVert = 1$, such that
$y^{(k)}\,\vect{w}^{\star\top}\vect{x}^{(k)} \geq \gamma$ for all $k$.
Let $R = \max_k \lVert\vect{x}^{(k)}\rVert$. Then the perceptron
algorithm~\eqref{eq:found-perceptron-update}, started from
$\vect{w} = \vect{0}$, makes at most
\begin{equation}
  T \;\leq\; \left(\frac{R}{\gamma}\right)^{2}
  \label{eq:found-novikoff}
\end{equation}
updates before finding a separating hyperplane.
\end{theorem}

\begin{remark}
The bound~\eqref{eq:found-novikoff} is independent of the input dimension
$n$ and of the number of examples $m$: only the \emph{normalized margin}
$\gamma / R$ matters. This is an early instance of a recurring theme —
the difficulty of a learning problem is governed by geometric quantities,
not by raw dimensionality.
\end{remark}

Shortly after the perceptron, Widrow and Hoff (1960) introduced ADALINE,
which differs in one crucial respect: the error is computed on the
\emph{linear} pre-activation $z = \vect{w}\transp\vect{x} + b$ rather than
on the thresholded output. Minimizing the squared error
$\tfrac{1}{2}(d - z)^2$ against a target $d$ gives the \emph{delta rule}
(or LMS, least-mean-squares, rule)
\begin{equation}
  \vect{w} \;\leftarrow\; \vect{w} + \eta\,(d - z)\,\vect{x},
  \label{eq:found-adaline}
\end{equation}
which, unlike~\eqref{eq:found-perceptron-update}, \emph{is} genuine
stochastic gradient descent on a differentiable objective. The delta rule
keeps improving even after the data are separated, driving the weights
toward the minimum mean-squared-error solution, and it does not diverge on
non-separable data. Gradient-based learning of exactly this kind — extended
to many layers — is the subject of the next chapter.

% ----------------------------------------------------------------------------
\subsection{The Limits of Linear Separation: XOR}
% ----------------------------------------------------------------------------

The perceptron can only realize decision boundaries that are hyperplanes.
Minsky and Papert (1969) analyzed this restriction with mathematical
precision, and their canonical counterexample is the exclusive-or function
XOR, shown in Figure~\ref{fig:found-xor}: the positive examples
$(0,1)$ and $(1,0)$ sit on one diagonal of the unit square, the negative
examples $(0,0)$ and $(1,1)$ on the other, and no straight line separates
two diagonals. The proof is elementary. If a separating line
$w_1 x_1 + w_2 x_2 + b = 0$ existed, then $(0,0) \mapsto 0$ forces
$b < 0$, while the positive cases force $w_1 + b \geq 0$ and
$w_2 + b \geq 0$; adding these, $w_1 + w_2 + 2b \geq 0$, hence
$w_1 + w_2 + b \geq -b > 0$, which would classify $(1,1)$ as positive — a
contradiction.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[scale=2.6]
    % axes
    \draw[fleche, black!60] (-0.30, 0) -- (1.55, 0)
      node[below, font=\small] {$x_1$};
    \draw[fleche, black!60] (0, -0.30) -- (0, 1.55)
      node[left, font=\small] {$x_2$};
    % the two hidden-unit hyperplanes
    \draw[cgate, dashed, thick] (-0.15, 0.65) -- (0.65, -0.15)
      node[etiquette, below, text=cgate!60!black]
      {$x_1 + x_2 = \tfrac{1}{2}$};
    \draw[cgate, dashed, thick] (0.38, 1.18) -- (1.18, 0.38)
      node[etiquette, below right, text=cgate!60!black]
      {$x_1 + x_2 = \tfrac{3}{2}$};
    % class 0 (blue) and class 1 (red) points
    \node[circle, fill=cinput,  draw=cinput!60!black,  inner sep=2.4pt,
          label={[etiquette]below left:$(0,0)$}]  at (0,0) {};
    \node[circle, fill=cinput,  draw=cinput!60!black,  inner sep=2.4pt,
          label={[etiquette]above right:$(1,1)$}] at (1,1) {};
    \node[circle, fill=coutput, draw=coutput!60!black, inner sep=2.4pt,
          label={[etiquette]above left:$(0,1)$}]  at (0,1) {};
    \node[circle, fill=coutput, draw=coutput!60!black, inner sep=2.4pt,
          label={[etiquette]below right:$(1,0)$}] at (1,0) {};
  \end{tikzpicture}
  \caption{The XOR problem. Negative examples (blue) occupy one diagonal
    of the unit square, positive examples (red) the other; no single line
    separates the two classes. The two dashed lines show the resolution by
    a hidden layer: two threshold units implementing
    $x_1 + x_2 \geq \tfrac{1}{2}$ (OR) and $x_1 + x_2 \leq \tfrac{3}{2}$
    (NAND) carve out the strip between the lines, and an AND unit on top
    of them computes XOR exactly.}
  \label{fig:found-xor}
\end{figure}

Crucially, XOR \emph{is} solvable with one hidden layer:
$\mathrm{XOR}(x_1, x_2) = \mathrm{OR}(x_1, x_2) \wedge
\neg\,\mathrm{AND}(x_1, x_2)$, i.e.\ two threshold units feeding a third.
Minsky and Papert's pessimism about such multilayer extensions — for which
no training algorithm was then known — is commonly cited as a trigger of
the first connectionist winter, which lasted until the mid-1980s. The
missing algorithm, backpropagation, is derived in the next chapter; the
representational question of what multilayer networks \emph{can} express
is answered at the end of this one.

% ----------------------------------------------------------------------------
\section{Activation Functions}
% ----------------------------------------------------------------------------

The nonlinearity $\varphi$ is not a detail: without it, a network of any
depth collapses. If every layer applied only an affine map, their
composition would again be affine, and the deepest network would be
exactly as expressive as a single linear layer. The choice of $\varphi$
also governs how gradients flow backward through the network — as we will
see in the next chapter, training multiplies derivatives $\varphi'$ across
layers, so activations that \emph{saturate} (have near-zero derivative
over most of their domain) starve deep networks of learning signal. We now
review the five activations that dominate practice, giving for each the
definition and the derivative; Figure~\ref{fig:found-activations} plots
them side by side.

\paragraph{Sigmoid.} The logistic sigmoid maps $\R$ onto $(0,1)$ and was
historically the default choice:
\begin{equation}
  \sigma(z) \;=\; \frac{1}{1 + e^{-z}},
  \qquad
  \sigma'(z) \;=\; \sigma(z)\bigl(1 - \sigma(z)\bigr).
  \label{eq:found-sigmoid}
\end{equation}
Its derivative is bounded by $\sigma'(0) = \tfrac{1}{4}$ and decays
exponentially for $\lvert z \rvert \gtrsim 5$: the function
\emph{saturates}, and its outputs are not zero-centred, which induces
correlated gradient signs within a layer. It survives today mainly in
gates and binary output units.

\paragraph{Hyperbolic tangent.} A rescaled sigmoid,
$\tanh(z) = 2\sigma(2z) - 1$, with range $(-1, 1)$:
\begin{equation}
  \tanh(z) \;=\; \frac{e^{z} - e^{-z}}{e^{z} + e^{-z}},
  \qquad
  \frac{d}{dz}\tanh(z) \;=\; 1 - \tanh^{2}(z).
  \label{eq:found-tanh}
\end{equation}
Zero-centred and with maximal derivative $1$ at the origin, it is better
conditioned than the sigmoid for hidden layers, though still saturating;
it remains standard inside recurrent cells.

\paragraph{ReLU.} The rectified linear unit, repopularized around
2010--2012, is the piecewise-linear map
\begin{equation}
  \mathrm{ReLU}(z) \;=\; \max(0, z),
  \qquad
  \mathrm{ReLU}'(z) \;=\;
  \begin{cases}
    1 & z > 0,\\
    0 & z < 0,
  \end{cases}
  \label{eq:found-relu}
\end{equation}
with the convention $\mathrm{ReLU}'(0) = 0$ at the (measure-zero)
non-differentiable point. For positive inputs the gradient is exactly $1$,
so ReLU does not saturate on its active half — the property that unlocked
the training of genuinely deep networks. Its failure mode is the
\emph{dying ReLU}: a unit pushed into the negative regime for every input
receives zero gradient forever and never recovers.

\paragraph{Leaky ReLU.} A minimal repair of the dying-unit problem replaces
the zero slope with a small $\alpha > 0$ (typically $\alpha = 0.01$):
\begin{equation}
  \mathrm{LReLU}(z) \;=\; \max(\alpha z,\, z)
  \;=\;
  \begin{cases}
    z        & z \geq 0,\\
    \alpha z & z < 0,
  \end{cases}
  \qquad
  \mathrm{LReLU}'(z) \;=\;
  \begin{cases}
    1      & z > 0,\\
    \alpha & z < 0.
  \end{cases}
  \label{eq:found-leaky}
\end{equation}
The parametric variant (PReLU) learns $\alpha$ per channel at negligible
cost.

\paragraph{GELU.} The Gaussian error linear unit weights its input by the
probability that a standard Gaussian falls below it. With $\Phi$ and
$\phi$ the standard normal cumulative distribution function and density,
\begin{equation}
  \mathrm{GELU}(z) \;=\; z\,\Phi(z)
  \;=\; \frac{z}{2}\left[1 + \operatorname{erf}\!\left(
        \frac{z}{\sqrt{2}}\right)\right],
  \qquad
  \frac{d}{dz}\mathrm{GELU}(z) \;=\; \Phi(z) + z\,\phi(z).
  \label{eq:found-gelu}
\end{equation}
GELU can be read as a deterministic version of stochastic gating: instead
of dropping a unit with probability $1 - \Phi(z)$, it scales the unit by
the expected mask. It is smooth, non-monotonic (a shallow negative dip
near $z \approx -0.75$), and is the default activation in Transformer
architectures. Implementations commonly use the tanh approximation
\begin{equation}
  \mathrm{GELU}(z) \;\approx\; \tfrac{1}{2}\, z \left(1 + \tanh\!\left[
    \sqrt{\tfrac{2}{\pi}}\left(z + 0.044715\, z^{3}\right)
  \right]\right).
  \label{eq:found-gelu-approx}
\end{equation}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
    \begin{axis}[
        width=0.50\textwidth, height=6.2cm,
        title={\small (a) Activation functions},
        xlabel={$z$}, ylabel={$\varphi(z)$},
        xmin=-4, xmax=4, ymin=-1.6, ymax=4,
        grid=major, grid style={black!12},
        legend pos=north west,
        legend style={font=\scriptsize, fill=white, fill opacity=0.85,
                      text opacity=1, draw=black!30},
        every axis plot/.append style={thick},
        samples=200, domain=-4:4,
      ]
      \addplot[cinput]  {1/(1+exp(-x))};
      \addlegendentry{sigmoid}
      \addplot[chidden] {tanh(x)};
      \addlegendentry{$\tanh$}
      \addplot[coutput] {max(0,x)};
      \addlegendentry{ReLU}
      \addplot[cgate, dashed] {max(0,x) + 0.1*min(0,x)};
      \addlegendentry{Leaky ReLU}
      \addplot[cmem]
        {0.5*x*(1 + tanh(0.7978845608*(x + 0.044715*x^3)))};
      \addlegendentry{GELU}
    \end{axis}
  \end{tikzpicture}\hfill
  \begin{tikzpicture}
    \begin{axis}[
        width=0.50\textwidth, height=6.2cm,
        title={\small (b) Derivatives},
        xlabel={$z$}, ylabel={$\varphi'(z)$},
        xmin=-4, xmax=4, ymin=-0.25, ymax=1.35,
        grid=major, grid style={black!12},
        legend pos=north west,
        legend style={font=\scriptsize, fill=white, fill opacity=0.85,
                      text opacity=1, draw=black!30},
        every axis plot/.append style={thick},
        samples=200, domain=-4:4,
      ]
      \addplot[cinput]  {exp(-x)/((1+exp(-x))^2)};
      \addlegendentry{sigmoid$'$}
      \addplot[chidden] {1 - tanh(x)^2};
      \addlegendentry{$\tanh'$}
      \addplot[coutput] coordinates {(-4,0) (0,0)};
      \addlegendentry{ReLU$'$}
      \addplot[coutput, forget plot] coordinates {(0,1) (4,1)};
      \addplot[cgate, dashed] coordinates {(-4,0.1) (0,0.1)};
      \addlegendentry{Leaky ReLU$'$}
      \addplot[cgate, dashed, forget plot] coordinates {(0,1) (4,1)};
      \addplot[cmem]
        {0.5*(1 + tanh(0.7978845608*(x + 0.044715*x^3)))
         + x*0.3989422804*exp(-x^2/2)};
      \addlegendentry{GELU$'$}
    \end{axis}
  \end{tikzpicture}
  \caption{The five standard activation functions
    \eqref{eq:found-sigmoid}--\eqref{eq:found-gelu} (left) and their
    derivatives (right). Leaky ReLU is drawn with $\alpha = 0.1$ for
    visibility (in practice $\alpha = 0.01$ is typical). Note the
    saturation of sigmoid and $\tanh$ — their derivatives vanish for
    $\lvert z\rvert \gtrsim 4$ — against the constant unit slope of the
    ReLU family on the positive half-line, and the smooth non-monotonic
    profile of GELU.}
  \label{fig:found-activations}
\end{figure}

% ----------------------------------------------------------------------------
\subsection{The Softmax Function}
% ----------------------------------------------------------------------------

Multiclass classification requires a vector-valued output layer that maps
$K$ real \emph{logits} to a probability distribution over $K$ classes.
This is the role of the softmax:
\begin{equation}
  \softmax(\vect{z})_i \;=\; \frac{e^{z_i}}{\sum_{j=1}^{K} e^{z_j}},
  \qquad i = 1, \dots, K,
  \label{eq:found-softmax}
\end{equation}
whose outputs are positive and sum to one. Its Jacobian has the compact
form
\begin{equation}
  \frac{\partial\, \softmax(\vect{z})_i}{\partial z_j}
  \;=\;
  \softmax(\vect{z})_i \left(\delta_{ij} - \softmax(\vect{z})_j\right),
  \label{eq:found-softmax-jacobian}
\end{equation}
with $\delta_{ij}$ the Kronecker delta — an expression that will combine
particularly gracefully with the cross-entropy loss in the next chapter.

\begin{remark}[Shift invariance and temperature]
Softmax is invariant to adding a constant to every logit,
$\softmax(\vect{z} + c\vect{1}) = \softmax(\vect{z})$; numerically stable
implementations exploit this by subtracting $\max_j z_j$ before
exponentiating. Dividing the logits by a \emph{temperature} $T > 0$
interpolates between a hard maximum ($T \to 0$) and the uniform
distribution ($T \to \infty$).
\end{remark}

% ----------------------------------------------------------------------------
\section{The Multilayer Perceptron}
% ----------------------------------------------------------------------------

A single neuron detects one linear feature; the multilayer perceptron
composes entire \emph{layers} of them, each layer feeding the next.

\begin{definition}[Multilayer perceptron]\label{def:found-mlp}
An MLP with $L$ layers of widths $n_1, \dots, n_L$ on inputs of dimension
$n_0$ is defined by weight matrices
$\mat{W}^{(\ell)} \in \R^{n_\ell \times n_{\ell-1}}$ and bias vectors
$\vect{b}^{(\ell)} \in \R^{n_\ell}$, $\ell = 1, \dots, L$. Setting
$\vect{a}^{(0)} = \vect{x}$, the \emph{forward propagation} computes, for
$\ell = 1, \dots, L$,
\begin{align}
  \vect{z}^{(\ell)} &= \mat{W}^{(\ell)} \vect{a}^{(\ell-1)}
                       + \vect{b}^{(\ell)},
  \label{eq:found-mlp-z}\\
  \vect{a}^{(\ell)} &= \varphi^{(\ell)}\!\left(\vect{z}^{(\ell)}\right),
  \label{eq:found-mlp-a}
\end{align}
where $\varphi^{(\ell)}$ acts componentwise, and the network output is
$\hat{\vect{y}} = \vect{a}^{(L)}$.
\end{definition}

Componentwise, \eqref{eq:found-mlp-z} reads
\begin{equation}
  z^{(\ell)}_j \;=\; \sum_{i=1}^{n_{\ell-1}}
    W^{(\ell)}_{ji}\, a^{(\ell-1)}_i + b^{(\ell)}_j,
  \label{eq:found-mlp-component}
\end{equation}
so that each unit of layer $\ell$ is exactly an artificial neuron in the
sense of Definition~\ref{def:found-neuron}, whose inputs are the
activations of the previous layer. The final activation
$\varphi^{(L)}$ is chosen to match the task: identity for regression,
sigmoid for binary classification, softmax~\eqref{eq:found-softmax} for
multiclass classification, while hidden layers use one of the
nonlinearities of Figure~\ref{fig:found-activations}. A network with two
hidden layers is drawn in Figure~\ref{fig:found-mlp}.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
    % --- input layer --------------------------------------------------------
    \foreach \i in {1,2,3}
      \node[ninput] (x\i) at (0, 2.2-\i*1.1) {$x_{\i}$};
    % --- hidden layer 1 -----------------------------------------------------
    \foreach \j in {1,...,4}
      \node[nhidden] (h1\j) at (2.7, 2.75-\j*1.1) {};
    % --- hidden layer 2 -----------------------------------------------------
    \foreach \j in {1,...,4}
      \node[nhidden] (h2\j) at (5.4, 2.75-\j*1.1) {};
    % --- output layer -------------------------------------------------------
    \foreach \k in {1,2}
      \node[noutput] (o\k) at (8.1, 1.1-\k*1.1) {};
    % --- connections ----------------------------------------------------------
    \foreach \i in {1,2,3} \foreach \j in {1,...,4}
      \draw[black!35, semithick] (x\i) -- (h1\j);
    \foreach \i in {1,...,4} \foreach \j in {1,...,4}
      \draw[black!35, semithick] (h1\i) -- (h2\j);
    \foreach \i in {1,...,4} \foreach \k in {1,2}
      \draw[black!35, semithick] (h2\i) -- (o\k);
    % --- outputs ---------------------------------------------------------------
    \draw[fleche] (o1) -- ++(1.3,0) node[right] {$\hat{y}_1$};
    \draw[fleche] (o2) -- ++(1.3,0) node[right] {$\hat{y}_2$};
    % --- weight-matrix labels ---------------------------------------------------
    \node[etiquette] at (1.35, 2.55) {$\mat{W}^{(1)}, \vect{b}^{(1)}$};
    \node[etiquette] at (4.05, 2.55) {$\mat{W}^{(2)}, \vect{b}^{(2)}$};
    \node[etiquette] at (6.75, 2.55) {$\mat{W}^{(3)}, \vect{b}^{(3)}$};
    % --- layer labels ---------------------------------------------------------
    \node[etiquette, align=center] at (0,   -2.6)
      {input layer\\ $\vect{a}^{(0)} = \vect{x}$};
    \node[etiquette, align=center] at (2.7, -2.6)
      {hidden layer 1\\ $\vect{a}^{(1)}$};
    \node[etiquette, align=center] at (5.4, -2.6)
      {hidden layer 2\\ $\vect{a}^{(2)}$};
    \node[etiquette, align=center] at (8.1, -2.6)
      {output layer\\ $\hat{\vect{y}} = \vect{a}^{(3)}$};
  \end{tikzpicture}
  \caption{A fully connected network with two hidden layers
    ($n_0 = 3$, $n_1 = n_2 = 4$, $n_3 = 2$). Each edge carries one entry
    of a weight matrix $\mat{W}^{(\ell)}$; each column of neurons applies
    the affine map~\eqref{eq:found-mlp-z} followed by the pointwise
    nonlinearity~\eqref{eq:found-mlp-a}.}
  \label{fig:found-mlp}
\end{figure}

\begin{remark}[Batched computation]
For a mini-batch of $m$ examples stacked as rows of
$\mat{X} \in \R^{m \times n_0}$, forward propagation becomes
$\mat{Z}^{(\ell)} = \mat{A}^{(\ell-1)} \mat{W}^{(\ell)\top}
+ \vect{1}_m \vect{b}^{(\ell)\top}$ — a chain of dense matrix products.
This is why MLPs map so efficiently onto modern hardware: the entire
network is a sequence of GEMM primitives.
\end{remark}

\begin{remark}[Why the nonlinearity is essential]
If $\varphi^{(\ell)} = \mathrm{id}$ for all $\ell$, then
$\hat{\vect{y}} = \mat{W}^{(L)} \cdots \mat{W}^{(1)} \vect{x} + \vect{c}$
for some constant $\vect{c}$: the composition of affine maps is affine,
and depth buys nothing. All the expressive power of the MLP resides in the
interleaving of~\eqref{eq:found-mlp-z} with the
nonlinearity~\eqref{eq:found-mlp-a}.
\end{remark}

% ----------------------------------------------------------------------------
\subsection{Universal Approximation}
% ----------------------------------------------------------------------------

How expressive is the MLP? The classical answer, due independently to
Cybenko (1989) and to Hornik, Stinchcombe and White (1989), is that
\emph{one} hidden layer already suffices, provided it is wide enough.

\begin{property}[Universal approximation]\label{prop:found-uat}
Let $\varphi$ be a continuous sigmoidal function
($\varphi(t) \to 1$ as $t \to +\infty$ and $\varphi(t) \to 0$ as
$t \to -\infty$). Then finite sums of the form
\begin{equation}
  G(\vect{x}) \;=\; \sum_{j=1}^{N} \alpha_j\,
    \varphi\!\left(\vect{w}_j\transp \vect{x} + \theta_j\right)
  \label{eq:found-uat}
\end{equation}
are dense in $C([0,1]^{n})$ for the uniform norm: for every continuous
$f : [0,1]^n \to \R$ and every $\varepsilon > 0$, there exist $N$ and
parameters $\{\alpha_j, \vect{w}_j, \theta_j\}$ such that
$\lvert G(\vect{x}) - f(\vect{x})\rvert < \varepsilon$ for all
$\vect{x} \in [0,1]^n$. More generally (Leshno et al., 1993), a
one-hidden-layer network with a locally bounded, piecewise-continuous
activation is a universal approximator \emph{if and only if} the
activation is not a polynomial.
\end{property}

The ``if and only if'' clause explains why ReLU — which is not sigmoidal —
is nevertheless universal, and why a purely linear network is not. Two
caveats temper the theorem's optimism, and both shape the rest of this
book~\cite{goodfellow2016book}. First,
Property~\ref{prop:found-uat} is an \emph{existence} result: it is silent
on how many hidden units are required (the width $N$ may grow
exponentially with the input dimension $n$) and on whether any learning
algorithm will \emph{find} the approximating weights. Second, it concerns
shallow networks only; depth-separation results show that certain
functions computable by a deep network with polynomially many units
require exponentially many units at bounded depth. Approximation theory
thus motivates depth, but it is the training machinery of the next
chapter — loss functions, backpropagation, and stochastic optimization —
that makes depth usable in practice.

% ----------------------------------------------------------------------------
\section{A Contrast: Radial Basis Function Networks}
% ----------------------------------------------------------------------------

The MLP is not the only way to combine simple units into a universal
approximator, and a brief look at its classical alternative sharpens our
understanding of what makes the MLP distinctive. A \emph{radial basis
function} (RBF) network, introduced by Broomhead and Lowe (1988) and
refined by Moody and Darken (1989), has exactly one hidden layer of $J$
\emph{locally tuned} units, each defined by a centre
$\vect{\mu}_j \in \R^n$ and a width $\sigma_j > 0$, followed by a linear
output layer:
\begin{equation}
  f(\vect{x}) \;=\; \sum_{j=1}^{J} w_j\,
    \varphi_j(\vect{x}) + b,
  \qquad
  \varphi_j(\vect{x}) \;=\;
    \exp\!\left(
      -\frac{\lVert \vect{x} - \vect{\mu}_j \rVert^{2}}{2\sigma_j^{2}}
    \right).
  \label{eq:found-rbf}
\end{equation}
The contrast with Definition~\ref{def:found-neuron} is fundamental. An
MLP unit computes an \emph{inner product} $\vect{w}\transp\vect{x}$ and
responds along a hyperplane — a global, distributed representation. An
RBF unit computes a \emph{distance} $\lVert\vect{x} - \vect{\mu}_j\rVert$
and responds only in a localized neighbourhood of its centre — a local,
spherical receptive field. Locality makes RBF networks fast to train:
once the centres are placed (by random subsampling or $k$-means
clustering), the model is \emph{linear} in the output weights, and with
the design matrix $\Phi_{ij} = \varphi_j(\vect{x}^{(i)})$ and targets
$\vect{y}$, the ridge-regularized least-squares solution is closed-form,
\begin{equation}
  \vect{w} \;=\;
  \left(\mat{\Phi}\transp \mat{\Phi} + \lambda \mat{I}\right)^{-1}
  \mat{\Phi}\transp \vect{y}.
  \label{eq:found-rbf-ls}
\end{equation}
The price of locality is the curse of dimensionality: covering a
high-dimensional input space with local bumps requires exponentially many
centres, whereas the global half-space features of the MLP can be shared
and composed. This trade-off — local interpolation versus global,
composable features — anticipates a pattern that recurs throughout the
book, and it is the composable option that deep learning has embraced.
Everything now hinges on one question: how are the weights of a
multilayer network actually learned? The next chapter answers it.