3. Linear Classifiers and Support Vector Machines

Previous: empirical risk and generalization · Next: kernels, Gaussian processes, and conformal prediction

Source: Lectures 13-17, pp. 47-63.

The previous part explained how controlling a class can support generalization. We now choose concrete classifiers. LDA and logistic regression can both produce linear boundaries, but they estimate different quantities. SVMs choose boundaries through their geometry.

1. Geometry of a linear classifier

Use binary labels $Y\in \{-1,1\}$ and a score $s(x)=w^{\top }x+b$, with $w\ne 0$. Predict $+1$ for $s(x)\ge 0$ and $-1$ otherwise. The boundary is

$$H_{w,b}=\{x:w^{\top }x+b=0\}.$$

If $x_0,x\in H_{w,b}$, then

$$w^{\top }(x-x_0)=(-b)-(-b)=0.$$

Thus $w$ is perpendicular to the hyperplane. Projecting $x-x_0$ onto its unit normal gives

$$\mathrm{dist}(x,H_{w,b})=\left|⟨x-x_0,\frac{w}{\Vert w\Vert }⟩\right|=\frac{|w^{\top }x+b|}{\Vert w\Vert }.$$

The two half-spaces correspond to positive and negative scores. Positive rescaling does not change the boundary or classifier:

$$H_{cw,cb}=H_{w,b}(c>0).$$

We will use this scaling freedom to turn geometric margin maximization into a tractable optimization problem.

2. QDA and LDA from the Bayes rule

Lectures 13-14; pp. 48-51.

For classes $j=1,\dots ,K$, assume

$$\mathrm{Pr}(Y=j)={\pi }_j,X\mid Y=j\sim \mathcal{N}({\mu }_j,{\Sigma }_j),$$

with positive priors and positive-definite covariances. Bayes’ rule gives

$$f_B(x)=\arg \underset{j}{\max }\mathrm{Pr}(Y=j\mid X=x)=\arg \underset{j}{\max }{\pi }_j{p}_j(x).$$

The density is

$$p_j(x)=\frac{\exp [-\frac{1}{2}(x-{\mu }_j{)}^{\top }{\Sigma }_j^{-1}(x-{\mu }_j)]}{(2\pi {)}^{d/2}\det ({\Sigma }_j{)}^{1/2}}.$$

Taking logarithms preserves the ordering. Dropping the common term $-\frac{d}{2}\log (2\pi )$, choose the largest score

$$d_j(x)=\log {\pi }_j-\frac{1}{2}\log \det {\Sigma }_j-\frac{1}{2}(x-{\mu }_j{)}^{\top }{\Sigma }_j^{-1}(x-{\mu }_j).$$

QDA: separate covariances

Expand the quadratic form:

$$(x-{\mu }_j{)}^{\top }{\Sigma }_j^{-1}(x-{\mu }_j)=x^{\top }{\Sigma }_j^{-1}x-2x^{\top }{\Sigma }_j^{-1}{\mu }_j+{\mu }_j^{\top }{\Sigma }_j^{-1}{\mu }_j.$$

When ${\Sigma }_j$ depends on the class, the quadratic term remains in $d_j-d_l$. The pairwise boundaries $d_j(x)=d_l(x)$ are generally quadratic: quadratic discriminant analysis.

With $n_j=\#\{i:Y_i=j\}$, estimate

$${\hat{\pi }}_j=\frac{n_j}{n},{\hat{\mu }}_j=\frac{1}{n_j}\sum _{i:Y_i=j}{X}_i,$$ $${\hat{\Sigma }}_j=\frac{1}{n_j}\sum _{i:Y_i=j}(X_i-{\hat{\mu }}_j)(X_i-{\hat{\mu }}_j{)}^{\top }.$$

These are the maximum-likelihood estimates under the model. Substitute them into $d_j$ to obtain the fitted classifier. The displayed inverse formulas require nonsingular estimates.

LDA: a shared covariance

Suppose every class has covariance $\Sigma$. Then

$$\begin{array}{rl}{d}_j(x)& =\underset{\text{common to all classes}}{\underbrace{-\frac{1}{2}\log \det \Sigma -\frac{1}{2}{x}^{\top }{\Sigma }^{-1}x}}\\ & +x^{\top }{\Sigma }^{-1}{\mu }_j-\frac{1}{2}{\mu }_j^{\top }{\Sigma }^{-1}{\mu }_j+\log {\pi }_j.\end{array}$$

Common terms do not affect the maximum. Therefore compare the affine scores

$${\ell }_j(x)=x^{\top }{\Sigma }^{-1}{\mu }_j-\frac{1}{2}{\mu }_j^{\top }{\Sigma }^{-1}{\mu }_j+\log {\pi }_j.$$

Their pairwise differences are linear in $x$: linear discriminant analysis. Estimate the common covariance by pooling within-class covariances, for example the MLE

