09 Support Vector Machines — Exercises¶

Test your understanding of margin geometry, hinge loss, sub-gradient computation, and the role of support vectors.

Prerequisites. Read theory.md and work through first_principles.ipynb before attempting these.

In [1]:

import random

import matplotlib.pyplot as plt
import numpy as np

%load_ext autoreload
%autoreload 2

SEED = 42
random.seed(SEED)
rng = np.random.default_rng(SEED)

plt.rcParams["figure.dpi"] = 90

import random import matplotlib.pyplot as plt import numpy as np %load_ext autoreload %autoreload 2 SEED = 42 random.seed(SEED) rng = np.random.default_rng(SEED) plt.rcParams["figure.dpi"] = 90

Exercise 1 — Hand Calculation: Margin and Support Vectors¶

Consider the following 4 points in 2D with labels $y_i \in \{-1, +1\}$:

Point	$x_1$	$x_2$	$y_i$
A	1	1	+1
B	2	2	+1
C	−1	−1	−1
D	−2	0	−1

Suppose the SVM finds the separating hyperplane $w^T x + b = 0$ with $w = [1, 1]$ and $b = 0$.

Tasks (compute by hand, then verify numerically):

1. Compute the functional margin $y_i(w^T x_i + b)$ for each point.
2. Compute the geometric margin $\frac{y_i(w^T x_i + b)}{\|w\|}$ for each point.
3. What is the margin of the classifier (minimum geometric margin)?
4. Which points are the support vectors (closest to the boundary)?
5. What is the margin width $2 / \|w\|$?

Expected results:

Point	Functional margin	Geometric margin
A	$1 \cdot (1+1+0) = 2$	$2 / \sqrt{2} \approx 1.4142$
B	$1 \cdot (2+2+0) = 4$	$4 / \sqrt{2} \approx 2.8284$
C	$-1 \cdot (-1-1+0) = 2$	$2 / \sqrt{2} \approx 1.4142$
D	$-1 \cdot (-2+0+0) = 2$	$2 / \sqrt{2} \approx 1.4142$

Minimum geometric margin = $\sqrt{2} \approx 1.4142$. Support vectors: A, C, D. Margin width = $2/\sqrt{2} = \sqrt{2} \approx 1.4142$.

In [2]:

# Verify your hand calculations
X_ex1 = np.array([[1, 1], [2, 2], [-1, -1], [-2, 0]], dtype=float)
y_ex1 = np.array([1, 1, -1, -1], dtype=float)
w_ex1 = np.array([1.0, 1.0])
b_ex1 = 0.0

# Functional margins
func_margins = y_ex1 * (X_ex1 @ w_ex1 + b_ex1)
print(f'Functional margins: {func_margins}')

# Geometric margins
w_norm = np.linalg.norm(w_ex1)
geom_margins = func_margins / w_norm
print(f'Geometric margins:  {geom_margins}')
print(f'||w|| = {w_norm:.4f}')

# Margin of the classifier
classifier_margin = np.min(geom_margins)
print(f'Classifier margin (min geometric margin): {classifier_margin:.4f}')

# Margin width
margin_width = 2.0 / w_norm
print(f'Margin width (2/||w||): {margin_width:.4f}')

# Verify expected values
assert np.allclose(func_margins, [2, 4, 2, 2], atol=1e-10)
assert np.isclose(classifier_margin, np.sqrt(2), atol=1e-10)
assert np.isclose(margin_width, np.sqrt(2), atol=1e-10)

# Support vectors: points with minimum geometric margin
sv_mask = np.isclose(geom_margins, classifier_margin, atol=1e-10)
print(f'\nSupport vector indices: {np.where(sv_mask)[0]}  (A=0, C=2, D=3)')
print('All hand calculation checks passed.')

