Support Vector Machines: Algorithm Deep Dive

Overview#

This notebook complements the applied SVM notebook from the main Machine Learning course by going deeper into the actual mathematics: the margin optimization problem, how Lagrange multipliers turn it into the "dual problem" that makes the kernel trick possible, the exact mechanics of several common kernels, and a rigorous treatment of why support vectors alone determine the boundary. If you want the practical, hands-on version with tuning workflows, see the SVM notebook in the main ML course — this one focuses on the "why" beneath the API calls.

1. The Geometry of the Margin, Precisely#

For linearly separable data, the decision boundary is a hyperplane defined by w · x + b = 0. The margin is the distance from this hyperplane to the nearest point of either class.

Python
CopyAsk AI
import numpy as np

# The distance from a point x to the hyperplane w·x + b = 0 is:
#   distance = |w · x + b| / ||w||
# where ||w|| is the Euclidean norm (length) of the weight vector

def point_to_hyperplane_distance(x, w, b):
    return abs(np.dot(w, x) + b) / np.linalg.norm(w)

w = np.array([1.0, 2.0])
b = -3.0
point = np.array([2.0, 1.0])
print(f"Distance: {point_to_hyperplane_distance(point, w, b):.3f}")

text
Ask AICopy
SVM's objective: find w and b that MAXIMIZE the margin, subject to every
training point being correctly classified (for the hard-margin case) —
i.e., every point sits on the correct side of the boundary, at or beyond
the margin.

2. Formulating the Optimization Problem#

Architecture & Data Flow
Copy
For a hard-margin SVM (assuming perfect linear separability), the
mathematical formulation is:

  minimize:    (1/2) * ||w||²
  subject to:  y_i * (w · x_i + b) >= 1,  for every training point i

Where y_i is +1 or -1 (the class label).

Architecture & Data Flow
Copy
Why minimize ||w||² to MAXIMIZE the margin?

The margin width turns out to equal 2 / ||w|| — so making the margin as
WIDE as possible is mathematically equivalent to making ||w|| as SMALL as
possible. Squaring it (||w||²) doesn't change where the minimum occurs,
but makes the math more convenient (the function becomes smooth and
convex, avoiding a square root).

The constraint y_i * (w·x_i + b) >= 1 encodes "every point must be
correctly classified, AND sit on the correct side of the margin, not just
the decision boundary itself" — for a positive example (y_i=+1), this
requires w·x_i + b >= 1; for a negative example (y_i=-1), it requires
w·x_i + b <= -1.

Python
CopyAsk AI
# A hard-margin SVM would fail entirely on non-separable data — this
# constraint has NO valid solution if even one point can't be correctly
# placed on the right side of the margin, which is why soft-margin SVM
# (next section) is what's actually used in practice

3. Soft Margin: Introducing Slack Variables#

Architecture & Data Flow
Copy
For real, noisy data, we relax the hard constraint by introducing SLACK
VARIABLES (ξ_i, one per training point) that allow some points to violate
the margin, at a cost:

  minimize:    (1/2) * ||w||² + C * sum(ξ_i)
  subject to:  y_i * (w·x_i + b) >= 1 - ξ_i,  for every point i
               ξ_i >= 0

text
Ask AICopy
ξ_i = 0            → point is correctly classified, outside the margin
0 < ξ_i <= 1        → point is correctly classified, but WITHIN the margin
ξ_i > 1              → point is actually MISCLASSIFIED

Architecture & Data Flow
Copy
The C parameter controls the TRADEOFF between the two goals in the
objective function:
- Minimizing ||w||² (wanting a WIDE margin)
- Minimizing sum(ξ_i) (wanting FEW/small margin violations)

A LARGE C weights the slack penalty heavily → prioritizes correctly
classifying every point → NARROWER margin, more sensitive to individual
points (higher variance).

A SMALL C weights the slack penalty lightly → tolerates more violations
→ WIDER margin, more tolerant of noise/outliers (higher bias, lower
variance).

This is the exact same C that appears in sklearn.svm.SVC(C=...) — now you can see precisely what it's mathematically trading off, not just that "higher C means less regularization."

4. The Dual Problem and Lagrange Multipliers#

The optimization problem above (the "primal" problem) can be mathematically transformed into an equivalent "dual" problem using Lagrange multipliers — and this transformation is what makes the kernel trick possible.

