Neural Networks

⚡ Key Takeaways

Neural networks are parametric function approximators built from layered compositions of weighted sums and nonlinear activation functions, trained by gradient descent on a loss function. Key result: a feedforward network with a single sufficiently large hidden layer can approximate any continuous function on a compact set to arbitrary accuracy (Universal Approximation). Applies in: machine learning, computer vision, natural language processing, function approximation, control. Who/when: McCulloch & Pitts (1943), Rosenblatt (1958), Rumelhart–Hinton–Williams backpropagation (1986), deep learning revival (2006–2012).

💡 The Core Insight

A single neuron computes a linear decision boundary; it cannot represent nonlinearly separable patterns (e.g., XOR). But if you feed the outputs of many neurons into another layer of neurons, the composition of affine maps and nonlinearities becomes a universal building block. Depth and nonlinearity together convert a limited linear model into a representation that can bend, fold, and carve the input space arbitrarily. Crucially, the whole composite remains differentiable in its parameters, so the gradient of any scalar loss can be computed efficiently by reverse-mode differentiation.

DefinitionArtificial Neuron

A single neuron with input $\mathbf{x} \in \mathbb{R}^n$ , weight vector $\mathbf{w} \in \mathbb{R}^n$ , bias $b \in \mathbb{R}$ , and activation function $\sigma: \mathbb{R} \to \mathbb{R}$ computes:

1

\quad a = \sigma\!\left( \mathbf{w}^\top \mathbf{x} + b \right) = \sigma\!\left( \sum_{i=1}^{n} w_i x_i + b \right)

Derivation hint: model the biological neuron's "weighted summation of inputs followed by a threshold firing rule"; replace the hard threshold with a smooth $\sigma$ for differentiability. Here $z = \mathbf{w}^\top \mathbf{x} + b$ is the pre-activation (or logit), and $a$ is the activation (output). The bias $b$ shifts the decision boundary away from the origin.

DefinitionFeedforward Network / Multilayer Perceptron

A network of $L$ layers maps input $\mathbf{a}^{(0)} = \mathbf{x}$ through layers indexed $\ell = 1, \dots, L$ . Let $W^{(\ell)} \in \mathbb{R}^{n_\ell \times n_{\ell-1}}$ be the weight matrix and $\mathbf{b}^{(\ell)} \in \mathbb{R}^{n_\ell}$ the bias of layer $\ell$ . Then:

2

\quad \mathbf{z}^{(\ell)} = W^{(\ell)} \mathbf{a}^{(\ell-1)} + \mathbf{b}^{(\ell)}, \qquad \mathbf{a}^{(\ell)} = \sigma^{(\ell)}\!\left( \mathbf{z}^{(\ell)} \right)

Derivation hint: stack $n_\ell$ neurons of form [1] into one layer; each row of $W^{(\ell)}$ is one neuron's weight vector, and $\sigma$ is applied elementwise. The full network is the composition $f_\theta(\mathbf{x}) = \sigma^{(L)} \circ A^{(L)} \circ \dots \circ \sigma^{(1)} \circ A^{(1)}(\mathbf{x})$ where $A^{(\ell)}(\mathbf{a}) = W^{(\ell)}\mathbf{a} + \mathbf{b}^{(\ell)}$ , and $\theta = \{W^{(\ell)}, \mathbf{b}^{(\ell)}\}_{\ell=1}^{L}$ .

DefinitionCommon Activation Functions

3

\quad \sigma_{\text{sig}}(z) = \frac{1}{1+e^{-z}}, \quad \tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}}, \quad \text{ReLU}(z) = \max(0, z)

Derivation hint: sigmoid is the logistic CDF squashing $\mathbb{R}\to(0,1)$ ; $\tanh$ is a rescaled sigmoid; ReLU is the simplest piecewise-linear nonlinearity, $\partial_z\text{ReLU} = \mathbf{1}[z>0]$ .

DefinitionLoss Functions

For supervised learning with targets $\mathbf{y}$ , common losses for a dataset of $N$ examples are mean squared error (regression) and cross-entropy (classification):

4

\quad \mathcal{L}_{\text{MSE}} = \frac{1}{N}\sum_{k=1}^{N} \left\| f_\theta(\mathbf{x}_k) - \mathbf{y}_k \right\|^2, \qquad \mathcal{L}_{\text{CE}} = -\frac{1}{N}\sum_{k=1}^{N} \sum_{c} y_{k,c}\,\log \hat{p}_{k,c}

