06_Regression_and_Logistic_Models

Module 5 — Linear Regression, Logistic Regression, Softmax

Sources: Lec 10 — Linear Regression; Lec 11 — Logistic Regression. · Prev: Module 4 · Next: Module 6 — SVM · Index: 00_INDEX_and_Coverage

Python helpers — run once, the checks below reuse them

import numpy as np
sigmoid = lambda z: 1 / (1 + np.exp(-z))
def softmax(z):
    z = np.asarray(z, float); e = np.exp(z - z.max())      # subtract the max: overflow-safe
    return e / e.sum()
def add_ones(x):                                           # build the design matrix Z
    return np.c_[np.ones(len(x)), x]

---

C26. Linear Regression and Least Squares

Intuition

Draw the straight line (or plane) that passes as close as possible to the data, where “close” means the sum of squared vertical gaps is smallest. “Linear” refers to the parameters, not necessarily to the inputs: $x_2=x_1^2$ is allowed.

  y
  |            ●        ← each vertical gap e_i = y_i − ŷ_i is a residual
  |         ┆ ╱
  |      ● ─┆╱─ ŷ = β0 + β1 x   (line minimises Σ e_i²)
  |     ╱┆
  |   ╱ ●
  +----------------→ x

Formal definition

Model: $Y={\beta }_0+{\beta }_{1}X+ϵ$ (one regressor), or for $\vec{X}\in {\mathbb{R}}^m$: $f(\vec{X})={\beta }_0+{\sum }_{j=1}^m{x}_j{\beta }_j.$ Given $({\vec{X}}_i,Y_i)$, $i=\mathrm{1..}n$, the sum of squared errors $E(\vec{\beta })={\sum }_{i=1}^n(Y_i-{\beta }_0-{\sum }_j{x}_{ij}{\beta }_j{)}^2=(\vec{Y}-Z\vec{\beta }{)}^T(\vec{Y}-Z\vec{\beta }),$ where $Z$ is the $n\times (m+1)$ matrix with rows $[1,x_{i1},\dots ,x_{im}]$ and $\vec{\beta }=[{\beta }_0,\dots ,{\beta }_m{]}^T$.

Derivation of the normal equations

Expand: $E={\vec{Y}}^T\vec{Y}-2{\vec{\beta }}^T{Z}^T\vec{Y}+{\vec{\beta }}^T{Z}^{T}Z\vec{\beta }$. Using $\frac{\partial }{\partial \vec{\beta }}({\vec{\beta }}^T\vec{a})=\vec{a}$ and $\frac{\partial }{\partial \vec{\beta }}({\vec{\beta }}^{T}A\vec{\beta })=2A\vec{\beta }$ for symmetric $A$: $\frac{\partial E}{\partial \vec{\beta }}=-2Z^T\vec{Y}+2Z^{T}Z\vec{\beta }=-2Z^T(\vec{Y}-Z\vec{\beta }).$ Set to zero: $Z^{T}Z\vec{\beta }=Z^T\vec{Y}$, so (when $Z^{T}Z$ is invertible) $\boxed{\vec{\beta }=(Z^{T}Z{)}^{-1}{Z}^T\vec{Y}.}$ The Hessian is $2Z^{T}Z⪰0$, so the stationary point is a minimum (unique if $Z$ has full column rank).

Key insights

• Residuals are orthogonal to every column of $Z$: $Z^T(\vec{Y}-Z\hat{\vec{\beta }})=0$. In particular, residuals sum to zero (the intercept column).
• If columns of $Z$ are linearly dependent (duplicate / collinear features, or $n<m+1$), $Z^{T}Z$ is singular and the solution is not unique.
• Basis expansions (polynomials, interactions) keep the model linear in $\vec{\beta }$.

Worked examples

Example 1 — Very Easy · Advertising and sales

