Support Vector Machine maximum margin concept

WHY do we want a maximum margin?

Suppose two classes are linearly separable. There are infinitely many lines that separate them perfectly (0 training errors). Which one is "best"?

The points that touch the edge of the street are the support vectors. They alone define the boundary — remove all other points and the answer is unchanged.

WHAT is the setup?

HOW do we measure the margin? (Derive from scratch)

Step 1 — Distance from a point to the hyperplane. Take a point $\mathbf{x}_0$ . Move perpendicular to the plane (along $\mathbf{w}/\|\mathbf{w}\|$ ) by distance $r$ to reach the plane at $\mathbf{x}_p$ : $\mathbf{x}_0 = \mathbf{x}_p + r\,\frac{\mathbf{w}}{\|\mathbf{w}\|}.$ Why this step? Any shortest path to a plane is along its normal.

Apply $\mathbf{w}^\top(\cdot)+b$ and use $\mathbf{w}^\top\mathbf{x}_p+b=0$ : $\mathbf{w}^\top\mathbf{x}_0 + b = r\,\frac{\mathbf{w}^\top\mathbf{w}}{\|\mathbf{w}\|} = r\|\mathbf{w}\|.$ So the signed distance is $r=\frac{\mathbf{w}^\top\mathbf{x}_0+b}{\|\mathbf{w}\|}.$

Step 2 — Fix the scale (the clever trick). $\mathbf{w},b$ can be scaled freely: $(\mathbf{w},b)$ and $(2\mathbf{w},2b)$ describe the same plane. We remove this ambiguity by choosing the scale so that the closest points satisfy $\min_i\; |\mathbf{w}^\top\mathbf{x}_i+b| = 1.$ Why this step? It pins one degree of freedom, turning a messy ratio into a clean constraint. This is the canonical hyperplane.

Step 3 — Compute the margin width. With that scaling, the nearest point has $|\mathbf{w}^\top\mathbf{x}_i+b|=1$ , so its distance is $1/\|\mathbf{w}\|$ . The street has this on both sides: $\boxed{\text{margin} = \frac{2}{\|\mathbf{w}\|}}.$

HOW do support vectors emerge? (KKT sketch)

Form the Lagrangian with multipliers $\alpha_i\ge 0$ : $L=\tfrac12\|\mathbf{w}\|^2-\sum_i\alpha_i\big[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\big].$ Stationarity gives $\frac{\partial L}{\partial \mathbf{w}}=0\Rightarrow \mathbf{w}=\sum_i\alpha_i y_i\mathbf{x}_i,\qquad \frac{\partial L}{\partial b}=0\Rightarrow \sum_i\alpha_i y_i=0.$ Why this matters: $\mathbf{w}$ is a weighted sum of the data points. Complementary slackness says $\alpha_i\big[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\big]=0$ , so $\alpha_i>0$ only for points exactly on the margin ( $y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1$ ). Those are the support vectors; all others have $\alpha_i=0$ and drop out.

Worked Examples

Worked example 2D: find the true max-margin direction

Positives $(3,3),(3,4)$ ; negatives $(1,1),(1,0)$ . Don't assume the boundary is vertical! The maximum-margin separator is perpendicular to the shortest segment joining the two classes. Why? The widest street is oriented across the tightest gap between the point sets. The closest opposite-class pair is $(3,3)$ and $(1,1)$ , separated by the vector $(3,3)-(1,1)=(2,2)$ . So $\mathbf{w}\parallel(2,2)$ ; take $\mathbf{w}=(a,a)$ . The boundary passes through the midpoint $(2,2)$ : $\mathbf{w}^\top(2,2)+b=0\Rightarrow 4a+b=0\Rightarrow b=-4a$ . Canonical scaling on the support vectors: at $(3,3)$ , $\mathbf{w}^\top\mathbf{x}+b = 3a+3a-4a = 2a \stackrel{!}{=}1\Rightarrow a=\tfrac12$ . So $\mathbf{w}=(\tfrac12,\tfrac12),\ b=-2$ . Margin $=2/\|\mathbf{w}\| = 2/\sqrt{(1/2)^2+(1/2)^2} = 2/\tfrac{1}{\sqrt2} = 2\sqrt2 \approx 2.828$ . Sanity check: distance between $(3,3)$ and $(1,1)$ is $\sqrt{2^2+2^2}=2\sqrt2$ — the full street width, as expected. Support vectors: $(3,3),(1,1)$ (and by symmetry the constraints on $(3,4),(1,0)$ are satisfied with slack). ✔ Steel-man: a vertical boundary $x_1=2$ ( $\mathbf{w}=(1,0)$ ) also separates the data, but its margin is only $2 < 2\sqrt2$ — so it is not the SVM solution.

