Support Vector Machines & Their Applications

Machine Learning — Lecture Notes A complete beginner-friendly guide covering theory, mathematics, kernel methods, and real-world applications

Table of Contents

1. Linear Classifiers
2. Classifier Margin
3. Maximum Margin & Linear SVM
4. SVM Mathematics
5. Solving the Optimization Problem
6. Noisy Data & Soft Margin Classification
7. Non-linear SVMs & the Kernel Trick
8. Properties of SVM
9. Real-World Applications
10. Limitations of SVM

Linear Classifiers

A classifier is a function that takes a data point and assigns it to one of several predefined classes. In the binary case, we have two classes — conventionally labeled +1 and −1.

A linear classifier separates these classes using a straight line (in 2D), a plane (in 3D), or more generally a hyperplane in higher-dimensional space.

Core Formula

$f(\mathbf{x}, \mathbf{w}, b) = \text{sign}(\mathbf{w} \cdot \mathbf{x} + b)$

• $\mathbf{w}$ — the weight vector, which is perpendicular to the decision boundary and controls its orientation
• $\mathbf{x}$ — the input feature vector (your data point)
• $b$ — the bias (also called intercept), which shifts the boundary away from the origin
• The output is +1 or −1 depending on which side of the hyperplane the point falls

How the Decision Rule Works

The expression $\mathbf{w} \cdot \mathbf{x} + b$ computes a score for each input:

• Score > 0 → classify as +1 (positive class)
• Score < 0 → classify as −1 (negative class)
• Score = 0 → the point lies exactly on the decision boundary

The Fundamental Problem: Infinitely Many Valid Boundaries

When two classes are perfectly separable, there exist infinitely many hyperplanes that correctly separate them. Each gives zero training error, but they will generalize differently on unseen data. This raises the key question:

Which hyperplane should we choose?

This is precisely the problem Support Vector Machines are designed to solve.

Classifier Margin

The margin is the distance between the decision boundary and the nearest data points from either class. These nearest points are called support vectors (introduced formally in the next section).

Intuitive Analogy

Think of building a road between two rows of houses. The margin is the road's total width. A wider road is safer — vehicles (new data points) have more room before hitting a house (being misclassified). You want to build the widest road possible.

Why a Larger Margin Generalizes Better

A boundary with a large margin is more robust to perturbations. If new data arrives slightly displaced from the training data, a large-margin classifier is less likely to misclassify it. This is formally justified by PAC (Probably Approximately Correct) learning theory, which proves:

In other words, maximizing the margin directly minimizes an upper bound on future classification error.

Maximum Margin & Linear SVM

The Support Vector Machine finds the unique hyperplane that maximizes the margin between the two classes. This is also called the Maximum Margin Classifier or Linear SVM (LSVM).

★ Key Insight

The data points lying exactly on the margin boundaries are the support vectors. They are the only points that define the optimal hyperplane. All other training points are irrelevant — you could remove them without changing the result.

SVM Mathematics

Defining the Three Key Hyperplanes

We define three parallel hyperplanes that characterize the SVM solution:

Decision boundary (the central separating hyperplane): $\mathbf{w} \cdot \mathbf{x} + b = 0$

Positive margin boundary $H_+$ (touches positive support vectors): $\mathbf{w} \cdot \mathbf{x}^+ + b = +1$

Negative margin boundary $H_-$ (touches negative support vectors): $\mathbf{w} \cdot \mathbf{x}^- + b = -1$

The constraints require that no training point falls between these two margin boundaries:

Computing the Margin Width

Step 1 — Pick one point from each boundary.

Let $\mathbf{x}^+$ be a support vector on $H_+$ and $\mathbf{x}^-$ be a support vector on $H_-$. By definition:

Step 2 — Subtract to relate the two points.

Step 3 — Project onto the normal direction $\mathbf{w}$.

The vector $(\mathbf{x}^+ - \mathbf{x}^-)$ points from $H_-$ to $H_+$ but is not necessarily perpendicular to the boundaries. The perpendicular distance (the margin $M$) is obtained by projecting onto the unit normal $\hat{\mathbf{w}} = \frac{\mathbf{w}}{\|\mathbf{w}\|}$:

Step 4 — Substitute the result from Step 2.

Optimization Objective