• Problem: A shop spends $x=1,2,3$ (₹ lakh) on ads and sees sales $y=2,3,5$ (₹ lakh). Fit $y={\beta }_0+{\beta }_{1}x$.
• Asked: ${\beta }_0,{\beta }_1$.
• Concept: Normal equations.
• Approach: Build $Z^{T}Z$ and $Z^T\vec{Y}$.
• Solution: $Z=\left(\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right)$, $\vec{Y}=(2,3,5{)}^T$. $Z^{T}Z=\left(\begin{array}{cc}3& 6\\ 6& 14\end{array}\right)$, $Z^T\vec{Y}=\left(\begin{array}{c}10\\ 23\end{array}\right)$. $\det =6$, inverse $=\frac{1}{6}\left(\begin{array}{cc}14& -6\\ -6& 3\end{array}\right)$. $\vec{\beta }=\frac{1}{6}\left(\begin{array}{c}140-138\\ -60+69\end{array}\right)=\left(\begin{array}{c}0.3333\\ 1.5\end{array}\right)$.
• Final answer: $y=0.333+1.5x$.

Python check

x = np.array([1, 2, 3.]); y = np.array([2, 3, 5.]); Z = add_ones(x)
beta = np.linalg.solve(Z.T @ Z, Z.T @ y); print(beta)       # [0.3333  1.5]

Key lesson

The slope equals $S_{xy}/S_{xx}=3/2$: every extra ₹ 1 lakh of ads adds ₹ 1.5 lakh of sales.

Example 2 — Easy · Residuals and SSE

• Problem: For Example 1, compute fitted values, residuals and SSE.
• Asked: ${\hat{y}}_i,e_i,E$.
• Concept: Residuals.
• Approach: Plug in.
• Solution: $\hat{y}=(1.8333,3.3333,4.8333)$. $e=y-\hat{y}=(0.1667,-0.3333,0.1667)$. $E=0.02778+0.11111+0.02778=0.16667$.
• Final answer: $E=1/6\approx 0.167$.

Key lesson

Residuals sum to $0$.

Example 3 — Moderate · Orthogonality of residuals

• Problem: Verify the orthogonality conditions $Z^T\vec{e}=0$ for Example 2 and explain what they say.
• Asked: Check.
• Concept: Normal equations as orthogonality.
• Approach: Dot products.
• Solution: Column of ones: $0.1667-0.3333+0.1667=0$ ✓. Column $x$: $1(0.1667)+2(-0.3333)+3(0.1667)=0$ ✓.
• Final answer: $Z^T\vec{e}=\vec{0}$.

Python check

e = y - Z @ beta; print(Z.T @ e)                           # ≈ [0, 0]

Key lesson

The fitted vector $Z\hat{\beta }$ is the orthogonal projection of $\vec{Y}$ onto the column space of $Z$.

Example 4 — Hard · Line vs quadratic

• Problem: A sensor’s error depends on the distance from its calibration point $x=1$. Data $(0,1),(1,0),(2,1),(3,4)$. Compare the best straight line with the quadratic $y={\beta }_0+{\beta }_{1}x+{\beta }_2{x}^2$.
• Asked: SSE of both.
• Concept: Basis expansion (linear in parameters).
• Approach: Line via $S_{xy}/S_{xx}$; quadratic by inspection and normal equations.
• Solution: Line: $\bar{x}=1.5$, $\bar{y}=1.5$. $S_{xy}=0.75+0.75-0.25+3.75=5$; $S_{xx}=5$. ${\beta }_1=1$, ${\beta }_0=0$. $\hat{y}=x$: residuals $1,-1,-1,1$, SSE $=4$. Quadratic: try $y=(x-1{)}^2=1-2x+x^2$: values $1,0,1,4$ ✓ exact. This is a feasible point with $E=0$ and $E\ge 0$, so it is the minimiser: $\vec{\beta }=(1,-2,1)$, SSE $=0$.
• Final answer: Line SSE $=4$; quadratic SSE $=0$ with $\vec{\beta }=(1,-2,1)$.

Python check

x = np.array([0, 1, 2, 3.]); y = np.array([1, 0, 1, 4.])
for deg in (1, 2):
    Z = np.vander(x, deg + 1, increasing=True)               # columns 1, x, x² ...
    b = np.linalg.lstsq(Z, y, rcond=None)[0]; print(deg, np.round(b, 4), round(((y - Z @ b)**2).sum(), 4))