Common Mistakes (Steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine two groups of kids on a playground, and you must paint one straight line so each group stays on its own side. You could paint many lines. The best line leaves the biggest empty walkway between the two groups, so if a kid wiggles a little they still don't cross. The kids standing right at the edge of the walkway are the "important" kids — they decide where the line goes. All the kids far in the back don't matter at all.

Flashcards

What does an SVM maximize among all separating hyperplanes?

The margin — the perpendicular distance to the nearest points of both classes (the widest "street").

Formula for the margin width in canonical form?

2/\|\mathbf{w}\|

Which direction is the max-margin hyperplane perpendicular to?

The vector joining the closest pair of opposite-class points (the tightest gap) — often diagonal, not an axis.

Why minimize

\tfrac12\|\mathbf{w}\|^2

instead of maximizing

2/\|\mathbf{w}\|

They are equivalent; the quadratic form is convex and differentiable, giving a clean QP.

What is the canonical (scaling) constraint that removes ambiguity in

(\mathbf{w},b)

\min_i |\mathbf{w}^\top\mathbf{x}_i+b| = 1

, i.e.

y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1

What are support vectors?

Training points lying exactly on the margin edges (

y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1

\alpha_i>0

); they alone define the boundary.

Why use labels

\pm1

instead of

0/1

So both class constraints collapse into one:

y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1

Distance from point

\mathbf{x}_0

to hyperplane

\mathbf{w}^\top\mathbf{x}+b=0

\dfrac{|\mathbf{w}^\top\mathbf{x}_0+b|}{\|\mathbf{w}\|}

After optimization,

\mathbf{w}

equals what combination of data?

\mathbf{w}=\sum_i \alpha_i y_i \mathbf{x}_i

(weighted sum over support vectors).

Decision rule for a new point

\mathbf{x}

\hat{y}=\operatorname{sign}(\mathbf{w}^\top\mathbf{x}+b)

Connections

Support Vector Machine soft margin (slack variables) — what to do when data isn't separable.
Kernel trick — replacing $\mathbf{x}_i^\top\mathbf{x}_j$ with $K(\mathbf{x}_i,\mathbf{x}_j)$ for nonlinear boundaries.
Lagrangian duality and KKT conditions — how support vectors formally arise.
Logistic Regression — contrast: probabilistic vs margin-based; hinge loss vs log loss.
VC dimension and generalization bounds — why large margin bounds test error.
Convex optimization / Quadratic Programming — the solver behind SVM.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho do class ke points hain aur tumhe ek straight line se unhe alag karna hai. Problem yeh hai ki aisi infinite lines ho sakti hain jo perfectly separate kar dein — toh best kaunsi? SVM ka jawab: woh line jo dono groups ke sabse nazdeek points se maximum door ho. Matlab beech mein sabse chaudi gali (street) banao. Yeh isliye best hai kyunki agar test point mein thoda noise aa jaye, tab bhi woh galat side par cross nahi karega — yani generalization achha hota hai.

Ek important baat jo log galti karte hain: yeh mat maan lo ki boundary hamesha vertical ya horizontal hogi. Actually max-margin line closest opposite-class pair ko jodne wale vector ke perpendicular hoti hai — jo aksar diagonal hoti hai. Humare 2D example mein closest pair $(3,3)$ aur $(1,1)$ hai, gap vector $(2,2)$ , toh $\mathbf{w}=(\tfrac12,\tfrac12)$ nikalta hai aur margin $2\sqrt2\approx2.83$ banta hai — vertical boundary ka margin sirf $2$ hota, jo chhota hai.

Math clean karne ke liye labels $+1$ aur $-1$ lete hain, aur scaling trick: closest point par $|\mathbf{w}^\top\mathbf{x}+b|=1$ . Isse margin width $=2/\|\mathbf{w}\|$ . Margin bada karna hai toh $\|\mathbf{w}\|$ chhota karo — isiliye $\tfrac12\|\mathbf{w}\|^2$ minimize karte hain, constraint $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1$ ke saath.

Sabse mast baat: sirf margin ki edge par khade points boundary decide karte hain — inhe support vectors kehte hain. Baaki hata do, answer nahi badlega. Naya point classify karna simple: $\operatorname{sign}(\mathbf{w}^\top\mathbf{x}+b)$ dekh lo.

Test yourself — SVM, Naive Bayes & Probabilistic Models

Connections