Hard- and soft-margin support-vector machines with an unpenalized bias

Let $X$ be a set, let $\mathcal{H}$ be a real Hilbert space, and let $\varphi :X\to \mathcal{H}$ be a feature map. Define its kernel by $k(x,z):=⟨\varphi (x),\varphi (z){⟩}_{\mathcal{H}}$. For a finite labeled sample $(x_i,y_i{)}_{i=1}^n$ with $n\ge 1$, $x_i\in X$, and $y_i\in \{-1,+1\}$, the soft-margin support-vector machine with cost $C>0$ is

${\min }_{w\in \mathcal{H},b\in \mathbb{R},\xi \in {\mathbb{R}}^n}\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}_{\mathcal{H}}^2+C{\sum }_{i=1}^n{\xi }_i$

subject to

$y_i(⟨w,\varphi (x_i){⟩}_{\mathcal{H}}+b)\ge 1-{\xi }_i,{\xi }_i\ge 0(1\le i\le n)\mathrm{.}$

The bias $b$ is unpenalized. The associated real score is $s_{w,b}(x):=⟨w,\varphi (x){⟩}_{\mathcal{H}}+b$. If a binary label is required, use the deterministic rule $+1$ when $s_{w,b}(x)\ge 0$ and $-1$ otherwise. The score is not defined as a probability, and this optimization includes no probability-calibration map.

The hard-margin problem removes the slack variables and minimizes $\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}_{\mathcal{H}}^2$ subject to $y_i(⟨w,\varphi (x_i){⟩}_{\mathcal{H}}+b)\ge 1$ for every $i$. In this library, “margin-separable sample” means exactly that this hard-margin feasible set is nonempty; no hard-margin conclusion is asserted for a sample that fails this condition.

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §§12.2.1 and 12.3.1–12.3.3

Rasmussen and Williams, Gaussian Processes for Machine Learning, §6.4.1

Positive semidefinite kernels and reproducing kernel Hilbert spaces

Hilbert space