# 1 [0. 1.] 4.0     2 [ 1. -2.  1.] 0.0

Key lesson

Adding $x^2$ as a feature keeps the problem linear and can remove the model’s bias.

Example 5 — Very Hard · Collinear features

• Problem: Features $x_1=(1,2,3)$ and $x_2=2x_1=(2,4,6)$ with intercept. (a) Show $Z^{T}Z$ is singular. (b) Describe all least-squares solutions. (c) Why are predictions still unique?
• Asked: Singularity and solution set.
• Concept: Collinearity.
• Approach: Dependent columns.
• Solution: (a) $Z=\left(\begin{array}{ccc}1& 1& 2\\ 1& 2& 4\\ 1& 3& 6\end{array}\right)$; col${}_3=2$col${}_2$. $Z^{T}Z=\left(\begin{array}{ccc}3& 6& 12\\ 6& 14& 28\\ 12& 28& 56\end{array}\right)$ with row${}_3=2$row${}_2$ ⇒ $\det =0$. (b) The model is ${\beta }_0+({\beta }_1+2{\beta }_2)x_1$. Only ${\beta }_0$ and $s={\beta }_1+2{\beta }_2$ are determined (from Example 1: ${\beta }_0=\frac{1}{3}$, $s=1.5$). Solutions: $(\frac{1}{3},1.5-2{\beta }_2,{\beta }_2)$ for any ${\beta }_2$. (c) All give the same $Z\vec{\beta }$, hence the same fitted values and SSE $=1/6$.
• Final answer: Infinite family; predictions identical.

Python check

Z = np.c_[np.ones(3), [1, 2, 3], [2, 4, 6]]
print(np.linalg.det(Z.T @ Z), np.linalg.matrix_rank(Z))     # 0.0  2
print(np.linalg.pinv(Z) @ [2, 3, 5])                        # [0.3333 0.3 0.6]  ← the minimum-norm member

Key lesson

Collinear features make coefficients meaningless though predictions are fine. Cures: drop a feature, regularise, or use the pseudo-inverse (which picks the minimum-norm solution ${\beta }_2=0.6$).

Common mistakes

• Forgetting the column of ones.
• Inverting $Z^{T}Z$ when $n\le m$.

Exam traps

• “Linear regression” = linear in the parameters.
• The normal equations require $Z^{T}Z$ invertible.

Connections: Logistic regression (C27), PCA reconstruction error (C45), perceptron’s squared-error variant (C49 / C51).

Mastery checklist

• Derive $\vec{\beta }=(Z^{T}Z{)}^{-1}{Z}^T\vec{Y}$.
• Fit a line by hand.
• Explain collinearity.

---

C27. Binomial Logistic Regression

Intuition

Regression on a 0/1 target produces nonsense (predictions outside $[0,1]$). Instead model the probability of class 1 with an S-shaped function of a linear score. The score is a distance-like quantity from a hyperplane; probability $0.5$ sits exactly on it.

 σ(z)
 1.0 |                 ________
     |              _/
 0.5 |- - - - - - -●        ← z = 0: on the boundary, p = 0.5
     |          __/
 0.0 |________/
     +--------------------→ z = β0 + βᵀX

Formal definition

$p(y=1|\vec{X};\vec{\beta })=\frac{e^{{\beta }_0+{\vec{\beta }}^T\vec{X}}}{1+e^{{\beta }_0+{\vec{\beta }}^T\vec{X}}}=\sigma (z),z={\beta }_0+{\vec{\beta }}^T\vec{X},p(y=0|\vec{X})=\frac{1}{1+e^z}.$ Decision: class 1 iff $p(y=1|\vec{X})\ge 0.5$ $⟺z\ge 0$. The decision boundary ${\beta }_0+{\vec{\beta }}^T\vec{X}=0$ is a hyperplane.

Derivation: likelihood → cross-entropy → gradient

