非线性支持向量机求解算法

非线性支持向量机求解算法

1. 非线性支持向量机的对偶优化问题回顾

非线性支持向量机的学习问题，通过引入松弛变量和核函数，最终转化为以下凸二次规划问题（对偶问题）：

${\min }_{\mathbf{\alpha }}W(\mathbf{\alpha })=\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)-{\sum }_{i=1}^N{\alpha }_i$

$\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0\text{ (约束 1)}$

$0\le {\alpha }_i\le C\text{对于所有 }i=1,\dots ,N\text{ (约束 2)}$

其中，$\mathbf{\alpha }=({\alpha }_1,\dots ,{\alpha }_N{)}^T$ 是拉格朗日乘子向量，$K({\mathbf{x}}_i,{\mathbf{x}}_j)$ 是核函数，$C$ 是惩罚参数。 这是一个具有 $N$ 个变量（${\alpha }_i$）和 $N+1$ 个约束（一个等式约束和 $N$ 个边界约束）的二次规划问题。当训练样本数量 $N$ 很大时，直接使用通用的二次规划求解器会非常低效。

2. 坐标下降法 (Coordinate Descent)

2.1 坐标下降法的基本原理

坐标下降法 (Coordinate Descent, CD) 是一种优化算法，其基本思想是：

• 在每次迭代中，只选择目标函数中的一个变量进行优化，同时固定其他所有变量。
• 对选定的变量，求解其最优值。
• 重复这个过程，轮流更新所有变量，直到目标函数收敛。

优点：当目标函数关于每个变量都是凸的（即使整体不是凸的），并且每个单变量优化问题都容易求解时，CD 算法非常有效。

2.2 坐标下降法在非线性 SVM 中的应用分析

对于非线性 SVM 的对偶问题，我们能将目标函数 $W(\mathbf{\alpha })$ 写成关于 ${\alpha }_i$ 的二次函数，所以对单个 ${\alpha }_i$ 而言，其优化是容易的。那么，坐标下降法可以直接应用吗？

答案：不能直接应用，会导致失败。

原因分析： 问题在于约束 1: ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$。

• 这个约束将所有的 ${\alpha }_i$ 都耦合在了一起。
• 如果我们只选择一个 ${\alpha }_i$ 进行更新，比如我们更新 ${\alpha }_1$ 而固定其他 ${\alpha }_2,\dots ,{\alpha }_N$，那么为了保持 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 这个等式约束，除非被更新的 ${\alpha }_1$ 恰好不改变其值，否则这个约束就会立即被违反。
• 换句话说，要满足这个等式约束，每次更新至少需要同时调整两个 $\alpha$ 值，使得它们的变化相互抵消，从而保持求和为零。

因此，朴素的坐标下降法（每次只更新一个变量）无法直接应用于带有这种等式约束的 SVM 对偶问题。

3. 序列最小优化 (Sequential Minimal Optimization, SMO) 算法

为了解决 SVM 对偶问题的大规模计算挑战，John Platt 于 1998 年提出了序列最小优化 (SMO) 算法。SMO 巧妙地规避了坐标下降法的限制，成为目前最广泛使用的 SVM 训练算法。

3.1 SMO 的核心思想：分解为二维子问题

SMO 的核心思想正是为了解决坐标下降法遇到的问题：

• SMO 每次迭代选择两个拉格朗日乘子 ${\alpha }_i$ 和 ${\alpha }_j$ 进行优化。
• 同时固定所有其他 $N-2$ 个 ${\alpha }_k$（$k\ne i,j$）。
• 将原始的 $N$ 维优化问题分解为一系列二维子问题 (Two-Variable Subproblems)。

为什么是两个变量？

• 当固定所有其他 ${\alpha }_k$ 时，等式约束 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 就可以简化为只涉及这两个变量 ${\alpha }_i,{\alpha }_j$ 的一个线性等式。例如，如果选择 ${\alpha }_1,{\alpha }_2$： ${\alpha }_1{y}_1+{\alpha }_2{y}_2+{\sum }_{k=3}^N{\alpha }_k{y}_k=0$

  ${\alpha }_1{y}_1+{\alpha }_2{y}_2=-{\sum }_{k=3}^N{\alpha }_k{y}_k=\text{常数 }\zeta$ 这个常数 $\zeta$ 是由固定不变的 ${\alpha }_k$ 决定的。

