描述：本节从最大间隔分类器出发，推导硬间隔 SVM 的原始问题、拉格朗日对偶、KKT 条件和 SMO，进一步整理特征映射、核函数以及 $\epsilon$-不敏感支持向量回归。

6.1 最大间隔思想

对线性可分训练集，能把两类样本分开的超平面通常不止一个。支持向量机选择两类之间间隔最大的超平面，以提高分类鲁棒性和泛化能力。

超平面写为

$$ \boldsymbol{w}^{\mathrm T}\boldsymbol{x}+b=0. $$

点 $\boldsymbol{x}$ 到超平面的几何距离为

$$ r

\frac{ \left|\boldsymbol{w}^{\mathrm T}\boldsymbol{x}+b\right| }{ |\boldsymbol{w}| }. $$

把正、负类标签记为 $y_i\in{+1,-1}$，通过缩放 $\boldsymbol{w},b$，可令离超平面最近的样本满足

$$ y_i \left( \boldsymbol{w}^{\mathrm T}\boldsymbol{x}_i+b \right)=1. $$

两条间隔边界为

$$ \boldsymbol{w}^{\mathrm T}\boldsymbol{x}+b=1 $$

和

$$ \boldsymbol{w}^{\mathrm T}\boldsymbol{x}+b=-1. $$

两者距离，即总间隔为

$$ \gamma=\frac{2}{|\boldsymbol{w}|}. $$

• 落在间隔边界上的训练样本称为支持向量。
• 间隔越大，分类边界对样本小扰动越不敏感。

6.2 硬间隔 SVM 原始问题

最大化

$$ \frac{2}{|\boldsymbol{w}|} $$

等价于最小化

$$ \frac{1}{2}|\boldsymbol{w}|^2. $$

硬间隔 SVM 的原始问题为

$$ \begin{aligned} \min_{\boldsymbol{w},b}\quad& \frac{1}{2}|\boldsymbol{w}|^2\ \text{s.t.}\quad& y_i \left( \boldsymbol{w}^{\mathrm T}\boldsymbol{x}_i+b \right)\geq1, \quad i=1,2,\ldots,m. \end{aligned} $$

• 这是凸二次规划问题。
• 硬间隔要求训练样本线性可分；若存在噪声或错分，需要软间隔等扩展。

6.3 拉格朗日对偶

6.3.1 构造拉格朗日函数

为每个约束引入拉格朗日乘子 $\alpha_i\geq0$：

$$ L(\boldsymbol{w},b,\boldsymbol{\alpha})

\frac{1}{2}|\boldsymbol{w}|^2 +\sum_{i=1}^{m} \alpha_i \left[ 1-y_i \left( \boldsymbol{w}^{\mathrm T}\boldsymbol{x}_i+b \right) \right]. $$

令 $L$ 对 $\boldsymbol{w}$ 和 $b$ 的偏导为 $0$：

$$ \boldsymbol{w} =\sum_{i=1}^{m} \alpha_i y_i\boldsymbol{x}_i, $$

$$ \sum_{i=1}^{m}\alpha_i y_i=0. $$

6.3.2 对偶问题

把上式代回拉格朗日函数，得到

$$ \begin{aligned} \max_{\boldsymbol{\alpha}}\quad& \sum_{i=1}^{m}\alpha_i -\frac{1}{2} \sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy_iy_j \boldsymbol{x}_i^{\mathrm T}\boldsymbol{x}j\ \text{s.t.}\quad& \sum{i=1}^{m}\alpha_i y_i=0,\ &\alpha_i\geq0, \quad i=1,2,\ldots,m. \end{aligned} $$

最终判别函数为

$$ f(\boldsymbol{x}) =\boldsymbol{w}^{\mathrm T}\boldsymbol{x}+b

\sum_{i=1}^{m} \alpha_i y_i \boldsymbol{x}_i^{\mathrm T}\boldsymbol{x} +b. $$

分类结果通常取

$$ \operatorname{sign}(f(\boldsymbol{x})). $$

6.4 KKT 条件与稀疏性

硬间隔问题的互补松弛条件为

$$ \alpha_i \left[ 1-y_if(\boldsymbol{x}_i) \right]=0. $$

结合

$$ \alpha_i\geq0 $$

和

$$ y_if(\boldsymbol{x}_i)\geq1, $$

可知每个样本必满足以下至少一个条件：

$$ \alpha_i=0 $$

或

$$ y_if(\boldsymbol{x}_i)=1. $$

• 非支持向量位于间隔之外，通常有 $\alpha_i=0$，不出现在最终求和中。
• 支持向量位于间隔边界上，可有 $\alpha_i>0$。
• 因此训练完成后，最终模型只与少量支持向量有关，具有稀疏性。