text
Ask AICopy
Introducing a Lagrange multiplier α_i >= 0 for each constraint, and
working through the calculus (differentiating with respect to w and b,
setting to zero, substituting back in), the DUAL problem becomes:

  maximize:    sum(α_i) - (1/2) * sum_i sum_j [α_i * α_j * y_i * y_j * (x_i · x_j)]
  subject to:  0 <= α_i <= C
               sum(α_i * y_i) = 0

text
Ask AICopy
The critical thing to notice: the ENTIRE dual problem depends on the
training data ONLY through DOT PRODUCTS between pairs of points
(x_i · x_j) — never through the individual points' raw coordinates
directly.

THIS is exactly why the kernel trick works: if we can compute
"what the dot product WOULD be after some transformation φ(x)" — written
K(x_i, x_j) = φ(x_i) · φ(x_j) — WITHOUT ever explicitly computing φ(x),
we get all the benefits of operating in a higher-dimensional
(transformed) space, at the computational cost of operating in the
ORIGINAL space.

5. Support Vectors, Precisely Defined via the Dual#

text
Ask AICopy
Solving the dual problem yields an α_i value for EVERY training point.
Crucially, for MOST points, α_i = 0 exactly — meaning they contribute
NOTHING to the final decision boundary.

Only points with α_i > 0 are SUPPORT VECTORS — and the final decision
function only depends on THESE points:

  w = sum over support vectors of (α_i * y_i * x_i)

  decision(x) = sign( sum over support vectors of [α_i * y_i * K(x_i, x)] + b )

Python
CopyAsk AI
from sklearn.svm import SVC
from sklearn.datasets import make_blobs

X, y = make_blobs(n_samples=100, centers=2, random_state=6, cluster_std=1.2)
svm = SVC(kernel="linear", C=1.0)
svm.fit(X, y)

print(f"Total training points: {len(X)}")
print(f"Support vectors: {len(svm.support_vectors_)}")
print(f"Dual coefficients (alpha_i * y_i) for support vectors: {svm.dual_coef_}")

›Total training points: 100
Support vectors: 14

This confirms mathematically what the applied SVM notebook stated intuitively: only a small fraction of training points (those with non-zero α_i, i.e. the support vectors) actually determine the boundary — every other point could be deleted from the training set entirely without changing the fitted model at all.

6. The Kernel Trick, Mathematically#

Python
CopyAsk AI
import numpy as np

def linear_kernel(x1, x2):
    return np.dot(x1, x2)

def polynomial_kernel(x1, x2, degree=3, gamma=1, coef0=1):
    return (gamma * np.dot(x1, x2) + coef0) ** degree

def rbf_kernel(x1, x2, gamma=0.5):
    return np.exp(-gamma * np.linalg.norm(x1 - x2) ** 2)

x1 = np.array([1.0, 2.0])
x2 = np.array([3.0, 1.0])

print(f"Linear kernel: {linear_kernel(x1, x2):.3f}")
print(f"Polynomial kernel (degree=3): {polynomial_kernel(x1, x2):.3f}")
print(f"RBF kernel: {rbf_kernel(x1, x2):.3f}")

Why the RBF kernel corresponds to an INFINITE-dimensional space#

Architecture & Data Flow
Copy
The RBF (Gaussian) kernel can be shown, via a Taylor series expansion of
the exponential function, to be mathematically equivalent to computing a
dot product in an INFINITE-dimensional feature space.

This means an RBF-kernel SVM is implicitly operating in a space with
infinitely many features — something that would be utterly impossible to
compute explicitly (you cannot construct an infinite-dimensional vector
in memory) — yet the kernel function K(x1, x2) = exp(-gamma * ||x1-x2||²)
computes the EQUIVALENT of a dot product in that space using only a
simple, finite calculation in the ORIGINAL feature space.

This is the full power of the kernel trick: accessing the expressiveness
of an infinite-dimensional feature space, at the computational cost of
working in the original, finite space.

7. Mercer's Condition: What Makes a Valid Kernel#

text
Ask AICopy
Not every function K(x1, x2) can be used as a valid SVM kernel. To be
valid, a kernel function must correspond to an ACTUAL dot product in
SOME (possibly infinite-dimensional) feature space — a requirement
formalized by Mercer's condition: the kernel must produce a symmetric,
POSITIVE SEMI-DEFINITE matrix for any set of input points.

