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. · Prev: Module 5 · Next: Module 7 — Clustering · Index: 00_INDEX_and_Coverage

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)$.

Python helpers — run once, the checks below reuse them

import numpy as np
from sklearn.svm import SVC
def hard_svm(X, y):                     # huge C ≈ hard margin
    return SVC(kernel="linear", C=1e8).fit(X, y)
# m.coef_ = W,  m.intercept_ = b,  m.dual_coef_ = α_i y_i for the support vectors m.support_

flowchart LR
    A["Hard margin<br/>separable data<br/>C30–C31"] -->|"allow slack γ"| B["Soft margin<br/>0 ≤ α ≤ C<br/>C32"]
    B -->|"replace X·X' by K(X, X')"| C["Kernel SVM<br/>non-linear boundary<br/>C33–C34"]

---

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. It is safer on new data. The few points that touch the edges of the street (support vectors) alone determine the answer.

 x2
  |   B   B                B = negative, A = positive
  |     B   ╲  ╲  ╲        |<— margin 2/‖W‖ —>|
  |  - - - - ╲ - ╲ - -   ← W·x + b = −1
  |           ╲  ╲        ← W·x + b =  0   (decision boundary)
  |  - - - - - -╲- ╲ -   ← W·x + b = +1
  |        A   A   A
  +--------------------→ x1     (points on the dashed lines = support vectors)

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; the distance of the hyperplane from the origin is $|b|/\Vert \vec{W}\Vert$; the 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 fix the scale so that the closest points satisfy $y_i({\vec{W}}^T{\vec{X}}_i+b)=1$ (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).
• Geometric view: the optimal margin equals the distance between the two convex hulls.

Worked examples

Example 1 — Very Easy · Distance to a hyperplane

• 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 =5$. Distance $=1$.
• Final answer: $1$.

Key lesson

Distance is the signed value divided by $\Vert \vec{W}\Vert$.

Example 2 — Easy · Margin from $\Vert \vec{W}\Vert$

• 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 · One point per class

• 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 $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.828$ = distance between the two points $\sqrt{8}=2.828$ ✓.
• Final answer: $\vec{W}=(0.5,0.5)$, $b=-1$, margin $2.83$.

Python check

m = hard_svm([[2, 2], [0, 0]], [1, -1]); print(m.coef_, m.intercept_, 2 / np.linalg.norm(m.coef_))
# [[0.5 0.5]] [-1.]  2.828

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 · Feasibility and support vectors

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

Python check

X = np.array([[2,2],[3,3],[1,1],[0,0]]); y = np.array([1,1,-1,-1])
print(y * (X @ [1, 1] - 3))                              # [1 3 1 3]  -> SVs are rows 0 and 2

Key lesson

Only points with value exactly $1$ are support vectors.

Example 5 — Very Hard · XOR is not separable

• 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 a different labelling of the same four points (positives $(0,0),(1,0)$, negatives $(0,1),(1,1)$) is separable.
• Asked: Hull intersection.
• Concept: Hull criterion.
• Approach: Find a common convex combination.
• Solution: The positive hull contains $\frac{1}{2}(0,0)+\frac{1}{2}(1,1)=(0.5,0.5)$. The 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 labelling: 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 labelling is separable.

   XOR (not separable)         separable
 (0,1)−     (1,1)+            (0,1)−   (1,1)−
    ╲       ╱                 ─────────────── x2 = 0.5
     ● (0.5,0.5) ← hulls      (0,0)+   (1,0)+
    ╱       ╲   cross
 (0,0)+     (1,0)−

Python check

m = hard_svm([[0,0],[1,0],[0,1],[1,1]], [1, 1, -1, -1]); print(m.coef_, m.intercept_)   # [[ 0. -2.]] [1.]

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 only).

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 · The 1-D dual

• 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=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 the points ✓.
• Final answer: $\alpha =(0.5,0.5)$, $W=1$, $b=-1$.

Python check

m = hard_svm([[2], [0]], [1, -1]); print(m.coef_, m.intercept_, m.dual_coef_)   # [[1.]] [-1.] [[-0.5  0.5]]  (= α_i y_i)

Key lesson

The constraint $\sum {\alpha }_i{y}_i=0$ ties the multipliers together.

Example 2 — Easy · Two points in 2-D

