Support Vector Machines

A Support Vector Machine (SVM) is a supervised algorithm that finds the decision boundary (hyperplane) that maximizes the margin between classes.

Margin Maximization and Slack Variables

In linear classification, we find a hyperplane $w^T x + b = 0$ that separates classes.

Primal Optimization Problem (Soft Margin)

To allow for noise and misclassifications, we introduce slack variables $\xi_i \ge 0$. The objective minimizes:

$\min_{w, b, \xi} \frac{1}{2} ||w||^2 + C \sum_{i=1}^{m} \xi_i$

subject to:

$y^{(i)} (w^T x^{(i)} + b) \ge 1 - \xi_i \quad \text{and} \quad \xi_i \ge 0$

The parameter $C$ controls the trade-off: a small $C$ allows more margin violations (regularized), while a large $C$ forces a hard margin (sensitive to noise).

The Dual Formulation and the Kernel Trick

By reformulating the optimization problem using Lagrange multipliers, we express the decision function using inner products of training instances:

$h(x) = \sum_{i=1}^{m} \alpha_i y^{(i)} (x^{(i)} \cdot x) + b$

The coefficients $\alpha_i$ are non-zero only for instances on the margin boundaries. These are the Support Vectors that determine the decision boundary.

The Kernel Trick

The kernel trick replaces the dot product with a kernel function $K(x^{(i)}, x^{(j)})$, avoiding mapping data to high-dimensional spaces explicitly.

• Polynomial Kernel: $K(x, z) = (\gamma x^T z + r)^d$
• Radial Basis Function (RBF) Kernel: $K(x, z) = \exp(-\gamma ||x - z||^2)$

The parameter $\gamma$ controls the RBF width: a larger $\gamma$ makes the boundary narrower and more irregular, fitting specific instances.

Example: Non-Linear Kernel SVM

The following example demonstrates training an SVM with an RBF kernel:

import numpy as np
from sklearn.svm import SVC

# Non-linear XOR problem dataset
X = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
y = np.array([0, 0, 1, 1])

# Radial Basis Function (RBF) kernel SVM handles non-linear boundaries
clf = SVC(kernel='rbf', C=10.0, gamma=1.0)
clf.fit(X, y)

print(f"Predictions: {clf.predict(X)}")
print(f"Number of Support Vectors per class: {clf.n_support_}")

Predictions: [0 0 1 1]
Number of Support Vectors per class: [2 2]

Exercise

Test your understanding of SVM margin constraints:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.
• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.