Logistic regression
How to turn a straight line into a classifier that reports how sure it is — and why the sigmoid, not a threshold, is the only function that lets you train the thing.
A linear score, squashed into a probability, trained by a loss built so the squashing cancels.
- Why not a hard label — a label carries no strength of belief, so you cannot triage, defer, re-tune the threshold, or combine models. We want $P(Y=k\mid x)$.
- Why thresholding fails — (1) it is absurdly certain, reporting $0$ or $1$ where the data overlaps; (2) decisively, $g_{\text{threshold}}'(z) = 0$ almost everywhere, so $\nabla_\theta J = \mathbf 0$ and gradient descent never moves.
- Logistic function — $\sigma(z) = \dfrac{1}{1+e^{-z}}$, with $\sigma(z) \in (0,1)$ (open), $\sigma(0) = \tfrac12$, asymptotes $0$ and $1$, and $\sigma(-z) = 1 - \sigma(z)$.
- The identity — $\sigma'(z) = \sigma(z)\bigl(1-\sigma(z)\bigr) > 0$, maximal $0.25$ at $z=0$. Everything trainable about the model rests on this.
- The model — $h(x) = \sigma(\theta^\top x) = P(Y=1\mid x)$, so $P(Y=0\mid x) = 1 - h(x)$. Bias folded in as a constant feature.
- Still a linear classifier — $h(x) \ge 0.5 \iff \theta^\top x \ge 0$, because $\sigma$ is strictly increasing and $\sigma(0)=0.5$. The boundary $\{x : \theta^\top x = 0\}$ is a hyperplane.
- Log-odds — $\log\dfrac{h(x)}{1-h(x)} = \theta^\top x$, so a unit rise in $x_j$ multiplies the odds by $e^{\theta_j}$.
- Cross-entropy — $\ell = -\bigl[y\log\hat y + (1-y)\log(1-\hat y)\bigr]$: the surprisal $\log\frac{1}{\hat p}$ of the true label. Monotone in $\hat p$, unbounded for confident errors; equals negative log-likelihood.
- Gradient — $\nabla_\theta J = \dfrac1N\sum_i\bigl(\sigma(\theta^\top x^{(i)}) - y^{(i)}\bigr)x^{(i)}$: prediction minus truth, times the input. Same form as linear regression; no closed form, so use GD/SGD.
- Convexity — chord never below the graph, equivalently $f'' \ge 0$ (Hessian PSD). Here $\ell''(z) = \sigma(1-\sigma) > 0$, so every local minimum is global — which is what licenses gradient descent.
- $K$ classes — softmax $\hat y_k = \dfrac{e^{\theta_k^\top x}}{\sum_j e^{\theta_j^\top x}}$, loss $-\log\hat y_{\,y}$, gradient $\frac1N\sum_i(\hat y^{(i)}_k - \1\{y^{(i)}=k\})x^{(i)}$. At $K=2$ it is the sigmoid with $\theta = \theta_1-\theta_0$.
Everything below is the explanation and the practice. If you are short on time, read this box, then go to the problems.
1. Why a hard decision is not enough
Every classifier so far hands you a label — decision trees walk you to a leaf and give you one. The notes put it this way:
Previously, we viewed classification as making an explicit decision on whether a given sample $x^{(i)}$ belongs to one of $K$ classes. But making a discrete decision on the class of $x^{(i)}$ doesn't tell us how strongly we believe $x^{(i)}$ belongs to that class.
Notation: $x^{(i)}$ is the $i$-th sample — a parenthesised superscript is an index, not an exponent. Both kinds appear below.
1.1 The concrete thing that goes wrong
A model screens chest X-rays and outputs "tumour" or "no tumour". Two patients come back "tumour": one from the middle of a cloud of obviously-cancerous scans, the other one pixel over the line, where half the training scans went each way. Same word for both, so you cannot:
- Triage. If you can biopsy 20 patients today and 100 came back positive, which 20?
- Defer. You want the model to say "I genuinely don't know, send this to a human." A label has no vocabulary for that.
- Re-tune the threshold. A false negative costs a life, a false positive a biopsy — the asymmetric loss of chapter 5. Trading one against the other needs a dial.
- Combine models. Two labels cannot be averaged sensibly. Two probabilities can.
1.2 Why linear, specifically
The notes' second observation: some classifiers, decision trees among them, are not linear functions of their input at all. A tree asking "is $x_1 > 3$?" then "is $x_2 > 7$?" carves feature space into axis-aligned boxes, one label each — a staircase, piecewise constant, with no coefficients $w_j$ to read.
Logistic regression models are an intuitive extension of linear regression that let us perform classification while still building on a linear model.
Linear models give up that flexibility for three things: interpretable coefficients, easy optimisation (a convex objective), and simplicity (few parameters, so less to overfit). Logistic regression keeps all three and outputs probabilities.
2. Four stages from a line to a classifier
The notes build the model by failing three times on purpose: each failure names the property the next attempt must have.
2.1 Stage 1 — the dataset (Figure 5)
The setup from the notes: a dataset
$$ \D = \{(x^{(i)}, y^{(i)})\}_{i=1}^{N}, \qquad x^{(i)} \in \R, \qquad y^{(i)} \in \{0, 1\} $$$N$ samples, each input one real number, each label $0$ or $1$. We want a linear classifier: one whose decision boundary is linear — in 1-D, a single point on the $x$-axis.
The dataset this page uses throughout — twelve points, six per class:
| $y$ | $x$ values | |||||
|---|---|---|---|---|---|---|
| 0 | −1.4 | −0.8 | −0.3 | 0.2 | 0.7 | 1.2 |
| 1 | 1.0 | 1.3 | 1.6 | 2.1 | 2.7 | 3.3 |
Read the overlap off the table: the largest class-0 input is $x = 1.2$, the smallest class-1 input $x = 1.0$. They cross, so in the strip $1.0 \le x \le 1.2$ the classes are interleaved and no threshold classifies all twelve correctly. That is the point, not a defect: real data overlaps, and a model forced to be certain there is lying.
2.2 Stage 2 — just use linear regression (Figure 6)
The notes' first idea: the labels are numbers, $0$ and $1$. Linear regression predicts numbers. So fit
$$ \hat{y} = wx + b $$by least squares. The normal equations on the twelve points give
$$ \hat{y} = 0.2184 + 0.2913\,x $$The notes: the model "learns some relationship between the input $x$ and the class $y$, where the class will increase if the input increases" — the positive slope is right — but "this doesn't necessarily constrain the output of a model to the appropriate class that we would like, either a 0 or a 1." A linear function is unbounded: at $x = 10$ this fit predicts $1.433$, and "$\hat y = 1.433$" is not a class, nor a probability. It has no interpretation at all.
The failure mode the notes skip, and you should see
Squared loss punishes being far from the target number. A point at $x = 10$ with label $1$ is the easiest point in the world to classify, but least squares sees $\hat y = 0.2184 + 0.2913(10) = 3.13$, which is $2.13$ from the target, for a squared penalty of $4.5$ — more than all twelve real points combined. So the fit contorts to pull it down, and the only way is to flatten the slope.
Squared loss has unbounded appetite: there is no "right enough", so a few easy, extreme points can outvote all the hard, informative ones near the boundary. The loss built in §7 saturates instead — refitting the logistic model with and without the point at $x = 10$ gives $w = 5.5119$, $b = -5.8044$ both times, identical to four decimal places, because that point already has probability $0.99999$ and so contributes no gradient.
2.3 Stage 3 — threshold the line (Figure 7)
The outputs are invalid, so clamp them at the natural cut $0.5$: class $0$ below, class $1$ above. The notes write a new model,
$$ \hat{y} = g_{\text{threshold}}(wx + b), \qquad g_{\text{threshold}}(z) = \begin{cases} 0 & z < 0.5\\ 1 & z \ge 0.5\end{cases} $$(Equivalently, absorb the $0.5$ into $b$ and threshold at $0$; nothing below depends on the convention.)
The notes name both problems; the second forces the design.
Problem (a) — the model is absurdly certain
In the notes' words: "The model is extremely certain about its predictions! It transitions rapidly from one class to the other right around input values $x = 1$. However, looking at the overlap in our data, we probably want our model to state that for $x = 1$, $P(Y = 1 \mid x) \approx 0.5$."
That is the overlap from §2.1, so the honest answer at $x = 1$ is a coin flip. The threshold model instead reports certainty $1$ for class 0 at $x = 0.9666$ and certainty $1$ for class 1 at $x = 0.9668$: it has thrown away all information about where the sample sits relative to the boundary — exactly what §1 wanted.
Problem (b) — there is nothing for gradient descent to descend
The notes: "it has a derivative of zero essentially everywhere, making it very problematic to optimize over." This is the hinge of the chapter, so make it precise.
Claim. Gradient descent cannot train $\hat y = g_{\text{threshold}}(wx+b)$.
Recall from chapter 9 the update rule:
$$ \theta \leftarrow \theta - \alpha \nabla_\theta J(\theta) $$where $J(\theta)$ is the training objective, $\alpha > 0$ is the learning rate, and $\nabla_\theta J$ is the gradient — the vector of partial derivatives $\partial J / \partial \theta_j$. The rule has exactly one input: the gradient. If the gradient is the zero vector, the update does nothing, whatever $\alpha$ is.
Now compute that gradient. Whatever per-sample loss $\ell$ you use, the chain rule gives
$$ \frac{\partial \ell}{\partial w} \;=\; \underbrace{\frac{\partial \ell}{\partial \hat y}}_{\text{depends on the loss}} \cdot \underbrace{g_{\text{threshold}}'(z)}_{\text{the model}} \cdot \underbrace{\frac{\partial z}{\partial w}}_{=\,x}, \qquad z = wx+b. $$The middle factor is the derivative of a step function. A step function is constant on $z < 0.5$ and constant on $z > 0.5$, so $g_{\text{threshold}}'(z) = 0$ at every $z \ne 0.5$. At $z = 0.5$ exactly, the function jumps, and the derivative does not exist (the left and right difference quotients blow up to $\pm\infty$).
So the middle factor is $0$ for almost every input, and undefined on a set of measure zero. Multiplying anything by that middle factor gives $0$. Therefore $\nabla_\theta J = \mathbf{0}$ almost everywhere, and
$$ \theta \leftarrow \theta - \alpha \cdot \mathbf{0} = \theta. $$Gradient descent takes a step of length zero, forever. $\blacksquare$
The same fact as a landscape: changing $w$ a little either flips no labels or flips exactly one, so the training loss is a staircase of flat plateaus with sudden drops. Gradient descent on a staircase is a blindfolded person on a flat floor told to walk downhill.
What kills the threshold is not "outputs must be probabilities" but "the loss must have a usable slope with respect to the parameters." Every gradient-trained model obeys this, which is why models are built out of smooth pieces. The sigmoid is chosen because it is differentiable and non-flat, not because it is pretty.
2.4 Stage 4 — replace the step with a smooth S (Figure 8)
The conclusion: keep the structure "apply a function $g$ to $wx+b$", but choose a $g$ that "smoothly maps all real input values $(-\infty, \infty)$ to the range $(0,1)$" — a probability. The standard choice is a sigmoid ("s-shaped") function, specifically the logistic function $\sigma$:
$z \in \R$ is any real number (here $wx+b$), and $\sigma(z)$ is the output — which we now prove lies strictly between $0$ and $1$.
The notes leave it as an exercise: prove that it outputs values in $[0,1]$, and $0.5$ at $0$. So do it.
3. The logistic function, proved and differentiated
Claim 1: $0 < \sigma(z) < 1$ for every real $z$.
Upper bound. The exponential is strictly positive: $e^{-z} > 0$ for every real $z$ (it never reaches zero, it only approaches it). Therefore
$$ 1 + e^{-z} \;>\; 1 \quad\Longrightarrow\quad \sigma(z) = \frac{1}{1+e^{-z}} \;<\; \frac{1}{1} = 1. $$The implication is legal because $t \mapsto 1/t$ is strictly decreasing on $t > 0$, and both $1+e^{-z}$ and $1$ are positive.
Lower bound. For any fixed real $z$, $e^{-z}$ is a finite positive number, so $1 + e^{-z}$ is finite and positive, so its reciprocal is positive:
$$ \sigma(z) = \frac{1}{1+e^{-z}} \;>\; 0. $$Together: $\sigma(z) \in (0,1)$ for all $z \in \R$. $\blacksquare$
Claim 2: $\sigma(0) = 0.5$. Substitute $z = 0$. Then $e^{-0} = e^{0} = 1$, so
$$ \sigma(0) = \frac{1}{1+1} = \frac{1}{2}. \qquad \blacksquare $$Claim 3: the asymptotes. As $z \to +\infty$, the exponent $-z \to -\infty$, so $e^{-z} \to 0$, so the denominator $\to 1$ and
$$ \lim_{z\to+\infty}\sigma(z) = \frac{1}{1+0} = 1. $$As $z \to -\infty$, the exponent $-z \to +\infty$, so $e^{-z} \to +\infty$, the denominator grows without bound, and
$$ \lim_{z\to-\infty}\sigma(z) = 0. \qquad \blacksquare $$The notes write "$[0,1]$" with closed brackets, the usual shorthand. Claim 1 shows the range is the open interval $(0,1)$: $\sigma$ approaches $0$ and $1$ but never reaches either. That matters twice — logistic regression can never be absolutely certain (a feature), and $\log\hat y$ is always finite, which is what stops the loss returning $\infty$ on real data.
3.1 The derivative — the identity that makes the model trainable
Stage 3 died of a zero derivative, so ask what $\sigma'$ is. Every gradient below rests on the answer.
Claim: $\sigma'(z) = \sigma(z)\,\bigl(1 - \sigma(z)\bigr)$.
Step 1 — rewrite as a power. $\sigma(z) = \bigl(1 + e^{-z}\bigr)^{-1}$.
Step 2 — chain rule. With $u(z) = 1 + e^{-z}$ we have $\sigma = u^{-1}$, so $\dfrac{d\sigma}{dz} = -u^{-2}\dfrac{du}{dz}$. This is legal because $u(z) > 0$ everywhere, so $u^{-1}$ is differentiable.
Step 3 — the inner derivative. $\dfrac{du}{dz} = \dfrac{d}{dz}\bigl(1 + e^{-z}\bigr) = 0 + e^{-z}\cdot(-1) = -e^{-z}$, using $\frac{d}{dz}e^{cz} = ce^{cz}$ with $c=-1$.
Step 4 — substitute.
$$ \sigma'(z) \;=\; -\bigl(1+e^{-z}\bigr)^{-2}\cdot\bigl(-e^{-z}\bigr) \;=\; \frac{e^{-z}}{\bigl(1+e^{-z}\bigr)^{2}}. $$Step 5 — split the fraction. This is the only clever step. Write the single fraction as a product of two:
$$ \frac{e^{-z}}{\bigl(1+e^{-z}\bigr)^{2}} \;=\; \underbrace{\frac{1}{1+e^{-z}}}_{=\;\sigma(z)}\cdot\underbrace{\frac{e^{-z}}{1+e^{-z}}}_{=\;?} $$Step 6 — identify the second factor. Add and subtract $1$ in the numerator:
$$ \frac{e^{-z}}{1+e^{-z}} \;=\; \frac{\bigl(1+e^{-z}\bigr) - 1}{1+e^{-z}} \;=\; \frac{1+e^{-z}}{1+e^{-z}} - \frac{1}{1+e^{-z}} \;=\; 1 - \sigma(z). $$Conclusion. $\sigma'(z) = \sigma(z)\bigl(1-\sigma(z)\bigr)$. $\blacksquare$
Three consequences, each of which you will use:
- $\sigma' > 0$ everywhere, since $\sigma$ and $1-\sigma$ are both positive. So $\sigma$ is strictly increasing, which is what lets §5 invert $\sigma(z) \ge 0.5 \iff z \ge 0$.
- Largest at the boundary. $\sigma(1-\sigma)$ is a downward parabola in $\sigma$, maximised at $\sigma = 1/2$, i.e. $z = 0$, where $\sigma'(0) = 0.25$. The model is most sensitive exactly where it is most uncertain — the opposite of the threshold.
- It is expressed in the function's own output. Given $\hat y = \sigma(z)$, $\sigma'(z) = \hat y(1-\hat y)$ — one multiply, no recomputing $e^{-z}$, which is why backpropagation is cheap.
3.2 One more identity: $\sigma(-z) = 1 - \sigma(z)$
Multiply numerator and denominator by $e^{-z}$ (legal: $e^{-z} \ne 0$):
$$ \frac{1}{1+e^{z}} \cdot \frac{e^{-z}}{e^{-z}} = \frac{e^{-z}}{e^{-z} + e^{z}e^{-z}} = \frac{e^{-z}}{e^{-z} + 1} = 1 - \sigma(z), $$where the last equality is Step 6 of the previous proof. $\blacksquare$
So the sigmoid is antisymmetric about $(0, 0.5)$, and the model therefore treats the classes symmetrically: $2$ units right of the boundary gives class 1 probability $0.8808$, and $2$ units left gives class 0 the same $0.8808$.
| $z$ | −4 | −2 | −1 | 0 | 1 | 2 | 4 |
|---|---|---|---|---|---|---|---|
| $\sigma(z)$ | 0.0180 | 0.1192 | 0.2689 | 0.5000 | 0.7311 | 0.8808 | 0.9820 |
| $\sigma'(z)$ | 0.0177 | 0.1050 | 0.1966 | 0.2500 | 0.1966 | 0.1050 | 0.0177 |
Worth memorising: $\sigma(0)=0.5$, $\sigma(2)\approx 0.88$, $\sigma(4)\approx 0.98$ — enough to sanity-check any logistic model in your head. The columns also confirm $\sigma(-z)=1-\sigma(z)$: $0.0180 + 0.9820 = 1$.
4. The logistic regression model (Figure 9)
Assemble it: apply $\sigma$ to the linear transformation of the input, where $g_{\text{threshold}}$ was before.
One-dimensional input ($x \in \R$):
$$ h(x) = \hat y = \sigma(wx + b) = \frac{1}{1 + e^{-(wx+b)}} $$$M$-dimensional input ($x \in \R^M$, with the bias term folded in as a constant feature):
$$ h(x) = \hat y = \sigma(\theta^\top x) = \frac{1}{1 + e^{-\theta^\top x}} $$Every symbol: $x \in \R^M$ is one sample's feature vector, $\theta \in \R^M$ is the parameter vector, $\theta^\top x = \sum_{j=1}^{M}\theta_j x_j$ is the dot product (a single real number, often called the logit or score), $\sigma$ is the logistic function, and $h$ is the hypothesis function.
"The bias term is included in this $x$" is chapter 10's trick: prepend a constant $1$ to every feature vector, so with $x = (1, x_1, \dots, x_{M-1})$ and $\theta = (\theta_0, \dots, \theta_{M-1})$,
$$ \theta^\top x = \theta_0 \cdot 1 + \theta_1 x_1 + \cdots + \theta_{M-1}x_{M-1} $$and $\theta_0$ plays the role of $b$. From here on "$\theta^\top x$" always includes the bias.
4.1 Reading the output as a probability
The second equation is not an extra assumption — with two classes the probabilities must sum to $1$, so $P(Y=0\mid x)$ is forced.
So the output is the distribution $\bigl(1-h(x),\; h(x)\bigr)$, which answers every complaint in §1.1: rank by $h(x)$, flag $h(x)\in(0.4,0.6)$ for review, move the operating threshold, average two models.
With §3.2, $P(Y=0\mid x) = 1 - \sigma(\theta^\top x) = \sigma(-\theta^\top x)$: class 0 is the same model with $\theta$ negated, so neither class is privileged.
Keep the two steps separate: $z = \theta^\top x$ collapses the feature vector to one score, and that is where all the learning lives; $\sigma$ then squashes the score into a probability, with no parameters of its own. The squashing changes the loss surface, and so the fit you get, but never which decision rules the model can express — as §5 proves.
5. Why this is still a linear classifier
$\sigma$ is emphatically non-linear — it curves, it saturates — yet the notes call logistic regression a linear model for classification. Both are true:
Claim. The rule "predict class 1 when $h(x) \ge 0.5$" is identical to the rule "predict class 1 when $\theta^\top x \ge 0$".
Start from the prediction rule and substitute the model:
$$ h(x) \ge 0.5 \iff \sigma(\theta^\top x) \ge 0.5 . $$By Claim 2 of §3, $0.5 = \sigma(0)$, so this is
$$ \sigma(\theta^\top x) \ge \sigma(0). $$By consequence 1 of §3.1, $\sigma'(z) = \sigma(1-\sigma) > 0$ everywhere, so $\sigma$ is strictly increasing, hence injective with a strictly increasing inverse — and a strictly increasing function preserves $\ge$ in both directions:
$$ \sigma(a) \ge \sigma(b) \iff a \ge b. $$Apply it with $a = \theta^\top x$ and $b = 0$:
$$ \boxed{\;h(x) \ge 0.5 \iff \theta^\top x \ge 0\;} $$The set $\{x : \theta^\top x = 0\}$ is, by definition, a hyperplane through the origin of the augmented feature space — a point in 1-D, a line in 2-D, a plane in 3-D. The decision boundary is that hyperplane. $\blacksquare$
In 1-D with $z = wx+b$ the boundary is the point $x = -b/w$; in 2-D it is the straight line $\theta_0 + \theta_1x_1 + \theta_2x_2 = 0$.
$\sigma$ is a monotone non-linearity applied after the linear part. Monotone functions cannot re-order their inputs, so they cannot change which side of the boundary a point falls on: $\sigma$ only relabels the score axis as a probability, moving nobody across the line.
So it inherits a linear classifier's limits exactly: no XOR, no circles. For curved boundaries, engineer features (chapter 10) — feed it $x_1^2, x_2^2, x_1x_2$ and the boundary is a conic in the original space, a hyperplane in the engineered one.
5.1 What $\|\theta\|$ does versus what the direction of $\theta$ does
Split $\theta = (\theta_0, w)$, with $w$ acting on the real features $\tilde x$, so $z = w^\top \tilde x + \theta_0$. The signed distance from $\tilde x$ to the boundary hyperplane is
$$ d(\tilde x) = \frac{w^\top \tilde x + \theta_0}{\|w\|} \qquad\Longrightarrow\qquad z = \|w\|\,d(\tilde x). $$Substituting into the model:
$$ h(x) = \sigma\bigl(\|w\|\; d(\tilde x)\bigr). $$Now everything separates cleanly:
- Direction $w/\|w\|$ — the normal to the boundary: it sets the hyperplane's orientation and points to the class-1 side, so changing it rotates the line. The bias $\theta_0$ slides the boundary along that normal without rotating it.
- Magnitude $\|w\|$ — multiplies the distance before $\sigma$ sees it, so it sets the sharpness of the transition: doubling it halves the fuzzy band. $\|w\| \to \infty$ degenerates into stage 3's threshold; $\|w\| \to 0$ says $0.5$ everywhere. The boundary itself does not move.
Algebraically: replacing $\theta$ by $c\theta$ for $c > 0$ leaves the boundary set $\{x : \theta^\top x = 0\}$ unchanged — scaling $\theta$ changes every probability and not one predicted label.
You are handed a trained model $h(x) = \sigma(\theta^\top x)$ with $\theta = [-3,\; 1,\; 2]^\top$, where the feature vector is $x = [1,\; x_1,\; x_2]^\top$ (the leading $1$ is the bias feature).
- Write down the equation of the decision boundary and sketch it.
- Compute $h$ at the points $(x_1,x_2) = (2,1)$ and $(1, 0.5)$, and classify each.
- Your colleague multiplies every parameter by $2$, giving $\theta' = [-6, 2, 4]^\top$. Which predictions change? Which probabilities change?
Step 1 — The boundary
By §5, the boundary is the set where $\theta^\top x = 0$:
$$ -3 + x_1 + 2x_2 = 0 \quad\Longleftrightarrow\quad x_2 = \frac{3 - x_1}{2} = 1.5 - 0.5\,x_1 . $$A straight line with intercept $1.5$ and slope $-0.5$. Class 1 is the side where $-3+x_1+2x_2 > 0$, i.e. above and to the right of the line; the normal direction $w = (1,2)$ points that way.
Step 2 — Evaluate the two points
Always compute the logit $z = \theta^\top x$ first; it is a plain dot product.
Point $(2,1)$: the augmented vector is $[1,2,1]^\top$, so
$$ z = (-3)(1) + (1)(2) + (2)(1) = -3 + 2 + 2 = 1, \qquad h = \sigma(1) = \frac{1}{1+e^{-1}} = 0.7311. $$$z \ge 0$, so predict class 1, with $73.11\%$ confidence. Cross-check with the boundary: at $x_1 = 2$ the line sits at $x_2 = 0.5$, and our point has $x_2 = 1 > 0.5$, so it is on the class-1 side. ✓
Point $(1, 0.5)$: augmented $[1,1,0.5]^\top$, so
$$ z = -3 + 1 + 1 = -1, \qquad h = \sigma(-1) = 0.2689. $$$z < 0$, so predict class 0. Note $h = 0.2689$ means $P(Y=0\mid x) = 1 - 0.2689 = 0.7311$ — the same confidence as the first point, which is the antisymmetry $\sigma(-z) = 1-\sigma(z)$ from §3.2 showing up in practice.
Step 3 — What doubling $\theta$ does
The boundary equation becomes $-6 + 2x_1 + 4x_2 = 0$. Divide by $2$: $-3 + x_1 + 2x_2 = 0$. Identical line. So no prediction changes — every point is on the same side it was before.
The probabilities all change, though. The logits double:
$$ (2,1):\ z = 2 \Rightarrow h = \sigma(2) = 0.8808, \qquad (1,0.5):\ z = -2 \Rightarrow h = \sigma(-2) = 0.1192. $$Both points moved further from $0.5$. The model became more confident about exactly the same decisions.
Answer & the takeaway
Answers. (1) $x_2 = 1.5 - 0.5x_1$. (2) $h(2,1) = 0.7311 \to$ class 1; $h(1,0.5) = 0.2689 \to$ class 0. (3) Predictions unchanged; probabilities move to $0.8808$ and $0.1192$.
Takeaway. $\|\theta\|$ is a confidence dial that the decision rule cannot see. This has a sharp practical consequence: if your training data happens to be perfectly linearly separable, the likelihood can always be improved by scaling $\theta$ up, so the optimiser drives $\|\theta\| \to \infty$ and never converges. beyond syllabus The fix is regularisation — add a penalty $\lambda\|\theta\|^2$ to the objective, which gives $\|\theta\|$ a reason to stay finite. Our dataset has overlapping classes, so this does not bite here; it is the first thing to check when a logistic regression "won't converge".
6. Log-odds: why the coefficients mean something
Can we get back from the probability to the linear part? The inverse has a name:
For a probability $p \in (0,1)$, the odds are $\dfrac{p}{1-p}$ — "how many times more likely the event is than its complement". A probability of $0.75$ is odds of $3$, i.e. 3-to-1 on. The log-odds or logit is $\log\dfrac{p}{1-p}$, which maps $(0,1)$ onto all of $\R$.
Claim: $\displaystyle \log\frac{h(x)}{1-h(x)} = \theta^\top x$. Write $z = \theta^\top x$.
Numerator. $h = \sigma(z) = \dfrac{1}{1+e^{-z}}$.
Denominator. From Step 6 of §3.1, $1 - \sigma(z) = \dfrac{e^{-z}}{1+e^{-z}}$.
Divide. The common denominator cancels:
$$ \frac{h}{1-h} \;=\; \frac{\dfrac{1}{1+e^{-z}}}{\dfrac{e^{-z}}{1+e^{-z}}} \;=\; \frac{1}{1+e^{-z}}\cdot\frac{1+e^{-z}}{e^{-z}} \;=\; \frac{1}{e^{-z}} \;=\; e^{z}. $$Take logs. $\log$ is the inverse of $\exp$, so
$$ \log\frac{h(x)}{1-h(x)} = \log e^{z} = z = \theta^\top x. \qquad \blacksquare $$Logistic regression is ordinary linear regression on the log-odds scale. What is modelled linearly is not the probability but $\log\frac{p}{1-p}$, which lives on all of $\R$ — a sensible target for an unbounded linear function. The sigmoid is just the inverse of the logit, converting back.
Hence interpretable coefficients. Hold every feature fixed but $x_j$ and raise $x_j$ by one unit: $z$ rises by exactly $\theta_j$, so
$$ \frac{\text{new odds}}{\text{old odds}} = \frac{e^{z + \theta_j}}{e^{z}} = e^{\theta_j}. $$A model predicts whether a student passes. The coefficient on hours studied per week is $\theta_j = 0.7$.
Interpretation: each extra hour multiplies the odds of passing by $e^{0.7} = 2.0138$ — it roughly doubles the odds, not the probability.
Worked numbers. A student currently at $P(\text{pass}) = 0.4$:
- Current odds: $\dfrac{0.4}{1-0.4} = \dfrac{0.4}{0.6} = 0.6667$.
- Add one study hour: odds $\times\, 2.0138 = 0.6667 \times 2.0138 = 1.3425$.
- Convert back to a probability with $p = \dfrac{\text{odds}}{1+\text{odds}} = \dfrac{1.3425}{2.3425} = 0.5731$.
So $0.400 \to 0.573$: a jump of $17.3$ percentage points. The same hour for a student already at $P = 0.95$: odds $= 19$, new odds $= 38.26$, new $p = 38.26/39.26 = 0.9745$ — a jump of only $2.5$ points.
The moral: the effect on the odds is a constant multiplier for everybody; the effect on the probability depends on where you started and is largest near $p = 0.5$. So "a one-hour increase raises the pass rate by 17 points" is wrong; it holds only near $40\%$.
7. The loss: cross-entropy
Three things remain: measuring this model's error, training it, and extending it to many classes.
7.0 The lecture's framing: grading an LLM
The lecture's example: grade an LLM on many tasks, recording each task's easiness ($x \in \R$) and whether it succeeded ($y \in \{0,1\}$). Tasks of equal easiness sometimes succeed and sometimes fail, so where the LLM succeeds half the time any prediction of the label is wrong half the time.
Estimate $P(y=1)$ for each $x$ instead. That number is continuous, so classification becomes a regression problem on probabilities — which is why "logistic regression" is literally accurate. The design questions are then the usual ERM ones: which loss, and which model class (here, the sigmoid of a linear function).
The lecture chooses the loss from two principles about grading a probability $\hat p$ for an event that then happens:
- Monotone: a higher reported $\hat p$ should incur a lower loss.
- Confidence matters: a certain wrong prediction is worse than an uncertain wrong one.
From information theory (chapter 7), the surprisal of an event you gave probability $\hat p$ is $\log\frac{1}{\hat p}$ — and it satisfies both: it falls as $\hat p$ rises, and it goes to $\infty$ as $\hat p \to 0$. That is the loss. The notes write it as
$$ \ell(\hat p, y) = \1\{y=1\}\log\frac{1}{\hat p} + \1\{y=0\}\log\frac{1}{1-\hat p} = y\log\frac{1}{\hat p} + (1-y)\log\frac{1}{1-\hat p}, $$the same as the $-[\,y\log\hat y + (1-y)\log(1-\hat y)\,]$ form below, since $\log\frac1a = -\log a$. First, why the obvious alternative fails.
7.1 Why not squared loss?
The obvious move is to reuse the loss from chapter 8:
$$ J_{\text{sq}}(\theta) = \frac{1}{N}\sum_{i=1}^{N}\Bigl(y^{(i)} - \sigma\bigl(\theta^\top x^{(i)}\bigr)\Bigr)^{2}. $$Not absurd: bounded, differentiable, minimised when $\hat y = y$. But it fails on two counts.
Failure 1: it is not convex in $\theta$
For linear regression, squared loss gave a bowl: one global minimum, a closed form. Wrap the prediction in $\sigma$ and the bowl buckles:
Take a dataset of one point, $x = 1$ (no bias), $y = 0$. Then $\hat y = \sigma(w)$ and
$$ J(w) = \bigl(0 - \sigma(w)\bigr)^2 = \sigma(w)^2 . $$Differentiate, using $\sigma' = \sigma(1-\sigma)$ from §3.1:
$$ J'(w) = 2\sigma\,\sigma' = 2\sigma^{2}(1-\sigma). $$Differentiate again — product rule on $\sigma^2$ and $(1-\sigma)$, then factor out $\sigma' = \sigma(1-\sigma)$:
$$ J''(w) = 2\Bigl[2\sigma\sigma'(1-\sigma) - \sigma^{2}\sigma'\Bigr] = 2\sigma'\sigma\Bigl[2(1-\sigma) - \sigma\Bigr] = 2\sigma'\sigma\,(2 - 3\sigma). $$Since $\sigma' > 0$ and $\sigma > 0$, the sign of $J''$ is the sign of $(2 - 3\sigma)$. So
- $\sigma < 2/3$ (that is, $w < \log 2 \approx 0.693$): $J'' > 0$, convex;
- $\sigma > 2/3$ (that is, $w > \log 2$): $J'' < 0$, concave.
Numerically: $J''(0) = +0.125$ and $J''(2) = -0.1188$. A convex function has $J'' \ge 0$ everywhere, so $J_{\text{sq}}$ is not convex. $\blacksquare$
With many points and parameters this gives genuine local minima and flat plateaus, so gradient descent's answer depends on where you started.
Failure 2: the gradient vanishes exactly when the model is most wrong
Differentiate one term of $J_{\text{sq}}$ with respect to $\theta$, chain rule through $\sigma$:
$$ \frac{\partial}{\partial\theta}\bigl(y - \sigma(z)\bigr)^2 = -2\bigl(y - \sigma(z)\bigr)\,\underbrace{\sigma(z)\bigl(1-\sigma(z)\bigr)}_{\sigma'(z)}\,x . $$The worst case: $y = 1$ and the model says $\hat y = 0.001$. The error factor $(y-\hat y) = 0.999$ is large, but the $\sigma'$ factor is $0.001\times0.999 = 0.000999$, so the product is $\approx 0.000998$ — a thousandth of what a point at the boundary would give ($0.25$ there). The model is confidently wrong and the optimiser barely notices.
Stage 3's pathology, back through the side door: saturation makes $\sigma'$ small and squared loss multiplies by $\sigma'$. We need a loss whose derivative cancels that factor.
7.2 The cross-entropy (negative log-likelihood) loss
For one sample with true label $y \in \{0,1\}$ and predicted probability $\hat y = h(x) \in (0,1)$, the binary cross-entropy loss is
$$ \ell(y,\hat y) \;=\; -\Bigl[\,y\log \hat y \;+\; (1-y)\log(1-\hat y)\,\Bigr] $$and the training objective averages it over the dataset:
$$ J(\theta) = \frac{1}{N}\sum_{i=1}^{N} -\Bigl[\,y^{(i)}\log \sigma\bigl(\theta^\top x^{(i)}\bigr) + \bigl(1-y^{(i)}\bigr)\log\bigl(1 - \sigma(\theta^\top x^{(i)})\bigr)\Bigr]. $$Read the two branches. $y$ is $0$ or $1$, so one term is always multiplied by zero — a switch written without an if:
- If $y = 1$: the second term dies and $\ell = -\log\hat y$ — the log of the probability you gave the right answer. $\hat y = 0.9$ costs $0.105$; $0.5$ costs $0.693$; $0.01$ costs $4.605$.
- If $y = 0$: the first term dies and $\ell = -\log(1-\hat y)$ — the same charge on $P(Y=0\mid x)$, again the probability given to the right answer.
Both branches are the same sentence: your loss is $-\log(\text{the probability you gave the true label})$.
Where does $-\log$ come from? Two equivalent stories.
Likelihood. The model treats the label as a Bernoulli draw, $P(y\mid x) = \hat y^{\,y}(1-\hat y)^{1-y}$. For independent samples the dataset's probability is $\prod_i P(y^{(i)}\mid x^{(i)})$; take logs — legal, since $\log$ is increasing and so does not move the maximiser — to turn the product into a sum, then flip the sign to turn maximise into minimise. You get exactly $J(\theta)$. Cross-entropy is negative log-likelihood, and fitting a logistic regression is maximum likelihood estimation.
Information. $-\log p$ is the nats of surprise in an event you gave probability $p$ (chapter 7), so cross-entropy charges your surprise at the truth: a confidently wrong model is infinitely surprised and pays accordingly.
A model has parameters $\theta = [-1,\; 2,\; 0.5]^\top$ acting on augmented feature vectors $x = [1,\; x_1,\; x_2]^\top$. Three samples arrive:
| sample | $x_1$ | $x_2$ | true $y$ |
|---|---|---|---|
| A | 1.5 | 2 | 1 |
| B | 0.5 | −1 | 0 |
| C | 2 | 1 | 0 |
For each: compute the logit, the predicted probability, and the cross-entropy loss. Then compute the average loss $J(\theta)$. Which sample is the model most embarrassed by, and why? (You may use $e^{-3} = 0.049787$, $e^{0.5} = 1.648721$, $e^{-3.5} = 0.030197$.)
Step 1 — Set up the recipe
Three mechanical steps per sample, never skip one:
- $z = \theta^\top x$ — a dot product including the bias feature $1$.
- $\hat y = \sigma(z) = 1/(1+e^{-z})$.
- $\ell = -\log\hat y$ if $y=1$, else $\ell = -\log(1-\hat y)$.
Logs here are natural logs. (Using $\log_2$ instead just rescales everything by $\log_2 e$ and changes nothing about the minimiser.)
Step 2 — Sample A
Augmented $x = [1,\;1.5,\;2]^\top$:
$$ z = (-1)(1) + (2)(1.5) + (0.5)(2) = -1 + 3 + 1 = 3. $$ $$ \hat y = \sigma(3) = \frac{1}{1+e^{-3}} = \frac{1}{1.049787} = 0.952574 . $$True label is $1$, so we are on the $-\log\hat y$ branch:
$$ \ell_A = -\log(0.952574) = 0.048587 . $$Small, as it should be: the model put $95.3\%$ on the correct class.
Step 3 — Sample B
Augmented $x = [1,\;0.5,\;-1]^\top$:
$$ z = -1 + (2)(0.5) + (0.5)(-1) = -1 + 1 - 0.5 = -0.5 . $$ $$ \hat y = \sigma(-0.5) = \frac{1}{1+e^{0.5}} = \frac{1}{2.648721} = 0.377541 . $$True label is $0$, so use the other branch, with $1-\hat y = 0.622459$:
$$ \ell_B = -\log(0.622459) = 0.474077 . $$Middling. The model leans the right way ($\hat y < 0.5$, so it would predict class 0) but only weakly — the logit is just $-0.5$, half a unit from the boundary.
Step 4 — Sample C, and the average
Augmented $x = [1,\;2,\;1]^\top$:
$$ z = -1 + 4 + 0.5 = 3.5, \qquad \hat y = \sigma(3.5) = \frac{1}{1.030197} = 0.970688 . $$True label is $0$, so $1 - \hat y = 0.029312$ and
$$ \ell_C = -\log(0.029312) = 3.529750 . $$Average over the three:
$$ J(\theta) = \frac{0.048587 + 0.474077 + 3.529750}{3} = \frac{4.052414}{3} = 1.350805 . $$Answer & the takeaway
Answers. A: $z=3$, $\hat y = 0.9526$, $\ell = 0.0486$. B: $z=-0.5$, $\hat y = 0.3775$, $\ell = 0.4741$. C: $z=3.5$, $\hat y = 0.9707$, $\ell = 3.5298$. Average $J = 1.3508$.
The model is most embarrassed by C, and by a mile: $\ell_C$ is $73\times$ larger than $\ell_A$ and accounts for $87\%$ of the total loss. C is the confidently-wrong case — the model assigned $97\%$ to the wrong class.
Takeaway. Under squared loss those same three samples would have cost $(1-0.9526)^2 = 0.0022$, $(0-0.3775)^2 = 0.1425$ and $(0-0.9707)^2 = 0.9423$ — C would be only $6.6\times$ worse than B instead of $7.4\times$, and its cost would be capped at $1$ no matter how wrong it got. Cross-entropy's unbounded penalty is what makes the optimiser go and fix C first. And as §7.3 will show, C is also where the gradient is biggest — under squared loss it would have been nearly the smallest.
7.3 Training it — the gradient
To run gradient descent we need $\nabla_\theta J$. Derive it for one sample; the average follows by linearity of differentiation.
Fix one sample $(x, y)$ and write $z = \theta^\top x$, $\hat y = \sigma(z)$. The per-sample loss is
$$ \ell = -\bigl[\,y\log\sigma(z) + (1-y)\log(1-\sigma(z))\,\bigr]. $$We want $\partial\ell/\partial\theta$. Chain through $z$:
$$ \frac{\partial \ell}{\partial \theta} = \frac{\partial \ell}{\partial z}\cdot\frac{\partial z}{\partial \theta}. $$Line 1 — differentiate $\ell$ with respect to $z$. Use $\frac{d}{dz}\log u = \frac{1}{u}\frac{du}{dz}$ on each term, with $u = \sigma$ in the first and $u = 1-\sigma$ in the second. Note $\frac{d}{dz}(1-\sigma) = -\sigma'$:
$$ \frac{\partial \ell}{\partial z} = -\left[\, y\cdot\frac{1}{\sigma}\cdot\sigma' \;+\; (1-y)\cdot\frac{1}{1-\sigma}\cdot(-\sigma')\,\right]. $$Line 2 — pull out the common $\sigma'$.
$$ \frac{\partial \ell}{\partial z} = -\,\sigma' \left[\, \frac{y}{\sigma} - \frac{1-y}{1-\sigma} \,\right]. $$Line 3 — substitute the identity $\sigma' = \sigma(1-\sigma)$. This is the step the whole chapter has been building toward:
$$ \frac{\partial \ell}{\partial z} = -\,\sigma(1-\sigma) \left[\, \frac{y}{\sigma} - \frac{1-y}{1-\sigma} \,\right]. $$Line 4 — distribute, and watch the denominators cancel. The first product cancels $\sigma$; the second cancels $(1-\sigma)$:
$$ \frac{\partial \ell}{\partial z} = -\Bigl[\, y(1-\sigma) \;-\; (1-y)\sigma \,\Bigr]. $$Line 5 — expand the bracket.
$$ y(1-\sigma) - (1-y)\sigma = y - y\sigma - \sigma + y\sigma = y - \sigma. $$The two $y\sigma$ terms annihilate. Therefore
$$ \frac{\partial \ell}{\partial z} = -(y - \sigma) = \sigma(z) - y = \hat y - y . $$Line 6 — the other factor. $z = \theta^\top x = \sum_j \theta_j x_j$, so $\partial z/\partial\theta_j = x_j$, i.e. $\partial z/\partial\theta = x$.
Line 7 — multiply, and average over the dataset.
$$ \frac{\partial \ell}{\partial \theta} = \bigl(\sigma(\theta^\top x) - y\bigr)\,x, \qquad\Longrightarrow\qquad \boxed{\;\nabla_\theta J = \frac{1}{N}\sum_{i=1}^{N}\Bigl(\sigma\bigl(\theta^\top x^{(i)}\bigr) - y^{(i)}\Bigr)\,x^{(i)}\;} $$$\blacksquare$
Every $\log$, every $e$, every $\sigma'$ has cancelled. What is left is
$$ \nabla_\theta J = \frac{1}{N}\sum_i (\text{prediction}_i - \text{truth}_i)\cdot x^{(i)} $$— "average the feature vectors, weighted by how wrong you were." Compare the linear-regression gradient of chapter 8:
$$ \nabla_\theta J_{\text{lin}} = \frac{1}{N}\sum_i \bigl(\theta^\top x^{(i)} - y^{(i)}\bigr)x^{(i)} \qquad\text{vs}\qquad \nabla_\theta J_{\text{log}} = \frac{1}{N}\sum_i \bigl(\sigma(\theta^\top x^{(i)}) - y^{(i)}\bigr)x^{(i)} $$Identical form, the only difference being that the prediction passes through $\sigma$ — a general property of the exponential family. beyond syllabus
Note what this gradient does not have: the $\sigma'$ factor that crippled squared loss. The confidently-wrong point ($y=1$, $\hat y = 0.001$) contributes $(0.001-1)x = -0.999\,x$, essentially full strength; a confidently-right point ($\hat y = 0.999$) contributes $-0.001\,x$, essentially nothing. The loss and the model were designed together so the saturation cancels exactly — which is why Figure B's far-away point left the logistic fit unchanged.
This is the lecture's $\nabla_\theta J^{(i)}(\theta) = \bigl(\hat p^{(i)}_\theta - y^{(i)}\bigr)x^{(i)}$. One question remains before running GD: linear regression's objective was a parabola — this is not, so now what?
7.4 There is no closed form
Setting the gradient to zero gives the score equations
$$ \sum_{i=1}^{N}\sigma\bigl(\theta^\top x^{(i)}\bigr)\,x^{(i)} \;=\; \sum_{i=1}^{N} y^{(i)}x^{(i)} . $$In linear regression the same step gave $X^\top X\theta = X^\top y$ — linear in $\theta$, so you invert a matrix and stop. Here $\theta$ is trapped inside an exponential, the equation is transcendental, and there is no normal equation for logistic regression.
So you iterate. $J$ is convex and differentiable, so gradient descent finds the global minimum given a small enough step size:
θ ← 0 # or small random values
repeat until converged:
g ← (1/N) Σ_i ( σ(θᵀx⁽ⁱ⁾) − y⁽ⁱ⁾ ) x⁽ⁱ⁾ # full-batch gradient
θ ← θ − α·g # α is the learning rateFor large $N$ use stochastic gradient descent: the same formula, averaged over one random sample or minibatch instead of all $N$. Everything from chapter 9 transfers verbatim.
A tiny dataset with one real feature, and the bias folded in so $x^{(i)} = [1,\; x_1^{(i)}]^\top$ and $\theta = [b,\; w]^\top$:
| $i$ | $x_1^{(i)}$ | $y^{(i)}$ |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 2 | 1 |
| 3 | 3 | 1 |
Start at $\theta^{(0)} = [0,\;0]^\top$ with learning rate $\alpha = 1$. Compute $J(\theta^{(0)})$, take one full-batch gradient step, and compute $J(\theta^{(1)})$. Did every point improve?
You may use $\log 2 = 0.6931$, $\sigma(0.8333)=0.6971$, $\sigma(1.5)=0.8176$, $\sigma(2.1667)=0.8972$.
Step 1 — Predictions and loss at the start
With $\theta = [0,0]^\top$ every logit is $z_i = 0\cdot 1 + 0\cdot x_1 = 0$, so every prediction is $\hat y_i = \sigma(0) = 0.5$. The model is maximally undecided about everything.
Each loss is $-\log(0.5) = \log 2 = 0.6931$ regardless of the label, so
$$ J(\theta^{(0)}) = \frac{3 \times 0.6931}{3} = 0.6931 . $$Sanity check to remember: $\log 2 \approx 0.693$ is the loss of a model that always shrugs. Any trained binary classifier reporting average cross-entropy above $0.693$ is doing worse than a coin.
Step 2 — The residuals
The gradient formula needs only $(\hat y_i - y_i)$:
| $i$ | $\hat y_i$ | $y_i$ | $\hat y_i - y_i$ | $x^{(i)}$ |
|---|---|---|---|---|
| 1 | 0.5 | 0 | $+0.5$ | $[1, 1]$ |
| 2 | 0.5 | 1 | $-0.5$ | $[1, 2]$ |
| 3 | 0.5 | 1 | $-0.5$ | $[1, 3]$ |
Sign check: a positive residual means the model predicted too high, so the step should push that sample's score down. Point 1 is the only one labelled $0$, so it is the only positive residual. Good.
Step 3 — Assemble the gradient
Bias component (first coordinate of every $x^{(i)}$ is $1$):
$$ \frac{\partial J}{\partial b} = \frac{1}{3}\bigl[(+0.5)(1) + (-0.5)(1) + (-0.5)(1)\bigr] = \frac{-0.5}{3} = -0.1667 . $$Weight component (second coordinate is $x_1^{(i)}$):
$$ \frac{\partial J}{\partial w} = \frac{1}{3}\bigl[(+0.5)(1) + (-0.5)(2) + (-0.5)(3)\bigr] = \frac{0.5 - 1 - 1.5}{3} = \frac{-2}{3} = -0.6667 . $$So $\nabla_\theta J = [-0.1667,\; -0.6667]^\top$. Both components are negative, meaning both parameters should increase — which matches intuition, since the class-1 points sit at larger $x$.
Step 4 — The update and the new loss
New logits $z_i = 0.1667 + 0.6667\,x_1^{(i)}$:
| $i$ | $z_i$ | $\hat y_i$ | $y_i$ | $\ell_i$ |
|---|---|---|---|---|
| 1 | 0.8333 | 0.6971 | 0 | $-\log(0.3029) = 1.1942$ |
| 2 | 1.5000 | 0.8176 | 1 | $-\log(0.8176) = 0.2014$ |
| 3 | 2.1667 | 0.8972 | 1 | $-\log(0.8972) = 0.1085$ |
Answer & the takeaway
Answers. $J(\theta^{(0)}) = 0.6931$; $\nabla J = [-0.1667, -0.6667]^\top$; $\theta^{(1)} = [0.1667, 0.6667]^\top$; $J(\theta^{(1)}) = 0.5014$. The loss fell by $0.192$.
No, not every point improved. Point 1 got distinctly worse: its loss rose from $0.6931$ to $1.1942$, because the step pushed the whole score line up and point 1 is the lone class-0 sample fighting against two class-1 samples at larger $x$. Points 2 and 3 improved enough to more than pay for it.
Takeaway. Gradient descent minimises the average, and the average is a negotiation. A single step can hurt individual samples; it can only ever hurt the majority-weighted sum if $\alpha$ is too large. This is also the honest answer to "why did my model get worse on my favourite example after retraining?" — because your favourite example is one term in a sum of $N$.
7.5 Convexity: why GD still finds the global minimum
Gradient descent looks downhill only locally, so on a bumpy surface it can settle in a dent that is not the lowest point (chapter 9). What made linear regression safe was being bowl-shaped; convexity is the precise version of that.
$f:\R\to\R$ is convex if the chord joining any two points on its graph never goes below the graph:
$$ f\bigl(\lambda z_1 + (1-\lambda) z_2\bigr) \;\le\; \lambda f(z_1) + (1-\lambda) f(z_2) \qquad \forall\, z_1, z_2 \in \R,\ \lambda\in[0,1]. $$Left to right: $\lambda z_1 + (1-\lambda)z_2$ is a point between $z_1$ and $z_2$ ($z_2$ at $\lambda=0$, $z_1$ at $\lambda=1$); the left side is the function there, the right side the same blend of the endpoint values — the height of the chord. For twice-differentiable $f$ the equivalent test is $f''(z) \ge 0$ everywhere: the slope never decreases. Both forms extend to $f:\R^d\to\R$, with $f''$ replaced by the Hessian, which must be positive semi-definite.
For a convex function, every local minimum is a global minimum. Suppose $z_1$ were a local minimum but $f(z_2) < f(z_1)$ for some $z_2$. Points on the segment just next to $z_1$ lie under the chord from $(z_1, f(z_1))$ to $(z_2, f(z_2))$, which slopes downward from $z_1$ — so they are strictly lower than $f(z_1)$ arbitrarily close to it, contradicting "local minimum". Hence GD/SGD, which find local minima, find the global one.
Take $\mathcal X = \R$, parameters $(\omega, b)$, one sample $(x, y)$, $z = \omega x + b$, $\hat p = \sigma(z)$. One term suffices, because a sum of convex functions is convex (add the chord inequalities term by term).
Step 1 — rewrite the loss without $\hat p$. Since $\frac{1}{\sigma(z)} = 1+e^{-z}$ and $\frac{1}{1-\sigma(z)} = 1 + e^{z}$,
$$ \ell = y\log(1+e^{-z}) + (1-y)\log(1+e^{z}). $$Step 2 — first derivative in $z$. $\frac{d}{dz}\log(1+e^{-z}) = \frac{-e^{-z}}{1+e^{-z}} = -(1-\sigma(z))$ and $\frac{d}{dz}\log(1+e^{z}) = \frac{e^{z}}{1+e^{z}} = \sigma(z)$. So
$$ \frac{d\ell}{dz} = -y(1-\sigma) + (1-y)\sigma = \sigma(z) - y . $$(Same answer as §7.3, by a shorter route.)
Step 3 — second derivative in $z$. $y$ is a constant, so $\frac{d^2\ell}{dz^2} = \sigma'(z) = \sigma(z)(1-\sigma(z)) > 0$.
Step 4 — back to the parameters. $z$ is linear in $(\omega, b)$ with $\partial z/\partial\omega = x$, $\partial z/\partial b = 1$. By the chain rule,
$$ \frac{\partial^2 \ell}{\partial\omega^2} = \sigma(1-\sigma)\,x^2 \ge 0, \qquad \nabla^2_{(\omega,b)}\,\ell = \sigma(1-\sigma)\begin{bmatrix} x^2 & x \\ x & 1\end{bmatrix}. $$That matrix is $\sigma(1-\sigma)\,vv^\top$ with $v = [x,\ 1]^\top$, and for any $u$, $u^\top vv^\top u = (v^\top u)^2 \ge 0$ — positive semi-definite. So each term is convex in $(\omega,b)$, and the sum over $N$ samples is too. $\blacksquare$
The same argument in $\R^d$ gives the Hessian $\sum_i \sigma_i(1-\sigma_i)\,x^{(i)}x^{(i)\top}$ — a non-negative combination of such outer products, hence PSD.
The loss is a convex function ($\log(1+e^{\pm z})$, a softened hinge) of a linear function of the parameters, and composing a linear map inside a convex function keeps it convex. Squared loss fails because $(y-\sigma(z))^2$ is not convex in $z$: the sigmoid's flattening bends it the wrong way.
8. More than two classes: softmax regression
For $K$ classes we want a distribution: $\hat y_k \ge 0$ with $\sum_k \hat y_k = 1$. Give each class a parameter vector $\theta_k \in \R^M$, compute the $K$ scores $\theta_k^\top x$, and normalise with the softmax:
$\exp$ makes every score positive and dividing by the sum makes them add to $1$, so the output is a distribution over the $K$ classes by construction.
Claim: softmax with $K=2$ is the sigmoid.
$$ \hat y_1 = \frac{e^{\theta_1^\top x}}{e^{\theta_1^\top x} + e^{\theta_0^\top x}} . $$Divide numerator and denominator by $e^{\theta_1^\top x}$ (non-zero, so legal):
$$ \hat y_1 = \frac{1}{1 + e^{\theta_0^\top x - \theta_1^\top x}} = \frac{1}{1 + e^{-(\theta_1 - \theta_0)^\top x}} = \sigma\bigl((\theta_1-\theta_0)^\top x\bigr). \qquad\blacksquare $$This is the lecture's exercise ("set $K=2$ and let $\theta = \theta_1 - \theta_2$"), with the second class indexed $0$ here. Only the difference of the two parameter vectors is identifiable, which is why two classes need one vector and not two — and in general why softmax has $K$ vectors but $K-1$ degrees of freedom: adding a constant vector to every $\theta_k$ cancels top and bottom.
The loss generalises the same way. With the true class $y \in \{1,\dots,K\}$, multi-class cross-entropy is
$$ \ell(y, \hat y) = -\sum_{k=1}^{K}\1\{y = k\}\log\hat y_k \;=\; -\log \hat y_{\,y} $$where $\1\{\cdot\}$ is the indicator — the same sentence as before, minus the log of the probability you gave the true class. The gradient keeps its shape:
$$ \nabla_{\theta_k} J = \frac{1}{N}\sum_{i=1}^{N}\Bigl(\hat y^{(i)}_k - \1\{y^{(i)} = k\}\Bigr)x^{(i)} $$— prediction minus truth, times the input, exactly as in §7.3, now once per class. Under ERM with this loss it is called softmax regression or multinomial logistic regression; in a neural network it is "a linear layer with a softmax output".
9. Common mistakes
1. "Logistic regression is regression, so it predicts a number." No — it is a classification model: labels in $\{0,1\}$, output used to choose a class.
The name comes from §6: $\log\frac{p}{1-p} = \theta^\top x$ is a bona fide linear regression on the log-odds, whose response happens to be a logit rather than an observed number. The name records the mathematics, not the task — and it misleads about one student a semester into fitting it with squared loss and wondering why nothing works.
2. Always thresholding at $0.5$. Nothing says $0.5$ is the right operating point; it is just the value making the rule coincide with $\theta^\top x \ge 0$. Two situations break it:
- Class imbalance. If only $1\%$ of samples are class 1, a well-fitted model may never output $h(x) > 0.5$, so thresholding there says "class 0" to everything: $99\%$ accurate, useless.
- Asymmetric loss. Recall the asymmetric loss table from chapter 5: if a false negative costs $C_{\text{FN}}$ and a false positive costs $C_{\text{FP}}$, the expected-cost-minimising rule is to predict class 1 when $h(x)\,C_{\text{FN}} > (1-h(x))\,C_{\text{FP}}$, i.e. when
If missing a tumour is $9\times$ worse than an unnecessary biopsy, the threshold is $1/(1+9) = 0.1$, not $0.5$. This is exactly why we wanted probabilities in §1 — a probability lets you move the threshold after training; a hard label does not.
3. Forgetting the bias term. Write $h(x) = \sigma(w^\top \tilde x)$ with no $\theta_0$ and the boundary $w^\top\tilde x = 0$ is forced through the origin: the model can rotate it but never translate it. On our 1-D dataset it is stuck at $x = 0$ instead of $x = 1.05$, and five points are misclassified whatever $w$ you pick.
The bug: you build the design matrix and forget to prepend the column of ones (chapter 10's column), then get stubbornly mediocre accuracy with no error message. Check that $\theta$ has $M+1$ entries for $M$ features.
4. Assuming $\sigma(\theta^\top x)$ is a calibrated probability. The output is a number in $(0,1)$ that we interpret as $P(Y=1\mid x)$, which assumes the true log-odds really are linear in $x$. When that is roughly right (and the loss really is cross-entropy, which pushes outputs toward the empirical rates), the numbers come out well calibrated; when it is not, they can be systematically off while the rankings and the accuracy stay fine.
How to check. Bin held-out predictions — say all samples with $h(x)\in[0.7,0.8)$ — and compute what fraction were actually class 1; calibrated means about $0.75$. Plotting bin midpoint against observed frequency (a reliability diagram) should give the diagonal. beyond syllabus Post-hoc fixes exist (Platt scaling, isotonic regression), but the first step is to look.
5. Small numerical traps. (a) Computing $\sigma(z)$ as 1/(1+exp(-z)) overflows for very negative $z$; libraries use the branch $\sigma(z) = e^{z}/(1+e^{z})$ when $z < 0$. (b) $\log(0)$ is $-\infty$, so never round $\hat y$ to $0$ or $1$ before taking the log — this is why real implementations fuse the sigmoid and the log into one "logits" function. (c) The range is $(0,1)$ open, so a printed $\hat y$ of exactly $1.0$ means floating-point rounding, not certainty.
10. Recap
Every formula and condition is in the Essentials box at the top. Five things worth saying once more:
- One requirement drives the chapter: the loss must have a usable slope in the parameters. That is what kills the threshold and chooses the sigmoid.
- $\sigma' = \sigma(1-\sigma)$ is the load-bearing identity: it makes the gradient cancel down to $(\hat y - y)x$, and it is why confidently-correct points stop voting.
- Non-linear in $x$, linear as a classifier: a monotone squashing cannot move a point across $\theta^\top x = 0$.
- Cross-entropy, not squared loss: squared loss is non-convex here, and its gradient vanishes exactly where the model is most wrong.
- Convexity licenses gradient descent — every local minimum is global — and there is no closed form, so iterating is the only option.