# Verify your hand calculations X_ex1 = np.array([[1, 1], [2, 2], [-1, -1], [-2, 0]], dtype=float) y_ex1 = np.array([1, 1, -1, -1], dtype=float) w_ex1 = np.array([1.0, 1.0]) b_ex1 = 0.0 # Functional margins func_margins = y_ex1 * (X_ex1 @ w_ex1 + b_ex1) print(f'Functional margins: {func_margins}') # Geometric margins w_norm = np.linalg.norm(w_ex1) geom_margins = func_margins / w_norm print(f'Geometric margins: {geom_margins}') print(f'||w|| = {w_norm:.4f}') # Margin of the classifier classifier_margin = np.min(geom_margins) print(f'Classifier margin (min geometric margin): {classifier_margin:.4f}') # Margin width margin_width = 2.0 / w_norm print(f'Margin width (2/||w||): {margin_width:.4f}') # Verify expected values assert np.allclose(func_margins, [2, 4, 2, 2], atol=1e-10) assert np.isclose(classifier_margin, np.sqrt(2), atol=1e-10) assert np.isclose(margin_width, np.sqrt(2), atol=1e-10) # Support vectors: points with minimum geometric margin sv_mask = np.isclose(geom_margins, classifier_margin, atol=1e-10) print(f'\nSupport vector indices: {np.where(sv_mask)[0]} (A=0, C=2, D=3)') print('All hand calculation checks passed.')

Functional margins: [2. 4. 2. 2.]
Geometric margins:  [1.41421356 2.82842712 1.41421356 1.41421356]
||w|| = 1.4142
Classifier margin (min geometric margin): 1.4142
Margin width (2/||w||): 1.4142

Support vector indices: [0 2 3]  (A=0, C=2, D=3)
All hand calculation checks passed.

Exercise 2 — Coding: Hinge Loss and Sub-Gradient¶

Implement the hinge loss and its sub-gradient for a linear SVM.

Hinge loss for one example: $$\ell_i = \max(0, 1 - y_i(w^T x_i + b))$$

Full objective: $$L(w, b) = \frac{1}{2}\|w\|^2 + C \cdot \frac{1}{n} \sum_{i=1}^n \max(0, 1 - y_i(w^T x_i + b))$$

Sub-gradient w.r.t. $w$: $$g_w = w - \frac{C}{n} \sum_{i:\, y_i f(x_i) < 1} y_i x_i$$

Sub-gradient w.r.t. $b$: $$g_b = -\frac{C}{n} \sum_{i:\, y_i f(x_i) < 1} y_i$$

Tasks:

1. Implement hinge_loss(X, y, w, b, C) returning the full objective value.
2. Implement hinge_subgradient(X, y, w, b, C) returning (g_w, g_b).
3. Verify on the test data below.

Test data: $X = [[1, 0], [0, 1], [-1, 0], [0, -1]]$, $y = [1, 1, -1, -1]$, $w = [0.5, 0.5]$, $b = 0$, $C = 1.0$.

Expected:

• Functional margins: $[0.5, 0.5, 0.5, 0.5]$ — all violate ($< 1$)
• Per-example hinge losses: $[0.5, 0.5, 0.5, 0.5]$
• Objective: $0.5 \cdot (0.25 + 0.25) + 1.0 \cdot 0.5 = 0.75$
• $g_w = [0.5, 0.5] - \frac{1}{4}([1, 0] + [0, 1] - [-1, 0] - [0, -1]) = [0.5, 0.5] - [0.5, 0.5] = [0, 0]$
• $g_b = -\frac{1}{4}(1 + 1 - (-1) - (-1)) = -\frac{4}{4} = 0$ ... wait, let me recalculate.

Actually: $g_w = w - C/n \sum y_i x_i$ over violators. All 4 violate.

• $\sum y_i x_i = 1 \cdot [1,0] + 1 \cdot [0,1] + (-1)\cdot[-1,0] + (-1)\cdot[0,-1] = [1,0]+[0,1]+[1,0]+[0,1] = [2,2]$
• $g_w = [0.5, 0.5] - (1.0/4) \cdot [2, 2] = [0.5, 0.5] - [0.5, 0.5] = [0, 0]$
• $\sum y_i = 1 + 1 + (-1) + (-1) = 0 \implies g_b = 0$

In [3]:

def hinge_loss(X, y, w, b, C=1.0):
    """Compute SVM objective: 0.5*||w||^2 + C*mean(hinge)."""
    # TODO: implement
    pass


def hinge_subgradient(X, y, w, b, C=1.0):
    """Compute sub-gradients (g_w, g_b) of the SVM objective."""
    # TODO: implement
    pass

def hinge_loss(X, y, w, b, C=1.0): """Compute SVM objective: 0.5*||w||^2 + C*mean(hinge).""" # TODO: implement pass def hinge_subgradient(X, y, w, b, C=1.0): """Compute sub-gradients (g_w, g_b) of the SVM objective.""" # TODO: implement pass

Solution 2¶

