Support Vector Machines (SVM) Theory

In this article, we will dive deeper into the theory behind Support Vector Machines (SVMs), focusing on the mathematical foundation that makes SVMs so powerful for both linear and nonlinear classification tasks. We will cover:

• The concept of hyperplanes and support vectors.
• Maximizing the margin between classes.
• The optimization problem solved by SVM.
• Soft margins and the regularization parameter (C).
• The kernel trick for nonlinear classification.

---

1. Hyperplanes and Support Vectors

1.1. Hyperplane

A hyperplane is a decision boundary that separates different classes in the feature space. In a 2D space, the hyperplane is a line, while in higher dimensions, it's a plane or a higher-dimensional analog.

For a binary classification problem, the hyperplane can be defined as:

$$w_1 x_1 + w_2 x_2 + \dots + w_n x_n + b = 0$$

Where:

• $w_1, w_2, \dots, w_n$ are the weights (or coefficients) associated with the input features.
• $b$ is the bias term (intercept).
• $x_1, x_2, \dots, x_n$ are the feature values of the data points.

A binary data point $x$ can be classified based on which side of the hyperplane it lies (using labels (-1) and (+1)):

• If $w^T x + b > 0$, classify as class 1.
• If $w^T x + b < 0$, classify as class (-1).

1.2. Support Vectors

Support vectors are the data points that lie closest to the hyperplane. These points are critical because the position of the hyperplane depends only on the support vectors, not on the other data points. The support vectors define the margin and play a central role in determining the optimal decision boundary.

---

2. Maximizing the Margin

One of the key principles of SVM is to maximize the margin between the two classes. The margin is the distance between the hyperplane and the nearest data points (support vectors) from each class. By maximizing this margin, the SVM aims to improve the generalization ability of the model, reducing the chance of overfitting.

Definition of Margin:

With the canonical constraints (y_i(w^Tx_i+b) \ge 1), the distance from the separating hyperplane to either margin boundary is (1/\lVert w\rVert). The full margin width is:

$$\text{Margin} = \frac{2}{\|w\|}$$

Where $\|w\|$ is the norm (magnitude) of the weight vector $w$. The goal of SVM is to maximize this margin, which is equivalent to minimizing $\|w\|$ (the size of the weight vector).

---

3. The Optimization Problem

The core objective of an SVM is to find the hyperplane that maximizes the margin while minimizing classification errors. This leads to the following optimization problem:

Primal Problem (Hard Margin SVM):

For perfectly separable data, the optimization problem is:

$$\min_{w, b} \frac{1}{2} \|w\|^2$$

Subject to the following constraints for each data point $i$:

• $y_i (w^T x_i + b) \geq 1$

Where:

• $y_i$ is the actual label (either $+1$ or $-1$).
• $x_i$ is the feature vector of the $i$-th data point.

This optimization problem ensures that each data point is correctly classified, and the margin is maximized. The term $\frac{1}{2} \|w\|^2$ is minimized to achieve the largest possible margin.

---

4. Soft Margin SVM (Handling Misclassification)

In most real-world datasets, the data is not perfectly separable, meaning some data points will inevitably be misclassified. To handle this, soft margin SVM allows some violations of the margin. These violations are controlled by introducing slack variables $\xi_i$, which measure how much each data point violates the margin.

Soft Margin Optimization Problem:

One common soft-margin optimization problem is formulated as:

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

Subject to the constraints:

• $y_i (w^T x_i + b) \geq 1 - \xi_i$
• $\xi_i \geq 0$

Where:

• $\xi_i$ are the slack variables that allow misclassification.
• $C$ is the regularization parameter that controls the trade-off between maximizing the margin and minimizing classification errors.

Role of Regularization Parameter (C):

• Small (C): Encourages a wider margin by penalizing violations less, potentially increasing training error.
• Large (C): Penalizes misclassification heavily, leading to a narrower margin and potentially overfitting the training data.

The parameter $C$ must be tuned carefully to balance model complexity and generalization.

---

5. The Kernel Trick

One of the key strengths of SVM is its ability to handle nonlinear decision boundaries using the kernel trick. A valid kernel computes inner products in an implicit feature space without explicitly constructing its coordinates. This can create nonlinear decision boundaries in the original feature space.

Common Kernel Functions:

1. Linear Kernel:

   • Produces a linear decision boundary; soft-margin fitting also works when classes overlap.
   • Kernel function: $K(x_i, x_j) = x_i^T x_j$

2. Polynomial Kernel:

   • Corresponds to interactions in a polynomial feature space.
   • Kernel function: $K(x_i, x_j) = (x_i^T x_j + c)^d$

3. Radial Basis Function (RBF) Kernel:

   • Measures similarity by squared Euclidean distance; (gamma) controls how local each point's influence is.
   • Kernel function: $K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)$

4. Sigmoid Kernel:

   • Similar to neural networks, but less commonly used.
   • Kernel function: $K(x_i, x_j) = \tanh(\alpha x_i^T x_j + c)$

Why the Kernel Trick?

Instead of explicitly mapping the data to a feature space, the kernel trick computes the required inner products directly. It can avoid materializing many transformed features, but the kernel matrix still scales quadratically in the number of training samples; nonlinear kernel SVMs are not automatically computationally cheap.

---

6. Dual Formulation of SVM

SVMs can also be formulated in their dual form, which is especially useful when applying kernel functions. In the dual form, the optimization problem is rewritten in terms of Lagrange multipliers $\alpha_i$, and the kernel function $K(x_i, x_j)$ is introduced.

Dual Problem:

The dual optimization problem is:

$$\max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j K(x_i, x_j)$$

Subject to:

• $0 \leq \alpha_i \leq C$
• $\sum_{i=1}^{n} \alpha_i y_i = 0$

Where $\alpha_i$ are the Lagrange multipliers, and $K(x_i, x_j)$ is the kernel function. The dual form is advantageous because it only depends on the dot products (or kernel values) between pairs of data points.

---

7. SVM for Regression (Support Vector Regression)

SVM can also be adapted for regression using Support Vector Regression (SVR). With (\epsilon)-SVR, residuals inside an (\epsilon)-wide tube incur no loss; deviations outside the tube are penalized through slack variables. (C) controls the penalty for those deviations, while kernel parameters control boundary flexibility. Scale features and tune (C), (\epsilon), and any kernel parameters inside training folds.

8. Multiclass Behavior and Probabilities

The optimization above is binary. scikit-learn's SVC handles (K) classes by fitting (K(K-1)/2) one-versus-one classifiers. Its default score output is transformed into an (n_samples, n_classes) one-versus-rest-shaped array, but training remains one-versus-one.

SVM decision scores are not probabilities. Probability calibration is a separate fitted model and must use only training data. Calibration quality and the downstream decision threshold should be validated separately from discrimination.

---

Summary

In this article, we explored the mathematical foundation of Support Vector Machines (SVMs), covering key concepts such as:

• Hyperplanes and support vectors.
• Maximizing the margin to improve generalization.
• The soft margin formulation for handling misclassification.
• The kernel trick for nonlinear classification.
• The dual formulation of SVM, which is especially useful when applying kernel functions.

Understanding the theory behind SVM is crucial for tuning the model's parameters and choosing the right kernel for your data. In the next section, we will cover practical examples of applying SVM using popular machine learning libraries like scikit-learn, TensorFlow, and PyTorch.