• 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: ${\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=0$. Margin $=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 · From α back to W and b

• 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 the primal from the 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$; 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 $+,-$.

Python check

m = hard_svm([[2,0],[0,2],[0,0]], [1, 1, -1])
print(np.round(m.coef_, 3), np.round(m.intercept_, 3), m.predict([[3, 1], [.5, .2]]))   # ≈[[1 1]] ≈[-1]  [ 1 -1]

Key lesson

Two different SVs must give the same $b$ (a consistency check).

Example 4 — Hard · A support vector with α = 0

• 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: Geometry first (margin = distance between the hulls), then recover $\alpha$.
• Solution: The negative hull is the segment from $(0,0)$ to $(2,0)$. The point of it closest to $(2,2)$ is $(2,0)$, at distance $2$. So the margin is $2$, the boundary is the horizontal line halfway: $\vec{W}=(0,1)$, $b=-1$. Check: $(2,2)$: $2-1=1$; $(0,0)$: $-(0-1)=1$; $(2,0)$: $-(0-1)=1$ — all three lie on the margin. Dual: $\vec{W}={\alpha }_1(2,2)-{\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)$.

Python check

m = hard_svm([[2,2],[0,0],[2,0]], [1, -1, -1])
print(m.coef_, m.intercept_, m.support_, m.dual_coef_)     # [[0. 1.]] [-1.]  [2 0]  → point 1 (0,0) is NOT a support vector

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 · Strong duality check

• 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=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+1)=1$ ✓ equal ⇒ strong duality. KKT: all three constraints tight ($y_i{f}_i=1$ for each) ⇒ 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.

Python check

X = np.array([[2,0],[0,2],[0,0]], float); y = np.array([1, 1, -1]); a = np.array([.5, .5, 1])
Q = (y[:, None] * y[None, :]) * (X @ X.T)
print(a.sum() - .5 * a @ Q @ a, .5 * (X.T @ (a * y)) @ (X.T @ (a * y)))   # 1.0  1.0

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 just $\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 the 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).

slack	meaning
$\gamma =0$	correct and outside the margin
$0<\gamma <1$	inside the margin but correctly classified (margin error)
$\gamma =1$	exactly 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 · Compute the slacks

• 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$, $\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)$.

Python helper for Examples 1–3

X = np.array([[3,0],[1.5,0],[.5,0],[0,0],[1.8,1]]); y = np.array([1, 1, 1, -1, -1])
def objective(W, b, C):
    W = np.asarray(W, float); g = np.maximum(0, 1 - y * (X @ W + b))
    return g, .5 * W @ W + C * g.sum()
print(objective([1, 0], -1, 1))        # slacks [0 .5 1.5 0 1.8], objective 4.3

Key lesson

$\gamma >1$ ⇔ misclassified.

Example 2 — Easy · The objective value

• 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 =3.8$. Total $=4.3$.
• Final answer: $4.3$.

Key lesson

The penalty dominates when many points violate.

Example 3 — Moderate · The effect of C

• 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)+$: $\gamma =0$. $(1.5,0)+$: $\gamma =0.75$. $(0.5,0)+$: $\gamma =1.25$. $(0,0)-$: $\gamma =0.5$. $(1.8,1)-$: $\gamma =1.4$. $\sum \gamma =3.9$; $\frac{1}{2}\Vert W{\Vert }^2=0.125$. $C=1$: A $=4.3$, B $=4.025$ ⇒ B. $C=10$: A $=38.5$, B $=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$.

Python check

for C in (1, 3.75, 10):
    print(C, objective([1, 0], -1, C)[1], objective([.5, 0], -.5, C)[1])   # B wins below 3.75, A above

Key lesson

Large $C$ prefers fewer violations (narrower margin); small $C$ prefers a wider margin.

Example 4 — Hard · Read the multipliers

• 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 · A small C widens the margin

• 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: The 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 $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$.

Python check

m = SVC(kernel="linear", C=0.25).fit([[2], [0]], [1, -1])
print(m.coef_, m.intercept_, m.dual_coef_)               # [[0.5]] [-0.5] [[-0.25  0.25]]   (α = C)

Key lesson

