Support Vector Machine

Several flat decision boundaries, called hyperplanes, may separate the same training data. A hard-margin support vector machine (SVM) chooses the one farthest from its nearest training point. When perfect separation is unavailable or undesirable, slack variables measure violations of the required margin, and the objective penalizes these violations. We then derive the dual problem to show how kernels allow nonlinear decision boundaries.

The derivation follows four steps:

• Calculating the distance from a point to a hyperplane and defining the margin.
• Formulating the hard-margin SVM and understanding how it finds the optimal separating hyperplane.
• Extending to soft-margin SVM to handle misclassifications and margin violations.
• Using the kernel trick to work with nonlinear boundaries through inner products, without explicitly computing the transformed feature vectors.

Let $\{(x_i, y_i)\}_{i=1}^n$ be our training set, with $x_i \in \mathbb{R}^p$ and $y_i \in \{-1, +1\}$, and assume both classes occur. We define:

• $w \in \mathbb{R}^p$ as the normal vector,
• $b \in \mathbb{R}$ as the bias,
• for a separating hyperplane, the geometric margin $\gamma$ as its minimum distance to a training point.

The sign of $w^T x + b$ determines the predicted class. If $w^T x + b > 0$, we predict $y=+1$; otherwise, we predict $y=-1$. To choose the separating hyperplane, we first need a measure of distance from that hyperplane.

In three-dimensional space, the perpendicular distance $d$ from a point $(x_1, y_1, z_1)$ to a plane

is given by

The normal vector $(A,B,C)$ must be nonzero.

Generalizing this to $\mathbb{R}^p$, consider the hyperplane

where $w \in \mathbb{R}^p$ is a nonzero normal vector and $b \in \mathbb{R}$ is the bias term. For any point $x_0$, its perpendicular distance to this hyperplane is

For a point $x_i$ with label $y_i$, its signed distance to the hyperplane is

Multiplying both the normal vector and the bias by a positive constant does not change the hyperplane. For separable data, we use this freedom to normalize the smallest functional margin to one. The constraints are then

with equality for at least one training point. Under this normalization, the geometric margin is

Thus, maximizing the margin reduces to minimizing $\|w\|$ (or $\tfrac12\|w\|^2$ for mathematical convenience).

If the training data are perfectly separable, we can write the constraints as

Then the hard-margin SVM optimization problem is

In practice, data are rarely perfectly separable. To accommodate misclassifications or margin violations, we introduce slack variables $\xi_i \geq 0$. The modified constraint is

For fixed model parameters, the smallest feasible slack variable $\xi_i$ is zero when the unit-margin constraint is met and equals its shortfall otherwise. Because the soft-margin objective below penalizes slack with a positive coefficient, it chooses this smallest value:

This expression is known as the hinge loss:

It is zero when $y_i(w^\top x_i + b) \geq 1$ (i.e., when the data point is correctly classified with a sufficient margin) and increases linearly otherwise.

We penalize the slack variables to balance margin width against margin violations. This gives the constrained soft-margin SVM problem:

where $C > 0$ balances the squared-norm penalty against total margin violations. The slack penalty is not the number of misclassified points: correctly classified points inside the unit margin also incur a penalty.

The hinge-loss expression lets us eliminate the slack variables and write the penalty as $C \sum_{i=1}^{n} \max\{0,\, 1 - y_i(w^\top x_i + b)\}$.
The equivalent unconstrained problem is therefore

The constrained formulation is a convex quadratic program. The hinge-loss formulation is also convex, but its corners make it nondifferentiable at some points. Direct optimization therefore requires subgradients or another method that allows these corners.

Some datasets cannot be well separated by a hyperplane in the original feature space. To address this, we map data into a (possibly high-dimensional) feature space using a transformation $\phi$:

The map $\phi$ takes an input $x$ from the original $p$-dimensional space to a representation $\phi(x)$ in a Hilbert space $\mathcal{H}$. In this notation:

• $\mathbb{R}^p$ is the original input space.
• $\mathcal{H}$ is a Hilbert space (often high-dimensional or even infinite-dimensional) in which the data may become linearly separable.
• The arrow $x \mapsto \phi(x)$ indicates that each data point $x$ is transformed into $\phi(x)$.

In the feature space $\mathcal{H}$, the SVM decision boundary is

Directly computing $\phi(x)$ might be impractical if $\mathcal{H}$ is very large. Instead, we define a kernel function $K$ such that

This identity is useful only once the optimization depends on features through inner products. The dual derivation below gives that form, allowing kernel evaluations to replace explicit calculations with $\phi(x)$. In finite-dimensional feature spaces, the inner product can be written as $K(x,x') = \phi(x)^T \phi(x')$. More generally, a symmetric kernel is valid when every finite matrix of pairwise kernel values, called a Gram matrix, is positive semidefinite. This means that its quadratic form is nonnegative for every vector. Such a kernel has an associated reproducing kernel Hilbert space (RKHS): a Hilbert space of functions in which evaluating a function at a fixed point is a continuous operation.

