---
title: Logistic Regression
module: Text Classification
moduleNumber: 2
lessonNumber: 3
order: 203
summary: >
  Logistic regression is the discriminative counterpart to naive Bayes: instead
  of modelling how a document is generated, it learns weights that directly
  separate the classes. We build it from the sigmoid, derive the cross-entropy
  loss from maximum likelihood, learn the weights by stochastic gradient descent,
  regularize to curb overfitting, and generalize to many classes with the softmax.
  The two-class model is already a one-neuron network, so this is the bridge to
  neural language models.
topics: [Classification]
sources:
  - book: Jurafsky
    ref: "Ch. 5 — Logistic Regression; §5.1 The Sigmoid; §5.2 Learning in Logistic Regression"
  - book: Jurafsky
    ref: "§5.3 Cross-Entropy Loss; §5.4 Gradient Descent; §5.5 Regularization; §5.6 Multinomial Logistic Regression"
---

[Naive Bayes](/natural-language-processing/classification/naive-bayes-and-sentiment)
classifies a document indirectly. To decide whether a review
is positive or negative it estimates, for each class, the likelihood $P(d \mid c)$
of the document under that class, then
multiplies by a prior and picks the class with the larger product. It models the
process that _generates_ the words. Logistic regression estimates the target
quantity, $P(c \mid d)$, directly. It never models how
documents are generated; it learns a boundary that separates the classes and reads
off the probability of the class from which side of the boundary a document lands
on.[^jm-gendisc]

That split — model the data, or model the boundary — has standard names.

> **Definition (Generative classifier).** A model of the joint distribution: it
> learns $P(d \mid c)$, the likelihood of generating the observed features from
> each class, and combines it with a prior $P(c)$ by Bayes' rule to classify.
> Naive Bayes is the canonical example.

> **Definition (Discriminative classifier).** A model of the posterior $P(c \mid
> d)$ directly. It never describes how documents arise; it assigns weight to
> whatever features best _discriminate_ between the classes, even features it could
> not use to generate an example. Logistic regression is the canonical example.

In practice, the discriminative choice means logistic regression handles
correlated features well. Naive Bayes assumes the features are
conditionally independent given the class; add the same feature twice and it
double-counts the evidence. Logistic regression, given two perfectly correlated
features, simply splits the weight between them and reaches the same, calibrated
answer. That robustness is why it usually wins on larger documents and larger
feature sets — though naive Bayes, with no optimization step to run, remains fast,
easy, and competitive on very small or very short data.[^jm-choose]

Logistic regression is a **supervised** classifier: it trains on $m$ labelled pairs
$(\mathbf{x}^{(i)}, y^{(i)})$, where each $\mathbf{x}^{(i)}$ is a feature vector and
$y^{(i)} \in \{0, 1\}$ is the gold label. It has four components, covered below in
order:[^jm-components]

| Component | What it is | Symbol |
| --- | --- | --- |
| Feature representation | the input as a vector of features | $\mathbf{x} = [x_1, \ldots, x_n]$ |
| Classifier | maps features to a class probability | $\sigma(\mathbf{w}\cdot\mathbf{x} + b)$ |
| Objective | scores how wrong the prediction is | cross-entropy loss $L_{CE}$ |
| Optimizer | adjusts the weights to reduce the loss | stochastic gradient descent |

## From a weighted sum to a probability

Represent an observation as a feature vector $\mathbf{x} = [x_1, \ldots, x_n]$.
Logistic regression learns a **weight** $w_i$ for each feature and a single **bias**
$b$ (also called the intercept). A weight records how strongly its feature indicates
the positive class: a large positive $w_i$ pushes toward $y = 1$, a large negative
$w_i$ toward $y = 0$. To score a test instance the classifier multiplies each
feature by its weight, sums, and adds the bias, producing a single number $z$ — the
weighted evidence for the class:

$$
z \;=\; \parens{\sum_{i=1}^{n} w_i x_i} + b \;=\; \mathbf{w} \cdot \mathbf{x} + b.
$$

The dot product $\mathbf{w} \cdot \mathbf{x}$ is just that sum of products, written
compactly. Nothing constrains $z$ to be a probability: the weights are real-valued,
so $z$ ranges over all of $(-\infty, \infty)$. We need to squash it into $[0, 1]$.
The **sigmoid** (or **logistic**) function does exactly that:[^jm-sigmoid]

$$
\sigma(z) \;=\; \frac{1}{1 + e^{-z}} \;=\; \frac{1}{1 + \exp(-z)}.
$$

$$
% caption: The sigmoid $\sigma(z) = 1/(1 + e^{-z})$ maps any real $z$ into $(0,1)$.
% It is nearly linear near $z = 0$ and saturates toward $0$ and $1$ at the extremes,
% which squashes outliers; the crossover $\sigma(0) = 0.5$ is the decision boundary.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (-4.2,0) -- (4.4,0) node[right, black, font=\footnotesize] {z};
  \draw[->, black] (0,-0.15) -- (0,2.5) node[above, black, font=\footnotesize] {sigma(z)};
  % gridline levels 0.5 and 1
  \draw[black, dashed] (-4.2,1.0) -- (4.2,1.0);
  \draw[black, dashed] (-4.2,2.0) -- (4.2,2.0);
  \node[black, font=\scriptsize, anchor=east] at (-0.08,1.0) {0.5};
  \node[black, font=\scriptsize, anchor=east] at (-0.08,2.0) {1.0};
  % sigmoid curve, y scaled by 2 so 1.0 sits at height 2
  \draw[acc, very thick, samples=120, domain=-4:4]
    plot (\x, {2/(1 + exp(-2*\x))});
  % crossover point
  \fill[red] (0,1.0) circle (2pt);
  \node[red, font=\scriptsize, anchor=south east] at (-0.12,1.06) {(0, 0.5)};
  % curve label at right end
  \node[acc, anchor=west, font=\footnotesize] at (4.05,1.92) {sigma(z)};