Small $C$ widens the margin and tolerates slack; here it also makes $b$ non-unique (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

• The 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 is $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.

 1-D: − − [+ + +] − −          lift x → (x, x²)        x²
       not separable        ───────────────────►        |  −          −
                                                         |    + + +        a straight line
                                                         |  ───────────    now separates
                                                         +--------------→ x

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$ — its 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 }$; its printed 7-vector contains a repeated $x_{i1}{x}_{i2}$ component and omits the constant, so check it 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 · Evaluate a kernel

• 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 · Check against φ

• 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$.

Python check

phi = lambda x: np.array([1, 2**.5*x[0], 2**.5*x[1], x[0]**2, x[1]**2, 2**.5*x[0]*x[1]])
print(phi((1, 2)) @ phi((3, 1)), (1 + 5)**2)             # 36.0  36

Key lesson

The kernel hides a 6-D dot product.

Example 3 — Moderate · An explicit non-linear map (lecture)

• Problem: 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$): $(2,0)\to (8,10)$; $(0,2)\to (10,8)$; $(-2,0)\to (12,10)$; $(0,-2)\to (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$).
• Final answer: Separated by $x_1+x_2=10$ in the transformed space (the original space has no separating line — the negatives form a ring around the positives).

Key lesson

A well-chosen $\varphi$ turns a non-separable set into a separable one.

Example 4 — Hard · XOR with a quadratic kernel

• 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: $-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 }_{ij}{y}_i{y}_j{K}_{ij}=36+[(\sum y{)}^2-\sum y^2]=36-4=32$. $L_D=4\alpha -16{\alpha }^2\Rightarrow \alpha =\frac{1}{8}$. Decision value at $A$: $\frac{1}{8}(9+1-1-1)=1$; at $C$: $\frac{1}{8}(1+1-9-1)=-1$. With $b=0$ every point satisfies $y_{i}f=1$ ✓ (all four are SVs). Expanding the kernel, 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$).

Python check

Xs = np.array([[1,1],[-1,-1],[1,-1],[-1,1]]); ys = np.array([1, 1, -1, -1])
m = SVC(kernel="poly", degree=2, gamma=1, coef0=1, C=1e8).fit(Xs, ys)
print(m.dual_coef_, m.intercept_)                        # α_i y_i = ±0.125, b ≈ 0
print(m.decision_function([[.5, .5], [.5, -.5], [2, 3]]))   # 0.25  -0.25  6.0   =  x1·x2 ✓

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 · How big is the feature space?

• 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$.

Python check

from math import comb
print(comb(4, 2), comb(13, 3), comb(1003, 3))            # 6  286  167668501

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

• The 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}$, 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.

Python helper for the checks in this section

def is_psd(G, tol=1e-10):
    G = np.asarray(G, float); return np.allclose(G, G.T) and np.linalg.eigvalsh(G).min() >= -tol

Worked examples

Example 1 — Very Easy · Is $x-z$ a kernel?

• 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 · Which Gram matrix is legal?

• 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 =1-4+1=-2<0$). $G_2$: $3,1$ ⇒ PSD.
• Final answer: $G_2$ only.

Python check

print(is_psd([[1, 2], [2, 1]]), is_psd([[2, 1], [1, 2]]))          # False  True

Key lesson

A negative eigenvalue disqualifies.

Example 3 — Moderate · Prove the polynomial kernel is PSD

• 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 · The sign typo in the Gaussian kernel

• 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 $\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.

Python check

c = np.exp(-.5); print(np.linalg.eigvalsh([[1, c], [c, 1]]))       # [0.3935 1.6065]
c = np.exp(+.5); print(np.linalg.eigvalsh([[1, c], [c, 1]]))       # [-0.6487 2.6487]  ← invalid

Key lesson

Similarity must decrease with distance; the lecture’s printed sign is a typo.

Example 5 — Very Hard · A broken sigmoid kernel and closure

• 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 (2)=0.96403$; $K_{22}=\tanh (5)=0.99991$; $K_{12}=\tanh (3)=0.99505$. $\det =0.96394-0.99013=-0.0262<0$ ⇒ one negative eigenvalue ($\approx -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 Gaussian kernels, both valid, hence valid.
• Final answer: The sigmoid kernel is not guaranteed valid; sums of kernels are kernels.

Python check

G = np.tanh(np.array([[1*1 + 1, 1*2 + 1], [1*2 + 1, 2*2 + 1]]))
print(np.linalg.det(G), np.linalg.eigvalsh(G))                      # -0.0262  [-0.0132  1.9772]

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.