$$\hat{\Sigma }=\frac{1}{n}\sum _j\sum _{i:Y_i=j}(X_i-{\hat{\mu }}_j)(X_i-{\hat{\mu }}_j{)}^{\top }.$$

The Gaussian model explains the rule’s derivation. The resulting plug-in classifier can still be used when the true distribution is not Gaussian, but then its Bayes optimality is not guaranteed.

3. Logistic regression from conditional probabilities

Lecture 14; p. 52.

Logistic regression models $Y\mid X$ directly. It does not specify a Gaussian model for $X\mid Y$.

For $K$ classes, set $s_j(x)={\beta }_j^{\top }x+b_j$ for $j<K$ and use the reference score $s_K(x)=0$. Define

$$p_j(x)=\frac{e^{s_j(x)}}{1+{\sum }_{l=1}^{K-1}{e}^{s_l(x)}}(j<K),p_K(x)=\frac{1}{1+{\sum }_{l=1}^{K-1}{e}^{s_l(x)}}.$$

The shared denominator cancels in an argmax. Exponentiation preserves order, so

$$\arg \underset{j}{\max }{p}_j(x)=\arg \underset{j}{\max }{s}_j(x).$$

Thus pairwise decision boundaries are affine despite the nonlinear probabilities.

Fit by maximum likelihood

For independent labeled observations, maximize the conditional likelihood ${\prod }_i{p}_{Y_i}(X_i)$. Taking logs and changing the sign gives

$$\underset{\{{\beta }_j,b_j\}}{\min }\sum _i\left[\log \left(1+\sum _{l<K}{e}^{s_l(X_i)}\right)-s_{Y_i}(X_i)\right],$$

where $s_K=0$. This is empirical minimization of negative log-likelihood.

For binary labels $Y_i\in \{-1,1\}$ and one score $s(x)$,

$$\mathrm{Pr}(Y=y\mid X=x)=\frac{1}{1+e^{-ys(x)}},$$

so the objective becomes

$$\underset{w,b}{\min }\frac{1}{n}\sum _i\log (1+e^{-Y_i(w^{\top }{X}_i+b)}).$$

A large positive signed score $Y_{i}s(X_i)$ means a confident correct prediction and a small loss. A negative signed score receives a larger penalty.

4. From perceptron motivation to maximum margin

Lectures 14-15; pp. 52-55.

The PDF motivates the perceptron by penalizing distances of wrongly classified observations to the boundary. For $w\ne 0$, wrong-side distances can be written as

$$\sum _{i:Y_i(w^{\top }{X}_i+b)<0}\frac{-Y_i(w^{\top }{X}_i+b)}{\Vert w\Vert }.$$

This motivates correcting wrong-side points, but does not distinguish all the separators of a separable dataset. It also gives no positive margin requirement.

Assume both classes occur and the data are strictly linearly separable:

$$Y_i(w^{\top }{X}_i+b)>0\text{for every }i$$

for some $w,b$. Strict positivity matters; classification by a tie convention at score zero does not ensure a positive margin.

Derive the hard-margin problem

The margin of a separating hyperplane is its smallest training-point distance:

$$\mathrm{margin}(w,b)=\underset{i}{\min }\frac{Y_i(w^{\top }{X}_i+b)}{\Vert w\Vert }.$$

Let $m={\min }_i{Y}_i(w^{\top }{X}_i+b)>0$. Rescale $(w,b)$ by $1/m$. The classifier is unchanged and its minimum signed score becomes 1. For the rescaled parameters,

$$\mathrm{margin}(w,b)=\frac{1}{\Vert w\Vert }.$$

Maximizing $1/\Vert w\Vert$ is equivalent to minimizing $\Vert w{\Vert }^2/2$. Hence the hard-margin SVM solves

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{subject to}{Y}_i(w^{\top }{X}_i+b)\ge 1\forall i.$$

The objective is convex and the constraints are affine. At an optimum, the minimum signed score is 1: otherwise scaling both parameters down would preserve feasibility and reduce the objective.

The distance from the decision boundary to the nearest observations is $1/\Vert w\Vert$; the distance between the two supporting hyperplanes is $2/\Vert w\Vert$.

5. Convex duality and KKT

Lecture 15; pp. 55-56.

Consider a differentiable convex objective $F(z)$ and differentiable convex constraints $h_i(z)\le 0$:

$$\underset{z}{\min }F(z)\text{subject to }{h}_i(z)\le 0.$$

Introduce multipliers ${\alpha }_i\ge 0$ and the Lagrangian

$$L(z,\alpha )=F(z)+\sum _i{\alpha }_i{h}_i(z).$$

Define the dual function $g(\alpha )={\inf }_{z}L(z,\alpha )$ and maximize it over $\alpha \ge 0$.