\end{tikzpicture}
$$

The sigmoid is a good squashing function for three reasons. It is nearly linear
around $z = 0$, so it preserves small differences in the evidence there; it flattens
toward $0$ and $1$ at the extremes, so a wildly confident outlier cannot dominate;
and it is smooth and **differentiable**, which is what makes learning by gradient
descent possible at all. Applying it to the weighted sum gives the probability of
the positive class, and the negative class takes the rest:

$$
P(y = 1 \mid \mathbf{x}) = \sigma(\mathbf{w}\cdot\mathbf{x} + b), \qquad
P(y = 0 \mid \mathbf{x}) = 1 - \sigma(\mathbf{w}\cdot\mathbf{x} + b).
$$

The two probabilities sum to one by construction, so the model is a valid
distribution over the two classes. A convenient identity, $1 - \sigma(z) =
\sigma(-z)$, lets us write $P(y = 0 \mid \mathbf{x}) = \sigma(-(\mathbf{w}\cdot
\mathbf{x} + b))$ as well.

### The decision boundary

To turn a probability into a class we threshold at $0.5$: predict the positive class
when it is the more probable one. The value $0.5$ is the **decision boundary**.

> **Definition (Decision boundary).** The threshold that converts the estimated
> probability into a discrete class. For binary logistic regression,
> $\hat{y} = 1$ if $P(y = 1 \mid \mathbf{x}) > 0.5$ and $\hat{y} = 0$ otherwise.

Because $\sigma(z) > 0.5$ exactly when $z > 0$, the boundary in feature space is the
set of points where the weighted sum is zero, $\mathbf{w}\cdot\mathbf{x} + b = 0$.
That is a **hyperplane** — a flat surface, a line in two dimensions. Logistic
regression is a linear classifier: it can only separate classes a straight boundary
can separate. The weight vector $\mathbf{w}$ is the normal to that hyperplane, and
$\mathbf{w}\cdot\mathbf{x} + b$ measures signed distance from it, which the sigmoid
converts to a confidence.

$$
% caption: The linear decision boundary $\mathbf{w}\cdot\mathbf{x} + b = 0$
% (heavy line) separates the two classes; the weight vector $\mathbf{w}$ is normal
% to it. Points on the positive side get $P(y{=}1\mid\mathbf{x}) > 0.5$, and the
% farther a point sits from the boundary, the more confident the sigmoid.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % frame
  \draw[black] (-0.2,-0.2) rectangle (6.4,4.4);
  \node[anchor=south east, black, font=\scriptsize] at (6.4,4.4) {x2};
  \node[anchor=north east, black, font=\scriptsize] at (6.4,-0.2) {x1};
  % decision boundary line: from lower-left to upper-right
  \draw[black, very thick] (0.4,0.2) -- (5.6,4.2);
  \node[black, font=\scriptsize, anchor=west] at (5.62,4.2) {w . x + b = 0};
  % positive-class points (upper-left side)
  \foreach \p in {(0.7,2.6),(1.2,3.5),(0.9,1.9),(1.8,3.9),(2.1,3.0),(1.5,2.4),(0.6,3.4)}
    \fill[acc] \p circle (2.3pt);
  % negative-class points (lower-right side)
  \foreach \p in {(3.6,0.7),(4.4,1.4),(5.1,1.0),(4.0,0.4),(5.6,2.0),(4.8,0.6),(3.4,1.5)}
    {\draw[red, thick] \p ++(-2.4pt,-2.4pt) -- ++(4.8pt,4.8pt);
     \draw[red, thick] \p ++(-2.4pt,2.4pt) -- ++(4.8pt,-4.8pt);}
  % normal vector w, drawn off the boundary into the positive region
  \draw[acc, very thick, ->] (3.3,2.0) -- (2.35,3.24);
  \node[acc, font=\scriptsize, anchor=south west] at (2.5,3.1) {w};
  % class labels
  \node[acc, font=\scriptsize] at (0.9,4.05) {y = 1};
  \node[red, font=\scriptsize] at (5.6,0.55) {y = 0};
\end{tikzpicture}
$$

### A worked sentiment example

For example, take binary sentiment classification of a movie review. Following
Jurafsky & Martin, represent a review by six features, hand-designed from linguistic
intuition:[^jm-features]

| Feature | Definition | Value in the sample review |
| --- | --- | --- |
| $x_1$ | count of positive-lexicon words in the doc | $3$ |
| $x_2$ | count of negative-lexicon words in the doc | $2$ |
| $x_3$ | $1$ if `no` appears in the doc, else $0$ | $1$ |
| $x_4$ | count of first- and second-person pronouns | $3$ |
| $x_5$ | $1$ if `!` appears in the doc, else $0$ | $0$ |
| $x_6$ | $\ln(\text{word count of doc})$ | $\ln(66) = 4.19$ |