Labels $y_i\in \{0,1\}$, $p_i=p({\vec{X}}_i;\vec{\beta })$. Bernoulli likelihood: $p(y_i|{\vec{X}}_i)=p_i^{y_i}(1-p_i{)}^{1-y_i}$. Log-likelihood per sample: $y_i\ln p_i+(1-y_i)\ln (1-p_i)$. Loss (negative, = cross-entropy): $L(\vec{\beta })=-{\sum }_{i=1}^n[y_i\ln p_i+(1-y_i)\ln (1-p_i)].$ Substitute $p_i=\frac{e^{z_i}}{1+e^{z_i}}$: $\ln p_i=z_i-\ln (1+e^{z_i})$ and $\ln (1-p_i)=-\ln (1+e^{z_i})$. Then $y_i\ln p_i+(1-y_i)\ln (1-p_i)=y_i{z}_i-\ln (1+e^{z_i}),$ $\boxed{L(\vec{\beta })=-\sum _i[y_i({\beta }_0+{\vec{\beta }}^T{\vec{X}}_i)-\ln (1+e^{{\beta }_0+{\vec{\beta }}^T{\vec{X}}_i})].}$ Differentiate: $\frac{\partial }{\partial {\beta }_j}\ln (1+e^{z_i})=\frac{e^{z_i}}{1+e^{z_i}}{x}_{ij}=p_i{x}_{ij}$ (with $x_{i0}=1$). Hence $\boxed{\frac{\partial L}{\partial {\beta }_j}=\sum _{i=1}^n{x}_{ij}(p_i-y_i).}$ No closed-form solution; solve by gradient descent or Newton’s method. $L$ is convex in $\vec{\beta }$ (its Hessian is $\sum p_i(1-p_i){\vec{x}}_i{\vec{x}}_i^T⪰0$), so there is no spurious local minimum.

Key insights

• Sigmoid derivative: ${\sigma }^{\prime }(z)=\sigma (z)(1-\sigma (z))$.
• The boundary is linear because it is $z=0$.
• (Lecture slip: “the loss is linear in $\vec{\beta }$” is inaccurate — the boundary is linear; the loss is convex, not linear.)

Worked examples

Example 1 — Very Easy · The sigmoid

• Problem: $\sigma (z)$ for $z=0,2,-2$.
• Asked: Three probabilities.
• Concept: Sigmoid.
• Approach: $1/(1+e^{-z})$.
• Solution: $\sigma (0)=0.5$; $\sigma (2)=1/(1+0.1353)=0.8808$; $\sigma (-2)=1/(1+7.389)=0.1192$.
• Final answer: $0.5,0.881,0.119$.

Key lesson

$\sigma (-z)=1-\sigma (z)$.

Example 2 — Easy · Pass probability vs study hours

• Problem: A model for passing an exam uses $z=-3+x$ ($x$ = hours studied). Find the boundary and $p(\text{pass})$ at $x=4$ and $x=2$.
• Asked: Boundary and probabilities.
• Concept: $z=0$ boundary.
• Approach: Solve $-3+x=0$.
• Solution: Boundary $x=3$ hours. $x=4$: $z=1$ ⇒ $0.7311$. $x=2$: $z=-1$ ⇒ $0.2689$.
• Final answer: Boundary $x=3$; probabilities $0.731$ and $0.269$.

Key lesson

Distance from the boundary controls confidence.

Example 3 — Moderate · Cross-entropy

• Problem: Predicted probabilities of class 1 are $0.9,0.2,0.6$ for labels $1,0,1$. Compute the total and average cross-entropy.
• Asked: $L$.
• Concept: Cross-entropy.
• Approach: $-\ln p$ for the true class.
• Solution: Sample 1: $-\ln 0.9=0.1054$. Sample 2 ($y=0$): $-\ln 0.8=0.2231$. Sample 3: $-\ln 0.6=0.5108$. Total $=0.8393$; mean $=0.2798$.
• Final answer: $L=0.839$ (mean $0.280$).

Python check

p = np.array([.9, .2, .6]); y = np.array([1, 0, 1])
l = -(y * np.log(p) + (1 - y) * np.log(1 - p)); print(l, l.sum(), l.mean())   # 0.839  0.280

Key lesson

The loss only looks at the probability assigned to the true class.

