07_Support_Vector_Machines

Module 6 — Support Vector Machines (Hard Margin, Soft Margin, Kernels)

Sources: Lec 13 — SVM (Hard Margin); Lec 14 — SVM (Soft Margin); Lec 15 — SVM Using Kernels.

Notation. $({\vec{X}}_i,y_i)$, $y_i\in \{+1,-1\}$; weight $\vec{W}\in {\mathbb{R}}^m$, bias $b$; hyperplane ${\vec{W}}^T\vec{X}+b=0$; classifier $\mathrm{sign}({\vec{W}}^T\vec{X}+b)$.

---

C30. Hard-Margin SVM: Geometry, Margin and Support Vectors

Intuition

Many lines separate two classes. Choose the one that stays as far as possible from both classes — a fat “street” with the boundary down the middle. Safer on new data. The few points that touch the edges of the street (support vectors) alone determine the answer.

Formal definition

• Data are linearly separable iff the convex hulls of the two classes do not intersect. Convex hull of $X_1..X_n$: $C=\{{\sum }_i{\lambda }_i{X}_i:{\lambda }_i\ge 0,\sum {\lambda }_i=1\}$.
• Separating hyperplane: $y_i({\vec{W}}^T{\vec{X}}_i+b)>0\forall i$.
• $\vec{W}$ is normal to the hyperplane; distance of the hyperplane from the origin is $|b|/\Vert \vec{W}\Vert$; distance of a point $\vec{X}$ from it is $\frac{|{\vec{W}}^T\vec{X}+b|}{\Vert \vec{W}\Vert }$.
• Rescaling freedom: $(\vec{W},b)\to (c\vec{W},cb)$ leaves the hyperplane unchanged, so we fix the scale such that the closest points satisfy $y_i({\vec{W}}^T{\vec{X}}_i+b)=1$ (setting the margin parameter $\gamma =1$). All constraints become $y_i({\vec{W}}^T{\vec{X}}_i+b)\ge 1\forall i.$
• Margin $=d_{+}+d_{-}=\frac{1}{\Vert \vec{W}\Vert }+\frac{1}{\Vert \vec{W}\Vert }=\frac{2}{\Vert \vec{W}\Vert }$.
• Support vectors: points with $y_i({\vec{W}}^T{\vec{X}}_i+b)=1$ (exactly on the margin).

Optimisation problem

$\max \frac{2}{\Vert \vec{W}\Vert }\text{s.t. }{y}_i({\vec{W}}^T{\vec{X}}_i+b)\ge 1⟺\boxed{\min \frac{1}{2}{\vec{W}}^T\vec{W}\text{ s.t. }{y}_i({\vec{W}}^T{\vec{X}}_i+b)\ge 1,i=\mathrm{1..}n.}$ (The lecture calls the second form the “dual”; strictly it is an equivalent primal. The true dual comes in C31.)

Derivation of the margin

Take a support vector ${\vec{X}}_{+}$ with ${\vec{W}}^T{\vec{X}}_{+}+b=1$ and ${\vec{X}}_{-}$ with ${\vec{W}}^T{\vec{X}}_{-}+b=-1$. Subtract: ${\vec{W}}^T({\vec{X}}_{+}-{\vec{X}}_{-})=2$. Projecting ${\vec{X}}_{+}-{\vec{X}}_{-}$ on the unit normal $\vec{W}/\Vert \vec{W}\Vert$ gives the width: $\frac{{\vec{W}}^T({\vec{X}}_{+}-{\vec{X}}_{-})}{\Vert \vec{W}\Vert }=\frac{2}{\Vert \vec{W}\Vert }$. ∎

Key insights

• Maximising margin $\equiv$ minimising $\Vert \vec{W}\Vert$.
• Interior points (with $y_{i}f({\vec{X}}_i)>1$) are irrelevant to the solution.
• Hard margin needs separable data (C32 relaxes this).

Worked examples

Example 1 — Very Easy

• Problem: $\vec{W}=(3,4)$, $b=-5$. Distance of $\vec{X}=(2,1)$ from the hyperplane?
• Asked: Distance.
• Concept: Point-to-hyperplane distance.
• Approach: $|{\vec{W}}^T\vec{X}+b|/\Vert \vec{W}\Vert$.
• Solution: ${\vec{W}}^T\vec{X}+b=6+4-5=5$; $\Vert \vec{W}\Vert =\sqrt{9+16}=5$. Distance $=1$.
• Final answer: $1$.
• Key lesson: Distance is the signed value divided by $\Vert \vec{W}\Vert$.

Example 2 — Easy

• Problem: If the support vectors satisfy $y_i({\vec{W}}^T{\vec{X}}_i+b)=1$ and $\vec{W}=(3,4)$, what is the margin? What $\Vert \vec{W}\Vert$ gives margin $2$?
• Asked: Two numbers.
• Concept: Margin $=2/\Vert \vec{W}\Vert$.
• Approach: Formula.
• Solution: $2/5=0.4$. Margin $2\Rightarrow \Vert \vec{W}\Vert =1$.
• Final answer: $0.4$; $\Vert \vec{W}\Vert =1$.
• Key lesson: Big margin ⇔ small weight vector.

Example 3 — Moderate

• Problem: Positive point $(2,2)$, negative point $(0,0)$. Find the hard-margin hyperplane by imposing both constraints with equality and symmetry $\vec{W}=(a,a)$.
• Asked: $\vec{W},b$, margin.
• Concept: Constraints active on both points.
• Approach: Solve for $a,b$.
• Solution: $(2,2)$: $4a+b=1$; $(0,0)$: $-(b)=1\Rightarrow b=-1$. So $4a=2$, $a=0.5$. $\vec{W}=(0.5,0.5)$, $b=-1$; boundary $x_1+x_2=2$. $\Vert \vec{W}\Vert =0.7071$; margin $=2/0.7071=2.828$ = distance between the two points $\sqrt{8}=2.828$ ✓.
• Final answer: $\vec{W}=(0.5,0.5)$, $b=-1$, margin $2.83$.
• Key lesson: With one point per class the optimal margin equals the distance between the points and the boundary is their perpendicular bisector.