Suppose learning has already produced the weights $\mathbf{w} = [2.5, -5.0, -1.2,
0.5, 2.0, 0.7]$ and bias $b = 0.1$. The weight $w_1 = 2.5$ is positive: positive-
lexicon words are evidence for a positive review. The weight $w_2 = -5.0$ is negative
and about twice as large in magnitude: negative words are evidence against, and count
for more.
Plug the feature vector in:

$$
\begin{aligned}
P(+ \mid \mathbf{x}) &= \sigma(\mathbf{w}\cdot\mathbf{x} + b) \\
&= \sigma\big([2.5, -5.0, -1.2, 0.5, 2.0, 0.7] \cdot [3, 2, 1, 3, 0, 4.19] + 0.1\big) \\
&= \sigma(0.833) = 0.70, \\
P(- \mid \mathbf{x}) &= 1 - \sigma(\mathbf{w}\cdot\mathbf{x} + b) = 0.30.
\end{aligned}
$$

The model calls it positive, with $0.70$ confidence. Nothing about logistic
regression restricts the features to sentiment: a feature can be any real-valued
property of the input. Period disambiguation (is a `.` the end of a sentence or part
of an abbreviation?) uses features like "is the current word lowercase?" or "is it
in an abbreviation dictionary?"; a feature can even combine primitives — a **feature
interaction** such as "period follows `St.` and the previous word is capitalized."
For tasks with large vocabularies, **feature templates** generate one feature per
observed n-gram automatically. The design of good features — by error analysis and
linguistic intuition — was, before representation learning, most of the applied
work; the [next chapter's embeddings](/natural-language-processing/semantics/vector-semantics-and-embeddings)
are the move to learning features instead of designing them.

## The cross-entropy loss

We have a classifier but no way to learn its weights. Learning needs an
**objective**: a number that measures how far the prediction $\hat{y} =
\sigma(\mathbf{w}\cdot\mathbf{x} + b)$ is from the gold label $y$, small when the two
agree and large when they diverge. The right objective falls out of a single
principle, **conditional maximum likelihood**: choose the weights that make the true
labels in the training data as probable as possible.[^jm-loss]

Consider one example with label $y \in \{0, 1\}$. Since there are exactly two
outcomes, the model's probability of the observed label is a Bernoulli, which a
single expression captures:

$$
p(y \mid \mathbf{x}) \;=\; \hat{y}^{\,y}\,(1 - \hat{y})^{\,1 - y}.
$$

The exponents select the right case. When $y = 1$ this reads $\hat{y}^{1}(1 - \hat{y})^{0}
= \hat{y}$; when $y = 0$ it reads $\hat{y}^{0}(1 - \hat{y})^{1} = 1 - \hat{y}$.
Either way it is the probability the model assigned to the _correct_ answer. Taking
the log — which is monotonic, so it does not move the maximizer — turns the product
into a sum:

$$
\log p(y \mid \mathbf{x}) \;=\; y \log \hat{y} + (1 - y)\log(1 - \hat{y}).
$$

This is a log likelihood we want to _maximize_. To make it a loss we want to
_minimize_, flip the sign. The result is the **cross-entropy loss**:

$$
L_{CE}(\hat{y}, y) \;=\; -\log p(y \mid \mathbf{x})
\;=\; -\big[\,y \log \hat{y} + (1 - y)\log(1 - \hat{y})\,\big].
$$

> **Definition (Cross-entropy loss).** The negative log probability the model
> assigns to the true label: $L_{CE}(\hat{y}, y) = -[y \log \hat{y} + (1 - y)
> \log(1 - \hat{y})]$. Minimizing it is exactly conditional maximum likelihood
> estimation of the weights. The name is because it is the cross-entropy between
> the true label distribution $y$ and the model's distribution $\hat{y}$.

Substituting $\hat{y} = \sigma(\mathbf{w}\cdot\mathbf{x} + b)$ gives the loss in
terms of the weights:

$$
L_{CE}(\hat{y}, y) \;=\; -\big[\,y \log \sigma(\mathbf{w}\cdot\mathbf{x} + b)
+ (1 - y)\log\big(1 - \sigma(\mathbf{w}\cdot\mathbf{x} + b)\big)\,\big].
$$

Why is this the right objective? A perfect classifier assigns probability $1$ to the
correct outcome, and $-\log 1 = 0$: no loss. The more probability it wastes on the
wrong answer, the larger $-\log(\text{correct prob})$ grows, running to infinity as
the correct probability approaches zero. On the worked example, if the gold label is
positive ($y = 1$) and the model said $\hat{y} = 0.70$, the loss is $-\log 0.70 =
0.36$ — small, because the model was mostly right. If the same review were actually
negative ($y = 0$), the model put $0.70$ on the wrong class and the loss is
$-\log(0.30) = 1.2$ — larger, because it was confidently wrong. The loss is small
when the model is right and large for confident mistakes.

$$
% caption: The two branches of the cross-entropy loss as a function of the
% predicted probability $\hat{y}$. When the true label is $y = 1$ (blue), the loss
% $-\log\hat{y}$ falls to $0$ as $\hat{y} \to 1$; when $y = 0$ (red), the loss
% $-\log(1-\hat{y})$ falls to $0$ as $\hat{y} \to 0$. Confident wrong answers
% diverge toward infinity.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes, y scaled: plot value = loss * 0.6, capped near 3
  \draw[->, black] (-0.15,0) -- (6.3,0) node[right, black, font=\scriptsize] {y-hat};
  \draw[->, black] (0,-0.15) -- (0,3.0) node[above, black, font=\scriptsize] {loss};
  % x ticks 0 and 1 (mapped 0..1 -> 0..6)
  \node[black, font=\scriptsize, anchor=north] at (0,-0.05) {0};
  \node[black, font=\scriptsize, anchor=north] at (6,-0.05) {1};
  % loss for y=1: -log(yhat), sampled away from singularities
  \draw[acc, very thick, samples=100, domain=0.045:0.985]
    plot ({6*\x}, {min(2.85, -0.6*ln(\x))});
  % loss for y=0: -log(1-yhat)
  \draw[red, very thick, samples=100, domain=0.015:0.955]
    plot ({6*\x}, {min(2.85, -0.6*ln(1-\x))});
  % curve labels
  \node[acc, font=\scriptsize, anchor=south east] at (1.5,2.55) {y = 1};
  \node[red, font=\scriptsize, anchor=south west] at (4.5,2.55) {y = 0};
\end{tikzpicture}
$$

For logistic regression this loss has a property neural networks lose: it is
**convex**. A convex function has a single minimum and no spurious local minima, so gradient
descent from any starting point is guaranteed to find the global optimum. The loss
surfaces of deep networks are non-convex — riddled with the saddle points and local
minima that the [deep-learning optimization](/deep-learning/optimization/gradient-descent-and-sgd)
chapter is about — but for one linear layer, the geometry is benign.

## Learning by gradient descent

The goal is the weights that minimize the average loss over the training set. Write
the parameters as $\theta = (\mathbf{w}, b)$; then

$$
\hat{\theta} \;=\; \argmin_{\theta}\; \frac{1}{m}\sum_{i=1}^{m}
L_{CE}\big(f(\mathbf{x}^{(i)}; \theta),\, y^{(i)}\big).
$$

**Gradient descent** finds that minimum by repeatedly stepping downhill. At the
current parameters it computes the direction in which the loss rises most steeply —
the gradient — and moves the opposite way. Picture the loss over a single weight $w$
as a curve: at a point where the slope is negative, the minimum lies to the right, so
we increase $w$; where the slope is positive, we decrease it. The slope's sign tells
us the direction; its magnitude, scaled by a step size, tells us how far.[^jm-gd]

$$
% caption: Gradient descent on a one-parameter loss. At the initial weight (blue
% dot) the tangent (dashed) has negative slope, so the minimum lies to the right;
% the update moves $w$ in the positive direction, opposite the slope, toward
% $w$-min.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (-0.2,0) -- (6.6,0) node[right, black, font=\scriptsize] {w};
  \draw[->, black] (0,-0.2) -- (0,3.4) node[above, black, font=\scriptsize] {loss};
  % a convex loss curve (parabola-ish), minimum near w=4.2
  \draw[black, very thick, samples=100, domain=0.5:6.2]
    plot (\x, {0.34*(\x-4.2)*(\x-4.2) + 0.35});
  % initial point w1 near x=1.7; loss value there = 0.34*(2.5)^2 + 0.35 = 2.475
  \fill[acc] (1.7,2.475) circle (2.4pt);
  \node[acc, font=\scriptsize, anchor=west] at (1.85,2.6) {w-init};
  % tangent at w-init: slope = 0.68*(1.7-4.2) = -1.7, through (1.7, 2.475)
  \draw[red, thick, dashed] (0.65,{2.475 + (-1.7)*(0.65-1.7)}) -- (2.9,{2.475 + (-1.7)*(2.9-1.7)});
  \node[red, font=\scriptsize, anchor=west] at (0.35,3.05) {tangent};
  % minimum
  \fill[black] (4.2,0.35) circle (2pt);
  \node[black, font=\scriptsize, anchor=north] at (4.2,0.28) {w-min (goal)};
  % descent arrow along the axis
  \draw[acc, very thick, ->] (1.9,0.15) -- (3.6,0.15);
  \node[acc, font=\scriptsize, anchor=south] at (2.75,0.18) {step};
\end{tikzpicture}
$$

### The gradient of the loss

In $n$ dimensions the gradient $\nabla_\theta L$ is the vector of partial
derivatives, one per weight (and one for the bias), each recording how much a small
change in that parameter changes the loss. For the cross-entropy loss the partial
derivative with respect to weight $w_j$ has a simple form:[^jm-grad]

$$
\frac{\partial L_{CE}}{\partial w_j}
\;=\; \big[\sigma(\mathbf{w}\cdot\mathbf{x} + b) - y\big]\,x_j
\;=\; (\hat{y} - y)\,x_j.
$$

The gradient for feature $j$ is the **prediction error**
$\hat{y} - y$ — how far the estimate overshot the truth — multiplied by the feature
value $x_j$. If the model is exactly right, $\hat{y} = y$, the error is zero and the
weight does not move. If it overshoots, the error is positive and the update shrinks
the weights on the active features; if it undershoots, the reverse. The size of the
correction scales with how active the feature was. The derivative of a sigmoid
composed with a log collapses to this simple form because the sigmoid and
cross-entropy are chosen _together_.

The collapse is worth deriving, because it is the same chain-rule pattern that
scales up to [backpropagation](/deep-learning/neural-networks/backpropagation). Write
$z = \mathbf{w}\cdot\mathbf{x} + b$ so $\hat{y} = \sigma(z)$, and use two facts. First,
the sigmoid has an unusually clean derivative,

$$
\frac{d\sigma}{dz} = \sigma(z)\big(1 - \sigma(z)\big) = \hat{y}(1 - \hat{y}),
$$

which follows from the quotient rule on $1/(1+e^{-z})$. Second, $\partial z/\partial
w_j = x_j$, since $z$ is linear in each weight. Differentiate the loss $L_{CE} =
-[y\log\hat{y} + (1-y)\log(1-\hat{y})]$ with respect to $\hat{y}$:

$$
\frac{\partial L_{CE}}{\partial \hat{y}}
= -\frac{y}{\hat{y}} + \frac{1-y}{1-\hat{y}}
= \frac{\hat{y} - y}{\hat{y}(1 - \hat{y})}.
$$

Now chain the three factors, $\dfrac{\partial L_{CE}}{\partial w_j} =
\dfrac{\partial L_{CE}}{\partial \hat{y}}\cdot\dfrac{d\hat{y}}{dz}\cdot\dfrac{\partial
z}{\partial w_j}$, and the $\hat{y}(1-\hat{y})$ from the sigmoid derivative cancels
the identical factor in the denominator of $\partial L_{CE}/\partial\hat{y}$:

$$
\frac{\partial L_{CE}}{\partial w_j}
= \frac{\hat{y} - y}{\hat{y}(1 - \hat{y})} \cdot \hat{y}(1 - \hat{y}) \cdot x_j
= (\hat{y} - y)\,x_j.
$$

The cancellation is the whole point of pairing the sigmoid with cross-entropy: any
other loss would leave a $\hat{y}(1-\hat{y})$ factor in the gradient, which vanishes
when the model is confidently wrong ($\hat{y}$ near $0$ or $1$) and stalls learning
exactly when it is most needed. Cross-entropy removes that factor, so the update is
driven by the raw error even at the extremes.

### The update rule and stochastic gradient descent

Each step moves the parameters against the gradient, scaled by the **learning rate**
$\eta$ — a hyperparameter setting the step size:

$$
\theta_{t+1} \;=\; \theta_t - \eta\, \nabla_\theta L\big(f(\mathbf{x}; \theta), y\big).
$$

Too large an $\eta$ overshoots the minimum and oscillates; too small an $\eta$
converges very slowly. **Stochastic gradient descent** (SGD) is the online version: it
computes the gradient on one training example at a time and updates immediately,
rather than waiting to average over the whole set. It processes the data
example-by-example, correcting the weights after each.[^jm-sgd]

```algorithm
caption: $\textsc{Stochastic-Gradient-Descent}(L, f, \mathbf{x}, \mathbf{y})$ — return trained $\theta$
input: loss $L$, model $f$ parameterized by $\theta$
input: training inputs $\mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(m)}$ and labels $y^{(1)}, \ldots, y^{(m)}$
$\theta \gets 0$
repeat
  for each training pair $(\mathbf{x}^{(i)}, y^{(i)})$ in random order do
    $\hat{y}^{(i)} \gets f(\mathbf{x}^{(i)}; \theta)$ // forward: current prediction
    $L^{(i)} \gets L(\hat{y}^{(i)}, y^{(i)})$ // how far off is it?
    $g \gets \nabla_\theta L(f(\mathbf{x}^{(i)}; \theta), y^{(i)})$ // gradient at this example
    $\theta \gets \theta - \eta\, g$ // step against the gradient
until convergence
return $\theta$
```

Termination is a judgment call: stop when the loss stops falling, when the gradient
norm drops below a tolerance, or when the loss on a held-out set starts _rising_ (a
sign of overfitting). It is common to start $\eta$ high and decay it over iterations,
writing $\eta_k$ for its value at step $k$, so early steps move fast and later ones
settle.

A single step, worked out. Take one positive example ($y = 1$) with two features,
$x_1 = 3$ and $x_2 = 2$, and start from $\mathbf{w} = \mathbf{0}$, $b = 0$, $\eta =
0.1$. With all weights zero, $\mathbf{w}\cdot\mathbf{x} + b = 0$ and $\sigma(0) =
0.5$, so the prediction error is $\hat{y} - y = 0.5 - 1 = -0.5$. The gradient
components are $(\hat{y} - y)x_j$:

$$
\nabla_\theta L \;=\;
\begin{bmatrix}(\hat{y}-y)x_1 \\ (\hat{y}-y)x_2 \\ \hat{y}-y\end{bmatrix}
\;=\;
\begin{bmatrix}-1.5 \\ -1.0 \\ -0.5\end{bmatrix},
\qquad
\theta_1 = \theta_0 - \eta\,\nabla_\theta L =
\begin{bmatrix}0.15 \\ 0.10 \\ 0.05\end{bmatrix}.
$$

After one step the weights have moved off zero in the direction that raises the
model's probability on this positive example: $w_1 = 0.15$, $w_2 = 0.10$, $b = 0.05$.

Iterate the same update on the same example and it converges. Each step recomputes
$z$, hence $\hat{y}$, hence the error; because this is one positive example with no
opposing data, $\hat{y}$ climbs toward $1$ and the loss falls. The gradient magnitude
shrinks with the error, so the steps get smaller as the fit improves — after ten
steps $\hat{y} \approx 0.87$. The table traces the first three:

| step | $z$ | $\hat{y} = \sigma(z)$ | error $\hat{y}-y$ | $L_{CE} = -\log\hat{y}$ |
| --- | --- | --- | --- | --- |
| 0 | $0.000$ | $0.500$ | $-0.500$ | $0.693$ |
| 1 | $0.700$ | $0.668$ | $-0.332$ | $0.403$ |
| 2 | $1.163$ | $0.762$ | $-0.238$ | $0.272$ |
| 3 | $1.503$ | $0.818$ | $-0.182$ | $0.201$ |

$$
% caption: The loss falling over SGD steps on one positive example. Each step moves
% the weights against the gradient; the prediction climbs toward 1 and the
% cross-entropy loss decays, with smaller steps as the error shrinks.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, black] (-0.2,0) -- (6.6,0) node[right, black, font=\scriptsize] {step};
  \draw[->, black] (0,-0.2) -- (0,3.2) node[above, black, font=\scriptsize] {loss};
  % loss values scaled x4: 0.693,0.403,0.272,0.201,0.158,... at steps 0..
  \draw[acc, very thick] plot[smooth] coordinates
    {(0.3,2.77)(1.3,1.61)(2.3,1.09)(3.3,0.80)(4.3,0.63)(5.3,0.52)(6.0,0.46)};
  \foreach \x/\y in {0.3/2.77, 1.3/1.61, 2.3/1.09, 3.3/0.80}
    \fill[acc] (\x,\y) circle (2pt);
  \node[acc, anchor=west, font=\scriptsize] at (4.3,0.9) {loss decays toward 0};