Derivation hint: MSE is the negative log-likelihood under a Gaussian noise model; cross-entropy is the negative log-likelihood under a categorical (softmax) model. The softmax output converts logits $\mathbf{z}$ into a probability vector: $\hat{p}_c = e^{z_c} / \sum_j e^{z_j}$ .

TheoremUniversal Approximation (Cybenko 1989; Hornik 1991)

Let $\sigma$ be a continuous, non-constant, bounded function (e.g. sigmoid). For any continuous function $g: K \to \mathbb{R}$ on a compact set $K \subset \mathbb{R}^n$ and any $\varepsilon > 0$ , there exist $N \in \mathbb{N}$ , weights $\mathbf{w}_i \in \mathbb{R}^n$ , biases $b_i \in \mathbb{R}$ , and coefficients $\alpha_i \in \mathbb{R}$ such that:

5

\quad \sup_{\mathbf{x}\in K}\left| g(\mathbf{x}) - \sum_{i=1}^{N} \alpha_i\,\sigma\!\left(\mathbf{w}_i^\top \mathbf{x} + b_i\right) \right| < \varepsilon

Derivation hint: the set of single-hidden-layer functions is dense in $C(K)$ ; Cybenko's proof uses the Hahn–Banach theorem and discriminatory property of $\sigma$ to show no nonzero signed measure annihilates this set. That is, a single hidden layer of unbounded width can approximate any continuous function uniformly on compacts. Width may be exponential; depth can give exponentially more efficient representations.

ProofBackpropagation

Goal: compute $\partial \mathcal{L} / \partial W^{(\ell)}_{ij}$ and $\partial \mathcal{L} / \partial b^{(\ell)}_i$ for all layers.

Step 1 — Define the error signal. Let $\delta^{(\ell)}_i = \partial \mathcal{L} / \partial z^{(\ell)}_i$ , the sensitivity of the loss to the pre-activation of neuron $i$ in layer $\ell$ . Collect into $\boldsymbol\delta^{(\ell)}$ .

Step 2 — Output layer. By the chain rule through $\mathbf{a}^{(L)} = \sigma^{(L)}(\mathbf{z}^{(L)})$ :

6

\quad \boldsymbol\delta^{(L)} = \nabla_{\mathbf{a}^{(L)}} \mathcal{L} \;\odot\; \sigma^{(L)\prime}\!\left(\mathbf{z}^{(L)}\right)

Derivation hint: $\partial\mathcal L/\partial z^{(L)}_i = (\partial\mathcal L/\partial a^{(L)}_i)(\partial a^{(L)}_i/\partial z^{(L)}_i)$ ; the second factor is $\sigma'$ ; $\odot$ is elementwise product.

Step 3 — Recursive backward pass. Since $z^{(\ell+1)}_j = \sum_i W^{(\ell+1)}_{ji} a^{(\ell)}_i + b^{(\ell+1)}_j$ and $a^{(\ell)}_i = \sigma(z^{(\ell)}_i)$ :

7

\quad \boldsymbol\delta^{(\ell)} = \left( W^{(\ell+1)\top} \boldsymbol\delta^{(\ell+1)} \right) \odot \sigma^{(\ell)\prime}\!\left(\mathbf{z}^{(\ell)}\right)

Derivation hint: apply the multivariable chain rule $\delta^{(\ell)}_i=\sum_j \delta^{(\ell+1)}_j (\partial z^{(\ell+1)}_j/\partial a^{(\ell)}_i)(\partial a^{(\ell)}_i/\partial z^{(\ell)}_i)$ ; the first partial is $W^{(\ell+1)}_{ji}$ .

Step 4 — Parameter gradients. Since $z^{(\ell)}_i$ depends on $W^{(\ell)}_{ij}$ through $a^{(\ell-1)}_j$ :

8

\quad \frac{\partial \mathcal{L}}{\partial W^{(\ell)}_{ij}} = \delta^{(\ell)}_i \, a^{(\ell-1)}_j, \qquad \frac{\partial \mathcal{L}}{\partial b^{(\ell)}_i} = \delta^{(\ell)}_i

Derivation hint: $\partial z^{(\ell)}_i/\partial W^{(\ell)}_{ij} = a^{(\ell-1)}_j$ and $\partial z^{(\ell)}_i/\partial b^{(\ell)}_i = 1$ ; multiply by $\delta^{(\ell)}_i$ .