• 有了这个线性的等式约束，我们就可以用其中一个变量表示另一个变量（例如 ${\alpha }_1=(\zeta -{\alpha }_2{y}_2)/y_1$），从而将二维优化问题转化为一个单变量的无约束二次函数最小化问题，然后结合边界约束 $[0,C]$ 进行求解。这种单变量的二次问题可以解析求解，效率极高。

3.2 SMO 的优化目标

我们从原始的对偶问题出发，抽取只依赖于 ${\alpha }_1$ 和 ${\alpha }_2$ 的项。 原目标函数： $W(\mathbf{\alpha })=\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)-{\sum }_{i=1}^N{\alpha }_i$

为了简化表达，我们只保留与 ${\alpha }_1,{\alpha }_2$ 相关的项，并将不相关的项视为常数：

$W({\alpha }_1,{\alpha }_2)=\frac{1}{2}\left({\alpha }_1^2{y}_1^2{K}_{11}+{\alpha }_2^2{y}_2^2{K}_{22}+2{\alpha }_1{\alpha }_2{y}_1{y}_2{K}_{12}\right)$ $+{\alpha }_1{y}_1{\sum }_{j=3}^N{\alpha }_j{y}_j{K}_{1j}+{\alpha }_2{y}_2{\sum }_{j=3}^N{\alpha }_j{y}_j{K}_{2j}$ $-{\alpha }_1-{\alpha }_2+\text{常数项}$

解释：

• $K_{ij}=K({\mathbf{x}}_i,{\mathbf{x}}_j)$。
• $y_i^2=1$ (因为 $y_i\in \{-1,+1\}$)。
• ${\sum }_{j=3}^N{\alpha }_j{y}_j{K}_{1j}$ 包含了固定变量对 ${\alpha }_1$ 所在项的贡献，我们可以简写为 $V_1$。
• ${\sum }_{j=3}^N{\alpha }_j{y}_j{K}_{2j}$ 包含了固定变量对 ${\alpha }_2$ 所在项的贡献，我们可以简写为 $V_2$.

所以，目标函数可以简化为：

$W({\alpha }_1,{\alpha }_2)=\frac{1}{2}{K}_{11}{\alpha }_1^2+\frac{1}{2}{K}_{22}{\alpha }_2^2+y_1{y}_2{K}_{12}{\alpha }_1{\alpha }_2+y_1{V}_1{\alpha }_1+y_2{V}_2{\alpha }_2-{\alpha }_1-{\alpha }_2+\text{常数}$

同时，我们有线性约束：${\alpha }_1{y}_1+{\alpha }_2{y}_2=\zeta$ (常数)。

3.3 最优解的解析推导

为了求解 ${\alpha }_1,{\alpha }_2$，我们利用约束 ${\alpha }_1{y}_1+{\alpha }_2{y}_2=\zeta$ 来将 ${\alpha }_1$ 表示为 ${\alpha }_2$ 的函数。 从约束得到：${\alpha }_1=(\zeta -{\alpha }_2{y}_2)/y_1$。 将 ${\alpha }_1$ 代入 $W({\alpha }_1,{\alpha }_2)$，得到一个只关于 ${\alpha }_2$ 的二次函数 $W({\alpha }_2)$。为了最小化这个二次函数，我们对其求导并令导数等于零。

推导 ${\alpha }_2^{\text{new, unclipped}}$：

这个推导涉及到当前的模型输出误差 $E_i=f({\mathbf{x}}_i)-y_i$，其中 $f({\mathbf{x}}_i)={\sum }_{k=1}^N{\alpha }_k{y}_{k}K({\mathbf{x}}_k,{\mathbf{x}}_i)+b$。