Example 4 — Hard

• Problem: $\vec{W}=(1,1)$, $b=-3$; positives $(2,2),(3,3)$; negatives $(1,1),(0,0)$. Check feasibility, find the support vectors and margin.
• Asked: Verification.
• Concept: Constraints and SVs.
• Approach: Compute $y_i({\vec{W}}^T{\vec{X}}_i+b)$.
• Solution: $(2,2)$: $+1(4-3)=1$ ✓ SV. $(3,3)$: $6-3=3\ge 1$ ✓ (not SV). $(1,1)$: $-1(2-3)=1$ ✓ SV. $(0,0)$: $-1(0-3)=3\ge 1$ ✓. Margin $=2/\sqrt{2}=1.414$.
• Final answer: Feasible; SVs $=\{(2,2),(1,1)\}$; margin $\sqrt{2}$.
• Key lesson: Only points with value exactly $1$ are support vectors.

Example 5 — Very Hard

• Problem: Show by the convex-hull criterion that the XOR set — positives $(0,0),(1,1)$, negatives $(0,1),(1,0)$ — is not linearly separable, and that adding a point makes a separable set (e.g. positives $(0,0),(1,0)$, negatives $(0,1),(1,1)$).
• Asked: Hull intersection.
• Concept: Hull criterion.
• Approach: Find a common convex combination.
• Solution: Positive hull contains $\frac{1}{2}(0,0)+\frac{1}{2}(1,1)=(0.5,0.5)$ (any $\lambda \ge 0,\sum \lambda =1$). Negative hull contains $\frac{1}{2}(0,1)+\frac{1}{2}(1,0)=(0.5,0.5)$. The hulls share a point ⇒ not separable. Second set: positive hull $=\{(t,0):0\le t\le 1\}$; negative hull $=\{(t,1)\}$: disjoint ($x_2=0$ vs $x_2=1$) ⇒ separable, e.g. $x_2=0.5$ ($\vec{W}=(0,-2)$, $b=1$ gives $y({\vec{W}}^T\vec{X}+b)=1$ on all four points).
• Final answer: XOR hulls intersect at $(0.5,0.5)$; the second set is separable.
• Key lesson: Separability is geometric: intersecting hulls ⇒ no hyperplane.

Common mistakes

• Forgetting the $1/\Vert \vec{W}\Vert$ in distances.
• Writing the margin as $1/\Vert \vec{W}\Vert$ (that is one side).

Exam traps

• “Support vectors” lie on the margin; margin $=2/\Vert \vec{W}\Vert$.
• Maximise $2/\Vert \vec{W}\Vert$ ≡ minimise $\frac{1}{2}{\vec{W}}^T\vec{W}$.

Connections

Perceptron (C49), logistic (C27), Lagrange dual (C31), soft margin (C32).

Mastery checklist

• Derive margin $=2/\Vert \vec{W}\Vert$.
• Identify support vectors.
• State the hull criterion.

---

C31. The Lagrange Dual of the Hard-Margin SVM and the KKT Conditions

Intuition

Constrained optimisation: introduce a “price” ${\alpha }_i\ge 0$ for violating each constraint. At the optimum only constraints that are tight have nonzero price. The dual problem is over the prices $\alpha$, and — crucially — the data enter only through inner products ${\vec{X}}_i^T{\vec{X}}_j$ (which is what makes kernels possible, C33).

Derivation

