SVM: Math Intuition and Cost Function

The previous post defined the SVM objective — maximize the margin — and showed that maximizing $2/\Vert w\Vert$ is equivalent to minimizing $\Vert w{\Vert }^2/2$. What it didn't explain is why the margin can be written as $2/\Vert w\Vert$ in the first place, how the constraints on individual samples translate into a single convex optimization problem, and why the solution is sparse (only support vectors contribute to the decision boundary). This post derives all three.

Same anchor dataset: Binary loan default prediction.

import numpy as np

X = np.array([
    [25, 0.3],  [30, 0.4],  [40, 0.5],  [55, 0.6],
    [70, 0.7],  [80, 0.8],  [90, 0.8],  [100, 0.9],
])
y = np.array([-1, -1, -1, -1, 1, 1, 1, 1])

From Slack Variables to Hinge Loss

Soft margin introduces slack variables ${\xi }_i\ge 0$. The constraint $y_i(w\cdot x_i+b)\ge 1-{\xi }_i$ defines ${\xi }_i$ implicitly: if the constraint is satisfied with margin $\ge 1$, then ${\xi }_i=0$; otherwise ${\xi }_i=1-y_i(w\cdot x_i+b)$.

Defining $f_i=y_i(w\cdot x_i+b)$ (the functional margin), we get:

${\xi }_i=\max (0,1-f_i)$

This is the hinge loss — zero when the point is outside the margin, and growing linearly as the point moves inside or across the boundary. Substituting into the soft margin objective:

$J=\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_{i=1}^n\max (0,1-y_i(w\cdot x_i+b))$

This is an unconstrained minimization in $w$ and $b$. The hinge loss is convex and piecewise linear — the gradient is well-defined except at the kink ($f_i=1$), where subgradients are used.

Hinge Loss Trace on the Anchor

Using approximate weights $w=[0.08,2.5]$, $b=-6.5$, $C=1$:

Total hinge loss $=0.40+0.15=0.55$. Regularization term $=\frac{1}{2}\Vert w{\Vert }^2=\frac{1}{2}(0.08^2+2.5^2)=\frac{1}{2}(0.0064+6.25)=3.128$.

Full objective:

$J=3.128+1\times 0.55=3.678$

Samples 4 and 5 are the only violators. Samples 1–3 and 6–8 have $y_i{f}_i\ge 1$ — they contribute nothing to the hinge loss term.

The red polyline is the hinge loss. Everything to the right of $y_i{f}_i=1$ contributes zero to the objective. The loss grows linearly as points move left (toward and past the boundary).

The Dual Problem

The primal soft margin SVM is a convex quadratic program in $w$ and $b$. Its Lagrangian (introducing multipliers ${\alpha }_i\ge 0$ for each constraint and ${\mu }_i\ge 0$ for each ${\xi }_i\ge 0$) yields the dual problem by minimizing over $w$, $b$, $\xi$ and retaining only $\alpha$:

$\text{Maximize}D(\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(x_i\cdot x_j)$

$\text{subject to}0\le {\alpha }_i\le C,{\sum }_{i=1}^n{\alpha }_i{y}_i=0$

Three observations:

1. The dual depends on inputs only through dot products $x_i\cdot x_j$ — this is where the kernel trick enters (next post).
2. The constraint ${\alpha }_i\le C$ (not just ${\alpha }_i\ge 0$) comes from the soft margin; hard margin has ${\alpha }_i\ge 0$ only.
3. The linear constraint $\sum {\alpha }_i{y}_i=0$ ensures the bias $b$ is free (no bound on $b$).

Once ${\alpha }^{\ast }$ is found, the primal solution is recovered:

$w^{\ast }={\sum }_{i=1}^n{\alpha }_i^{\ast }{y}_i{x}_i$

Most ${\alpha }_i^{\ast }=0$. Only support vectors have ${\alpha }_i^{\ast }>0$, making $w^{\ast }$ a sparse combination of training points.

KKT Conditions — The Three Cases

The Karush-Kuhn-Tucker (KKT) conditions characterize the optimal ${\alpha }^{\ast }$ exactly. For each sample:

This gives a direct algorithm to identify each sample's role from the trained model's $\alpha$ values. Samples with ${\alpha }_i=0$ have no influence on the decision boundary.

Computing $b$ from Support Vectors

After solving for $w^{\ast }$, compute $b$ by averaging over free support vectors (those with $0<{\alpha }_i<C$):

$b^{\ast }=\frac{1}{|\mathcal{S}|}{\sum }_{i\in \mathcal{S}}\left(y_i-w^{\ast }\cdot x_i\right)$

where $\mathcal{S}$ is the set of free support vectors. Using a single support vector would be numerically fragile; averaging improves stability.

Connecting Hinge Loss to Other Losses

SVM is one member of a broader family of loss functions, each emphasizing different tradeoffs:

Hinge loss is the tightest convex upper bound on the 0-1 loss (the theoretically ideal but non-convex loss). Logistic loss is smooth everywhere; hinge is piecewise linear with a flat region. The flat region is what creates sparsity — all points outside the margin get ${\alpha }_i=0$ exactly.

Computing the Dual Objective on the Anchor

To verify the dual objective numerically, compute the dot product matrix $Q_{ij}=y_i{y}_j(x_i\cdot x_j)$:

import numpy as np
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler

X = np.array([[25,0.3],[30,0.4],[40,0.5],[55,0.6],
              [70,0.7],[80,0.8],[90,0.8],[100,0.9]])
y = np.array([-1,-1,-1,-1,1,1,1,1])

# Compute the kernel (dot product) matrix
K = X @ X.T          # shape (8,8)
yy = np.outer(y, y)  # shape (8,8): y_i * y_j
Q = yy * K           # Q_ij = y_i * y_j * (x_i . x_j)

print("Dot products for first 4 pairs:")
for i in range(4):
    for j in range(i, 4):
        print(f"  x{i+1}·x{j+1} = {X[i]@X[j]:.2f}")

The dual objective $D(\alpha )=\sum {\alpha }_i-\frac{1}{2}{\alpha }^{T}Q\alpha$ is maximized over $\alpha$ subject to the box and linear constraints. sklearn's SVC solves this internally using libsvm's Sequential Minimal Optimization (SMO).

scaler = StandardScaler()
X_sc = scaler.fit_transform(X)

svm = SVC(kernel='linear', C=1.0)
svm.fit(X_sc, y)

print(f"Dual coefficients (α_i * y_i): {svm.dual_coef_}")
print(f"Support vectors:\n{svm.support_vectors_}")
print(f"Support vector indices: {svm.support_}")
print(f"n_support (per class): {svm.n_support_}")

4 support vectors (indices 2,3,4,5 → income=40,55,70,80). The dual coefficients are ${\alpha }_i{y}_i$: positive for $y=+1$ support vectors and negative for $y=-1$ support vectors. Notice |α_i| = 1.0 for indices 3,4 — these are bounded support vectors (${\alpha }_i=C$), inside the margin.

Why the Dual Form Is Preferred

The primal has $d+1$ variables ($d$ weights + bias) and $n$ constraints. The dual has $n$ variables (one $\alpha$ per sample) and $n+1$ constraints. When $n\ll d$ (many features, few samples), the dual is much smaller — but more importantly, the dual's dependence on $x_i\cdot x_j$ (not on $x_i$ and $x_j$ individually) is what makes the kernel trick possible.

Test Your Understanding

1. Sample 4 (income=55) has $y_i{f}_i=0.60$ and sample 5 (income=70) has $y_i{f}_i=0.85$. What are their ${\alpha }_i$ values relative to $C=1$? Are they free support vectors ($0<{\alpha }_i<C$) or bounded (${\alpha }_i=C$)?

2. The dual constraint is ${\sum }_{i=1}^n{\alpha }_i{y}_i=0$. The dual coefficients shown are $[-0.742,-1.0,1.0,0.742]$ (for ${\alpha }_i{y}_i$). Verify that this constraint is satisfied.

3. Hinge loss is zero for $y_i{f}_i\ge 1$. Logistic loss is never exactly zero. How does this difference in the "zero region" explain why SVM produces sparse $\alpha$ values but logistic regression does not?

4. If $C\to \infty$, the penalty for margin violations grows unboundedly. What happens to the constraint ${\alpha }_i\le C$ in the dual problem? Does the dual reduce to the hard margin problem?

5. The weight vector $w^{\ast }={\sum }_i{\alpha }_i^{\ast }{y}_i{x}_i$ uses only support vectors. If you add 100 new samples far from the decision boundary (all with $y_i{f}_i\gg 1$), does $w^{\ast }$ change? Why or why not?