\end{tikzpicture}
$$

On a real training set the picture is the same but noisier: each example pulls the
weights in its own direction, and the loss falls on average rather than monotonically,
which is why SGD's stopping rule watches a held-out set instead of demanding the
training loss reach zero.

**Minibatch** training is the middle ground between SGD's one-example updates and
full-batch descent over the entire set. It averages the gradient over a group of $m$
examples — a few hundred to a thousand — cutting the noise of single-example steps
while staying cheap, and the batch vectorizes cleanly onto parallel hardware. The
minibatch gradient is just the average of the per-example gradients:

$$
\frac{\partial\, \text{Cost}}{\partial w_j}
\;=\; \frac{1}{m}\sum_{i=1}^{m}\big[\sigma(\mathbf{w}\cdot\mathbf{x}^{(i)} + b)
- y^{(i)}\big]\,x_j^{(i)}.
$$

## Regularization

A model that fits the training data _too_ well fits its noise. If some feature
happens to occur only in positive examples in the training set — a fluke of a small
sample — logistic regression will assign it a huge weight to match those cases exactly,
and that weight will mislead on unseen data. This is **overfitting**: excellent
training accuracy, poor generalization.[^jm-reg]

The fix is to add a **regularization** term $R(\theta)$ that penalizes large weights,
so the objective trades off fitting the data against keeping the weights small:

$$
\hat{\theta} \;=\; \argmax_{\theta}\;
\sum_{i=1}^{m} \log P(y^{(i)} \mid \mathbf{x}^{(i)}) \;-\; \alpha\, R(\theta).
$$

The hyperparameter $\alpha$ sets how hard to push. A weight setting that fits the
data with many small weights is now preferred over one that fits marginally better
using a few enormous ones. The two standard choices differ in the norm they penalize:

> **Definition (L2 regularization).** Penalize the squared Euclidean (L2) norm of
> the weights, $R(\theta) = \norm{\theta}_2^2 = \sum_{j=1}^{n} \theta_j^2$. Also
> called **ridge** regression. Its derivative is the simple $2\theta_j$, so it is
> easy to optimize; it prefers many small weights and shrinks them smoothly toward
> zero without forcing any to exactly zero.

> **Definition (L1 regularization).** Penalize the L1 (Manhattan) norm,
> $R(\theta) = \norm{\theta}_1 = \sum_{j=1}^{n} \abs{\theta_j}$. Also called
> **lasso** regression. Its derivative is non-continuous at zero, so it is harder to
> optimize, but it drives many weights _exactly_ to zero, yielding a sparse model
> that uses far fewer features.

Both have Bayesian readings as priors on the weights: L2 corresponds to a Gaussian
prior centered at zero (weights are pulled toward zero), L1 to a Laplace prior. The
choice is L2 when you want smooth shrinkage, L1 when you want feature selection built
into the fit.