In [4]:

def hinge_loss(X, y, w, b, C=1.0):
    """Compute SVM objective: 0.5*||w||^2 + C*mean(hinge)."""
    margins = y * (X @ w + b)
    hinge = np.maximum(0.0, 1.0 - margins)
    return 0.5 * np.dot(w, w) + C * np.mean(hinge)


def hinge_subgradient(X, y, w, b, C=1.0):
    """Compute sub-gradients (g_w, g_b) of the SVM objective."""
    margins = y * (X @ w + b)
    violating = margins < 1.0
    n = len(y)
    g_w = w - (C / n) * (y[violating] @ X[violating])
    g_b = -(C / n) * np.sum(y[violating])
    return g_w, g_b


# Deterministic check
X_ex2 = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]], dtype=float)
y_ex2 = np.array([1, 1, -1, -1], dtype=float)
w_ex2 = np.array([0.5, 0.5])
b_ex2 = 0.0
C_ex2 = 1.0

loss_val = hinge_loss(X_ex2, y_ex2, w_ex2, b_ex2, C_ex2)
g_w, g_b = hinge_subgradient(X_ex2, y_ex2, w_ex2, b_ex2, C_ex2)

print(f'Objective: {loss_val:.4f}  (expected 0.7500)')
print(f'g_w: {g_w}  (expected [0, 0])')
print(f'g_b: {g_b:.4f}  (expected 0.0)')

assert np.isclose(loss_val, 0.75, atol=1e-10), f'Loss should be 0.75, got {loss_val}'
assert np.allclose(g_w, [0.0, 0.0], atol=1e-10), f'g_w should be [0, 0], got {g_w}'
assert np.isclose(g_b, 0.0, atol=1e-10), f'g_b should be 0, got {g_b}'
print('All hinge loss checks passed.')

def hinge_loss(X, y, w, b, C=1.0): """Compute SVM objective: 0.5*||w||^2 + C*mean(hinge).""" margins = y * (X @ w + b) hinge = np.maximum(0.0, 1.0 - margins) return 0.5 * np.dot(w, w) + C * np.mean(hinge) def hinge_subgradient(X, y, w, b, C=1.0): """Compute sub-gradients (g_w, g_b) of the SVM objective.""" margins = y * (X @ w + b) violating = margins < 1.0 n = len(y) g_w = w - (C / n) * (y[violating] @ X[violating]) g_b = -(C / n) * np.sum(y[violating]) return g_w, g_b # Deterministic check X_ex2 = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]], dtype=float) y_ex2 = np.array([1, 1, -1, -1], dtype=float) w_ex2 = np.array([0.5, 0.5]) b_ex2 = 0.0 C_ex2 = 1.0 loss_val = hinge_loss(X_ex2, y_ex2, w_ex2, b_ex2, C_ex2) g_w, g_b = hinge_subgradient(X_ex2, y_ex2, w_ex2, b_ex2, C_ex2) print(f'Objective: {loss_val:.4f} (expected 0.7500)') print(f'g_w: {g_w} (expected [0, 0])') print(f'g_b: {g_b:.4f} (expected 0.0)') assert np.isclose(loss_val, 0.75, atol=1e-10), f'Loss should be 0.75, got {loss_val}' assert np.allclose(g_w, [0.0, 0.0], atol=1e-10), f'g_w should be [0, 0], got {g_w}' assert np.isclose(g_b, 0.0, atol=1e-10), f'g_b should be 0, got {g_b}' print('All hinge loss checks passed.')

Objective: 0.7500  (expected 0.7500)
g_w: [0. 0.]  (expected [0, 0])
g_b: -0.0000  (expected 0.0)
All hinge loss checks passed.

In [5]:

# Extra check: non-symmetric case
w_ex2b = np.array([1.0, 0.0])
b_ex2b = 0.5

# Functional margins:
# A: 1*(1*1 + 0*0 + 0.5) = 1.5 → hinge = 0
# B: 1*(1*0 + 0*1 + 0.5) = 0.5 → hinge = 0.5
# C: -1*(1*(-1) + 0*0 + 0.5) = -1*(-0.5) = 0.5 → hinge = 0.5
# D: -1*(1*0 + 0*(-1) + 0.5) = -1*(0.5) = -0.5 → hinge = 1.5