对任一满足 $y_sf(\boldsymbol{x}_s)=1$ 的支持向量，可求

$$ b =y_s -\sum_{i=1}^{m} \alpha_i y_i \boldsymbol{x}_i^{\mathrm T}\boldsymbol{x}_s. $$

• 为提高数值鲁棒性，通常对多个支持向量得到的 $b$ 取平均。

6.5 SMO 求解

序列最小最优化（SMO）反复执行：

1. 选择一对需要更新的变量 $\alpha_i,\alpha_j$。
2. 固定其余乘子，把对偶问题化为关于这一对变量的小规模问题。
3. 利用约束

$$ \sum_{k=1}^{m}\alpha_ky_k=0 $$

得到

$$ \alpha_i y_i+\alpha_j y_j=c, $$

把一个变量表示为另一个变量，求闭式更新并裁剪到可行域。 4. 重复直到满足收敛和 KKT 条件。

• 对偶约束使单独更新一个 $\alpha_i$ 通常无法保持等式成立，因此 SMO 每次至少联合更新两个变量。

6.6 特征空间映射

若原始空间中样本不能被线性超平面正确分开，可使用映射

$$ \phi:\mathcal X\rightarrow\mathcal H $$

把输入映射到更高维特征空间，在该空间中构造线性分类器：

$$ f(\boldsymbol{x})

\boldsymbol{w}^{\mathrm T} \phi(\boldsymbol{x})+b. $$

相应原始问题为

$$ \begin{aligned} \min_{\boldsymbol{w},b}\quad& \frac{1}{2}|\boldsymbol{w}|^2\ \text{s.t.}\quad& y_i \left( \boldsymbol{w}^{\mathrm T}\phi(\boldsymbol{x}_i)+b \right)\geq1. \end{aligned} $$

对偶问题只通过内积

$$ \phi(\boldsymbol{x}_i)^\mathrm T \phi(\boldsymbol{x}_j) $$

依赖映射后的特征。

• 高维特征空间可能维数极高甚至无限，显式构造 $\phi(\boldsymbol{x})$ 会带来巨大计算和存储开销。

6.7 核函数

核技巧直接在原空间计算高维特征内积：

$$ \kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)

\phi(\boldsymbol{x}_i)^\mathrm T \phi(\boldsymbol{x}_j). $$

于是对偶目标中的

$$ \boldsymbol{x}_i^\mathrm T\boldsymbol{x}_j $$

替换为

$$ \kappa(\boldsymbol{x}_i,\boldsymbol{x}_j), $$

无需显式求出 $\phi$。

核化后的判别函数为

$$ f(\boldsymbol{x})

\sum_{i=1}^{m} \alpha_i y_i \kappa(\boldsymbol{x}_i,\boldsymbol{x}) +b. $$

6.7.1 Mercer 条件与核矩阵

对有限样本 ${\boldsymbol{x}_1,\ldots,\boldsymbol{x}_m}$，核矩阵为

$$ \boldsymbol{K}_{ij} =\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j). $$

有效核函数应使核矩阵对称、半正定，即对任意 $\boldsymbol{c}$ 有

$$ \boldsymbol{c}^{\mathrm T} \boldsymbol{K} \boldsymbol{c}\geq0. $$

• 满足相应条件的核函数隐式定义一个再生核希尔伯特空间（RKHS）。
• 源资料把“核矩阵主对角线为 0、副对角线对称”作为条件，这实际上混淆了距离矩阵与核 Gram 矩阵。核矩阵对角元是

$$ K_{ii} =\kappa(\boldsymbol{x}_i,\boldsymbol{x}_i) =|\phi(\boldsymbol{x}_i)|^2\geq0, $$

一般不为 $0$；关键条件是对称半正定。

• 不同核函数对应不同特征空间与归纳偏好，核函数选择是 SVM 模型选择的关键。

6.8 支持向量回归

支持向量回归（SVR）允许预测与真实输出之间存在宽度为 $2\epsilon$ 的无损失间隔带。

$\epsilon$-不敏感损失为

$$ \ell_\epsilon(z)

\begin{cases} 0,&|z|\leq\epsilon,\ |z|-\epsilon,&|z|>\epsilon. \end{cases} $$

• 落在间隔带内的样本不计损失，带外样本只计算超出 $\epsilon$ 的部分。
• 与对所有残差都平方惩罚的最小二乘不同，SVR 对小误差不敏感。

引入松弛变量 $\xi_i,\hat\xi_i$ 后，原始问题为