Why the dual gives a lower bound

For any feasible $z$ and $\alpha \ge 0$,

$$g(\alpha )\le L(z,\alpha )=F(z)+\sum _i{\alpha }_i{h}_i(z)\le F(z).$$

Thus the best dual value cannot exceed the best primal value: weak duality.

The primal can also be written as ${\inf }_z{\sup }_{\alpha \ge 0}L(z,\alpha )$. For feasible $z$, the inner supremum equals $F(z)$; if any constraint is violated, its multiplier can grow without bound. The dual reverses the optimization order. Strong duality means the optimal values coincide.

Slater and the KKT conditions

Slater’s condition asks for a strictly feasible point $\tilde{z}$ with $h_i(\tilde{z})<0$ for every inequality. Under the stated convex setting and an attained finite optimum, it ensures the usual strong-duality and multiplier-existence result.

The Karush-Kuhn-Tucker conditions are

$$\begin{array}{rlrl}\nabla F(z^{\ast })+\sum _i{\alpha }_i^{\ast }\nabla h_i(z^{\ast })& =0& & \text{stationarity},\\ h_i(z^{\ast })& \le 0& & \text{primal feasibility},\\ {\alpha }_i^{\ast }& \ge 0& & \text{dual feasibility},\\ {\alpha }_i^{\ast }{h}_i(z^{\ast })& =0& & \text{complementary slackness}.\end{array}$$

To see sufficiency, stationarity minimizes the convex function $L(\cdot ,{\alpha }^{\ast })$, so $g({\alpha }^{\ast })=L(z^{\ast },{\alpha }^{\ast })$. Complementary slackness makes this equal $F(z^{\ast })$. Weak duality then shows both points are optimal.

For strictly separable SVM data, scale a separator until every signed score is strictly greater than 1. This supplies Slater’s point.

6. Derive the hard-margin SVM dual

Lectures 15-16; pp. 56-60.

The constraints are $h_i(w,b)=1-Y_i(w^{\top }{X}_i+b)\le 0$. Therefore

$$\begin{array}{rl}L(w,b,\alpha )& =\frac{1}{2}\Vert w{\Vert }^2+\sum _i{\alpha }_i[1-Y_i(w^{\top }{X}_i+b)]\\ & =\frac{1}{2}\Vert w{\Vert }^2+\sum _i{\alpha }_i-w^{\top }\sum _i{\alpha }_i{Y}_i{X}_i-b\sum _i{\alpha }_i{Y}_i.\end{array}$$

First minimize over the intercept

If ${\sum }_i{\alpha }_i{Y}_i\ne 0$, letting $b$ move in the appropriate direction drives the Lagrangian to $-\infty$. A finite dual value thus requires

$$\sum _i{\alpha }_i{Y}_i=0.$$

Under this constraint, the intercept term vanishes.

Then minimize over the weight vector

Set its gradient to zero:

$${\nabla }_{w}L=w-\sum _i{\alpha }_i{Y}_i{X}_i=0⟹w=\sum _i{\alpha }_i{Y}_i{X}_i.$$

Writing $v={\sum }_i{\alpha }_i{Y}_i{X}_i$, the $w$ terms at the minimum are $\Vert v{\Vert }^2/2-v^{\top }v=-\Vert v{\Vert }^2/2$. Hence