我们使用 ${\alpha }_1^{old}$ 和 ${\alpha }_2^{old}$ 作为当前值。 ${\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2=\zeta$。

化简后的目标函数（关于 ${\alpha }_2$ 的二次函数）为：

$W({\alpha }_2)=\frac{1}{2}(K_{11}+K_{22}-2K_{12}){\alpha }_2^2+y_2(E_1^{old}-E_2^{old}){\alpha }_2+\text{常数}$

解释：

• $E_1^{old}=({\sum }_{k=1}^N{\alpha }_k^{old}{y}_{k}K({\mathbf{x}}_k,{\mathbf{x}}_1)+b^{old})-y_1$
• $E_2^{old}=({\sum }_{k=1}^N{\alpha }_k^{old}{y}_{k}K({\mathbf{x}}_k,{\mathbf{x}}_2)+b^{old})-y_2$
• $\eta =K_{11}+K_{22}-2K_{12}$（在图片中也有这个符号），它通常被称为二次项系数，且 $\eta \ge 0$。如果 $\eta =0$，则可能需要特殊处理。

对 $W({\alpha }_2)$ 关于 ${\alpha }_2$ 求导并令为零：

$\frac{\partial W}{\partial {\alpha }_2}=(K_{11}+K_{22}-2K_{12}){\alpha }_2+y_2(E_1^{old}-E_2^{old})=0$

解出 ${\alpha }_2$：

${\alpha }_2^{\text{new, unclipped}}={\alpha }_2^{old}+\frac{y_2(E_1^{old}-E_2^{old})}{K_{11}+K_{22}-2K_{12}}$

解释：这是在不考虑边界约束 $[0,C]$ 的情况下，${\alpha }_2$ 的最优解。它利用了当前模型在 ${\mathbf{x}}_1$ 和 ${\mathbf{x}}_2$ 上的预测误差。

3.4 约束条件下的解 (Clipping)

由于 ${\alpha }_1,{\alpha }_2$ 必须满足边界约束 $0\le {\alpha }_1\le C$ 和 $0\le {\alpha }_2\le C$，以及线性约束 ${\alpha }_1{y}_1+{\alpha }_2{y}_2=\zeta$。我们需要对 ${\alpha }_2^{\text{new, unclipped}}$ 进行裁剪。

线性约束 ${\alpha }_1{y}_1+{\alpha }_2{y}_2=\zeta$ 定义了 $({\alpha }_1,{\alpha }_2)$ 在一个平面上的直线。同时，方框约束 $0\le {\alpha }_1\le C$ 和 $0\le {\alpha }_2\le C$ 定义了一个边长为 $C$ 的正方形区域。因此，$({\alpha }_1,{\alpha }_2)$ 的可行域是这条直线段与正方形区域的交集。

根据 $y_1$ 和 $y_2$ 的关系（同号或异号），这条直线的形状和截距不同：

1. 情况 1: $y_1=y_2$ (同号) 此时 $y_1{\alpha }_1+y_2{\alpha }_2=y_1({\alpha }_1+{\alpha }_2)=\zeta ⟹{\alpha }_1+{\alpha }_2=\zeta y_1=\text{常数 }k$。 这是一条斜率为 -1 的直线。 通过计算直线与正方形边界的交点，可以确定 ${\alpha }_2$ 的边界 $L$ 和 $H$： $L=\max (0,{\alpha }_2^{old}+{\alpha }_1^{old}-C)$ $H=\min (C,{\alpha }_2^{old}+{\alpha }_1^{old})$

2. 情况 2: $y_1\ne y_2$ (异号) 此时 $y_1{\alpha }_1+y_2{\alpha }_2=y_1{\alpha }_1-y_1{\alpha }_2=\zeta ⟹{\alpha }_1-{\alpha }_2=\zeta y_1=\text{常数 }k$。 这是一条斜率为 1 的直线。 通过计算直线与正方形边界的交点，可以确定 ${\alpha }_2$ 的边界 $L$ 和 $H$： $L=\max (0,{\alpha }_2^{old}-{\alpha }_1^{old})$ $H=\min (C,C+{\alpha }_2^{old}-{\alpha }_1^{old})$

计算出 $L$ 和 $H$ 后，对 ${\alpha }_2^{\text{new, unclipped}}$ 进行裁剪，得到最终的 ${\alpha }_2^{\text{new}}$：

${\alpha }_2^{\text{new}}=\{\begin{array}{ll}H& \text{如果 }{\alpha }_2^{\text{new, unclipped}}>H\\ {\alpha }_2^{\text{new, unclipped}}& \text{如果 }L\le {\alpha }_2^{\text{new, unclipped}}\le H\\ L& \text{如果 }{\alpha }_2^{\text{new, unclipped}}<L\end{array}$

更新 ${\alpha }_1^{\text{new}}$： 一旦 ${\alpha }_2^{\text{new}}$ 确定，根据线性约束 ${\alpha }_1^{\text{new}}{y}_1+{\alpha }_2^{\text{new}}{y}_2=\zeta$：

${\alpha }_1^{\text{new}}={\alpha }_1^{old}+y_1{y}_2({\alpha }_2^{old}-{\alpha }_2^{\text{new}})$

解释：这个公式确保了即使在裁剪后，${\alpha }_1^{\text{new}}$ 和 ${\alpha }_2^{\text{new}}$ 仍然满足线性约束。

3.5 偏置项 $b$ 的更新

每次迭代后，偏置项 $b$ 也需要更新。$b$ 的更新依赖于 KKT 条件。 理想情况下，当 $0<{\alpha }_i^{new}<C$ 时，样本 ${\mathbf{x}}_i$ 是支持向量，且 ${\xi }_i=0$，KKT 条件要求 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=1$。 所以 $b=y_i-{\mathbf{w}}^T{\mathbf{x}}_i=y_i-{\sum }_{k=1}^N{\alpha }_k{y}_{k}K({\mathbf{x}}_k,{\mathbf{x}}_i)$。 为了数值稳定性，SMO 会根据更新后的 ${\alpha }_1^{\text{new}}$ 和 ${\alpha }_2^{\text{new}}$ 来更新 $b$：

• 如果 $0<{\alpha }_1^{\text{new}}<C$： $b_1^{\text{new}}=y_1-{\sum }_{k=1}^N{\alpha }_k^{\text{new}}{y}_{k}K({\mathbf{x}}_k,{\mathbf{x}}_1)=y_1-({\alpha }_1^{\text{new}}{y}_1{K}_{11}+{\alpha }_2^{\text{new}}{y}_2{K}_{12}+{\sum }_{k=3}^N{\alpha }_k^{old}{y}_k{K}_{k1})$ 这个可以简化为：$b_1^{\text{new}}=b^{old}-E_1^{old}-y_1{K}_{11}({\alpha }_1^{\text{new}}-{\alpha }_1^{old})-y_2{K}_{12}({\alpha }_2^{\text{new}}-{\alpha }_2^{old})$

• 如果 $0<{\alpha }_2^{\text{new}}<C$： $b_2^{\text{new}}=y_2-{\sum }_{k=1}^N{\alpha }_k^{\text{new}}{y}_{k}K({\mathbf{x}}_k,{\mathbf{x}}_2)$ 这个可以简化为：$b_2^{\text{new}}=b^{old}-E_2^{old}-y_1{K}_{12}({\alpha }_1^{\text{new}}-{\alpha }_1^{old})-y_2{K}_{22}({\alpha }_2^{\text{new}}-{\alpha }_2^{old})$

• 最终 $b$ 的更新规则：

  • 如果 $0<{\alpha }_1^{\text{new}}<C$ 且 $0<{\alpha }_2^{\text{new}}<C$，则 $b^{\text{new}}=b_1^{\text{new}}=b_2^{\text{new}}$。
  • 如果 ${\alpha }_1^{\text{new}}$ 和 ${\alpha }_2^{\text{new}}$ 都不在 $(0,C)$ 区间内（即它们是 0 或 $C$），那么理论上 $b$ 的取值范围由 KKT 条件决定，此时可以取 $b_1^{\text{new}}$ 和 $b_2^{\text{new}}$ 的中点，即 $b^{\text{new}}=(b_1^{\text{new}}+b_2^{\text{new}})/2$。

3.6 变量选择启发式

SMO 算法的关键在于如何高效地选择每次迭代要优化的两个 ${\alpha }_i$ 和 ${\alpha }_j$。选择策略对算法的收敛速度有显著影响。

1. 选择第一个 ${\alpha }_i$ (外层循环)： 通常选择一个最严重违反 KKT 条件的样本点对应的 ${\alpha }_i$。 KKT 条件的核心是：
   • 如果 ${\alpha }_i=0$，则 $y_{i}f({\mathbf{x}}_i)\ge 1$
   • 如果 $0<{\alpha }_i<C$，则 $y_{i}f({\mathbf{x}}_i)=1$
   • 如果 ${\alpha }_i=C$，则 $y_{i}f({\mathbf{x}}_i)\le 1$ 违反 KKT 条件意味着上述关系不成立。算法会遍历所有样本，寻找违反程度最大的 ${\alpha }_i$。
2. 选择第二个 ${\alpha }_j$ (内层循环)： 一旦确定了第一个 ${\alpha }_i$，选择第二个 ${\alpha }_j$ 的目标是使得目标函数 $W(\mathbf{\alpha })$ 有足够大的变化。 这通常通过最大化 $|E_i-E_j|$ 来实现（即选择与第一个 ${\alpha }_i$ 对应误差 $E_i$ 差距最大的 $E_j$ 的 ${\alpha }_j$）。因为 ${\alpha }_2^{\text{new, unclipped}}$ 的更新量正比于 $E_1-E_2$，最大化这个差值能够最大化更新步长。 如果这种选择方式没有显著改进，则可以退而求其次，遍历所有非边界值（$0<{\alpha }_k<C$）的 ${\alpha }_k$，直到找到合适的 ${\alpha }_j$。

3.7 SMO 算法的整体流程

1. 初始化：设置 $\mathbf{\alpha }=0$，偏置 $b=0$。选择惩罚参数 $C$ 和收敛容差 tol。
2. 外层循环：
   • 遍历所有样本，检查它们是否违反 KKT 条件。
   • 如果发现违反 KKT 条件的 ${\alpha }_i$，则将其选为第一个变量。
   • 如果没有变量违反 KKT 条件（或违反程度小于 tol），则算法收敛，停止迭代。
3. 内层循环：
   • 在确定第一个 ${\alpha }_i$ 后，选择使目标函数变化最大的第二个 ${\alpha }_j$。
   • 如果成功找到了合适的 ${\alpha }_j$，则进行下面的优化步骤。
   • 如果找不到合适的 ${\alpha }_j$，则放弃当前选择的 ${\alpha }_i$，重新在外层循环中选择下一个 ${\alpha }_i$。
4. 优化步骤： a. 计算 ${\alpha }_2^{\text{new, unclipped}}$。 b. 根据 $y_1,y_2$ 的关系和 $C$ 值，计算 ${\alpha }_2$ 的裁剪边界 $L,H$。 c. 将 ${\alpha }_2^{\text{new, unclipped}}$ 裁剪到 $[L,H]$ 范围内，得到 ${\alpha }_2^{\text{new}}$。 d. 如果 ${\alpha }_2^{\text{new}}$ 相对于 ${\alpha }_2^{old}$ 的变化太小（小于一个极小的阈值），则放弃本次更新，重新选择 ${\alpha }_j$ 或跳出内层循环。 e. 根据 ${\alpha }_2^{\text{new}}$，更新 ${\alpha }_1^{\text{new}}$。 f. 更新偏置项 $b^{\text{new}}$。 g. 更新所有相关的误差缓存 $E_k$。

4. 总结

• 线性 SVM 的对偶问题是一个凸二次规划问题，其目标函数和约束条件都依赖于拉格朗日乘子 $\mathbf{\alpha }$。
• 坐标下降法由于等式约束的存在，无法直接应用于 SVM 的对偶问题，因为它无法在每次只更新一个变量的情况下保持约束。
• 序列最小优化 (SMO) 算法是解决 SVM 对偶问题的核心。它通过每次选择两个 ${\alpha }_i$ 进行优化，巧妙地将 $N$ 维问题分解为一系列可以解析求解的二维子问题。
• SMO 的高效性在于其解析解和启发式的变量选择策略，使其能够有效地处理大规模数据集。
• KKT 条件在 SMO 算法中扮演了核心角色，它不仅指导了变量的选择（识别违反条件的样本），也用于计算最优的偏置项 $b$。