## More than two classes: the softmax

Many tasks have more than two classes — 3-way sentiment (positive, negative,
neutral), part-of-speech tags, named-entity types. **Multinomial logistic
regression** (historically, the **maxent** classifier) generalizes the binary model
to $K$ classes. Where the sigmoid squashed one number into $[0, 1]$, the **softmax**
squashes a vector of $K$ numbers into a probability distribution over the $K$
classes:[^jm-softmax]

$$
\text{softmax}(z_i) \;=\; \frac{\exp(z_i)}{\sum_{j=1}^{K}\exp(z_j)},
\qquad 1 \le i \le K.
$$

The numerator is exponential, so it is always positive; the denominator sums the
exponentials of every class, so the outputs sum to one — a valid distribution. Like
the sigmoid, the softmax sharpens differences: the largest component of $z$ is pushed
toward $1$ and the rest are suppressed. Now each class $c$ has its _own_ weight vector
$\mathbf{w}_c$ and bias $b_c$, and the probability of class $c$ is its exponentiated
score, normalized:

$$
p(y = c \mid \mathbf{x}) \;=\;
\frac{\exp(\mathbf{w}_c \cdot \mathbf{x} + b_c)}
{\sum_{j=1}^{K}\exp(\mathbf{w}_j \cdot \mathbf{x} + b_j)}.
$$