Example 4 — Hard · One gradient step on pass/fail data

• Problem: Hours studied vs pass: $(0,0),(1,0),(2,1),(3,1)$. Start at $\vec{\beta }=(0,0)$. Do one gradient-descent step with $\eta =0.1$ and compare the loss before and after.
• Asked: New $\vec{\beta }$ and loss.
• Concept: Gradient formula.
• Approach: $p_i=0.5$ at the start.
• Solution: $p_i=0.5$ for all. $\partial L/\partial {\beta }_0=\sum (p_i-y_i)=0.5+0.5-0.5-0.5=0$. $\partial L/\partial {\beta }_1=\sum x_i(p_i-y_i)=0+0.5-1-1.5=-2$. Update: $\vec{\beta }=(0,0)-0.1(0,-2)=(0,0.2)$. Loss before: $4\ln 2=2.7726$. After: $p=\sigma (0.2x)=(0.5,0.5498,0.5987,0.6457)$; $L=0.6931+0.7981+0.5130+0.4373=2.4417$ (decrease of $0.331$).
• Final answer: $\vec{\beta }=(0,0.2)$; loss $2.7726\to 2.4417$.

Python check

X = np.array([0, 1, 2, 3.]); Y = np.array([0, 0, 1, 1.])
L = lambda b0, b1: -(Y*np.log(sigmoid(b0 + b1*X)) + (1-Y)*np.log(1 - sigmoid(b0 + b1*X))).sum()
p = sigmoid(0 * X); grad = np.array([(p - Y).sum(), (X * (p - Y)).sum()]); print(grad)   # [ 0. -2.]
b = -0.1 * grad; print(b, L(0, 0), L(*b))                  # [0. 0.2]  2.7726  2.4418

Key lesson

A positive slope emerges because larger $x$ go with $y=1$.

Example 5 — Very Hard · Perfectly separable data

• Problem: Two points $(x,y)=(-1,0),(1,1)$, model $z=bx$ (no intercept). Show the loss has no minimiser and explain.
• Asked: Behaviour of $L(b)$.
• Concept: Separable data ⇒ MLE does not exist.
• Approach: Write the loss.
• Solution: At $x=1,y=1$: $-\ln \sigma (b)=\ln (1+e^{-b})$. At $x=-1,y=0$: $-\ln (1-\sigma (-b))=-\ln \sigma (b)=\ln (1+e^{-b})$. $L(b)=2\ln (1+e^{-b})$: $b=1$: $0.6265$; $b=3$: $0.0972$; $b=5$: $0.0134$; $L\to 0$ as $b\to \infty$ but $L>0$ for every finite $b$.
• Final answer: The infimum $0$ is never attained: $\hat{b}=+\infty$.

Python check

print([round(2*np.log(1 + np.exp(-b)), 4) for b in (1, 3, 5, 10)])   # 0.6265  0.0972  0.0134  0.0001

Key lesson

On linearly separable data, unregularised logistic regression pushes the weights to infinity; use regularisation or early stopping.

Common mistakes

• Using labels $\{-1,+1\}$ with the $\{0,1\}$ formulas.
• Sign errors in the gradient ($p_i-y_i$).

Exam traps

• Threshold $0.5$ ⇔ $z=0$.
• The model is a classifier despite “regression” in its name.

Connections: C26, C28 (softmax), C29, perceptron (C49), SVM (C30).

Mastery checklist

• Derive cross-entropy from the Bernoulli likelihood.
• Derive $\partial L/\partial {\beta }_j$.
• Explain why the boundary is linear.

---

C28. Multinomial Logistic Regression and Softmax

Intuition

With $k$ classes keep one score per class and turn the scores into probabilities that sum to 1 by exponentiating and normalising.

Formal definition