To maximize the margin $m = \frac{2}{\|\mathbf{w}\|}$, we minimize $\|\mathbf{w}\|$. For convenience, we minimize the squared norm:

subject to:

This is a convex quadratic program with linear constraints — it has a unique global minimum and can be solved efficiently.

Solving the Optimization Problem

Why Use Lagrange Multipliers?

The SVM optimization has linear constraints, making it ideal for the Lagrangian method. Rather than solving the constrained problem directly, we transform it into an unconstrained dual problem that is often easier to solve and reveals important structure.

Step 1 — Form the Lagrangian

Introduce a non-negative multiplier $\alpha_i \geq 0$ for each training constraint:

At the optimum, increasing any $\alpha_i$ for a non-binding constraint does not help, so the Lagrangian captures all the information in the original problem.

Step 2 — Derive Stationarity Conditions

Setting the partial derivatives to zero:

Important: The weight vector $\mathbf{w}$ is a linear combination of the training points, weighted by their $\alpha_i$ values. Points with $\alpha_i = 0$ contribute nothing — these are the non-support vectors.

Step 3 — The Dual Problem

Substituting the stationarity conditions back into the Lagrangian eliminates $\mathbf{w}$ and $b$, yielding the dual problem:

Subject to:

Key Observations

1. Sparsity: After solving, most $\alpha_i = 0$. Only the support vectors have $\alpha_i > 0$. This means the classifier stores and uses only a small subset of training data.

2. Data appears only as dot products $\mathbf{x}_i \cdot \mathbf{x}_j$: This is the critical structural property that enables the kernel trick (Section 07). We can replace dot products with any valid kernel without changing the optimization procedure.

Making Predictions

Once $\boldsymbol{\alpha}$ is found, the bias $b$ is recovered from any support vector:

The classifier for a new point $\mathbf{x}$ is:

Noisy Data & Soft Margin Classification

The Problem with Hard Margin SVM

The formulation above assumes data is perfectly linearly separable — no overlap, no noise, no outliers. In practice:

• Real-world data almost always has noise and mislabeled examples
• Forcing zero training error on noisy data causes overfitting: the boundary contorts to accommodate every outlier and performs poorly on new data
• For slightly non-separable data, the hard margin problem is infeasible (no solution exists)

Solution: Slack Variables (Soft Margin SVM)

We introduce slack variables $\xi_i \geq 0$, one per training point, that allow controlled violation of the margin constraints.

Interpretation of $\xi_i$:

The Soft Margin Optimization Problem

Subject to:

The objective has two competing terms:

• $\frac{1}{2}\|\mathbf{w}\|^2$ — maximize the margin
• $C \sum_i \xi_i$ — minimize total margin violations

The Role of the Regularization Parameter C

In practice, $C$ is chosen using cross-validation.

Hard vs. Soft Margin Comparison

Non-linear SVMs & the Kernel Trick

When Linear Boundaries Are Insufficient

Some datasets cannot be separated by any hyperplane. Consider a ring of red points surrounded by blue points — no straight line separates them. A linear SVM will fail here regardless of the margin.

The Core Idea: Feature Space Mapping

The key insight is to map the data into a higher-dimensional feature space $\mathcal{F}$ using a function $\phi: \mathbb{R}^d \to \mathcal{F}$, where the classes become linearly separable. We then apply a linear SVM in this higher-dimensional space.

Example

Consider 2D data lying on concentric circles (not linearly separable). Add a third feature $z = x_1^2 + x_2^2$. In 3D space, the inner circle has small $z$ values and the outer circle has large $z$ values — they are now separated by the plane $z = c$. This plane corresponds to a circle in the original 2D space.

The Computational Problem — and Its Elegant Solution

Explicitly computing $\phi(\mathbf{x})$ for a very high (or infinite) dimensional space is prohibitively expensive. However, notice that in the SVM dual problem, data only appears as dot products $\mathbf{x}_i \cdot \mathbf{x}_j$. After mapping, these become $\phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)$.

A kernel function computes this dot product directly in the original space, without ever computing $\phi(\mathbf{x})$ explicitly:

This is the kernel trick: replace every dot product with a kernel evaluation, and the SVM works implicitly in a potentially infinite-dimensional space at the cost of computing $n \times n$ kernel values.

Worked Example — Polynomial Kernel