The primal problem optimizes the original decision variables subject to constraints. A general constrained minimization problem has the form

To form the dual problem, we introduce Lagrange multipliers and take the infimum of the Lagrangian over the primal variables. The resulting dual objective gives a lower bound on the primal optimum. Under conditions such as convexity and Slater’s condition, strong duality holds: the primal and dual optimal values are equal. For the soft-margin SVM, the primal variables are the weight vector $w$, bias $b$, and slack variables $\xi$, with objective

subject to

We assign Lagrange multipliers $\alpha_i \ge 0$ to the margin constraints and $\beta_i \ge 0$ to the nonnegativity constraints on the slack variables. The Lagrangian is

Differentiating the Lagrangian $L$ with respect to the primal variables gives the stationarity part of the Karush–Kuhn–Tucker (KKT) conditions. The full conditions also require primal feasibility, dual feasibility, and complementary slackness. We begin with stationarity:

Differentiating with respect to $w$:

Differentiating with respect to $b$:

Differentiating with respect to each $\xi_i$:

Since $\beta_i \ge 0$, it follows that $0 \le \alpha_i \le C$. The remaining KKT conditions, for every training point, are

Convexity and strict feasibility make these KKT conditions an optimality characterization, rather than only a set of derivative equations. Substituting the stationarity relations into the Lagrangian removes the primal variables. The remaining feature dependence is through inner products, which can be replaced by kernel evaluations. Andrew Ng’s CS229 notes, Sections 5–8, give the duality and kernel arguments in detail.

Using the feature map $\phi$ and its kernel $K(x,x') = \langle\phi(x),\phi(x')\rangle_{\mathcal H}$, the soft-margin primal problem becomes

The term $\|w\|_{\mathcal H}^2$ controls the margin width in feature space. Applying the same stationarity argument gives

Substituting this expression back into the norm term yields:

Thus, the kernelized dual formulation is:

subject to $0 \le \alpha_i \le C$ and $\sum_{i=1}^{n}\alpha_i y_i = 0$. The $L_2$ penalty now depends only on kernel evaluations. We can therefore fit a nonlinear decision boundary without explicitly computing $\phi(x)$.

• Polynomial Kernel:
  $$K(x, x') = \bigl(\alpha\, x^\top x' + c\bigr)^d,$$

  Scroll to see the full equation →
  where $\alpha\ge0$, $c\ge0$, and $d$ is a positive integer. Here $\alpha$ is a kernel parameter, not one of the dual multipliers.

• Radial Basis Function (RBF) Kernel:
  $$K(x, x') = \exp\Bigl(-\gamma\,\|x - x'\|^2\Bigr),$$

  Scroll to see the full equation →
  with $\gamma > 0$ controlling the spread.

• What happens:
  • In training, the dual formulation of the SVM uses only dot products, which are computed as $K(x_i, x_j)$.
  • The final classifier depends solely on these kernel evaluations rather than on explicit high-dimensional feature vectors.

• What does not happen:
  • We do not build or store the high-dimensional vectors $\phi(x)$.
  • We do not directly compute large dot products $\phi(x_i) \cdot \phi(x_j)$ in the transformed space.

• Distance to Hyperplane:
  $$d = \frac{|w^\top x + b|}{\|w\|}.$$

  Scroll to see the full equation →

• Margin:
  With $y_i\bigl(w^\top x_i + b\bigr) \ge 1$ and equality for at least one point, the geometric margin is $\gamma = \frac{1}{\|w\|}$.

• Hard-Margin SVM:
  $$\min_{w,b} \; \frac12 \|w\|^2 \quad \text{s.t.} \quad y_i\bigl(w^\top x_i + b\bigr) \ge 1.$$

  Scroll to see the full equation →

• Hinge Loss:
  $$\max\{0,\,1 - y_i\bigl(w^\top x_i + b\bigr)\}.$$

  Scroll to see the full equation →

• Soft-Margin SVM:
  $$\min_{w,b} \; \frac12 \|w\|^2 + C \sum_{i=1}^n \max\{0,\,1 - y_i\bigl(w^\top x_i + b\bigr)\}.$$

  Scroll to see the full equation →

• Kernel Trick:
  $$K(x,x') = \langle\phi(x),\phi(x')\rangle_{\mathcal H},$$

  Scroll to see the full equation →
  which allows us to implicitly map data to a high-dimensional space without explicitly computing $\phi(x)$.

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

  Scroll to see the full equation →
  subject to $0 \le \alpha_i \le C$ and $\sum_{i=1}^{n}\alpha_i y_i = 0$.