Step 5 — Cost. One forward pass plus one backward pass computes the entire gradient in $O(|\theta|)$ time — the same order as evaluating the network itself. $\blacksquare$

∎

DefinitionGradient Descent Update

Parameters are updated against the gradient with learning rate $\eta > 0$ . Stochastic gradient descent (SGD) uses a minibatch $\mathcal{B}$ :

9

\quad \theta \leftarrow \theta - \eta\,\nabla_\theta \mathcal{L}_{\mathcal{B}}(\theta), \qquad \nabla_\theta \mathcal{L}_{\mathcal{B}} = \frac{1}{|\mathcal{B}|}\sum_{k\in\mathcal{B}} \nabla_\theta \ell(f_\theta(\mathbf{x}_k), \mathbf{y}_k)

Derivation hint: first-order Taylor expansion $\mathcal L(\theta-\eta\nabla)\approx \mathcal L(\theta)-\eta\|\nabla\|^2$ shows movement along $-\nabla$ decreases loss for small $\eta$ ; the minibatch estimate is an unbiased gradient estimator.

Figure

A two-hidden-layer feedforward network: forward signal flow and backward gradient flow

FR

Frank Rosenblatt

1928–1971

An American psychologist who, in 1958, built the Perceptron — both an algorithm and a physical machine (the Mark I Perceptron) with motor-driven potentiometers as adjustable weights, designed to recognize images. Rosenblatt proved the Perceptron Convergence Theorem: for linearly separable data, the simple update $\mathbf{w} \leftarrow \mathbf{w} + y_k\mathbf{x}_k$ on misclassified points terminates in finitely many steps. His optimistic claims drew sharp criticism; Minsky and Papert's 1969 book Perceptrons showed single-layer perceptrons cannot compute XOR, contributing to the first "AI winter." Multilayer networks with backpropagation eventually vindicated the broader research program two decades later.

🧠 Intuition

Think of each neuron as drawing a hyperplane in input space and outputting "how far, and on which side" (softened by $\sigma$ ). The first hidden layer carves space into linear regions; the second layer takes logical combinations of those regions (intersections via AND-like patterns, unions via OR-like patterns); deeper layers combine those into ever-more-elaborate shapes. With ReLU, the network is literally a continuous piecewise-linear function — the input space is partitioned into polytopes, and the network is affine on each. Depth multiplies the number of linear regions exponentially, which is why deep narrow networks can be vastly more expressive than shallow wide ones with the same parameter count. Training "bends" all these boundaries simultaneously by following the negative gradient downhill on the loss surface.

ExampleForward pass through one neuron

Given: input $\mathbf{x} = (1, 2)^\top$ , weights $\mathbf{w} = (0.5, -1)^\top$ , bias $b = 0.5$ , activation = sigmoid.

Step 1 — Pre-activation: $z = 0.5(1) + (-1)(2) + 0.5 = 0.5 - 2 + 0.5 = -1.0$ .

Step 2 — Activation: $a = \sigma(-1.0) = \dfrac{1}{1+e^{1.0}} = \dfrac{1}{1+2.718} = \dfrac{1}{3.718} = 0.269$ .

Step 3 — Derivative (for later backprop): $\sigma'(z) = a(1-a) = 0.269 \times 0.731 = 0.197$ .

\boxed{a = 0.269,\qquad \sigma'(z) = 0.197\ \text{(dimensionless)}}

ExampleOne backprop / SGD step on MSE

Given: the neuron above with output $a = 0.269$ , target $y = 1$ , MSE loss $\ell = (a - y)^2$ , learning rate $\eta = 0.1$ .

Step 1 — Loss gradient w.r.t. output: $\partial \ell / \partial a = 2(a - y) = 2(0.269 - 1) = -1.462$ .

Step 2 — Error signal: $\delta = \dfrac{\partial \ell}{\partial a}\,\sigma'(z) = (-1.462)(0.197) = -0.288$ .

Step 3 — Weight gradients: $\partial\ell/\partial w_1 = \delta\,x_1 = -0.288(1) = -0.288$ ; $\partial\ell/\partial w_2 = \delta\,x_2 = -0.288(2) = -0.576$ ; $\partial\ell/\partial b = \delta = -0.288$ .

Step 4 — Update [9]: $w_1 \leftarrow 0.5 - 0.1(-0.288) = 0.529$ ; $w_2 \leftarrow -1 - 0.1(-0.576) = -0.942$ ; $b \leftarrow 0.5 - 0.1(-0.288) = 0.529$ .

\boxed{\mathbf{w} \to (0.529,\,-0.942),\quad b \to 0.529\ \text{(moves output toward target 1)}}

⚠️ Common mistake

"More layers always help." Naïvely stacking layers can worsen training due to vanishing/exploding gradients: by [7], $\boldsymbol\delta$ is repeatedly multiplied by $W^\top$ and $\sigma'$ . With sigmoids ( $\sigma' \le 0.25$ ), the gradient shrinks geometrically with depth, so early layers barely learn. Remedies — ReLU activations, careful initialization (He/Xavier), batch normalization, and residual connections — were essential to make deep networks trainable. Depth without these tricks is often harder, not better.