loss_val_b = hinge_loss(X_ex2, y_ex2, w_ex2b, b_ex2b, C_ex2)
expected_loss_b = 0.5 * 1.0 + 1.0 * np.mean([0, 0.5, 0.5, 1.5])
print(f'Objective: {loss_val_b:.4f}  (expected {expected_loss_b:.4f})')
assert np.isclose(loss_val_b, expected_loss_b, atol=1e-10)
print('Extra check passed.')

# Extra check: non-symmetric case w_ex2b = np.array([1.0, 0.0]) b_ex2b = 0.5 # Functional margins: # A: 1*(1*1 + 0*0 + 0.5) = 1.5 → hinge = 0 # B: 1*(1*0 + 0*1 + 0.5) = 0.5 → hinge = 0.5 # C: -1*(1*(-1) + 0*0 + 0.5) = -1*(-0.5) = 0.5 → hinge = 0.5 # D: -1*(1*0 + 0*(-1) + 0.5) = -1*(0.5) = -0.5 → hinge = 1.5 loss_val_b = hinge_loss(X_ex2, y_ex2, w_ex2b, b_ex2b, C_ex2) expected_loss_b = 0.5 * 1.0 + 1.0 * np.mean([0, 0.5, 0.5, 1.5]) print(f'Objective: {loss_val_b:.4f} (expected {expected_loss_b:.4f})') assert np.isclose(loss_val_b, expected_loss_b, atol=1e-10) print('Extra check passed.')

Objective: 1.1250  (expected 1.1250)
Extra check passed.

Exercise 3 — Conceptual: Support Vector Sparsity¶

Questions:

1. Why do only support vectors matter? The SVM solution $w = \sum_i \alpha_i y_i x_i$ has $\alpha_i > 0$ only for support vectors. Explain geometrically why a point far from the margin boundary has no influence on the optimal hyperplane.

2. What happens if you remove a non-support-vector point? Suppose point B (from Exercise 1) is removed from the dataset. Does the optimal hyperplane change? Why or why not?

3. What happens if you remove a support vector? Now remove point A (a support vector) instead. Will the optimal hyperplane change? Explain.

4. SVM vs Logistic Regression sparsity. Logistic regression's gradient involves all training points via the residual $p_i - y_i$. SVM's sub-gradient involves only violating points. Connect this to the difference between the hinge loss (flat for $m \ge 1$) and the log-loss (always positive). Why does the hinge loss produce sparsity in the dual ($\alpha_i = 0$ for non-SVs) while the log-loss does not?

In [6]:

# Experimental verification for Q2 and Q3
# Using sklearn SVC which solves the dual exactly and reports support vectors
from sklearn.svm import SVC

X_full = np.array([[1, 1], [2, 2], [-1, -1], [-2, 0]], dtype=float)
y_full = np.array([1, 1, -1, -1])

# Full dataset
svc_full = SVC(kernel='linear', C=100.0)  # large C ≈ hard margin
svc_full.fit(X_full, y_full)
print('=== Full dataset ===')
print(f'w = {svc_full.coef_[0]}, b = {svc_full.intercept_[0]:.4f}')
print(f'Support vector indices: {svc_full.support_}')

# TODO: Remove point B (index 1, a non-SV) and retrain.
# Does the hyperplane change?
# X_no_B = ...
# y_no_B = ...

# TODO: Remove point A (index 0, a SV) and retrain.
# Does the hyperplane change?
# X_no_A = ...
# y_no_A = ...

# Experimental verification for Q2 and Q3 # Using sklearn SVC which solves the dual exactly and reports support vectors from sklearn.svm import SVC X_full = np.array([[1, 1], [2, 2], [-1, -1], [-2, 0]], dtype=float) y_full = np.array([1, 1, -1, -1]) # Full dataset svc_full = SVC(kernel='linear', C=100.0) # large C ≈ hard margin svc_full.fit(X_full, y_full) print('=== Full dataset ===') print(f'w = {svc_full.coef_[0]}, b = {svc_full.intercept_[0]:.4f}') print(f'Support vector indices: {svc_full.support_}') # TODO: Remove point B (index 1, a non-SV) and retrain. # Does the hyperplane change? # X_no_B = ... # y_no_B = ... # TODO: Remove point A (index 0, a SV) and retrain. # Does the hyperplane change? # X_no_A = ... # y_no_A = ...

=== Full dataset ===
w = [0.5 0.5], b = -0.0000
Support vector indices: [2 0]