$$
% caption: The softmax turns $K$ per-class scores $z_1, \ldots, z_K$ (each a
% separate weighted sum $\mathbf{w}_c\cdot\mathbf{x} + b_c$) into a probability
% distribution over the classes: exponentiate each score, then normalize by their
% sum so the outputs are positive and total $1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  fbox/.style={draw, minimum width=9mm, minimum height=7mm, font=\scriptsize},
  pbox/.style={draw=acc, minimum width=9mm, minimum height=7mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % input features (left)
  \node[fbox] (x) at (0,0) {x};
  % score nodes
  \node[fbox] (z1) at (2.6,1.7)  {z1};
  \node[fbox] (z2) at (2.6,0.6)  {z2};
  \node[fbox] (z3) at (2.6,-0.5) {z3};
  \node[black, font=\scriptsize] at (2.6,-1.5) {...};
  \node[fbox] (zk) at (2.6,-2.4) {zK};
  % edges input -> scores, labeled with separate weight vectors
  \draw[->, acc] (x) -- (z1);
  \draw[->, acc] (x) -- (z2);
  \draw[->, acc] (x) -- (z3);
  \draw[->, acc] (x) -- (zk);
  \node[acc, font=\scriptsize, anchor=south] at (1.3,1.15) {w1, b1};
  \node[black, font=\scriptsize, anchor=east] at (1.15,-1.75) {wK, bK};
  % softmax box
  \node[fbox, minimum height=32mm, minimum width=13mm] (sm) at (5.0,-0.35) {softmax};
  \draw[->, black] (z1) -- (sm.west |- z1);
  \draw[->, black] (z2) -- (sm.west |- z2);
  \draw[->, black] (z3) -- (sm.west |- z3);
  \draw[->, black] (zk) -- (sm.west |- zk);
  % probability outputs
  \node[pbox] (p1) at (7.4,1.7)  {p1};
  \node[pbox] (p2) at (7.4,0.6)  {p2};
  \node[pbox] (p3) at (7.4,-0.5) {p3};
  \node[black, font=\scriptsize] at (7.4,-1.5) {...};
  \node[pbox] (pk) at (7.4,-2.4) {pK};
  \draw[->, acc] (sm.east |- p1) -- (p1);
  \draw[->, acc] (sm.east |- p2) -- (p2);
  \draw[->, acc] (sm.east |- p3) -- (p3);
  \draw[->, acc] (sm.east |- pk) -- (pk);
  \node[acc, font=\scriptsize, anchor=west] at (7.9,-0.35) {sum = 1};
\end{tikzpicture}
$$

The loss generalizes just as cleanly. With $K$ classes the label $y$ is a **one-hot
vector** — a $1$ in the position of the true class $k$, zeros elsewhere. The
cross-entropy loss sums over the classes, but every term vanishes except the one for
the true class, so it reduces to the negative log probability of the correct class:

$$
L_{CE}(\hat{y}, y) \;=\; -\sum_{k=1}^{K} y_k \log \hat{y}_k
\;=\; -\log \hat{y}_k \quad (\text{$k$ the correct class}).
$$

This is the **negative log likelihood loss**, and its gradient with respect to the
weight $w_{k}$ for class $k$ echoes the binary case — the difference between the
true indicator for class $k$ and the model's probability for it, scaled by the input:

$$
\frac{\partial L_{CE}}{\partial w_{k, i}}
\;=\; -\big(\mathbb{1}\{y = k\} - p(y = k \mid \mathbf{x})\big)\,x_i.
$$

## Classification in the transformer era

Everything above learns weights over features a human specified — counts of positive
words, a `no`-present bit, the log document length. That design step was, for
decades, most of the applied work in text classification, and it is the step
modern models do away with. The output layer, though, does not change.

A transformer classifier keeps the softmax-over-logits head derived here and swaps
the hand-built feature vector $\mathbf{x}$ for a **learned representation** of the
text. The standard approach is to take a model pretrained on unlabeled text — BERT
(Devlin et al., 2019, NAACL) is the canonical one[^devlin-cls] — run the document
through it to get a contextual vector (conventionally the vector above a special
`[CLS]` token), and put a single logistic/softmax layer on top. Fine-tuning trains
that top layer, and usually the whole network, on the labeled classification data with
the same cross-entropy loss and the same gradient descent this lesson built. The
classifier at the top is still $\text{softmax}(\mathbf{W}\mathbf{h} + \mathbf{b})$;
what changed is that $\mathbf{h}$ is now learned from the text rather than assembled
from lexicon counts.

$$
% caption: A transformer text classifier. The pretrained encoder replaces the
% hand-built feature vector with a learned representation h of the document; the
% classification head on top is the same softmax-over-logits layer derived in this
% lesson, trained with the same cross-entropy loss.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (text) at (0,0) {document text};
  \node[box] (enc) at (0,1.3) {pretrained encoder};
  \node[box] (h) at (0,2.6) {representation h};
  \node[box, draw=acc, text=acc, thick] (head) at (0,3.9) {softmax head};
  \node[box] (out) at (0,5.2) {class probabilities};
  \draw[->, black, thick] (text) -- (enc);
  \draw[->, black, thick] (enc) -- (h);
  \draw[->, acc, thick] (h) -- (head);
  \draw[->, acc, thick] (head) -- (out);
  \node[acc, anchor=west, font=\scriptsize, align=left] at (2.2,3.9)
    {same softmax + \\ cross-entropy \\ as this lesson};
\end{tikzpicture}
$$

Two consequences follow. First, the discriminative-versus-
generative distinction that opened the lesson still applies: a fine-tuned encoder
with a softmax head is still a discriminative model of $P(c \mid d)$, now with a
learned rather than designed feature map. Second, the very largest models can classify
with _no_ fine-tuning at all, by prompting — describe the labels in words and read off
the predicted class from the model's next-token distribution (Brown et al., 2020,
NeurIPS, showed this few-shot behavior).[^brown-cls] That removes even the labeled
training set for the top layer, but when labeled data _is_ available, a fine-tuned
encoder with the classification head derived here remains the accurate, cheap choice
for a fixed task. Logistic regression remains in use as the last layer of these
models.