In practice, this means you generally can't just invent an arbitrary
similarity function and plug it in as a kernel — linear, polynomial, RBF,
and sigmoid (with caveats) are all PROVEN valid kernels; a custom
function would need to satisfy Mercer's condition to be mathematically
sound.

8. Support Vector Regression: The Epsilon-Insensitive Loss#

Architecture & Data Flow
Copy
SVR modifies the objective to find a function where predictions within
epsilon of the true value incur ZERO loss, and only errors beyond
epsilon are penalized (linearly, by default):

  Loss(y, y_pred) = max(0, |y - y_pred| - epsilon)

  minimize: (1/2)*||w||² + C * sum(Loss(y_i, prediction_i))

Python
CopyAsk AI
from sklearn.svm import SVR
import numpy as np

def epsilon_insensitive_loss(y_true, y_pred, epsilon=0.5):
    return np.maximum(0, np.abs(y_true - y_pred) - epsilon)

errors = np.array([0.1, 0.3, 0.6, 1.2])
losses = epsilon_insensitive_loss(np.zeros(4), errors, epsilon=0.5)
print(losses)   # [0.  0.  0.1 0.7] — errors within epsilon (0.5) incur zero loss

This "tube" of zero-penalty tolerance around the predicted function (controlled by epsilon) is what gives SVR its name and its distinctive robustness to small errors — directly analogous to how classification SVM tolerates points that are correctly classified but simply not maximally far from the boundary.

9. Computational Complexity: Why SVM Doesn't Scale Well#

text
Ask AICopy
Solving the dual quadratic programming problem has a computational
complexity that scales, in the worst case, between O(n²) and O(n³) with
the number of training samples n — because the problem fundamentally
requires considering the pairwise relationships (dot products/kernel
evaluations) between EVERY pair of training points.

This is precisely why SVM (especially with non-linear kernels) becomes
impractically slow on datasets beyond roughly tens of thousands of
samples — in stark contrast to tree ensembles and linear models, whose
training complexity scales much more favorably (closer to linear) with
sample count.

Python
CopyAsk AI
# For large datasets, LinearSVC uses a different, more scalable
# optimization algorithm specifically for the LINEAR kernel case —
# avoiding the full O(n²)-O(n³) dual problem entirely
from sklearn.svm import LinearSVC

linear_svc = LinearSVC(C=1.0, max_iter=10000)   # scales much better than SVC(kernel="linear")
                                                    # for large datasets, though it optimizes a
                                                    # slightly different formulation internally

Notes#

• The margin width is mathematically 2/||w||, which is why maximizing the margin is equivalent to minimizing ||w||² — this single fact underlies the entire SVM formulation.
• C in the soft-margin formulation directly trades off margin width against tolerance for margin violations — this is the precise mathematical meaning behind the informal "less regularization" framing.
• The kernel trick is possible specifically because the dual optimization problem depends on training data only through pairwise dot products — a mathematical coincidence (of the Lagrangian transformation) that turns out to be enormously useful.
• Only points with non-zero Lagrange multipliers (α_i > 0) are support vectors and influence the final model — this can be verified directly by inspecting dual_coef_ and support_vectors_.
• SVM's computational complexity scaling (roughly O(n²) to O(n³)) is the fundamental mathematical reason it struggles with very large datasets, not an implementation detail that might be optimized away.

Best Practices Checklist#

• Understand C as a mathematical tradeoff between margin width and slack/violation tolerance, not just an arbitrary "regularization knob"
• Recognize that only support vectors (α_i > 0) affect the final model — inspect support_vectors_ to gauge model complexity
• Use LinearSVC instead of SVC(kernel="linear") for large datasets, since it scales substantially better
• Remember RBF kernels implicitly operate in an infinite-dimensional space — this explains both their flexibility and their tendency to overfit without proper C/gamma tuning
• Be cautious inventing custom kernel functions without verifying they satisfy Mercer's condition
• Expect SVM training time to scale poorly (roughly quadratically to cubically) with dataset size — plan accordingly for large datasets
• Use the epsilon-insensitive loss framing to understand why SVR is naturally robust to small prediction errors