⚠️ Common mistake

"Universal approximation means networks can learn anything from data." Theorem [5] is purely about existence of weights, not learnability. It guarantees nothing about (a) finding those weights by gradient descent, (b) how many samples are required, or (c) generalization to unseen inputs. Approximation, optimization, and generalization are three separate problems.

CounterexampleA single neuron cannot solve XOR

The XOR function maps $(0,0)\to 0$ , $(0,1)\to 1$ , $(1,0)\to 1$ , $(1,1)\to 0$ . A single neuron computes $\sigma(\mathbf{w}^\top\mathbf{x}+b)$ , whose decision boundary $\mathbf{w}^\top\mathbf{x}+b = 0$ is a single line. No line separates $\{(0,1),(1,0)\}$ from $\{(0,0),(1,1)\}$ — the positive and negative classes are interleaved at opposite corners. Resolution: one hidden layer of two neurons (e.g. computing OR and NAND) followed by an AND output neuron solves XOR exactly. This concrete failure of single-layer perceptrons, highlighted by Minsky–Papert (1969), motivated multilayer networks.

connection

Neural networks sit at the intersection of several fields. The training objective and update rule come from Gradient Descent and Convex Optimization (though the landscape is non-convex). Backpropagation is exactly reverse-mode Automatic Differentiation applied to a computational graph. The cross-entropy loss and softmax derive from Maximum Likelihood Estimation under a categorical model, linking to Probability Theory. The single-neuron model with sigmoid is precisely Logistic Regression, so a network generalizes a stack of regressions. Universal approximation rests on density arguments from Functional Analysis (Hahn–Banach, Stone–Weierstrass). The matrix operations in [2] are Linear Algebra, and convolutional variants connect to Fourier Analysis and signal processing.

🔬 Where this appears

⏳ History

- 1943 — McCulloch & Pitts publish a logical model of the neuron as a threshold unit, showing networks can compute logical functions.

- 1949 — Donald Hebb proposes Hebbian learning ("neurons that fire together wire together").

- 1958 — Rosenblatt introduces the Perceptron and proves its convergence theorem for linearly separable data.

- 1969 — Minsky & Papert's Perceptrons exposes the XOR limitation; funding and interest decline (first AI winter).

- 1974/1986 — Werbos (1974) and Rumelhart, Hinton & Williams (1986) popularize backpropagation for training multilayer networks.

- 1989 — Cybenko proves the Universal Approximation Theorem; LeCun applies convolutional networks to handwritten digits (LeNet).

- 1997 — Hochreiter & Schmidhuber introduce LSTM, solving long-range dependency learning in recurrent nets.

- 2012 — Krizhevsky, Sutskever & Hinton's AlexNet wins ImageNet by a wide margin on GPUs, igniting the deep-learning era.

- 2017 — Vaswani et al. introduce the Transformer ("Attention Is All You Need"), now the dominant architecture for language and beyond.

open-problem

Despite practical success, deep learning's theory has large gaps. Why does SGD generalize? Overparameterized networks with more parameters than data points can fit random labels yet still generalize on real data, defying classical bias-variance intuition (the "double descent" phenomenon). Why is non-convex optimization easy? The loss surface has exponentially many saddle points and local minima, yet SGD reliably finds good solutions — partial explanations invoke the geometry of overparameterized landscapes and the "lottery ticket" hypothesis. Expressivity vs. trainability: depth gives exponential expressive power, but provably learnable function classes remain narrow. Robustness and interpretability: networks are vulnerable to imperceptible adversarial perturbations and remain largely black boxes. Sample/energy efficiency: humans learn from far fewer examples and far less energy than current models. These questions span optimization theory, statistical learning theory, and approximation theory.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also