$$ \begin{aligned} \min_{\boldsymbol{w},b,\boldsymbol{\xi},\hat{\boldsymbol{\xi}}} \quad& \frac{1}{2}|\boldsymbol{w}|^2 +C\sum_{i=1}^{m} (\xi_i+\hat\xi_i)\ \text{s.t.}\quad& f(\boldsymbol{x}_i)-y_i \leq\epsilon+\xi_i,\ & y_i-f(\boldsymbol{x}_i) \leq\epsilon+\hat\xi_i,\ & \xi_i\geq0,\quad \hat\xi_i\geq0. \end{aligned} $$

其对偶形式可写为

$$ \begin{aligned} \max_{\boldsymbol{\alpha},\hat{\boldsymbol{\alpha}}}\quad& \sum_{i=1}^{m} y_i(\hat\alpha_i-\alpha_i) -\epsilon\sum_{i=1}^{m} (\alpha_i+\hat\alpha_i)\ &-\frac{1}{2} \sum_{i=1}^{m}\sum_{j=1}^{m} (\hat\alpha_i-\alpha_i) (\hat\alpha_j-\alpha_j) \boldsymbol{x}_i^\mathrm T\boldsymbol{x}j\ \text{s.t.}\quad& \sum{i=1}^{m} (\hat\alpha_i-\alpha_i)=0,\ & 0\leq\alpha_i,\hat\alpha_i\leq C. \end{aligned} $$

预测函数为

$$ f(\boldsymbol{x})

\sum_{i=1}^{m} (\hat\alpha_i-\alpha_i) \boldsymbol{x}_i^\mathrm T\boldsymbol{x} +b. $$

• 核化 SVR 只需把内积替换为核函数。
• $C$ 控制模型平坦程度与带外误差的权衡；$\epsilon$ 控制无损失间隔带宽。

6.9 使用层次

源资料把 SVM 的使用概括为三个层次：

• 入门：能够调用和实现常见 SVM 版本。
• 进阶：理解并尝试选择、组合核函数。
• 深入：根据具体问题设计目标函数、替代损失和约束。

6.10 易错点

• 支持向量到分类超平面的单侧距离是 $1/|\boldsymbol{w}|$，两条间隔边界的总宽度才是 $2/|\boldsymbol{w}|$。
• 最大化间隔等价于最小化 $\frac12|\boldsymbol{w}|^2$，不是最小化间隔本身。
• 对偶问题是最大化问题；原始问题是最小化问题。
• 硬间隔 SVM 中，$\alpha_i>0$ 的样本位于间隔边界。软间隔 SVM 中，$0<\alpha_i<C$ 的样本位于间隔边界，而 $\alpha_i=C$ 的支持向量还可落在间隔内或被误分类；写成“所有支持向量都在 $\pm1$ 边界”是错误的。
• SMO 每次更新两个拉格朗日乘子，是为了维持 $\sum_i\alpha_iy_i=0$。
• 核函数计算的是特征空间内积，不是直接计算距离。
• Mercer 核矩阵应对称半正定，对角线一般不为 $0$。
• “映射到更高维一定线性可分”需要结合有限样本、所选映射和模型条件理解；核技巧本身不保证任意数据在任意核下都可分。
• 硬间隔 SVM 要求线性可分；现实数据通常还需软间隔参数 $C$。
• SVR 的 $2\epsilon$ 间隔带内损失为 $0$，带外损失为 $|z|-\epsilon$。

相关知识

• 科目导航：复试常考科目导航
• 阅读顺序：上一篇：神经网络模型 · 下一篇：贝叶斯决策论

6.11 本节复盘

• 硬间隔 SVM 的支持向量位于 $\boldsymbol{w}^{\mathrm T}\boldsymbol{x}+b=\pm1$ 上，总间隔为 $2/|\boldsymbol{w}|$；软间隔支持向量还可位于间隔内或错误一侧。
• 硬间隔原始问题最小化 $\frac12|\boldsymbol{w}|^2$，对偶问题只依赖样本内积。
• 只有 $\alpha_i>0$ 的支持向量进入最终判别函数，因此解常具有稀疏性；但支持向量数量取决于数据、核与超参数，不能保证总是很少。
• SMO 每次联合更新两个乘子，以满足对偶等式约束。
• 核函数用 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)$ 直接计算高维特征内积；有效核矩阵应对称半正定。
• 核函数决定隐式特征空间，因此核选择属于重要的模型选择问题。
• SVR 用 $\epsilon$-不敏感损失忽略间隔带内的小误差，并用 $C$ 平衡模型平坦性与带外误差。