硬间隔支持向量机

形式陈述 ​

取非空有限样本 $m\ge 1$、标签 $y_i\in \{-1,+1\}$，以及到实Hilbert 空间理路Hilbert 空间Hilbert space关于内积诱导范数完备的实或复内积空间。 $H$ 的固定特征映射 $\varphi$。硬间隔 SVM 的原始问题固定为

这是具有平方范数目标和仿射约束的凸优化模型理路凸优化问题Convex optimization problem在凸可行域上最小化凸目标且不等式约束为凸函数的优化模型。。约束把最小函数间隔的下界固定为 $1$。若两类都出现且严格可分，可行权向量必非零；按几何间隔理路线性分类器与几何间隔Linear classifier · Geometric margin用仿射超平面分类，并以缩放不变的几何间隔衡量分离余量。定义，其最小间隔至少为 $1/\Vert w\Vert$。最优时最小函数间隔恰为 $1$，否则可同时缩小 $(w,b)$ 改善目标。因此在这个非退化情形，最小化 $\frac{1}{2}\Vert w{\Vert }^2$ 等价于最大化几何间隔。$b$ 不惩罚，因而不能未经说明把它并入 $w$ 的范数。

问题要求样本在该特征空间严格可分。即使 $H$ 无限维，也只需考虑 $V=\mathrm{span}\{\varphi (x_i){\}}_{i=1}^m$：由正交投影理路Hilbert 空间投影定理Hilbert projection theorem · Projection theoremHilbert 空间中每个闭线性子空间都给出唯一的正交分解与最近点投影。，将 $w$ 换成 $P_{V}w$ 保留每个训练分数和截距 $b$，并使范数不增。这将训练化为有限维凸二次规划。两类均出现时，目标上界限制 $w$，正、负类约束再分别限制 $b$ 的下、上界；由有限维的Heine–Borel 定理理路Heine–Borel 定理Heine–Borel theorem欧氏空间子集紧致当且仅当它闭且有界。，这些闭水平集紧，极值定理理路极值定理Extreme value theorem连续实值函数在非空紧空间上取得最大值和最小值。保证最优解存在。只有一类时可直接取 $w=0$ 和合适的常数截距达到零目标，此时不用 $1/\Vert w\Vert$ 解释间隔。

对严格可分的两类数据，放大一个可行解即可取得严格可行性。KKT 条件理路KKT 条件Karush–Kuhn–Tucker conditions · KKT conditions用可行性、乘子符号、互补松弛与驻点方程刻画约束最优性的条件。的驻点方程于是给出

于是借助核技巧理路核技巧kernel trick · kernelization by inner products · 核替换将只依赖特征内积的算法改写为 Gram 矩阵计算，从而隐式使用特征空间。，并固定零分数时预测 $+1$，决策函数为

${\alpha }_i>0$ 的训练点称为支持向量；互补松弛使它们位于 $y_{i}f(x_i)=1$ 的 margin 边界。核技巧是计算工具，不是硬间隔 SVM 的定义前置：取 $\varphi (x)=x$ 就得到普通线性 SVM。