Support Vector Machine maximum margin concept

2.4.1 · AI-ML › SVM, Naive Bayes & Probabilistic Models

WHY: hum maximum margin kyun chahte hain?

Maano do classes linearly separable hain. Unhe perfectly separate (0 training errors) karne wali infinitely many lines hain. Kaun si "best" hai?

Jo points street ke edge ko touch karte hain wo support vectors hain. Sirf wohi boundary define karte hain — baaki sabhi points hata do aur answer same rahega.

WHAT: setup kya hai?

HOW: margin measure kaise karte hain? (Scratch se derive)

Step 1 — Ek point se hyperplane ki distance. Ek point $x_{0}$ lo. Plane ke perpendicular (yaani $w /∥ w ∥$ direction mein) distance $r$ chalke plane pe $x_{p}$ tak pahuncho: $x_{0} = x_{p} + r \frac{w}{∥ w ∥} .$ Ye step kyun? Kisi bhi plane tak sabse chhota rasta uske normal ke along hota hai.

$w^{⊤} (\cdot) + b$ apply karo aur $w^{⊤} x_{p} + b = 0$ use karo: $w^{⊤} x_{0} + b = r \frac{w ^{⊤} w}{∥ w ∥} = r ∥ w ∥.$ Toh signed distance hai $r = \frac{w ^{⊤} x _{0} + b}{∥ w ∥} .$

Step 2 — Scale fix karo (wo clever trick). $w, b$ ko freely scale kiya ja sakta hai: $(w, b)$ aur $(2 w, 2 b)$ same plane describe karte hain. Hum ye ambiguity scale choose karke hataate hain, jisse nearest points satisfy karein: $min_{i} ∣ w^{⊤} x_{i} + b ∣ = 1.$ Ye step kyun? Ye ek degree of freedom pin kar deta hai, ek messy ratio ko ek clean constraint mein badal deta hai. Yahi canonical hyperplane hai.

Step 3 — Margin width compute karo. Us scaling ke saath, nearest point ka $∣ w^{⊤} x_{i} + b ∣ = 1$ hai, toh uski distance $1/∥ w ∥$ hai. Street dono sides pe itni hi hai: $margin = \frac{2}{∥ w ∥} .$

HOW: support vectors kaise emerge hote hain? (KKT sketch)

Multipliers $α_{i} \geq 0$ ke saath Lagrangian banao: $L = \frac{1}{2} ∥ w ∥^{2} - \sum_{i} α_{i} [y_{i} (w^{⊤} x_{i} + b) - 1] .$ Stationarity deta hai: $\frac{\partial L}{\partial w} = 0 \Rightarrow w = \sum_{i} α_{i} y_{i} x_{i}, \frac{\partial L}{\partial b} = 0 \Rightarrow \sum_{i} α_{i} y_{i} = 0.$ Ye kyun matter karta hai: $w$ data points ka ek weighted sum hai. Complementary slackness kehta hai $α_{i} [y_{i} (w^{⊤} x_{i} + b) - 1] = 0$ , toh $α_{i} > 0$ sirf unhi points ke liye hai jo exactly margin pe hain ( $y_{i} (w^{⊤} x_{i} + b) = 1$ ). Wohi support vectors hain; baaki sab ka $α_{i} = 0$ hota hai aur wo dropout ho jaate hain.

Worked Examples

Worked example 2D: true max-margin direction dhundho

