5. SVM

Linear Classifiers

Maximizing the margin

• $\gamma:$ The distance between a data point to the decision boundary

Decision Rule

Hyperplane

w

• a vector perpendicular to the median line

u

• an unknown example

$w^\intercal u \ge -b$

• Project $u$ onto $w$

How to calculate w and b?

Add more constraints

Width of the Street

• Given that $y^{(i)}(w^\intercal x^{(i)} + b) = a$ for $x$ in gutter

• Since $a$ is arbitrary, can normalize equations by $a$

Support Vectors

• lies in:

• Under the KKT condition, only a few $\alpha_i$ can be non-zero

where

• $g_i(w^*) = 1 - y^{(i)}(w^\intercal x^{(i)} + b)$

• Training data are called support vectors if their $\alpha_i$ are non-zero
• $\because$
• only a few $\alpha_i$ can be non-zero
• $y^{(i)}(w^\intercal x^{(i)} + b) = 1$ when $\alpha_i$ is non-zero
• $\therefore$
• $b = y^{(t)} - w^\intercal x^{(t)} \quad (\alpha_t > 0)$

Hard Margin SVM

• Assume that data are linearly separable

• This is a convex quadratic programming problem with linear constraints

Soft Margin SVM

• In real-world data, there may be:
• Overlapping classes
• Noisy points
• Outliers
• Assume that data are non-linearly separable
• Introduce a trade-off parameter between error and margin and slack variables to measure how much a point violates the margin constraint

C

• regularization parameter
• tolerance controller for errors
• controlling the trade-off between large margin (generalization) and few margin violations (accuracy on training data)
• $C \rightarrow \infty$
• Hard Margin SVM
• Small C:
• The optimizer allows larger $\xi_i$ tolerating misclassification to get a smoother margin.
• Larger C:
• The optimizer will do everything it can to make $\xi_i = 0$, even if it means a smaller margin

$\xi_i$

• slack variables for each data point
• pay linear penalty if mistake

• Results for correction

New Optimization Problem

• Make the margin as large as possible
• Keep the total slack small

Margin Support Vector

• $\xi_i = 0, y^{(i)} (w^\intercal x + b) = 1$
• don’t contribute to objective but enforce constraints on solution
• correctly classified

Digression to Lagrange Duality

Primal Problem vs. Dual Problem

$\bullet$ The Primal Problem

• The SVM formulation expressed directly in terms of weights ($w$), bias ($b$), slack variables ($\xi_i$)
• It’s primal because it directly optimizes the parameters of the model.

$\bullet$ The Dual Problem

• Use Lagrange multipliers $\alpha_i$ to handle the constraints
• Depends only on dot products between data points - allowing the kernel trick.
• $\alpha_i$ correspond to the importance (weights) of each training point

From Primal to Dual

1. The original (Soft-Margin) SVM Primal Problem

where

• $\theta = (w, b, \xi)$
• $f(\theta) = \frac{1}{2}||w||^2 + C \sum_i^N \xi_i$
• Constraints
• $g_i(\theta) \le 0 \quad i = 1, \dots, k$
• $h_i(\theta) = 0 \quad i = 1, \dots, l$

2. Generalized Lagrangian:

3. Derive the Re-written Primal

• Given $\alpha(\alpha_i \ge 0), \beta$: Lagrang multipliers.

Lagrange Duality

$\bullet$ A Re-written Primal:

$\bullet$ Dual Optimization Problem

• The value of the dual problem is always the lower bound of the value of the primal problem

$\bullet$ Connection between Primal and Dual

Weak Duality

• Always holds

• When you minimize the parameters first and then find the maximized lagrange multipliers, you can never do worse than the other way round

Strong Duality

• Whenever strong duality holds, the Karush-Kuhn-Tucker (KKT) conditions are true for $\theta^*, \alpha^*, \beta^*$

Karush-Kuhn-Tucker (KKT)

Stationarity

• gradient equilibrium
• No more improvement condition

Primal Feasibility

• obey the original constraints

Dual Feasibility

• obey the dual constraints
• No negative penalties

Complementary Slackness

• If a constraint is active $g_i(\theta^*) = 0$
• $\alpha_i^*$ may be positive
• If a constraint is inactive $g_i(\theta^*) < 0$
• $\alpha^*_i$ must be zero

How to Minimize without thinking about the constraints?

1. Minimize $L(w, b, \alpha)$ w.r.t. $w, b$

2. Plug them back to derive SVM Lagrangian

3. Derive Hard Margin SVM Dual

• Dual problem is also QP. Its solution gives a global maximum of $\alpha^*$
• $w^*$ can be recovered

• Dependence

4. Derive Soft Margin SVM Dual

• It’s pretty much the same but we introduce an upper bound $C$ for the $\alpha_i$ term

Results: Primal ↔ Dual (Hard vs. Soft) + Prediction

Summary Table

Recovering $w$ and $b$

• Weight vector (linear case):

• Bias term: For any support vector $x_t$ with $0 < \alpha_t^* < C$:

If multiple margin SVs exist, take the average $b^*$.

KKT Conditions (Soft-Margin)

Intepretation

Final Decision Function

• Linear Case:

• Kernelized Case:

Margin and Limit Behavior

• Margin width: $\frac{2}{\|w^*\|}$
• As $C \to \infty$: Soft-margin SVM → Hard-margin SVM (if data are separable)
• As $C \to 0$: Margin dominates, high tolerance for error (underfitting)

Intuitive Summary

• Hard-Margin: No misclassification; all points must be correctly separated.
• Soft-Margin: Allows some violations; balances accuracy and generalization via $C$.
• Support Vectors: Points with $\alpha_i > 0$ define the decision boundary.
• Dual Form: Enables kernel trick; optimization depends only on dot products or $K(x_i, x_j)$.

Implementation

Helper

def poly_implementation(x, y, degree):
 assert x.size() == y.size(), 'The dimensions of inputs do not match!'
 with torch.no_grad():
 return (1 + (x * y).sum()).pow(degree)

def poly(degree):
 return lambda x, y: poly_implementation(x, y, degree)

def rbf_implementation(x, y, sigma):
 assert x.size() == y.size(), 'The dimensions of inputs do not match!'
 with torch.no_grad():
 return (-(x - y).norm().pow(2) / 2 / sigma / sigma).exp()

def rbf(sigma):
 return lambda x, y: rbf_implementation(x, y, sigma)

def xor_data():
 x = torch.tensor([[1, 1], [-1, 1], [-1, -1], [1, -1]], dtype=torch.float)
 y = torch.tensor([1, -1, 1, -1], dtype=torch.float)
 return x, y

SVM

def svm_solver(
 x_train, y_train, lr, num_iters, kernel=hw3_utils.poly(degree=1), c=None
):
 """
 Computes an SVM given a training set, training labels, the number of
 iterations to perform projected gradient descent, a kernel, and a trade-off
 parameter for soft-margin SVM.

 Arguments:
 x_train: 2d tensor with shape (N, d).
 y_train: 1d tensor with shape (N,), whose elememnts are +1 or -1.
 lr: The learning rate.
 num_iters: The number of gradient descent steps.
 kernel: The kernel function.
 The default kernel function is 1 + <x, y>.
 c: The trade-off parameter in soft-margin SVM.
 The default value is None, referring to the basic, hard-margin SVM.

 Returns:
 alpha: a 1d tensor with shape (N,), denoting an optimal dual solution.
 Initialize alpha to be 0.
 Return alpha.detach() could possibly help you save some time
 when you try to use alpha in other places.
 """
 # TODO
 N = x_train.shape[0]
 alpha = torch.zeros(N, requires_grad=True)
 Y = torch.diag(y_train)

 # Build the kernel beforehand
 K = create_kernel(x_train, x_train, N, N, kernel)
 for _ in range(num_iters):
 # The matrix form of the original dual problem: sum(alpha) - alpha^T(YKY)alpha
 L = alpha.sum() - 0.5 * alpha @ (Y @ K @ Y) @ alpha
 L.backward()

 # update alpha
 with torch.no_grad():
 alpha += lr * alpha.grad

 # clamp the range
 if c:
 alpha = torch.clamp_(
 alpha,
 min=0,
 max=c,
 )
 else:
 alpha = torch.clamp_(
 alpha,
 min=0,
 )
 alpha.grad.zero_()
 alpha.requires_grad_()

 return alpha.detach()


def svm_predictor(alpha, x_train, y_train, x_test, kernel=hw3_utils.poly(degree=1)):
 """
 Returns the kernel SVM's predictions for x_test using the SVM trained on
 x_train, y_train with computed dual variables alpha.

 Arguments:
 alpha: 1d tensor with shape (N,), denoting an optimal dual solution.
 x_train: 2d tensor with shape (N, d), denoting the training set.
 y_train: 1d tensor with shape (N,), whose elements are +1 or -1.
 x_test: 2d tensor with shape (M, d), denoting the test set.
 kernel: The kernel function.
 The default kernel function is 1 + <x, y>.

 Return:
 A 1d tensor with shape (M,), the outputs of SVM on the test set.
 """
 N = x_train.shape[0]
 M = x_test.shape[0]

 K_train = create_kernel(x_train, x_train, N, N, kernel)
 K_test = create_kernel(x_train, x_test, N, M, kernel)

 support_idx = torch.where(alpha > _EPS)[0]
 if len(support_idx) == 0:
 return torch.zeros(M)

 min_alpha_idx = support_idx[torch.argmin(alpha[support_idx])]

 # y_support - \sum^{N}_{j = 1} \alpha_j * y_j * K(x_j, x_k)
 b = y_train[min_alpha_idx] - (alpha * y_train * K_train[:, min_alpha_idx]).sum()

 # Compute predictions: f(x) = \sum_{i=1}^{N} \alpha_i * y_i * K(x_i, x) + b
 f = torch.sum((alpha * y_train).unsqueeze(1) * K_test, dim=0) + b
 return torch.sign(f)