$\text{softmax}(\vec{z}{)}_r=\frac{e^{z_r}}{{\sum }_{j=1}^k{e}^{z_j}},{\hat{y}}_r=p(y_r|\vec{X})=\frac{e^{{\beta }_{r0}+{\vec{\beta }}_r^T\vec{X}}}{{\sum }_{j=1}^k{e}^{{\beta }_{j0}+{\vec{\beta }}_j^T\vec{X}}}.$ Labels are one-hot vectors ${\vec{Y}}_i=[0,\dots ,1,\dots ,0]$. Per-sample loss with true class $c$: $L_i=-{\sum }_j{y}_j\ln {\hat{y}}_j=-\ln {\hat{y}}_c=-({\beta }_{c0}+{\vec{\beta }}_c^T{\vec{X}}_i)+\ln {\sum }_j{e}^{{\beta }_{j0}+{\vec{\beta }}_j^T{\vec{X}}_i}.$ The parameters form a $k\times (m+1)$ matrix (the lecture writes $k\times m$ without the bias).

Derivation of the gradient w.r.t. scores

$\frac{\partial {\hat{y}}_j}{\partial z_r}={\hat{y}}_j({\delta }_{jr}-{\hat{y}}_r)$. Then $\frac{\partial L}{\partial z_r}=-{\sum }_j{y}_j\frac{1}{{\hat{y}}_j}{\hat{y}}_j({\delta }_{jr}-{\hat{y}}_r)=-y_r+{\hat{y}}_r{\sum }_j{y}_j={\hat{y}}_r-y_r$. ∎ (Same shape as the binary gradient $p-y$.)

Key insights

• Binary logistic regression = softmax with 2 classes (Example 3).
• Softmax is shift-invariant: $\text{softmax}(\vec{z}+c\vec{1})=\text{softmax}(\vec{z})$.
• Predicted class = $\arg {\max }_r{\hat{y}}_r$ (equivalently $\arg \max$ of the scores).

Worked examples

Example 1 — Very Easy · Softmax of three scores

• Problem: Softmax of $\vec{z}=(1,2,3)$.
• Asked: Probabilities.
• Concept: Softmax.
• Approach: Exponentiate, normalise.
• Solution: $e^1=2.718,e^2=7.389,e^3=20.086$; sum $=30.193$. Probabilities: $0.0900,0.2447,0.6652$.
• Final answer: $(0.090,0.245,0.665)$.

Key lesson

Outputs lie in $(0,1)$ and sum to 1.

Example 2 — Easy · Cross-entropy

• Problem: The true class is the second. Cross-entropy for Example 1?
• Asked: $L$.
• Concept: $-\ln {\hat{y}}_c$.
• Approach: Pick the true class.
• Solution: $-\ln 0.2447=1.4076$.
• Final answer: $1.408$.

Key lesson

Other classes’ probabilities matter only through the normalisation.

Example 3 — Moderate · Softmax contains the sigmoid

• Problem: Show that softmax over $(0,z)$ equals the binary logistic probabilities.
• Asked: Equivalence.
• Concept: Softmax generalises the sigmoid.
• Approach: Write ${\hat{y}}_2$.
• Solution: ${\hat{y}}_2=\frac{e^z}{e^0+e^z}=\frac{e^z}{1+e^z}=\sigma (z)$ and ${\hat{y}}_1=\frac{1}{1+e^z}$.
• Final answer: Identical to the binary formulas of C27.

Key lesson

Binary logistic is the $k=2$ case with one score set to $0$ (using shift invariance).

Example 4 — Hard · Overflow-safe softmax

• Problem: Scores $(1000,1001,1002)$. Direct $e^z$ overflows. Compute softmax stably.
• Asked: Probabilities.
• Concept: Shift invariance.
• Approach: Subtract the max.
• Solution: $\vec{z}-1002=(-2,-1,0)$. $e^{-2}=0.1353,e^{-1}=0.3679,e^0=1$; sum $=1.5032$. Probabilities: $0.0900,0.2447,0.6652$ — identical to Example 1 (the scores differ by the same offsets).
• Final answer: $(0.090,0.245,0.665)$.

Python check

print(softmax([1, 2, 3]), softmax([1000, 1001, 1002]))     # same: [0.09  0.2447  0.6652]
print(np.exp(1000))                                        # inf  (overflow warning without the shift)

Key lesson

Always subtract ${\max }_j{z}_j$ before exponentiating.