Positives $(3, 3), (3, 4)$ ; negatives $(1, 1), (1, 0)$ . Ye mat maano ki boundary vertical hai! Maximum-margin separator do classes ko join karne wale shortest segment ke perpendicular hota hai. Kyun? Sabse chaudi street point sets ke beech tightest gap ke across oriented hoti hai. Sabse close opposite-class pair hai $(3, 3)$ aur $(1, 1)$ , jo vector $(3, 3) - (1, 1) = (2, 2)$ se separated hain. Toh $w ∥ (2, 2)$ ; lo $w = (a, a)$ . Boundary midpoint $(2, 2)$ se guzarti hai: $w^{⊤} (2, 2) + b = 0 \Rightarrow 4 a + b = 0 \Rightarrow b = - 4 a$ . Support vectors par canonical scaling: $(3, 3)$ par, $w^{⊤} x + b = 3 a + 3 a - 4 a = 2 a =! 1 \Rightarrow a = \frac{1}{2}$ . Toh $w = (\frac{1}{2}, \frac{1}{2}), b = - 2$ . Margin $= 2/∥ w ∥ = 2/ (1/2)^{2} + (1/2)^{2} = 2/ \frac{1}{2} = 22 \approx 2.828$ . Sanity check: $(3, 3)$ aur $(1, 1)$ ke beech distance $2^{2} + 2^{2} = 22$ hai — pura street width, jaisa expected tha. Support vectors: $(3, 3), (1, 1)$ (aur symmetry se $(3, 4), (1, 0)$ par constraints slack ke saath satisfy hain). ✔ Steel-man: ek vertical boundary $x_{1} = 2$ ( $w = (1, 0)$ ) bhi data separate karta hai, lekin uska margin sirf $2 < 22$ hai — toh wo SVM solution nahi hai.

Common Mistakes (Steel-manned)

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho playground mein do groups of kids hain, aur tumhe ek seedhi line paint karni hai taaki har group apni side pe rahe. Tum kaafi saari lines paint kar sakte ho. Best line wohi hai jo dono groups ke beech sabse bada khali walkway chhodi, taaki agar koi kid thoda hilta bhi hai toh cross na kare. Jo kids walkway ke edge pe khade hain wo "important" kids hain — wohi decide karte hain line kahan jayegi. Pichhle hisse mein door khade sabhi kids bilkul matter nahi karte.

Flashcards

SVM sabhi separating hyperplanes mein se kya maximize karta hai?

Margin — dono classes ke nearest points tak perpendicular distance (sabse chaudi "street").

Canonical form mein margin width ka formula?

2/∥ w ∥

Max-margin hyperplane kis direction ke perpendicular hota hai?

Opposite-class points ke closest pair ko join karne wale vector ke (tightest gap) — aksar diagonal, koi axis nahi.

2/∥ w ∥

maximize karne ki jagah

\frac{1}{2} ∥ w ∥^{2}

minimize kyun karte hain?

Dono equivalent hain; quadratic form convex aur differentiable hai, jo ek clean QP deta hai.

Canonical (scaling) constraint jo

(w, b)

mein ambiguity hataata hai?

min_{i} ∣ w^{⊤} x_{i} + b ∣ = 1

, yaani

y_{i} (w^{⊤} x_{i} + b) \geq 1

Support vectors kya hote hain?

Training points jo exactly margin edges pe hote hain (

y_{i} (w^{⊤} x_{i} + b) = 1

α_{i} > 0

); sirf wohi boundary define karte hain.

0/1

ki jagah

\pm 1

labels kyun use karte hain?

Taaki dono class constraints ek mein collapse ho jayein:

y_{i} (w^{⊤} x_{i} + b) \geq 1

Point

x_{0}

se hyperplane

w^{⊤} x + b = 0

tak distance?

\frac{∣ w ^{⊤} x _{0} + b ∣}{∥ w ∥}

Optimization ke baad,

w

data ke kis combination ke barabar hota hai?

w = \sum_{i} α_{i} y_{i} x_{i}

(support vectors par weighted sum).

Naye point

x

ke liye decision rule?

\overset{y}{^} = sign (w^{⊤} x + b)

Connections

Support Vector Machine soft margin (slack variables) — jab data separable nahi ho tab kya karein.
Kernel trick — nonlinear boundaries ke liye $x_{i}^{⊤} x_{j}$ ko $K (x_{i}, x_{j})$ se replace karna.
Lagrangian duality and KKT conditions — support vectors formally kaise arise hote hain.
Logistic Regression — contrast: probabilistic vs margin-based; hinge loss vs log loss.
VC dimension and generalization bounds — large margin test error kyun bound karta hai.
Convex optimization / Quadratic Programming — SVM ke peeche ka solver.