$$g(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{Y}_i{Y}_j{X}_i^{\top }{X}_j.$$

The dual is

$$\underset{\alpha \ge 0}{\max }\left[\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{Y}_i{Y}_j{X}_i^{\top }{X}_j\right]\text{subject to }\sum _i{\alpha }_i{Y}_i=0.$$

The matrix $Q_{ij}=Y_i{Y}_j{X}_i^{\top }{X}_j$ is positive semidefinite, since

$$c^{\top }Qc={\Vert \sum _i{c}_i{Y}_i{X}_i\Vert }^2\ge 0.$$

The dual objective is therefore concave.

Recover the primal solution

Stationarity gives $w^{\ast }={\sum }_i{\alpha }_i^{\ast }{Y}_i{X}_i$. Complementary slackness gives

$${\alpha }_i^{\ast }[1-Y_i((w^{\ast }{)}^{\top }{X}_i+b^{\ast })]=0.$$

If ${\alpha }_i^{\ast }>0$, the constraint is tight. Since $Y_i^2=1$,

$$Y_i((w^{\ast }{)}^{\top }{X}_i+b^{\ast })=1⟹b^{\ast }=Y_i-(w^{\ast }{)}^{\top }{X}_i.$$

Such an index exists when both classes are present: if every multiplier were zero, stationarity would give $w^{\ast }=0$, and one intercept could not meet the constraints for both signs.

Support vectors and perturbations

Points with positive multipliers contribute to $w^{\ast }$ and lie on the hard margin. The PDF calls every margin point a support vector; in a degenerate solution a margin point may have multiplier zero, so the reverse implication need not hold.

Suppose a point lies strictly outside the margin on the correct side. Its multiplier is zero. Move it while keeping the old separator feasible. The original weights, intercept, and multipliers still satisfy KKT:

• Its zero multiplier leaves stationarity unchanged.
• Feasibility holds by the condition on its new location.
• Its complementary-slackness product remains zero.
• The other constraints and multipliers are unchanged.

Therefore the original solution remains optimal. This explains the limited sensitivity to observations that do not determine the margin.

Dimensions and inner products

The primal optimizes $d+1$ parameters; the dual optimizes $n$ multipliers. Training and prediction depend on inputs only through inner products:

$$s(x)=\sum _i{\alpha }_i^{\ast }{Y}_i{X}_i^{\top }x+b^{\ast }.$$

This can be useful when $d$ is large, although dual computation also depends on the cost of forming and storing the $n\times n$ Gram matrix.

7. Soft margins and hinge loss

Lecture 17; p. 61.

Hard-margin constraints are infeasible for nonseparable data. Introduce slack variables:

$$\underset{w,b,\xi \ge 0}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _i{\xi }_i\text{subject to}{Y}_i(w^{\top }{X}_i+b)\ge 1-{\xi }_i.$$

For fixed $w,b$, each constraint requires both ${\xi }_i\ge 0$ and ${\xi }_i\ge 1-Y_{i}s(X_i)$. Since $C>0$, the smallest feasible slack is optimal:

$${\xi }_i=\max \{0,1-Y_{i}s(X_i)\}.$$

Substituting gives the equivalent unconstrained objective

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _i\max \{0,1-Y_i(w^{\top }{X}_i+b)\}.$$

This is regularization plus hinge loss. A correctly classified observation can still incur loss when its signed score is between 0 and 1.

Larger $C$ penalizes violations more strongly; smaller $C$ puts more emphasis on a small norm. The hard-margin limit as $C$ grows requires separable data.

The corresponding dual constraint

To continue the earlier derivation, add multipliers ${\mu }_i\ge 0$ for $-{\xi }_i\le 0$. The coefficient of ${\xi }_i$ in the Lagrangian is $C-{\alpha }_i-{\mu }_i$. Minimization requires it to vanish:

$$C-{\alpha }_i-{\mu }_i=0⟹0\le {\alpha }_i\le C.$$

The other stationarity equations are unchanged. Thus the same dual objective now has box constraints $0\le {\alpha }_i\le C$ and ${\sum }_i{\alpha }_i{Y}_i=0$.

If $0<{\alpha }_i<C$, then ${\mu }_i>0$ forces ${\xi }_i=0$, and complementary slackness gives $Y_{i}s(X_i)=1$. Such points can recover the intercept. A soft-margin support vector with ${\alpha }_i=C$ may lie inside the margin or be misclassified.

Choose the tuning parameter

Fit the model for each candidate $C$ on training data. Evaluate its classification error on a separate validation set and choose the value with the smallest validation error. Cross-validation repeats this fit-and-evaluate procedure over folds. Keep final test data separate from tuning.

8. Nonlinear geometry and the kernel trick

Lecture 17; pp. 61-63.

A linear boundary cannot separate every useful geometry. For points in inner and outer rings in ${\mathbb{R}}^2$, the map

$$\Phi (x_1,x_2)=(x_1,x_2,x_1^2+x_2^2)$$

adds squared radius as a coordinate. A plane in this feature space can separate radii that no line in the original plane can separate.

For a general feature map $\Phi :\mathcal{X}\to \mathcal{H}$, the hard-margin problem becomes

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_{\mathcal{H}}^2\text{subject to}{Y}_i(⟨w,\Phi (X_i){⟩}_{\mathcal{H}}+b)\ge 1.$$

The same stationarity calculation gives

$$w^{\ast }=\sum _i{\alpha }_i^{\ast }{Y}_i\Phi (X_i).$$

Thus the dual uses only $⟨\Phi (X_i),\Phi (X_j){⟩}_{\mathcal{H}}$. Define

$$K(x,z)=⟨\Phi (x),\Phi (z){⟩}_{\mathcal{H}}.$$

Replace every original inner product by $K$. Prediction becomes

$$s(x)=\sum _i{\alpha }_i^{\ast }{Y}_{i}K(X_i,x)+b^{\ast }.$$

For a hard-margin point with positive multiplier,

$$b^{\ast }=Y_i-\sum _j{\alpha }_j^{\ast }{Y}_{j}K(X_j,X_i).$$

This rule is linear in the feature space and can be nonlinear in the original inputs. We can compute it without explicitly constructing $\Phi$.

The next question is which functions $K$ really behave as feature-space inner products. That leads to kernels and RKHS: continue to Part 4.