## The bridge to neural networks

Look again at the two-class model: it takes an input vector, forms one weighted sum
$\mathbf{w}\cdot\mathbf{x} + b$, and passes it through a nonlinearity $\sigma$. That
is precisely a **single artificial neuron** — one unit, one activation. Logistic
regression _is_ a one-layer neural network, and the multinomial version, with its
softmax over $K$ scores, is the output layer of a classification network.
Everything assembled here reappears at scale: the softmax and cross-entropy loss are
the standard output and objective of the classifiers in the
[deep-learning course](/deep-learning/neural-networks/loss-functions-and-output-units),
and the same gradient-descent machinery trains them.

Stack more layers of these units, each learning its own features from the layer
below instead of relying on features a human designed, and logistic regression grows
into a [neural language model](/natural-language-processing/semantics/neural-language-models).
The pieces do not change — a weighted sum, a nonlinearity, a cross-entropy loss, a
gradient step — only their number.

[^jm-gendisc]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 5 — Logistic Regression: naive Bayes as a generative model using the likelihood $P(d \mid c)$ and a prior, versus logistic regression as a discriminative model computing $P(c \mid d)$ directly.
[^jm-choose]: **Jurafsky & Martin**, §5.1 — Choosing a classifier: logistic regression's robustness to correlated features against naive Bayes's conditional-independence assumption, and where naive Bayes still wins (small or short data).
[^jm-components]: **Jurafsky & Martin**, Ch. 5 — Components of a probabilistic machine learning classifier: feature representation, a sigmoid/softmax classifier, the cross-entropy objective, and stochastic gradient descent, with training and test phases.
[^jm-sigmoid]: **Jurafsky & Martin**, §5.1 — Classification: the sigmoid: the weighted sum $z = \mathbf{w}\cdot\mathbf{x} + b$ passed through $\sigma(z) = 1/(1 + e^{-z})$ to yield $P(y{=}1\mid\mathbf{x})$, and the property $1 - \sigma(x) = \sigma(-x)$.
[^jm-features]: **Jurafsky & Martin**, §5.1.1 — Example: sentiment classification: the six hand-designed features, learned weights and worked $\sigma(0.833) = 0.70$ computation, feature interactions and feature templates.
[^jm-loss]: **Jurafsky & Martin**, §5.3 — The cross-entropy loss function: derivation from conditional maximum likelihood and the Bernoulli $p(y\mid\mathbf{x}) = \hat{y}^{y}(1-\hat{y})^{1-y}$, giving $L_{CE} = -[y\log\hat{y} + (1-y)\log(1-\hat{y})]$.
[^jm-gd]: **Jurafsky & Martin**, §5.4 — Gradient descent: minimizing the loss by moving against its slope, the convexity of the logistic loss, and the learning rate $\eta$ as step size.
[^jm-grad]: **Jurafsky & Martin**, §5.4.1 — The gradient for logistic regression: the per-weight partial derivative $\partial L_{CE}/\partial w_j = [\sigma(\mathbf{w}\cdot\mathbf{x}+b) - y]\,x_j$, the prediction error times the feature value.
[^jm-sgd]: **Jurafsky & Martin**, §5.4.2–5.4.4 — The stochastic gradient descent algorithm, the worked single-step example ($\theta^1 = [.15, .1, .05]$), and minibatch training.
[^jm-reg]: **Jurafsky & Martin**, §5.5 — Regularization: overfitting from features that accidentally correlate with the class, the penalty term $R(\theta)$, and L2 (ridge) versus L1 (lasso) with their Bayesian prior interpretations.
[^jm-softmax]: **Jurafsky & Martin**, §5.6 — Multinomial logistic regression: the softmax over $K$ classes, per-class weight vectors, the one-hot cross-entropy loss as negative log likelihood, and its gradient.
[^devlin-cls]: **J. Devlin, M.-W. Chang, K. Lee, K. Toutanova**, "BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding," _Proceedings of NAACL-HLT_, 2019 — fine-tuning a pretrained transformer for classification by adding a single output layer over the `[CLS]` representation and training with cross-entropy, which set state-of-the-art results across the GLUE classification suite.
[^brown-cls]: **T. Brown, B. Mann, N. Ryder, et al.**, "Language Models are Few-Shot Learners," _Advances in Neural Information Processing Systems_ (NeurIPS) 33, 2020 — classifying by prompting a large autoregressive language model with a task description and a few labeled examples, reading the predicted class from the next-token distribution with no gradient update.