For 2D vectors $\mathbf{x} = [x_1, x_2]^T$, the kernel $K(\mathbf{x}_i, \mathbf{x}_j) = (1 + \mathbf{x}_i^T \mathbf{x}_j)^2$ implicitly corresponds to the 6-dimensional mapping:

$\phi(\mathbf{x}) = [1,\ x_1^2,\ \sqrt{2}\,x_1 x_2,\ x_2^2,\ \sqrt{2}\,x_1,\ \sqrt{2}\,x_2]^T$

The kernel computes the 6D dot product using only 2D arithmetic — a significant computational saving.

What Makes a Valid Kernel? (Mercer's Theorem)

A function $K(\mathbf{x}_i, \mathbf{x}_j)$ is a valid kernel if and only if the Gram matrix $G$ with entries $G_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)$ is symmetric and positive semi-definite for any set of inputs. You do not need to explicitly construct $\phi$ — just verify this condition.

Common Kernel Functions

The Non-linear SVM Dual Problem

Replacing dot products with kernel evaluations in the dual:

The decision function becomes:

The optimization algorithm is identical to the linear case — only the inner products are replaced by kernel evaluations.

Properties of SVM

Real-World Applications

Application 1 — Cancer Classification via Gene Expression Data

The Challenge

How SVM Addresses Each Challenge

Handling imbalance: A modified kernel adds a correction term proportional to the fraction of positive samples:

where $n^+$ is the number of positive training examples and $N$ is the total. This re-balances the effective cost of misclassifying minority-class examples.

Feature selection: In the linear SVM, the weight magnitude $w_j^2$ ranks each gene by importance. Genes with very small weights are likely irrelevant and can be removed — a process called recursive feature elimination (RFE).

High-dimensional stability: SVM's generalization bound depends on the margin, not the number of features. This makes it particularly well-suited to the $p \gg n$ regime of genomic data.

Known Limitation

SVM is sensitive to label noise (mislabeled training examples). Even a small fraction of incorrectly labeled patients can significantly degrade classification performance. Careful data curation is essential.

Application 2 — Text Categorization

The Task

Automatically assign text documents (news articles, emails, web pages) to predefined categories. Since a document can belong to multiple categories, this is decomposed into a set of independent binary classification problems — one per category (e.g., "politics vs. not politics", "sports vs. not sports").

Representing Documents as Vectors: Bag of Words (TF-IDF)

Before SVM can process text, documents must be converted to numerical vectors:

1. Build a vocabulary of all words appearing in the training corpus (after preprocessing).
2. Preprocess: Remove stop words ("the", "is", "a") and apply stemming (map "running", "runs", "ran" → "run").
3. Assign TF-IDF weights to each word per document:

where $\text{tf}_j$ is the term frequency (how often word $j$ appears in the document), $\text{idf}_j = N / \text{df}_j$ is the inverse document frequency ($\text{df}_j$ = number of documents containing word $j$, $N$ = total documents), and $\kappa$ is a normalization constant. This down-weights common words and up-weights discriminative words.

4. The result is a sparse, high-dimensional vector where most entries are zero (most words don't appear in any given document).

Why SVM Is a Natural Fit for Text

Limitations of SVM

Limitations 1 — Sensitivity to Label Noise

Mislabeled training examples can have a disproportionate effect on the decision boundary (particularly if they become support vectors). This is especially problematic in medical applications where annotation errors are common.

Limitations 2 — Inherently Binary

Standard SVM is formulated for two-class problems. Real tasks often require distinguishing among $m > 2$ classes.

Extending SVM to Multi-class Problems

The standard approach is one-vs-rest (OvR) classification:

1. Train $m$ separate SVMs. SVM-$k$ is trained to distinguish class $k$ from all other classes (positive label = class $k$, negative label = all others).
2. To classify a new point $\mathbf{x}$, evaluate all $m$ classifiers.
3. Assign the class whose classifier gives the largest positive score (i.e., the point is furthest into the positive region):

Practical Guidelines for Applying SVM

★ Summary

SVM remains one of the most theoretically well-grounded classifiers in machine learning. Its convex optimization guarantees a unique global solution. The kernel trick provides principled non-linear generalization at manageable computational cost. The soft margin formulation handles real-world noise robustly. Despite the rise of deep learning, SVM continues to be competitive — and often superior — on small, high-dimensional datasets such as those encountered in genomics, text analysis, and medical diagnostics.