Example 5 — Very Hard · The gradient on the scores

• Problem: For Example 1 with the true class second, write $\partial L/\partial \vec{z}$ and verify it sums to zero. Then explain the gradient step’s effect on each score.
• Asked: Gradient vector and interpretation.
• Concept: $\hat{y}-y$.
• Approach: $\hat{\vec{y}}-\vec{y}$ with $\vec{y}=(0,1,0)$.
• Solution: $\partial L/\partial \vec{z}=(0.0900,0.2447-1,0.6652)=(0.090,-0.755,0.665)$. Sum $=0$ ✓ (both $\hat{y}$ and $y$ sum to 1). A descent step lowers $z_1,z_3$ (wrong classes, positive gradient) and raises $z_2$ (true class, negative gradient) — the push is proportional to the error.
• Final answer: Gradient $=(0.090,-0.755,0.665)$.

Python check

g = softmax([1, 2, 3]) - np.array([0, 1, 0]); print(g, g.sum())    # [ 0.09 -0.7553  0.6652]  0.0

Key lesson

The sum-to-zero property reflects shift invariance: there is one redundant degree of freedom among the scores.

Common mistakes

• Using the sigmoid for each class independently (probabilities then do not sum to 1).
• Forgetting the log-sum-exp stabilisation.

Exam traps

• One-hot encoding of labels.
• Loss $=-\ln$ of the probability of the correct class.

Connections: C27, C29, neural-network output layers (C53–C54).

Mastery checklist

• Compute softmax and its cross-entropy.
• Derive $\hat{y}-y$.
• Use the max-subtraction trick.

---

C29. Discriminative vs Generative Classifiers

Intuition

Generative (e.g. Naive Bayes, Gaussian discriminant analysis): learn what each class looks like, $p(\vec{X}|w)p(w)$, then invert with Bayes. Discriminative (e.g. logistic regression, SVM, perceptron): learn the boundary or $p(w|\vec{X})$ directly, without modelling $\vec{X}$. Lecture example: all dogs in training wear collars, no cat does. A discriminative model happily uses the collar; a generative model tries to learn what dogs and cats actually look like.

flowchart LR
    subgraph Generative
      A["learn p(X | w) and p(w)"] --> B["Bayes rule"] --> C["p(w | X)"]
    end
    subgraph Discriminative
      D["learn p(w | X) or the boundary directly"] --> E["p(w | X)"]
    end

Formal comparison

	Generative	Discriminative
Models	$p(\vec{X}\mid w),p(w)$	$p(w\mid \vec{X})$ or boundary
Predicts via	Bayes’ rule	direct
Can sample $\vec{X}$?	Yes	No
Examples	Naive Bayes, LDA	Logistic, SVM, perceptron

Mathematical bridge

For two Gaussian classes with a shared covariance, the generative posterior is a logistic function: $p(w_1|\vec{X})=\frac{p_1{f}_1}{p_1{f}_1+p_2{f}_2}=\frac{1}{1+e^{-g(\vec{X})}},g=\ln \frac{p_1{f}_1}{p_2{f}_2}={\vec{w}}^T\vec{X}+w_0$ with $\vec{w}={\Sigma }^{-1}({\vec{\mu }}_1-{\vec{\mu }}_2)$ (C18). So the two families coincide in form; they differ in how the parameters are fitted (joint likelihood vs conditional likelihood) and in robustness to model misspecification.

Worked examples

Example 1 — Very Easy · Label the algorithm

• Problem: Classify as generative or discriminative: Naive Bayes, logistic regression, SVM, perceptron, Gaussian discriminant analysis.
• Asked: Label each.
• Concept: Taxonomy.
• Approach: Does it model $p(\vec{X}|w)$?
• Solution: NB — generative; logistic — discriminative; SVM — discriminative; perceptron — discriminative; Gaussian discriminant analysis — generative.
• Final answer: As stated.

Key lesson

The lecture’s contrast: logistic regression vs Naive Bayes.

Example 2 — Easy · The dog without a collar

