Neural Networks

The logistic regression model draws a linear decision boundary in the features we supply. Some label patterns require different features before a linear boundary can separate them. A neural network learns a transformation of the inputs along with the classifier that uses its output.

How can we simultaneously learn the features and the model?

We will construct features for a pattern that a linear classifier cannot separate, then use derivatives of the classification loss to show how those features can be learned.

Features for Classification

Consider the four equally weighted examples from Problem 10. The label is one when the two coordinates agree: \[ \begin{array}{c|rr|r} \text{Example}&x_1&x_2&y\\ \hline A&1&1&1\\ B&1&-1&0\\ C&-1&1&0\\ D&-1&-1&1 \end{array} \] A logistic classifier uses a score \(z=w_0+w_1x_1+w_2x_2\), where \(w_0\) is the weight of the constant feature. Predict class one when \(z>0\) and class zero otherwise. The score \(x_1+x_2-1\) gets three labels right, but no choice gets all four right.

Claim: No affine classifier separates these four examples.

Proof

Correct predictions on \(A\) and \(D\) require \[ \begin{aligned} w_0+w_1+w_2&>0,\\ w_0-w_1-w_2&>0. \end{aligned} \] Adding gives \(2w_0>0\). Correct predictions on \(B\) and \(C\) require \[ \begin{aligned} w_0+w_1-w_2&\leq0,\\ w_0-w_1+w_2&\leq0. \end{aligned} \] Adding gives \(2w_0\leq0\), a contradiction.

Features and Predictions

To separate these labels, we can construct features that respond when the coordinates agree. The sum \(x_1+x_2\) is positive at \(A\), negative at \(D\), and zero at both negative examples. The rectified linear unit (ReLU), \(\operatorname{ReLU}(t)=\max(0,t)\), keeps the positive part of a number. Applying it to the sum and its negative gives two features: \[ \begin{aligned} h_1&=\operatorname{ReLU}(x_1+x_2),\\ h_2&=\operatorname{ReLU}(-x_1-x_2). \end{aligned} \] A logistic classifier can now use \(h_1\) and \(h_2\) as its inputs. Using the sigmoid \(\sigma\) from Logistic Regression, it computes

\(\displaystyle z=h_1+h_2-1,\) \(\displaystyle p=\sigma(z)=\frac{1}{1+e^{-z}}.\)

Here \(p\) is the probability assigned to class one, and the coefficient \(-1\) supplies the classifier’s intercept. The plots compare the decision rule in the original input coordinates and in the new feature coordinates.

No line separates the original points. After the ReLU transformation, A and D move to (2, 0) and (0, 2), while B and C both move to (0, 0). The line h₁ + h₂ = 1 separates the two classes.

These features send \(A\) to \((2,0)\), \(D\) to \((0,2)\), and both \(B\) and \(C\) to \((0,0)\). Thus \(z=1\) for the positive examples and \(z=-1\) for the negative examples: all four are classified correctly. The two negative examples can share a representation because they have the same label.

Neural Networks

The two ReLU features above form a hidden layer: they are computed from the input and passed to a classifier. We chose their coefficients by hand to show that this representation can separate the labels. A neural network makes those coefficients trainable and can compose several such layers. Hidden layers compute intermediate features and the output layer turns those features into a prediction.

Write \(\mathbf h^{(0)}=\mathbf x\) for the original input and \(\mathbf h^{(l)}\) for the feature vector at layer \(l\). A hidden layer computes \[ \mathbf h^{(l+1)}=g\!\left(\mathbf W^{(l+1)}\mathbf h^{(l)}\right). \] The output of layer \(l\) is the input to layer \(l+1\). The weight matrix \(\mathbf W^{(l+1)}\) has one column per input feature and one row per output feature. Each row forms a weighted sum, and an activation function \(g\) acts on each sum to produce the next layer’s features. A neuron is one such weighted sum followed by its activation.

As in linear regression, an offset can be represented by a weight on a constant feature \(1\). Append that constant to the input of any layer that needs an offset. It stays fixed rather than passing through the activation. We leave these constant coordinates implicit, so there are no separate bias terms in the formulas.

The ReLU step is what lets our example change which points a linear classifier can separate. Without a nonlinearity, two layers collapse into one: \[ \mathbf h^{(2)}=\mathbf W^{(2)}\mathbf W^{(1)}\mathbf h^{(0)}. \] The matrix product can be used as the weight matrix of a single layer. Including constant offsets gives a single affine map. Nonlinear activations let the network learn features that a single affine map cannot produce.

