Appendix C — The Mathematics

The chapters state some results without proof, so that the ideas come first. This appendix gives the proofs. It assumes first-semester calculus: derivatives, the chain rule, and the derivatives of \(e^x\) and \(\log x\). Throughout, \(\log\) is the natural logarithm.

ImportantThese code cells are live

Each cell here runs on its own; no cell needs another to have run first. The first run takes fifteen to thirty seconds while Python downloads.

C.1 The gradient behind gradient descent

Section 4.1.3 stated that for logistic regression with the cross-entropy loss, the slope of the loss with respect to a weight is

\[ \frac{\partial L}{\partial w_j} = (\hat{y} - y)\, x_j , \]

and then used it to update the weights. This section derives that formula with the chain rule, explains the update with differentials, and repeats both for more than two classes.

C.1.1 The calculus we need

Four facts from Calculus I, plus one way of extending them to functions of several variables.

  • Derivatives of the exponential and the logarithm: \(\dfrac{d}{dx}e^{x} = e^{x}\) and \(\dfrac{d}{dx}\log x = \dfrac{1}{x}\).
  • The chain rule. If \(y\) depends on \(u\) and \(u\) depends on \(x\), then \(\dfrac{dy}{dx} = \dfrac{dy}{du}\,\dfrac{du}{dx}\). A long chain multiplies one derivative per link.
  • The quotient rule: \(\left(\dfrac{f}{g}\right)' = \dfrac{f'g - fg'}{g^{2}}\).
  • The differential. If \(y = f(x)\), then \(dy = f'(x)\,dx\): a small change \(dx\) in the input changes the output by approximately \(f'(x)\,dx\). This is the tangent-line approximation, and it is accurate only while \(dx\) is small.
  • Partial derivatives. The loss depends on many weights at once. The partial derivative \(\partial L/\partial w_j\) is the ordinary derivative with respect to \(w_j\), with every other weight held fixed.

C.1.2 Two classes: the sigmoid

C.1.2.1 The loss as a composition

For one report with feature values \(x_1, \ldots, x_n\) and true label \(y\) (0 or 1), the loss is built in three stages, each feeding the next:

\[ \begin{aligned} z &= w_1x_1 + w_2x_2 + \cdots + w_nx_n + b, \\ \hat{y} &= \sigma(z) = \frac{1}{1 + e^{-z}}, \\ L &= -\Big[\, y\log \hat{y} + (1-y)\log(1-\hat{y}) \,\Big]. \end{aligned} \]

So \(L\) is a function of \(\hat{y}\), which is a function of \(z\), which is a function of the weights \(w_1, w_2, \ldots, w_n\) and the bias \(b\):

\[ L = L\big(\hat{y}(z(w_1, w_2, \ldots, w_n, b))\big). \]

A weight \(w_j\) reaches the loss only through this chain, \(w_j \to z \to \hat{y} \to L\), so the chain rule gives the slope as a product of three derivatives, one per link:

\[ \frac{\partial L}{\partial w_j} = \frac{dL}{d\hat{y}} \cdot \frac{d\hat{y}}{dz} \cdot \frac{\partial z}{\partial w_j}. \]

Here are the three links, one at a time.

C.1.3 From slope to update: differentials

The gradient gives a slope. Here is why the update in Section 4.1.3,

\[ w_j \leftarrow w_j - \eta\,(\hat{y} - y)\,x_j , \]

is the right way to use it.

C.1.3.1 One weight

Change one weight \(w_j\) by a small amount \(dw_j\), holding everything else fixed. By the differential formula \(dy = f'(x)\,dx\), the loss changes by approximately

\[ dL = \frac{\partial L}{\partial w_j}\, dw_j . \]

We want \(dL\) to be negative: the loss should go down. That happens when \(dw_j\) has the opposite sign to \(\partial L/\partial w_j\). The simplest choice is a small multiple of the slope with its sign flipped:

\[ dw_j = -\eta\, \frac{\partial L}{\partial w_j} , \qquad\text{which gives}\qquad dL = -\eta \left(\frac{\partial L}{\partial w_j}\right)^{2} \le 0 . \]

A square is never negative, so with \(\eta > 0\) the loss can only go down (to this approximation), and it goes down fastest along the weights with the steepest slopes. The new weight is the old one plus the change, \(w_j + dw_j\), which is

\[ w_j \leftarrow w_j - \eta\,\frac{\partial L}{\partial w_j} = w_j - \eta\,(\hat{y} - y)\,x_j . \]

That is step 4 of Section 4.1.3.

C.1.3.2 All the weights at once

Gradient descent changes every weight in the same step. For a function of several variables the differential adds up one term per variable:

\[ dL = \frac{\partial L}{\partial w_1}\,dw_1 + \cdots + \frac{\partial L}{\partial w_n}\,dw_n + \frac{\partial L}{\partial b}\,db . \]

Making the same choice for every weight and the bias, \(dw_j = -\eta\,\partial L/\partial w_j\) and \(db = -\eta\,\partial L/\partial b\), gives

\[ dL = -\eta \left[ \left(\frac{\partial L}{\partial w_1}\right)^{2} + \cdots + \left(\frac{\partial L}{\partial w_n}\right)^{2} + \left(\frac{\partial L}{\partial b}\right)^{2} \right] \le 0 . \]

Every term is a square, so again the loss goes down.

C.1.3.3 Why the step must be small

The differential is the tangent-line approximation, so it is trustworthy only for small changes. This is the learning rate’s job: a small \(\eta\) keeps every \(dw_j\) small. The cell below takes review 1 of Chapter 4 with the hand-chosen weights, makes one gradient-descent step with several learning rates, and compares the change in loss the differential predicts with the change that actually happens:

How the code works:

  • predicted is the differential, \(\sum_j \frac{\partial L}{\partial w_j}dw_j + \frac{\partial L}{\partial b}db\). new_L - L is the true change, computed by actually moving the weights and recomputing the loss.
  • At \(\eta = 0.01\) and \(0.1\) the two agree closely, and the loss goes down as promised.
  • At \(\eta = 5\) the differential predicts a drop of more than 3, which is impossible: the loss is only 0.34 to begin with, and cross-entropy is never negative. The step left the region where the tangent line is a good guide. The loss did still fall here, but in general a step that large can overshoot and make the loss worse. That is the overshooting described in Section 4.1.3.

C.1.4 More than two classes: the softmax

C.1.4.1 The loss as a composition

With \(K\) classes, class \(c\) has its own weights \(w_{c,1}, \ldots, w_{c,n}\) and bias \(b_c\) (Section 4.2). For one report the stages are

\[ \begin{aligned} z_c &= w_{c,1}x_1 + \cdots + w_{c,n}x_n + b_c , \\ p_c &= \frac{e^{z_c}}{\sum_{k=1}^{K} e^{z_k}} , \\ L &= -\log p_t , \end{aligned} \]

where \(t\) is the true class. It helps to write the label as \(K\) numbers \(y_1, \ldots, y_K\), with \(y_t = 1\) for the true class and \(y_c = 0\) for the others. Then the loss is \(L = -\sum_k y_k \log p_k\); all terms but one are zero.

The chain is \(w_{c,j} \to z_c \to (p_1, \ldots, p_K) \to L\). There is one new feature: a single logit \(z_c\) affects every probability, because every \(p_k\) has \(e^{z_c}\) in its denominator. When one variable reaches the result along several paths, the chain rule adds the paths:

\[ \frac{\partial L}{\partial z_c} = \sum_{k=1}^{K} \frac{\partial L}{\partial p_k}\, \frac{\partial p_k}{\partial z_c} . \]

C.1.4.6 The update

The differential argument of Section C.1.3 does not care how many weights there are. Choosing \(dw_{c,j} = -\eta\,\partial L/\partial w_{c,j}\) for every class and feature makes \(dL\) minus \(\eta\) times a sum of squares, so the loss goes down, and the update is

\[ w_{c,j} \leftarrow w_{c,j} - \eta\,(p_c - y_c)\,x_j . \]

Read it class by class. For the true class, \(p_t - 1\) is negative, so its weights for the features present in the report go up, by \(\eta(1 - p_t)x_j\). For every other class, \(p_c\) is positive, so its weights go down, by \(\eta\,p_c\,x_j\): the more probability a wrong class received, the harder it is pushed down.

C.1.4.7 Two classes again

With \(K = 2\), fix the logit of class 0 at \(z_0 = 0\) and call the other logit \(z\), as in Section 4.2. Then \(p_1 = \sigma(z) = \hat{y}\) and \(y_1 = y\), and the formula for class 1 becomes \((\hat{y} - y)\,x_j\): the softmax derivation contains the sigmoid one as a special case.

C.1.4.8 A numerical check

A derivative can be checked without any calculus: nudge one logit by a tiny \(h\) and divide the change in loss by \(h\). The cell compares that with \(p_c - y_c\) for the logits of the chart in Section 4.2, \(z = [2.0,\ 1.0,\ 0.1]\), with the first class (Breast) as the true class:

How the code works:

  • loss computes \(-\log p_t\) straight from the logits, with no derivative anywhere.
  • Dividing the change in loss by the size of the nudge is the differential read backwards: \(dL = \frac{\partial L}{\partial z_c}\,dz_c\), so \(\frac{\partial L}{\partial z_c} \approx dL/h\) when \(dz_c = h\) is tiny.
  • The two columns agree to five decimal places. The true class gets \(-0.341\), so gradient descent raises its logit; the two wrong classes get \(+0.242\) and \(+0.099\), so it lowers theirs.