• Problem: In the dog / cat story a new dog without a collar arrives. What does a collar-based discriminative model say? What might a generative model say?
• Asked: Predictions and reason.
• Concept: Shortcut learning.
• Approach: Think about what each model learned.
• Solution: Discriminative: the only learned separator is “collar ⇒ dog”, so no collar ⇒ cat (wrong). Generative: it has modelled dog shape, ears, tail, etc.; $p(\text{image}|\text{dog})$ stays high ⇒ likely dog.
• Final answer: Discriminative errs; generative may be right.

Key lesson

Discriminative models exploit whatever separates the training classes, even spurious cues.

Example 3 — Moderate · Posterior from a generative model

• Problem: Two Gaussian classes $\Sigma =I$, ${\vec{\mu }}_1=(0,0)$, ${\vec{\mu }}_2=(2,2)$, equal priors. Compute $p(w_1|\vec{X})$ at $\vec{X}=(1,0)$.
• Asked: Posterior.
• Concept: The generative posterior is logistic.
• Approach: $g=-2x_1-2x_2+4$ (C18 Ex. 1).
• Solution: $g(1,0)=2$. $p=\sigma (2)=0.8808$.
• Final answer: $0.881$.

Python check

from scipy.stats import multivariate_normal as mvn
f1, f2 = mvn([0, 0], np.eye(2)), mvn([2, 2], np.eye(2))
print(f1.pdf([1, 0]) / (f1.pdf([1, 0]) + f2.pdf([1, 0])), sigmoid(2))   # both 0.8808

Key lesson

Gaussian generative model ⇒ logistic posterior.

Example 4 — Hard · Prove the logistic form

• Problem: Prove $p(w_1|\vec{X})=1/(1+e^{-g})$ with $g=\ln \frac{p_1{f}_1}{p_2{f}_2}$.
• Asked: Algebra.
• Concept: Bayes in log-odds form.
• Approach: Divide numerator and denominator by $p_1{f}_1$.
• Solution: $p(w_1|\vec{X})=\frac{p_1{f}_1}{p_1{f}_1+p_2{f}_2}=\frac{1}{1+\frac{p_2{f}_2}{p_1{f}_1}}=\frac{1}{1+e^{-g}}$. ∎ For equal-covariance Gaussians $g$ is the linear discriminant of C18.
• Final answer: As shown.

Key lesson

The log-odds of the posterior equal the discriminant function.

Example 5 — Very Hard · Duplicate feature: NB vs logistic

• Problem: A binary feature $f$ with $p(f|w_1)=0.6$, $p(f|w_2)=0.2$, equal priors, appears twice (duplicate column). Compare Naive Bayes (generative) and logistic regression (discriminative) posteriors for an instance with $f=1$.
• Asked: Two posteriors.
• Concept: Calibration under redundancy.
• Approach: Log-odds.
• Solution: Truth: $P(w_1|f=1)=\frac{0.6}{0.8}=0.75$, log-odds $\ln 3=1.0986$. NB: each copy adds $\ln 3$ ⇒ $2.1972$ ⇒ $\sigma (2.1972)=0.90$. Logistic regression fitted by maximum conditional likelihood: $z={\beta }_0+({\beta }_1+{\beta }_2)f$; the likelihood depends only on ${\beta }_1+{\beta }_2$ and is maximised at ${\beta }_1+{\beta }_2=1.0986$ ⇒ posterior $0.75$.
• Final answer: NB $0.90$; logistic $0.75$ (correct).

Python check

print(sigmoid(np.log(3)), sigmoid(2 * np.log(3)))         # 0.75 (logistic)   0.90 (NB, double-counted)

Key lesson

Discriminative training adjusts weights to the joint evidence and is robust to correlated features; NB double-counts. (Both still pick $w_1$.)

Common mistakes

• Believing generative models are always more accurate.
• Believing discriminative models cannot give probabilities.

Exam traps

• “Logistic regression is discriminative; Naive Bayes is generative” (lecture).
• A generative classifier can create synthetic data; a discriminative one cannot.

Connections: C14, C18–C22, C27.

Mastery checklist

• Give the definition and an example of each.
• Derive the logistic form of the Gaussian posterior.
• Explain the collar example.