Training adjusts the weights while keeping the chosen activation functions fixed. The output uses a function suited to the prediction: sigmoid for a binary probability, softmax for several classes, or a linear output for regression.

Learning Hidden Features

We now want a training procedure to adjust the hidden features along with the classifier. For \(n\) training examples, let \(\ell_i\) be the cross-entropy loss of example \(i\). Here \(n=4\). As in logistic regression, we minimize their average, omitting the example index when writing one example’s loss \(\ell\): \[ \begin{aligned} \mathcal L&=\frac1n\sum_{i=1}^n\ell_i,\\ \ell&=-y\log p-(1-y)\log(1-p). \end{aligned} \] Gradient descent updates the hidden-layer weights as well as the output weights.

Follow one hidden weight for example \(A=(1,1)\) with \(y=1\). Replace the coefficient of \(x_1\) in the first neuron by \(w=W^{(1)}_{11}\), keeping the other weights fixed. At \(w=1\) this is the construction above. For example \(A\), the second neuron has \(h_2=0\). Writing \(a_1\) for the first neuron’s weighted sum before ReLU, the forward calculation is

\(\displaystyle a_1=w+1,\) \(\displaystyle h_1=\max(0,a_1),\) \(\displaystyle z=h_1+0-1=h_1-1,\) \(\displaystyle p=\sigma(z)=\frac{1}{1+e^{-z}}.\)

Since this example has \(y=1\), its cross-entropy is \(\ell=-\log p\). Substituting the sigmoid probability gives

\(\displaystyle \ell=-\log p\) \(\displaystyle =-\log\!\left(\frac{1}{1+e^{-z}}\right)\) \(\displaystyle =\log(1+e^{-z}).\)

At \(w=1\), we have \(h_1=2\), so \(z=2+0-1=1\), \(p=1/(1+e^{-1})\approx0.731\), and \(\ell\approx0.313\).

For the backward pass, the local derivatives are

\(\displaystyle \frac{\partial\ell}{\partial z}=p-1,\) \(\displaystyle \frac{\partial z}{\partial h_1}=1,\) \(\displaystyle \frac{\partial h_1}{\partial a_1}=\mathbf 1_{\{a_1>0\}},\) \(\displaystyle \frac{\partial a_1}{\partial w}=1.\)

The first derivative is the logistic-regression residual \(p-y\), with \(y=1\). At the ReLU corner \(a_1=0\), we use derivative zero.

Press Forward to compute the next value.

For example A, vary the first hidden weight w and hold the other weights fixed. At w = 1, a₁ = 2, h₁ = 2, z = 1, and the loss is 0.313. The backward calculation gives ∂ℓ/∂z = −0.269. Multiplying by 1 at each remaining step gives ∂ℓ/∂w = −0.269. When w ≤ −1, ReLU blocks the gradient to w, using derivative zero at its corner.

There is one route from \(w\) to this loss, so multiply the four local derivatives:

\(\displaystyle \frac{\partial\ell}{\partial w}=\frac{\partial\ell}{\partial z}\frac{\partial z}{\partial h_1}\frac{\partial h_1}{\partial a_1}\frac{\partial a_1}{\partial w}\) \(\displaystyle =\begin{cases}p-1,&w>-1,\\0,&w\leq-1.\end{cases}\)

When the neuron is active, \(p-1<0\), so gradient descent increases \(w\). This increases \(h_1\) for example \(A\), raising its score and correct-label probability. When the neuron is inactive, this example gives no gradient to \(w\) through that ReLU. Repeat the calculation for the other examples and average their gradients to obtain \(\nabla\mathcal L\). The loss now guides changes to the features themselves.

Local Computations and the Chain Rule

Our calculation followed one route from a weight to the loss. In a larger network, a hidden value can affect several later neurons, and its loss derivative must include every contribution. A computation graph records these dependencies: each node holds a value, and an edge shows that one value is used to compute another.

The diagrams below isolate one operation within a larger computation. Forward, computing \(v\) needs only its inputs \(u_i,u_j,\ldots\) and the rule \(g\). Backward, computing \(\partial\ell/\partial u\) needs the derivatives arriving from the outputs \(v_i,v_j,\ldots\) that use \(u\), multiplied by their local derivatives. Once the derivatives from later operations are available, this backward step needs only the local derivatives.