Lagrangian: $L(\vec{W},b,\alpha )=\frac{1}{2}{\vec{W}}^T\vec{W}+{\sum }_i{\alpha }_i[1-y_i({\vec{W}}^T{\vec{X}}_i+b)],{\alpha }_i\ge 0.$ Minimise over $(\vec{W},b)$, maximise over $\alpha$. $\frac{\partial L}{\partial \vec{W}}=\vec{W}-{\sum }_i{\alpha }_i{y}_i{\vec{X}}_i=0\Rightarrow \boxed{\vec{W}=\sum _i{\alpha }_i{y}_i{\vec{X}}_i},\frac{\partial L}{\partial b}=-{\sum }_i{\alpha }_i{y}_i=0\Rightarrow \boxed{\sum _i{\alpha }_i{y}_i=0}.$ Substitute: ${\sum }_i{\alpha }_i{y}_i{\vec{W}}^T{\vec{X}}_i={\vec{W}}^T\vec{W}$ and ${\sum }_i{\alpha }_i{y}_{i}b=0$, so $L=\frac{1}{2}{\vec{W}}^T\vec{W}-{\vec{W}}^T\vec{W}+\sum {\alpha }_i={\sum }_i{\alpha }_i-\frac{1}{2}{\vec{W}}^T\vec{W}.$ Dual problem: $\boxed{\underset{\alpha }{\max }{L}_D(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{\vec{X}}_i^T{\vec{X}}_j\text{s.t. }{\alpha }_i\ge 0,\sum _i{\alpha }_i{y}_i=0.}$ A concave quadratic program (QP); in matrix form: minimise $\frac{1}{2}{\alpha }^{T}Q\alpha -{\vec{1}}^T\alpha$ with $Q_{ij}=y_i{y}_j{\vec{X}}_i^T{\vec{X}}_j$, ${\vec{y}}^T\alpha =0$, $\alpha \ge 0$.

KKT conditions: stationarity (above), primal feasibility $y_i({\vec{W}}^T{\vec{X}}_i+b)\ge 1$, dual feasibility ${\alpha }_i\ge 0$, and complementary slackness ${\alpha }_i[y_i({\vec{W}}^T{\vec{X}}_i+b)-1]=0.$ Hence ${\alpha }_i>0\Rightarrow$ the point is on the margin (support vector); non-SVs have ${\alpha }_i=0$. $b$ from any SV $j$: $b=y_j-{\vec{W}}^T{\vec{X}}_j$. Prediction: $\mathrm{sign}({\vec{W}}^T{\vec{X}}_0+b)=\mathrm{sign}({\sum }_i{\alpha }_i{y}_i{\vec{X}}_i^T{\vec{X}}_0+b)$.

Key insights

• $\vec{W}$ is a linear combination of support vectors only.
• Strong duality (convex problem): $\frac{1}{2}\Vert \vec{W}{\Vert }^2=L_D({\alpha }^{\ast })$.
• Complexity depends on $n$ (size of the QP), not on $m$.

Worked examples

Example 1 — Very Easy

• Problem: 1-D: $x_1=2(+1)$, $x_2=0(-1)$. Solve the dual.
• Asked: $\alpha ,W,b$.
• Concept: Dual QP.
• Approach: $\sum {\alpha }_i{y}_i=0\Rightarrow {\alpha }_1={\alpha }_2=\alpha$.
• Solution: Gram: $x_1{x}_1=4$, others $0$. $L_D=2\alpha -\frac{1}{2}({\alpha }^2\cdot 4)=2\alpha -2{\alpha }^2$; $\frac{d{L}_D}{d\alpha }=2-4\alpha =0\Rightarrow \alpha =0.5$. $W={\alpha }_1{y}_1{x}_1+{\alpha }_2{y}_2{x}_2=0.5(2)=1$. SV $x_1$: $b=y_1-W{x}_1=1-2=-1$. Boundary at $x=1$; margin $2/|W|=2$ = distance between points ✓.
• Final answer: $\alpha =(0.5,0.5)$, $W=1$, $b=-1$.
• Key lesson: The constraint $\sum {\alpha }_i{y}_i=0$ ties the multipliers together.

Example 2 — Easy

• Problem: 2-D: ${\vec{X}}_1=(1,1)(+1)$, ${\vec{X}}_2=(-1,-1)(-1)$. Solve.
• Asked: $\alpha ,\vec{W},b$.
• Concept: Dual with a Gram matrix.
• Approach: ${\alpha }_1={\alpha }_2=\alpha$.
• Solution: Inner products: ${\vec{X}}_1^T{\vec{X}}_1=2$, ${\vec{X}}_2^T{\vec{X}}_2=2$, ${\vec{X}}_1^T{\vec{X}}_2=-2$. ${\sum }_{ij}{\alpha }_i{\alpha }_j{y}_i{y}_j{X}_i^T{X}_j={\alpha }^2[2+2+2(-1)(-2)]=8{\alpha }^2$. $L_D=2\alpha -4{\alpha }^2$; $\alpha =0.25$. $\vec{W}=0.25(1,1)+0.25(1,1)=(0.5,0.5)$. $b=1-{\vec{W}}^T{\vec{X}}_1=1-1=0$. Margin $=2/\Vert \vec{W}\Vert =2/0.7071=2.83=\Vert {\vec{X}}_1-{\vec{X}}_2\Vert$ ✓.
• Final answer: $\alpha =0.25$ each, $\vec{W}=(0.5,0.5)$, $b=0$.
• Key lesson: Verify with the geometric answer.

Example 3 — Moderate

• Problem: Points ${\vec{X}}_1=(2,0)(+)$, ${\vec{X}}_2=(0,2)(+)$, ${\vec{X}}_3=(0,0)(-)$ with multipliers $\alpha =(0.5,0.5,1)$. Compute $\vec{W},b$ and classify $(3,1)$ and $(0.5,0.2)$.
• Asked: $\vec{W},b$, two labels.
• Concept: Recover primal from dual.
• Approach: $\vec{W}=\sum {\alpha }_i{y}_i{\vec{X}}_i$.
• Solution: $\vec{W}=0.5(2,0)+0.5(0,2)-1(0,0)=(1,1)$. SV ${\vec{X}}_1$: $b=1-{\vec{W}}^T{\vec{X}}_1=1-2=-1$; check with ${\vec{X}}_3$: $b=-1-0=-1$ ✓. $f(\vec{X})=x_1+x_2-1$. $f(3,1)=3>0\Rightarrow +$. $f(0.5,0.2)=-0.3<0\Rightarrow -$. Check $\sum {\alpha }_i{y}_i=0.5+0.5-1=0$ ✓.
• Final answer: $\vec{W}=(1,1)$, $b=-1$; labels $+,-$.
• Key lesson: Two different SVs must give the same $b$ (a consistency check).

Example 4 — Hard

• Problem: Points $(2,2)(+)$, $(0,0)(-)$, $(2,0)(-)$. Find the optimal $\vec{W},b,\alpha$ and explain why one point on the margin has $\alpha =0$.
• Asked: Solution and explanation.
• Concept: Complementary slackness is one-directional.
• Approach: Primal geometry, then recover $\alpha$.
• Solution: Intuitively the closest approach is vertical: $\vec{W}=(0,1)$, $b=-1$. Constraints: $(2,2)$: $2-1=1$; $(0,0)$: $-(-1)=1$; $(2,0)$: $-(0-1)=1$ — all three on the margin. (Optimality: with $b=-1-t$ the constraints force $a\le t/2$ and $a+c\ge 1+t/2$, giving $\Vert \vec{W}{\Vert }^2\ge 1+t^2/4$, minimal at $t=0$.) Dual: $\vec{W}={\alpha }_1(2,2)-{\alpha }_2(0,0)-{\alpha }_3(2,0)=(2{\alpha }_1-2{\alpha }_3,2{\alpha }_1)=(0,1)\Rightarrow {\alpha }_1=0.5,{\alpha }_3=0.5$. $\sum {\alpha }_i{y}_i=0\Rightarrow 0.5-{\alpha }_2-0.5=0\Rightarrow {\alpha }_2=0$.
• Final answer: $\vec{W}=(0,1),b=-1$, $\alpha =(0.5,0,0.5)$.
• Key lesson: ${\alpha }_i>0\Rightarrow$ on the margin, but a point on the margin can still have ${\alpha }_i=0$ (a “degenerate” SV); removing it does not change the solution.

Example 5 — Very Hard

• Problem: For the data of Example 3, solve the dual from scratch and verify strong duality and all KKT conditions.
• Asked: ${\alpha }^{\ast }$, $L_D^{\ast }$, primal value.
• Concept: Strong duality.
• Approach: Eliminate ${\alpha }_3={\alpha }_1+{\alpha }_2$.
• Solution: Gram entries: $X_1^T{X}_1=4$, $X_2^T{X}_2=4$, $X_1^T{X}_2=0$, anything with $X_3=\vec{0}$ equals $0$. $L_D={\alpha }_1+{\alpha }_2+{\alpha }_3-\frac{1}{2}(4{\alpha }_1^2+4{\alpha }_2^2)=2({\alpha }_1+{\alpha }_2)-2{\alpha }_1^2-2{\alpha }_2^2$. $\partial /\partial {\alpha }_1=2-4{\alpha }_1=0\Rightarrow {\alpha }_1=0.5$; likewise ${\alpha }_2=0.5$; ${\alpha }_3=1$. $L_D^{\ast }=2(1)-0.5-0.5=1$. Primal: $\frac{1}{2}\Vert \vec{W}{\Vert }^2=\frac{1}{2}(1^2+1^2)=1$ ✓ equal ⇒ strong duality. KKT: all three constraints tight ($f({\vec{X}}_1)=1,f({\vec{X}}_2)=1,f({\vec{X}}_3)=-1$ so $y_{i}f=1$) ⇒ complementary slackness holds for every ${\alpha }_i$; $\sum {\alpha }_i{y}_i=0$ ✓; ${\alpha }_i\ge 0$ ✓.
• Final answer: ${\alpha }^{\ast }=(0.5,0.5,1)$, optimal value $1$ for both problems.
• Key lesson: Primal and dual optimal values coincide; use this as a numerical check.

Common mistakes

• Forgetting the equality constraint $\sum {\alpha }_i{y}_i=0$.
• Using $b=y_j-{\vec{W}}^T{\vec{X}}_j$ with a non-support vector.

Exam traps

• The lecture’s "$0\le \alpha \le \infty$" is $\alpha \ge 0$.
• The lecture says ”${\alpha }_i>0$ for support vectors and $0$ otherwise” — true except for degenerate boundary points.

Connections

C30, C32 (box constraint), C33 (kernels replace ${\vec{X}}_i^T{\vec{X}}_j$).

Mastery checklist

• Derive the dual from the Lagrangian.
• State KKT conditions.
• Recover $\vec{W},b$ from $\alpha$.

---

C32. Soft-Margin SVM (Slack Variables and the Parameter $C$)

Intuition

Real data overlap. Allow some points to be inside the street or on the wrong side, but pay a penalty proportional to how badly they violate the margin. $C$ sets the exchange rate between a wide street and violations.

Formal definition

Slack ${\gamma }_i\ge 0$ (the lecture’s notation; often ${\xi }_i$): ${\min }_{\vec{W},b,\gamma }\frac{1}{2}{\vec{W}}^T\vec{W}+C{\sum }_{i=1}^n{\gamma }_i\text{s.t. }{\gamma }_i\ge 0,y_i({\vec{W}}^T{\vec{X}}_i+b)\ge 1-{\gamma }_i.$ Equivalent: ${\gamma }_i=\max (0,1-y_{i}f({\vec{X}}_i))$ (hinge loss). Meaning of ${\gamma }_i$: $\gamma =0$ correct & outside margin; $0<\gamma <1$ inside the margin but correctly classified (margin error); $\gamma =1$ on the boundary; $\gamma >1$ misclassified.

Derivation of the dual

$L=\frac{1}{2}{\vec{W}}^T\vec{W}+C\sum {\gamma }_i+\sum {\alpha }_i[1-{\gamma }_i-y_i({\vec{W}}^T{\vec{X}}_i+b)]-\sum {\mu }_i{\gamma }_i,{\alpha }_i,{\mu }_i\ge 0.$ ${\partial }_{\vec{W}}:\vec{W}=\sum {\alpha }_i{y}_i{\vec{X}}_i$; ${\partial }_b:\sum {\alpha }_i{y}_i=0$; ${\partial }_{{\gamma }_i}:C-{\alpha }_i-{\mu }_i=0$. Substituting gives the same dual as hard margin, $L_D=\sum {\alpha }_i-\frac{1}{2}{\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{\vec{X}}_i^T{\vec{X}}_j,$ but with the box constraint $0\le {\alpha }_i\le C$ (since ${\mu }_i=C-{\alpha }_i\ge 0$). $C\to \infty$ recovers the hard margin.

KKT / what ${\alpha }_i$ means: complementary slackness ${\alpha }_i[y_i{f}_i-1+{\gamma }_i]=0$ and ${\mu }_i{\gamma }_i=0$:

${\alpha }_i$	${\mu }_i$	${\gamma }_i$	Position
$0$	$C$	$0$	correct, outside margin (not an SV)
$0<{\alpha }_i<C$	$>0$	$0$	exactly on the margin ($y_i{f}_i=1$)
$C$	$0$	$\ge 0$	inside the margin or misclassified

All points with ${\alpha }_i>0$ are support vectors (the lecture’s wording that margin-violators “are not support vectors” is non-standard). $b$ is computed from a support vector with $0<{\alpha }_j<C$: $b=y_j-{\vec{W}}^T{\vec{X}}_j$.

Effect of $C$

Large $C$ ⇒ violations are expensive ⇒ narrow margin, few violations, risk of overfitting. Small $C$ ⇒ wide margin tolerant of violations, may underfit. Choose $C$ by cross-validation (C13).

Worked examples

Example 1 — Very Easy

• Problem: $\vec{W}=(1,0)$, $b=-1$. Compute $\gamma$ for $(3,0)+$, $(1.5,0)+$, $(0.5,0)+$, $(0,0)-$, $(1.8,1)-$.
• Asked: Slacks and categories.
• Concept: Hinge slack.
• Approach: $\gamma =\max (0,1-yf)$, $f=x_1-1$.
• Solution: $(3,0)$: $f=2$, $yf=2$, $\gamma =0$ (correct, outside margin). $(1.5,0)$: $f=0.5$, $\gamma =0.5$ (margin error). $(0.5,0)$: $f=-0.5$, $yf=-0.5$, $\gamma =1.5>1$ (misclassified). $(0,0)-$: $f=-1$, $yf=1$, $\gamma =0$ (on margin). $(1.8,1)-$: $f=0.8$, $yf=-0.8$, $\gamma =1.8$ (misclassified).
• Final answer: $\gamma =(0,0.5,1.5,0,1.8)$.
• Key lesson: $\gamma >1$ ⇔ misclassified.

Example 2 — Easy

• Problem: Compute the soft-margin objective for Example 1 with $C=1$.
• Asked: Value.
• Concept: $\frac{1}{2}\Vert \vec{W}{\Vert }^2+C\sum \gamma$.
• Approach: Sum.
• Solution: $\frac{1}{2}\Vert \vec{W}{\Vert }^2=0.5$; $\sum \gamma =0+0.5+1.5+0+1.8=3.8$. Total $=0.5+3.8=4.3$.
• Final answer: $4.3$.
• Key lesson: The penalty dominates when many points violate.

Example 3 — Moderate

• Problem: Compare candidate A: $\vec{W}=(1,0),b=-1$ (objective part: $\frac{1}{2}\Vert W{\Vert }^2=0.5$, $\sum \gamma =3.8$) with candidate B: $\vec{W}=(0.5,0),b=-0.5$. Which wins for $C=1$ and $C=10$?
• Asked: Winner vs $C$.
• Concept: Trade-off.
• Approach: Compute B’s slacks.
• Solution: B: $f=0.5x_1-0.5$. $(3,0)+$: $f=1$ ⇒ $\gamma =0$. $(1.5,0)+$: $f=0.25$ ⇒ $\gamma =0.75$. $(0.5,0)+$: $f=-0.25$ ⇒ $\gamma =1.25$. $(0,0)-$: $f=-0.5$, $yf=0.5$ ⇒ $\gamma =0.5$. $(1.8,1)-$: $f=0.4$, $yf=-0.4$ ⇒ $\gamma =1.4$. $\sum \gamma =3.9$; $\frac{1}{2}\Vert W{\Vert }^2=0.125$. Objectives: $C=1$: A $=4.3$, B $=4.025$ ⇒ B. $C=10$: A $=0.5+38=38.5$, B $=0.125+39=39.125$ ⇒ A. Break-even: $0.375-0.1C=0\Rightarrow C=3.75$.
• Final answer: B for $C<3.75$, A for $C>3.75$.
• Key lesson: Large $C$ prefers fewer violations (narrower margin); small $C$ prefers a wider margin.

Example 4 — Hard

• Problem: $C=1$; labels $y=(-1,-1,+1,+1,-1)$ and multipliers $\alpha =(1,0,0.6,1,0.6)$. (a) Check $\sum {\alpha }_i{y}_i=0$. (b) Classify each point’s status. (c) Compute ${\mu }_i$ and which ${\gamma }_i$ are forced to $0$.
• Asked: Checks and statuses.
• Concept: KKT table.
• Approach: Apply the table.
• Solution: (a) $-1-0+0.6+1-0.6=0$ ✓. (b) Point 1: $\alpha =C$ ⇒ inside margin or misclassified. Point 2: $\alpha =0$ ⇒ correct, outside margin. Point 3: $0<\alpha <C$ ⇒ on margin. Point 4: $\alpha =C$ ⇒ violator. Point 5: on margin. (c) ${\mu }_i=C-{\alpha }_i=(0,1,0.4,0,0.4)$. ${\mu }_i{\gamma }_i=0$ forces ${\gamma }_i=0$ for points 2, 3, 5. Support vectors: points 1,3,4,5.
• Final answer: 4 support vectors; two on the margin (3,5), two violators (1,4).
• Key lesson: The multipliers tell you where each point sits without looking at coordinates.

Example 5 — Very Hard

• Problem: 1-D: $x_1=2(+)$, $x_2=0(-)$ with $C=0.25$. Solve both the dual and the primal and show they agree. Compare with the hard margin ($W=1$).
• Asked: $W$, margin, slacks.
• Concept: Box constraint binds.
• Approach: Dual $L_D=2\alpha -2{\alpha }^2$ on $0\le \alpha \le C$.
• Solution: Dual: $L_D$ increases on $[0,0.5]$; with $C=0.25<0.5$ the maximum over $[0,0.25]$ is at $\alpha =C=0.25$. $W=\alpha y_1{x}_1=0.25\times 2=0.5$. Primal: with symmetry, objective $=\frac{1}{2}{W}^2+C({\gamma }_1+{\gamma }_2)$ with ${\gamma }_1=1-(2W+b)$, ${\gamma }_2=1+b$ (valid when both $>0$): ${\gamma }_1+{\gamma }_2=2-2W$, so objective $=\frac{1}{2}{W}^2+C(2-2W)$; derivative $W-2C=0\Rightarrow W=2C=0.5$ ✓ agrees. Margin $=2/W=4$ (vs $2$ hard margin). With the symmetric choice $b=-0.5$: $f(2)=0.5$ ⇒ ${\gamma }_1=0.5$; $f(0)=-0.5$ ⇒ ${\gamma }_2=0.5$. Both have $\alpha =C$ ✓.
• Final answer: $W=0.5$, margin $4$, slacks $0.5$ each; both points are margin violators with $\alpha =C$.
• Key lesson: Small $C$ widens the margin and tolerates slack; it also makes $b$ non-unique here (any $b\in [-1,0]$ gives the same objective).

Common mistakes

• Writing ${\alpha }_i\le C$ for the hard-margin case.
• Forgetting that ${\alpha }_i=C$ points are support vectors.

Exam traps

• Dual objective is identical to hard margin; only the constraints $0\le {\alpha }_i\le C$ differ.
• $C=\infty$ ⇔ hard margin; the lecture’s “range $C\in (0,\infty ]$”.
• The lecture’s remark “larger $C$ pays more attention to points near the decision boundary” is about the same effect (fewer tolerated violations).

Connections

C30, C31, hinge loss, cross-validation (C13).

Mastery checklist

• Define slack and its four cases.
• Derive the box-constrained dual.
• Classify points from ${\alpha }_i$ and $C$.

---

C33. The Kernel Trick

Intuition

If the data are not linearly separable in the original space, lift them to a higher-dimensional space where a straight cut works. Better still, never actually go there: the dual only needs inner products, and a kernel function computes the inner product in the lifted space directly from the original coordinates.

Formal definition

Feature map $\varphi :{\mathbb{R}}^m\to {\mathbb{R}}^{m^{\prime }}$ ($m^{\prime }\ge m$, possibly infinite). Kernel $K({\vec{X}}_i,{\vec{X}}_j)=\varphi ({\vec{X}}_i{)}^T\varphi ({\vec{X}}_j)$.

• Dual in feature space: $L_D=\sum {\alpha }_i-\frac{1}{2}{\sum }_{ij}{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\vec{X}}_i,{\vec{X}}_j)$, $0\le {\alpha }_i\le C$, $\sum {\alpha }_i{y}_i=0$. The dual lives in ${\mathbb{R}}^n$ — dimension does not change.
• Prediction: $\mathrm{sign}({\sum }_i{\alpha }_i{y}_{i}K({\vec{X}}_i,{\vec{X}}_0)+b)$, with $b=y_j-{\sum }_i{\alpha }_i{y}_{i}K({\vec{X}}_i,{\vec{X}}_j)$ for any $0<{\alpha }_j<C$.

Worked derivation: the polynomial kernel

$K(\vec{X},\vec{Z})=(1+{\vec{X}}^T\vec{Z}{)}^2$ for $\vec{X},\vec{Z}\in {\mathbb{R}}^2$: $(1+x_1{z}_1+x_2{z}_2{)}^2=1+2x_1{z}_1+2x_2{z}_2+x_1^2{z}_1^2+x_2^2{z}_2^2+2x_1{z}_1{x}_2{z}_2.$ This equals $\varphi (\vec{X}{)}^T\varphi (\vec{Z})$ for $\varphi (\vec{X})=[1,\sqrt{2}{x}_1,\sqrt{2}{x}_2,x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2]$ (a map ${\mathbb{R}}^2\to {\mathbb{R}}^6$): the product of corresponding entries gives each of the six terms above. In general $(1+{\vec{X}}^T\vec{Z}{)}^p$ in ${\mathbb{R}}^m$ corresponds to a feature space of dimension $\left(\genfrac{}{}{0ex}{}{m+p}{p}\right)$. The map for a given kernel is not unique (the lecture exhibits a second ${\varphi }^{\prime }$; note its printed 7-vector contains a repeated $x_{i1}{x}_{i2}$ component and omits the constant, so it should be checked before use).

Key insights

• Cost of $K$: $O(m)$; cost of explicit $\varphi$: $O(m^p)$ or infinite.
• A kernel SVM is a linear SVM in feature space, a non-linear classifier in input space.

Worked examples

Example 1 — Very Easy

• Problem: $K(\vec{X},\vec{Z})=(1+{\vec{X}}^T\vec{Z}{)}^2$ for $\vec{X}=(1,2)$, $\vec{Z}=(3,1)$.
• Asked: $K$.
• Concept: Kernel evaluation.
• Approach: Inner product first.
• Solution: ${\vec{X}}^T\vec{Z}=3+2=5$; $K=(1+5{)}^2=36$.
• Final answer: $36$.
• Key lesson: One inner product and a power — no feature map needed.

Example 2 — Easy

• Problem: Verify $K=\varphi (\vec{X}{)}^T\varphi (\vec{Z})$ for Example 1 using $\varphi (\vec{X})=[1,\sqrt{2}{x}_1,\sqrt{2}{x}_2,x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2]$.
• Asked: Same value via $\varphi$.
• Concept: Equivalence of kernel and feature map.
• Approach: Compute both vectors.
• Solution: $\varphi (1,2)=[1,1.4142,2.8284,1,4,2.8284]$; $\varphi (3,1)=[1,4.2426,1.4142,9,1,4.2426]$. Products: $1,6,4,9,4,12$. Sum $=36$ ✓.
• Final answer: $36$.
• Key lesson: The kernel hides a 6-D dot product.

Example 3 — Moderate

• Problem: (Lecture example) Positives $(1,1),(-1,1),(-1,-1),(1,-1)$; negatives $(2,0),(0,2),(-2,0),(0,-2)$. Use $\varphi (\vec{x})=\vec{x}$ if $\Vert \vec{x}\Vert <2$, else $\varphi (\vec{x})=(6-x_1+(x_1-x_2{)}^2,6-x_2+(x_1-x_2{)}^2)$. Transform all points and find a separating line.
• Asked: Images and a hyperplane.
• Concept: Explicit non-linear map.
• Approach: Compute the four negative images.
• Solution: Positives have $\Vert \vec{x}\Vert =\sqrt{2}<2$ ⇒ unchanged. Negatives (norm $=2$, so the second branch): $(2,0)\to (6-2+4,6-0+4)=(8,10)$; $(0,2)\to (6-0+4,6-2+4)=(10,8)$; $(-2,0)\to (6+2+4,6-0+4)=(12,10)$; $(0,-2)\to (6-0+4,6+2+4)=(10,12)$. Positives have $x_1+x_2\in \{-2,0,2\}$; negatives $18,18,22,22$. The line $x_1+x_2=10$ separates ($\vec{W}=(1,1)$, $b=-10$): positives give $\le 2-10<0$; negatives give $\ge 18-10>0$.
• Final answer: Separated by $x_1+x_2=10$ in the transformed space (the original space has no separating line).
• Key lesson: A well-chosen $\varphi$ turns a non-separable set into a separable one.

Example 4 — Hard

• Problem: XOR: $A=(1,1)+$, $B=(-1,-1)+$, $C=(1,-1)-$, $D=(-1,1)-$. With $K=(1+{\vec{X}}^T\vec{Z}{)}^2$ solve the hard-margin dual.
• Asked: $\alpha ,b$, classifier.
• Concept: Kernel SVM end-to-end.
• Approach: Build the Gram matrix; use symmetry.
• Solution: ${\vec{X}}^T\vec{Z}$: same point $=2$ ⇒ $K=9$; opposite points $(A,B)$ or $(C,D)$: $-2$ ⇒ $K=1$; all other pairs $0$ ⇒ $K=1$. So $K=\left(\begin{array}{cccc}9& 1& 1& 1\\ 1& 9& 1& 1\\ 1& 1& 9& 1\\ 1& 1& 1& 9\end{array}\right)$, $y=(+,+,-,-)$. By symmetry all ${\alpha }_i=\alpha$ ($\sum {\alpha }_i{y}_i=0$ ✓). ${\sum }_{ij}{y}_i{y}_j{K}_{ij}={\sum }_i{K}_{ii}+{\sum }_{i\ne j}{y}_i{y}_j(1)=36+[(\sum y{)}^2-\sum y^2]=36+(0-4)=32$. $L_D=4\alpha -16{\alpha }^2\Rightarrow \alpha =\frac{1}{8}$. Decision value at $A$: $\sum {\alpha }_i{y}_{i}K(\cdot ,A)=\frac{1}{8}(9+1-1-1)=1$; at $C$: $\frac{1}{8}(1+1-9-1)=-1$. So with $b=0$ every point satisfies $y_{i}f=1$ ✓ (all four are SVs). Classifier: $f(\vec{X})=\frac{1}{8}[K(A,\vec{X})+K(B,\vec{X})-K(C,\vec{X})-K(D,\vec{X})]$. Expanding, only the cross term survives: $f=x_1{x}_2$.
• Final answer: ${\alpha }_i=\frac{1}{8}$, $b=0$, $f(\vec{X})=x_1{x}_2$ (class $+$ iff $x_1{x}_2>0$).
• Key lesson: The classic XOR problem is linearly solvable in the feature $x_1{x}_2$; the kernel finds it automatically.

Example 5 — Very Hard

• Problem: (a) Feature-space dimension of $(1+{\vec{X}}^T\vec{Z}{)}^p$ for $m=2,p=2$; $m=10,p=3$; $m=1000,p=3$. (b) Show the Gaussian kernel’s feature space is infinite-dimensional. (c) Cost comparison for $m=1000$, $p=3$.
• Asked: Dimensions and argument.
• Concept: Why kernels matter.
• Approach: $\left(\genfrac{}{}{0ex}{}{m+p}{p}\right)$; Taylor series.
• Solution: (a) $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$; $\left(\genfrac{}{}{0ex}{}{13}{3}\right)=286$; $\left(\genfrac{}{}{0ex}{}{1003}{3}\right)=167,668,501$. (b) $e^{-\Vert \vec{X}-\vec{Z}{\Vert }^2/2{\sigma }^2}=e^{-\Vert \vec{X}{\Vert }^2/2{\sigma }^2}{e}^{-\Vert \vec{Z}{\Vert }^2/2{\sigma }^2}{e}^{{\vec{X}}^T\vec{Z}/{\sigma }^2}$, and $e^u={\sum }_{k=0}^{\infty }\frac{u^k}{k!}$ with $u={\vec{X}}^T\vec{Z}/{\sigma }^2$. Each term $({\vec{X}}^T\vec{Z}{)}^k$ is a polynomial kernel of degree $k$ with its own feature space; the sum over all $k$ gives infinitely many features. (c) $K$: about $1000$ multiplications + a cube; $\varphi$: $\approx 1.7\times 10^8$ coordinates per point.
• Final answer: $6$, $286$, $167,668,501$; Gaussian: $\infty$.
• Key lesson: The trick turns an intractable (or impossible) computation into $O(m)$.

Common mistakes

• Computing $\varphi$ explicitly when a kernel is available.
• Forgetting to use the kernel in prediction as well as training.

Exam traps

• Dual has $n$ variables regardless of $\varphi$‘s dimension.
• $K({\vec{X}}_i,{\vec{X}}_j)=\varphi ({\vec{X}}_i{)}^T\varphi ({\vec{X}}_j)$; $\varphi$ need not be unique.

Connections

C31, C32, C34.

Mastery checklist

• Write the kernelised dual and predictor.
• Derive the quadratic-kernel feature map.
• Solve XOR with a kernel.

---

C34. Valid Kernels: Symmetry, Positive Semidefiniteness, Mercer; Popular Kernels

Intuition

Not every similarity function is an inner product in some space. A function qualifies only if every Gram matrix it generates is symmetric and positive semidefinite (PSD) — i.e. behaves like a matrix of dot products.

Formal conditions

1. Symmetric: $K({\vec{X}}_i,{\vec{X}}_j)=K({\vec{X}}_j,{\vec{X}}_i)$.
2. Positive semidefinite: for every $n$, points ${\vec{X}}_1..{\vec{X}}_n$ and scalars ${\lambda }_i$: ${\sum }_{i,j}{\lambda }_i{\lambda }_{j}K({\vec{X}}_i,{\vec{X}}_j)\ge 0$, i.e. the Gram matrix $K_{ij}$ is PSD (all eigenvalues $\ge 0$).
3. Mercer’s theorem: for a symmetric $K$ with $\iint G(\vec{X})K(\vec{X},\vec{Y})G(\vec{Y})d\vec{X}d\vec{Y}\ge 0$ for all square-integrable $G$, there is a space $H$ and map $\varphi$ with $K={\varphi }^T\varphi$. Popular kernels

• Polynomial: $K({\vec{X}}_i,{\vec{X}}_j)=(1+{\vec{X}}_i^T{\vec{X}}_j{)}^p$.
• Gaussian/RBF: $K({\vec{X}}_i,{\vec{X}}_j)=\exp (-\Vert {\vec{X}}_i-{\vec{X}}_j{\Vert }^2/2{\sigma }^2)$, $\sigma >0$ (the lecture prints $e^{+\Vert \cdot {\Vert }^2/2{\sigma }^2}$, which is a typo — see Example 4).
• Sigmoid: $K=\tanh (a{\vec{X}}_i^T{\vec{X}}_j+\theta )$ — not PSD for all parameters.

Derivation: an explicit-feature kernel is PSD

If $K(\vec{X},\vec{Z})=\varphi (\vec{X}{)}^T\varphi (\vec{Z})$ then ${\sum }_{ij}{\lambda }_i{\lambda }_j{K}_{ij}=\Vert {\sum }_i{\lambda }_i\varphi ({\vec{X}}_i){\Vert }^2\ge 0$. ∎

Closure properties (standard)

Sum of kernels, positive scalar multiple, and product of kernels are kernels.

Worked examples

Example 1 — Very Easy

• Problem: Is $K(x,z)=x-z$ a valid kernel?
• Asked: Validity.
• Concept: Symmetry.
• Approach: Swap arguments.
• Solution: $K(z,x)=z-x=-K(x,z)\ne K(x,z)$ unless $x=z$ ⇒ not symmetric.
• Final answer: No.
• Key lesson: Check symmetry first (it is the cheapest test).

Example 2 — Easy

• Problem: Which Gram matrix can come from a kernel: $G_1=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$ or $G_2=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$?
• Asked: PSD test.
• Concept: Eigenvalues.
• Approach: Eigenvalues of $\left(\begin{array}{cc}a& b\\ b& a\end{array}\right)$ are $a\pm b$.
• Solution: $G_1$: $3,-1$ ⇒ not PSD (the vector $\lambda =(1,-1)$ gives ${\lambda }^T{G}_1\lambda =G_{11}-2G_{12}+G_{22}=1-4+1=-2<0$). $G_2$: $3,1$ ⇒ PSD.
• Final answer: $G_2$ only.
• Key lesson: A negative eigenvalue disqualifies.

Example 3 — Moderate

• Problem: Prove that $K(\vec{X},\vec{Z})=(1+{\vec{X}}^T\vec{Z}{)}^2$ is PSD.
• Asked: Proof.
• Concept: Explicit feature map.
• Approach: Use the $\varphi$ from C33.
• Solution: $K=\varphi (\vec{X}{)}^T\varphi (\vec{Z})$ with $\varphi \in {\mathbb{R}}^6$ ⇒ ${\sum }_{ij}{\lambda }_i{\lambda }_j{K}_{ij}=\Vert {\sum }_i{\lambda }_i\varphi ({\vec{X}}_i){\Vert }^2\ge 0$.
• Final answer: PSD.
• Key lesson: Exhibiting $\varphi$ is the cleanest proof of validity.

Example 4 — Hard

• Problem: Points $x=0$ and $x=1$ (1-D), $\sigma =1$. Build the Gram matrix for (a) $K=e^{-(x-z{)}^2/2}$ and (b) the lecture’s printed $e^{+(x-z{)}^2/2}$. Check PSD.
• Asked: Which is valid.
• Concept: PSD check; sign typo.
• Approach: Eigenvalues of a $2\times 2$ symmetric matrix $\left(\begin{array}{cc}1& c\\ c& 1\end{array}\right)$ are $1\pm c$.
• Solution: (a) $c=e^{-0.5}=0.6065$: eigenvalues $1.6065,0.3935>0$ ✓. (b) $c=e^{0.5}=1.6487$: eigenvalues $2.6487,-0.6487<0$ ✗.
• Final answer: Only the negative exponent gives a valid kernel.
• Key lesson: Similarity must decrease with distance; the lecture’s printed sign is a typo.

Example 5 — Very Hard

• Problem: (a) Show the sigmoid kernel $\tanh (axz+\theta )$ with $a=1,\theta =1$ fails PSD using points $x=1$ and $x=2$. (b) Show closure: if $K_1,K_2$ are kernels then $K_1+K_2$ is; give a valid composite such as $(1+{\vec{X}}^T\vec{Z}{)}^2+e^{-\Vert \vec{X}-\vec{Z}{\Vert }^2/2}$.
• Asked: Counter-example and closure proof.
• Concept: Mercer validity.
• Approach: Determinant of the Gram matrix.
• Solution: (a) $K_{11}=\tanh (1+1)=0.96403$; $K_{22}=\tanh (4+1)=0.99991$; $K_{12}=\tanh (2+1)=0.99505$. $\det =0.96403(0.99991)-0.99505^2=0.96394-0.99013=-0.0262<0$ ⇒ one negative eigenvalue (about $-0.0132$) ⇒ not PSD even though $a,\theta >0$. (b) $\sum {\lambda }_i{\lambda }_j(K_1+K_2{)}_{ij}=\sum {\lambda }_i{\lambda }_j(K_1{)}_{ij}+\sum {\lambda }_i{\lambda }_j(K_2{)}_{ij}\ge 0+0$ ✓. The composite is a sum of the polynomial and the Gaussian kernels, both valid, hence valid.
• Final answer: Sigmoid kernel is not guaranteed valid; sums of kernels are kernels.
• Key lesson: Validity depends on parameters; verify before relying on the dual being concave.

Common mistakes

• Believing any similarity score is a kernel.
• Forgetting that the Gaussian kernel has a negative exponent.

Exam traps

• PSD must hold for all $n$ and point sets.
• RBF kernel SVM $=$ a Gaussian RBF network whose centres are the support vectors (lecture): $f(\vec{X})={\sum }_{j\in SV}{\alpha }_j{y}_j{e}^{-\Vert {\vec{X}}_j-\vec{X}{\Vert }^2/2{\sigma }^2}+b$.

Connections

C33; Gaussian-kernel bandwidth $\sigma$ and $C$ tuned by cross-validation (C13).

Mastery checklist

• State symmetric + PSD + Mercer.
• Test PSD by eigenvalues of a Gram matrix.
• Write the Gaussian-kernel decision function.