Fact (multivariate chain rule). Suppose \(g:\mathbb R^d\to\mathbb R^m\) maps an input \(\mathbf u\in\mathbb R^d\) to an output \(\mathbf v=g(\mathbf u)\in\mathbb R^m\), and the scalar loss \(\ell\) depends on \(\mathbf u\) through \(\mathbf v\). If both maps are differentiable at the values under consideration, then for each input coordinate \(u_j\), with \(j=1,\ldots,d\), \[ \frac{\partial\ell}{\partial u_j} =\sum_{i=1}^m\frac{\partial\ell}{\partial v_i} \frac{\partial v_i}{\partial u_j}. \] Multiply along each route from \(u_j\) through an output \(v_i\), then add over the outputs.

Proof

A small input change \(\Delta\mathbf u\) produces changes \(\Delta\mathbf v\) and \(\Delta\ell\). Differentiability gives the first-order approximations \[ \begin{aligned} \Delta\ell&\approx\sum_{i=1}^m\frac{\partial\ell}{\partial v_i}\,\Delta v_i,\\ \Delta v_i&\approx\sum_{j=1}^d\frac{\partial v_i}{\partial u_j}\,\Delta u_j. \end{aligned} \] Substitute the second into the first and collect the coefficient of each input change: \[ \Delta\ell \approx\sum_{j=1}^d\left(\sum_{i=1}^m\frac{\partial\ell}{\partial v_i} \frac{\partial v_i}{\partial u_j}\right)\Delta u_j. \] Now vary only \(u_j\), divide by \(\Delta u_j\), and let \(\Delta u_j\to0\). The approximation errors vanish after division, so the coefficient in parentheses is \(\partial\ell/\partial u_j\).

Backpropagation applies this rule from the loss back toward the inputs, storing each derivative so it can be reused. It starts with \(\partial\ell/\partial\ell=1\). At each operation, multiply by the local derivatives and add contributions when a value is used more than once. Changing the loss or the network structure changes the local calculations, but the backward procedure stays the same. For an activation such as ReLU, we also choose a derivative convention at its nondifferentiable corner.

For more reading, see Boaz Barak’s notes on backpropagation.

Matrix Gradients and GPUs

The same calculation handles a whole layer at once. Write \(\mathbf u=\mathbf h^{(l)}\) for its input, \(\mathbf v=\mathbf h^{(l+1)}\) for its output, and \(\mathbf W=\mathbf W^{(l+1)}\). For \(d\) inputs and \(m\) outputs, \(\mathbf u\in\mathbb R^d\), \(\mathbf a,\mathbf v\in\mathbb R^m\), and \(\mathbf W\in\mathbb R^{m\times d}\). The layer computes \[ \mathbf a=\mathbf W\mathbf u,\qquad \mathbf v=g(\mathbf a). \] The later computation supplies \(\nabla_{\mathbf v}\ell\). We need the derivative with respect to \(\mathbf W\) to update this layer’s weights and the derivative with respect to \(\mathbf u\) to continue backward through earlier layers. First pass the supplied gradient through the activation, then through the matrix multiplication.

Claim: With \(g\) applied coordinatewise, let \(\boldsymbol\delta=(\nabla_{\mathbf v}\ell)\odot g'(\mathbf a)\), where \(\odot\) denotes coordinatewise multiplication. Then \[ \begin{aligned} \nabla_{\mathbf u}\ell&=\mathbf W^\top\boldsymbol\delta,\\ \nabla_{\mathbf W}\ell&=\boldsymbol\delta\mathbf u^\top. \end{aligned} \]

Proof

Since \(v_i=g(a_i)\), the chain rule gives \(\partial\ell/\partial a_i=\delta_i\). Now \(a_i=\sum_{j=1}^d W_{ij}u_j\), so for \(j=1,\ldots,d\), \[ \frac{\partial\ell}{\partial u_j} =\sum_{i=1}^m\delta_iW_{ij} =(\mathbf W^\top\boldsymbol\delta)_j. \] Only \(a_i\) depends on \(W_{ij}\), and its derivative is \(u_j\). Therefore \[ \frac{\partial\ell}{\partial W_{ij}}=\delta_i u_j =(\boldsymbol\delta\mathbf u^\top)_{ij}. \] These are the two matrix formulas.

Why GPUs Help

For a batch of \(B\) examples, put the input vectors in the columns of \(\mathbf U\in\mathbb R^{d\times B}\) and their per-example \(\boldsymbol\delta\) vectors in the columns of \(\mathbf D\in\mathbb R^{m\times B}\). The forward weighted sums, backward input derivatives, and average weight gradient are \[ \mathbf W\mathbf U, \qquad \mathbf W^\top\mathbf D, \qquad \frac1B\mathbf D\mathbf U^\top, \] respectively. All three are matrix multiplications. Batching groups many small weighted sums into larger products with many entries that can be computed in parallel. This is work that graphics processing units (GPUs) can perform efficiently.

GPU development and deep learning have reinforced each other. The 2012 AlexNet paper trained its network on two GPUs. Faster hardware made larger experiments feasible, while those experiments increased demand for faster matrix computation.

Why the Cost Scales

Let \(P\) be the number of weights in a dense feedforward network. Using ordinary matrix multiplication, a layer with \(md\) weights takes \(\Theta(md)\) arithmetic operations for one example’s forward pass. Its two backward products also take \(\Theta(md)\), and the activation work is linear in the number of neurons. Summing across layers gives \(\Theta(P)\) work to compute all parameter derivatives for one example.

For \(n\) training examples, the loss value and its entire gradient can be computed in \(O(nP)\) time. Compare this with the \(O(nP^2+P^3)\) cost of directly solving least squares, or the \(O(nP^2)\) cost of estimating all \(P\) derivatives by finite differences. Backpropagation makes each gradient step linear in the number of parameters.

The neural network’s loss is generally nonconvex, so these gradient calculations give no general guarantee of reaching optimal or even good parameters. We could get stuck in a poor local minimum. In practice, however, large networks often train successfully without becoming trapped in poor local minima. High-dimensional geometry can behave very differently from our low-dimensional pictures. For an accessible example, see Quanta’s explanation of why larger neural networks can help.

Activation and Normalization Reference

The example used ReLU in the hidden layer and sigmoid at the output. The following table collects other common operations for reference. Their choice changes the forward computation and its local derivatives, which the same backpropagation procedure combines.

For softmax, \(\mathbf z\in\mathbb R^k\) contains the scores for \(k\) classes, and \(p_j\) is the probability of class \(j\), for \(j=1,\ldots,k\). For the two normalization operations, \(\mathbf z\in\mathbb R^d\) instead contains \(d\) features, with \(j=1,\ldots,d\). Their coordinate mean and variance are \[ \begin{aligned} \mu&=\frac1d\sum_{i=1}^d z_i,\\ \sigma^2&=\frac1d\sum_{i=1}^d(z_i-\mu)^2. \end{aligned} \] RMS normalization uses the mean square \(\|\mathbf z\|_2^2/d=d^{-1}\sum_{i=1}^d z_i^2\). A small \(\delta>0\) prevents division by zero in either normalization.

Operation	Rule	Effect
ReLU	\(\max(0,t)\)	Zeros negative inputs
Leaky ReLU	\(\max(\alpha t,t)\)	Scales negative inputs by \(\alpha\)
Softplus	\(\log(1+e^t)\)	Smooth ReLU
GELU	\(t\Phi(t)\)	Smooth gating
SiLU	\(t\sigma(t)\)	Smooth gating
Sigmoid	\(\dfrac{1}{1+e^{-t}}\)	Range \((0,1)\)
Tanh	\(\dfrac{e^t-e^{-t}}{e^t+e^{-t}}\)	Range \((-1,1)\)
Softmax	\(p_j=\dfrac{e^{z_j}}{\sum_{l=1}^k e^{z_l}}\)	Sum to \(1\)
Layer normalization	\(\dfrac{z_j-\mu}{\sqrt{\sigma^2+\delta}}\)	Centers and rescales
RMS normalization	\(\dfrac{z_j}{\sqrt{\|\mathbf z\|_2^2/d+\delta}}\)	Rescales without centering

Here \(\sigma\) is sigmoid and \(\Phi(t)=\Pr(Z\leq t)\) for a standard normal \(Z\). For leaky ReLU, \(0<\alpha<1\) is fixed, often \(0.01\). Normalization controls the scale of the features and is often combined with an activation. The table shows its core operation before any learned scaling or offsets, which we study in Depth Enablers.