线性支持向量机

线性支持向量机 (Linear Support Vector Machines)

1. 线性支持向量机的由来与学习问题

在之前的初识SVM和线性可分支持向量机中，我们了解了硬间隔支持向量机 (Hard Margin SVM)。它的核心思想是找到一个超平面，能够完美地将两类线性可分的数据分开，并且使分类间隔最大化。其优化问题为：

${\min }_{\mathbf{w},b}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$ $\text{s.t.}{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1\text{对于所有 }i=1,\dots ,N$ 其中，$({\mathbf{x}}_i,y_i)$ 是训练样本，$y_i\in \{-1,+1\}$。

1.1 线性不可分与噪声

硬间隔 SVM 的前提是数据必须是线性可分的。然而，在现实世界中，这个条件往往难以满足：

1. 数据可能并非严格线性可分：即使大部分数据可以通过线性超平面分开，也可能存在少数“异常点”（outliers）或“噪声”，导致无法找到一个完美划分的超平面。
2. 对噪声敏感：如果数据中存在少量噪声点，硬间隔 SVM 可能会为了将这些噪声点也完美分类，而扭曲决策边界，导致泛化能力下降。

为了应对这些挑战，SVM 被扩展为软间隔支持向量机 (Soft Margin SVM)。

1.2 软间隔的概念：引入松弛变量

软间隔 SVM 允许一些训练样本不满足硬间隔的约束，即允许它们位于间隔内部甚至被错误分类。为此，我们为每个样本引入一个松弛变量 (Slack Variable) ${\xi }_i$ (读作 “xi”)。

• 松弛变量的定义：${\xi }_i\ge 0$。
• 修改后的约束条件： 对于每个样本 $({\mathbf{x}}_i,y_i)$，原约束 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$ 被修改为： $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i$ 解释：
  • ${\xi }_i=0$：这表示样本 ${\mathbf{x}}_i$ 满足原始的硬间隔约束，即它被正确分类并且位于间隔边界（$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=1$）上或正确的一侧（$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)>1$）。
  • $0<{\xi }_i<1$：这表示样本 ${\mathbf{x}}_i$ 被正确分类，但它位于间隔内部（即 $0<y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)<1$）。它“侵犯”了间隔，但没有越过决策超平面。
  • ${\xi }_i\ge 1$：这表示样本 ${\mathbf{x}}_i$ 被错误分类。它的函数间隔 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)$ 将小于或等于 0。
    • 如果 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=0$，则 ${\xi }_i=1$。
    • 如果 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)<0$，则 ${\xi }_i>1$。

1.3 软间隔优化目标：惩罚项

虽然允许了松弛，但我们不希望太多的样本不满足间隔约束，也不希望松弛变量的值太大。因此，我们需要在目标函数中加入一个惩罚项来限制松弛变量的总量。

我们选择最小化所有松弛变量之和 ${\sum }_{i=1}^N{\xi }_i$。这个求和项被乘以一个惩罚参数 $C$，然后加到原始的目标函数中。

• 惩罚参数 $C>0$：它是一个超参数，用于平衡最大化间隔（对应 $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$）和最小化分类错误及间隔违规（对应 $C{\sum }_{i=1}^N{\xi }_i$）之间的关系。
  • $C$ 越大：对违规的惩罚越重，模型会更倾向于减小误分类数量，可能导致间隔变窄，甚至过拟合。
  • $C$ 越小：对违规的惩罚越轻，模型会允许更多的误分类，可能导致间隔更宽，但欠拟合的风险增加。

1.4 线性支持向量机的原始优化问题 (Primal Problem)

综合上述，线性支持向量机的原始优化问题（即软间隔 SVM 的优化问题）表示为：

${\min }_{\mathbf{w},b,\mathbf{\xi }}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C{\sum }_{i=1}^N{\xi }_i$ $\text{s.t.}{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i\text{对于所有 }i=1,\dots ,N$ ${\xi }_i\ge 0\text{对于所有 }i=1,\dots ,N$ 解释：

• 这是一个凸二次规划问题：目标函数是凸的（二次项），约束条件是线性的（定义了一个凸可行域）。
• 存在唯一的最优解 $({\mathbf{w}}^{\ast },b^{\ast })$。
• 这个问题的求解涉及到同时优化 $\mathbf{w}$、 $b$ 和所有的 ${\xi }_i$。当 $N$ 很大时，直接求解这个原始问题可能比较困难。

2. 从原始问题到对偶问题 (Dual Problem)

为了更高效地求解软间隔 SVM，特别是为了引入核函数 (Kernel Function) 以处理非线性可分数据（尽管核函数是针对非线性 SVM 的，但它是通过对偶形式引入的），我们通常将原始问题转化为其对偶问题 (Dual Problem)。

2.1 拉格朗日函数 (Lagrangian Function)

我们使用拉格朗日乘子法 (Lagrange Multipliers) 来构建原始优化问题的拉格朗日函数。对于每个不等式约束，我们引入一个非负的拉格朗日乘子。

对于约束 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i$，可以写成 $1-{\xi }_i-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\le 0$。引入拉格朗日乘子 ${\alpha }_i\ge 0$。 对于约束 ${\xi }_i\ge 0$，可以写成 $-{\xi }_i\le 0$。引入拉格朗日乘子 ${\mu }_i\ge 0$。

广义拉格朗日函数 $L(\mathbf{w},b,\mathbf{\xi },\mathbf{\alpha },\mathbf{\mu })$ 定义为： $L(\mathbf{w},b,\mathbf{\xi },\mathbf{\alpha },\mathbf{\mu })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C{\sum }_{i=1}^N{\xi }_i+{\sum }_{i=1}^N{\alpha }_i(1-{\xi }_i-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b))+{\sum }_{i=1}^N{\mu }_i(-{\xi }_i)$ 其中 $\mathbf{\alpha }=({\alpha }_1,\dots ,{\alpha }_N{)}^T$ 和 $\mathbf{\mu }=({\mu }_1,\dots ,{\mu }_N{)}^T$ 是拉格朗日乘子向量。

2.2 对偶问题的一般形式

对偶问题是通过对拉格朗日函数（相关可以看看最大熵与拉格朗日算子求解）进行最大化-最小化交换得到的。对于原始问题（最小化问题），其对偶问题是： ${\max }_{\mathbf{\alpha },\mathbf{\mu }\ge 0}{\min }_{\mathbf{w},b,\mathbf{\xi }}L(\mathbf{w},b,\mathbf{\xi },\mathbf{\alpha },\mathbf{\mu })$

由于原始问题是凸二次规划，满足 KKT 条件，所以原始问题的最优解与对偶问题的最优解是等价的。

2.3 求解 ${\min }_{\mathbf{w},b,\mathbf{\xi }}L(\mathbf{w},b,\mathbf{\xi },\mathbf{\alpha },\mathbf{\mu })$

首先，我们对 $L$ 关于原始变量 $\mathbf{w},b,\mathbf{\xi }$ 求偏导，并令其为零。

1. 对 $\mathbf{w}$ 求偏导： $\frac{\partial L}{\partial \mathbf{w}}=\frac{\partial }{\partial \mathbf{w}}\left(\frac{1}{2}{\mathbf{w}}^T\mathbf{w}-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{w}}^T{\mathbf{x}}_i\right)=\mathbf{w}-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i$ 令偏导为零： $\mathbf{w}-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i=0$ 得到最重要的一个关系： $\mathbf{w}={\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i$ 解释：这个结果表明，最优的权重向量 ${\mathbf{w}}^{\ast }$ 可以表示为训练样本的线性组合。只有那些对应的 ${\alpha }_i>0$ 的样本才会在这个组合中起作用，这些样本就是支持向量 (Support Vectors)。

2. 对 $b$ 求偏导： $\frac{\partial L}{\partial b}=\frac{\partial }{\partial b}\left(-{\sum }_{i=1}^N{\alpha }_i{y}_{i}b\right)=-{\sum }_{i=1}^N{\alpha }_i{y}_i$ 令偏导为零： $-{\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 得到约束条件： ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$

3. 对 ${\xi }_i$ 求偏导： $\frac{\partial L}{\partial {\xi }_i}=\frac{\partial }{\partial {\xi }_i}\left(C{\xi }_i-{\alpha }_i{\xi }_i-{\mu }_i{\xi }_i\right)=C-{\alpha }_i-{\mu }_i$ 令偏导为零： $C-{\alpha }_i-{\mu }_i=0$ 得到关系： ${\alpha }_i+{\mu }_i=C$ 解释：由于 ${\mu }_i\ge 0$，这意味着 ${\alpha }_i\le C$。结合 ${\alpha }_i\ge 0$，我们得到了对偶问题中拉格朗日乘子 ${\alpha }_i$ 的范围约束：$0\le {\alpha }_i\le C$。

2.4 将结果代回拉格朗日函数

现在，我们将上述求导结果代回到广义拉格朗日函数 $L(\mathbf{w},b,\mathbf{\xi },\mathbf{\alpha },\mathbf{\mu })$ 中，以消除原始变量 $\mathbf{w},b,\mathbf{\xi }$：

${\min }_{\mathbf{w},b,\mathbf{\xi }}L=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C{\sum }_{i=1}^N{\xi }_i+{\sum }_{i=1}^N{\alpha }_i(1-{\xi }_i-y_i{\mathbf{w}}^T{\mathbf{x}}_i-y_{i}b)-{\sum }_{i=1}^N{\mu }_i{\xi }_i$ 整理为： $=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{w}}^T{\mathbf{x}}_i-b{\sum }_{i=1}^N{\alpha }_i{y}_i+{\sum }_{i=1}^N(C-{\alpha }_i-{\mu }_i){\xi }_i$

根据我们推导的关系：

• $b{\sum }_{i=1}^N{\alpha }_i{y}_i=b\cdot 0=0$ (因为 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$)
• ${\sum }_{i=1}^N(C-{\alpha }_i-{\mu }_i){\xi }_i={\sum }_{i=1}^N(0){\xi }_i=0$ (因为 $C-{\alpha }_i-{\mu }_i=0$)

所以，拉格朗日函数简化为： $=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{w}}^T{\mathbf{x}}_i$ 现在代入 $\mathbf{w}={\sum }_{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j$： $=\frac{1}{2}{\left({\sum }_{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j\right)}^T\left({\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i\right)+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i^T\left({\sum }_{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j\right)$ $=\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)$ 解释：

• ${\mathbf{w}}^T\mathbf{w}=({\sum }_j{\alpha }_j{y}_j{\mathbf{x}}_j{)}^T({\sum }_i{\alpha }_i{y}_i{\mathbf{x}}_i)={\sum }_j{\sum }_i{\alpha }_j{\alpha }_i{y}_j{y}_i({\mathbf{x}}_j^T{\mathbf{x}}_i)={\sum }_i{\sum }_j{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)$
• ${\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i^T\mathbf{w}={\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i^T({\sum }_{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j)={\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)$

将两项合并（$\frac{1}{2}$ 减去 1 得到 $-\frac{1}{2}$）： $={\sum }_{i=1}^N{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)$

2.5 线性支持向量机的对偶优化问题 (Dual Problem)

现在，我们将这个结果放入对偶问题的最大化形式中： ${\max }_{\mathbf{\alpha }}{\sum }_{i=1}^N{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)$ $\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0$ $0\le {\alpha }_i\le C\text{对于所有 }i=1,\dots ,N$ 解释：

• 这个对偶问题是一个关于拉格朗日乘子 $\mathbf{\alpha }$ 的凸二次规划问题。
• 它的目标函数只依赖于 ${\alpha }_i$ 和训练样本的内积 ${\mathbf{x}}_i^T{\mathbf{x}}_j$。这是核函数能够被引入的关键点，因为我们可以用一个核函数 $K({\mathbf{x}}_i,{\mathbf{x}}_j)$ 来替换内积，从而处理非线性可分数据，而无需显式地在高维空间进行特征映射。
• 约束条件包括了 $\sum {\alpha }_i{y}_i=0$ 和 $0\le {\alpha }_i\le C$。

3. 最优解的性质：KKT 条件与支持向量

对偶问题求得的最优解 ${\mathbf{\alpha }}^{\ast }$ 具有非常重要的性质，这些性质由 KKT (Karush-Kuhn-Tucker) 条件给出。KKT 条件是凸优化问题在满足一定条件（如 Slater 条件）下最优解的必要充分条件。

对于软间隔 SVM，KKT 条件包括：

1. 原始可行性：满足所有约束条件。
   • $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i$
   • ${\xi }_i\ge 0$
2. 对偶可行性：满足拉格朗日乘子非负约束。
   • ${\alpha }_i\ge 0$
   • ${\mu }_i\ge 0$
3. 梯度为零条件：我们之前通过对 $L$ 求偏导并令为零已经得到。
   • ${\mathbf{w}}^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i$
   • ${\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i=0$
   • $C-{\alpha }_i^{\ast }-{\mu }_i^{\ast }=0$
4. 互补松弛性 (Complementary Slackness)：这是最关键的条件，它揭示了 ${\alpha }_i^{\ast }$ 和样本点位置的关系。
   • ${\alpha }_i^{\ast }(1-{\xi }_i^{\ast }-y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast }))=0$
   • ${\mu }_i^{\ast }{\xi }_i^{\ast }=0$

通过这些 KKT 条件，我们可以分析最优解 ${\mathbf{\alpha }}^{\ast }$ 的含义：

• 如果 ${\alpha }_i^{\ast }>0$： 根据第一条互补松弛性条件，由于 ${\alpha }_i^{\ast }\ne 0$，那么其括号内的项必须为零： $1-{\xi }_i^{\ast }-y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast })=0⟹y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast })=1-{\xi }_i^{\ast }$。 这些 ${\mathbf{x}}_i$ 对应的点被称为支持向量 (Support Vectors)。只有支持向量才会在 ${\mathbf{w}}^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i$ 的计算中贡献非零的权重。 进一步，根据 ${\alpha }_i^{\ast }+{\mu }_i^{\ast }=C$：
  • 如果 $0<{\alpha }_i^{\ast }<C$： 那么 ${\mu }_i^{\ast }=C-{\alpha }_i^{\ast }>0$。根据第二条互补松弛性条件 ${\mu }_i^{\ast }{\xi }_i^{\ast }=0$，由于 ${\mu }_i^{\ast }\ne 0$，所以 ${\xi }_i^{\ast }=0$。 这意味着这些支持向量恰好位于间隔边界上：$y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast })=1$。
  • 如果 ${\alpha }_i^{\ast }=C$： 那么 ${\mu }_i^{\ast }=0$。此时第二条互补松弛性条件 ${\mu }_i^{\ast }{\xi }_i^{\ast }=0$ 总是成立，无法推断 ${\xi }_i^{\ast }$ 的值。 在这种情况下，我们只知道 $y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast })=1-{\xi }_i^{\ast }$。
    • 如果 ${\xi }_i^{\ast }=0$，则点在间隔边界上。
    • 如果 $0<{\xi }_i^{\ast }<1$，则点在间隔内部（但分类正确）。
    • 如果 ${\xi }_i^{\ast }\ge 1$，则点被错误分类。 这些点同样是支持向量。
• 如果 ${\alpha }_i^{\ast }=0$： 根据第一条互补松弛性条件，${\alpha }_i^{\ast }$ 为零，所以括号内的项 $(1-{\xi }_i^{\ast }-y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast }))$ 不再强制为零，它只需满足 $\le 0$ 的约束（即 $y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast })\ge 1-{\xi }_i^{\ast }$）。 同时，由于 ${\alpha }_i^{\ast }=0$，根据 $C-{\alpha }_i^{\ast }-{\mu }_i^{\ast }=0⟹{\mu }_i^{\ast }=C>0$ (因为 $C>0$)。 根据第二条互补松弛性条件 ${\mu }_i^{\ast }{\xi }_i^{\ast }=0$，由于 ${\mu }_i^{\ast }\ne 0$，所以 ${\xi }_i^{\ast }=0$。 这意味着这些点不满足 $y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast })=1$，它们位于间隔边界之外，并且被正确分类：$y_i({\mathbf{w}}^{\ast T}{\mathbf{x}}_i+b^{\ast })>1$。 这些点不是支持向量，它们对超平面的最终确定没有直接贡献。

总结支持向量：

• 支持向量就是那些 ${\alpha }_i^{\ast }>0$ 的训练样本。它们对最终的分类超平面有贡献。
• 它们可以是位于间隔边界上的点 ($0<{\alpha }_i^{\ast }<C$)，也可以是位于间隔内部或被错误分类的点 (${\alpha }_i^{\ast }=C$)。

3.4 求解 $b^{\ast }$

一旦我们通过求解对偶问题获得了 ${\mathbf{\alpha }}^{\ast }$，我们就可以根据 ${\mathbf{w}}^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i$ 来计算 ${\mathbf{w}}^{\ast }$。 为了计算 $b^{\ast }$，我们可以利用 KKT 条件中位于间隔边界上的支持向量。选择任何一个满足 $0<{\alpha }_j^{\ast }<C$ 的支持向量 $({\mathbf{x}}_j,y_j)$。对于这样的点，我们知道 ${\xi }_j^{\ast }=0$ 且 $y_j({\mathbf{w}}^{\ast T}{\mathbf{x}}_j+b^{\ast })=1$。

从 $y_j({\mathbf{w}}^{\ast T}{\mathbf{x}}_j+b^{\ast })=1$ 我们可以得到： ${\mathbf{w}}^{\ast T}{\mathbf{x}}_j+b^{\ast }=y_j$ 因此： $b^{\ast }=y_j-{\mathbf{w}}^{\ast T}{\mathbf{x}}_j$ 在实际实现中，为了提高数值稳定性，通常会取所有满足 $0<{\alpha }_j^{\ast }<C$ 的支持向量，计算出多个 $b^{\ast }$ 值，然后取它们的平均值。

4. 求解对偶问题：SMO 算法

对偶问题是一个凸二次规划问题，原则上可以使用通用的二次规划求解器来解决。然而，对于大规模数据集，样本数量 $N$ 非常大时，直接使用标准二次规划算法会非常慢。

序列最小优化 (Sequential Minimal Optimization, SMO) 算法是专门用于高效解决 SVM 对偶问题的一种启发式算法，由 John Platt 在 1998 年提出。它是目前最广泛使用的 SVM 训练算法之一。

4.1 SMO 的核心思想

SMO 的基本思想是：

• 将大问题分解为小问题：它不试图同时优化所有的 ${\alpha }_i$，而是每次只选择两个 ${\alpha }_i$ 进行优化，而固定其他所有 ${\alpha }_j$ ($j\ne i$)。
• 解析求解：当只优化两个 ${\alpha }_i$ 时，约束条件 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 变成一个简单的线性方程（只涉及这两个 ${\alpha }_i$），使得优化问题可以在闭合形式下解析求解，而无需调用复杂的数值优化库。
• 迭代更新：SMO 算法重复以下步骤，直到收敛：
  1. 选择两个 ${\alpha }_i$：启发式地选择两个需要更新的 ${\alpha }_i$。通常，一个选择是违反 KKT 条件最严重的 ${\alpha }_i$，另一个选择是使目标函数变化最大的 ${\alpha }_j$。
  2. 固定其他 $\alpha$ 值：将所有除这两个 ${\alpha }_i,{\alpha }_j$ 之外的 $\alpha$ 值固定。
  3. 解析求解：针对这两个选定的 ${\alpha }_i,{\alpha }_j$ 构建一个二维的凸二次规划问题，并解析求解，得到它们的更新值。
  4. 更新 $b$：根据更新后的 ${\alpha }_i,{\alpha }_j$ 和 KKT 条件，更新偏置项 $b$。

4.2 SMO 的优势

• 高效性：每次迭代只处理两个变量，计算量极小。
• 解析解：避免了复杂的矩阵运算和数值迭代，使得算法非常快。
• 适用于大规模数据：其计算复杂度与数据集大小呈近似线性关系，使其能够处理具有数百万样本的大规模数据集。

5. 线性支持向量机的工作流程总结

1. 输入：训练数据集 $T=\{({\mathbf{x}}_1,y_1),\dots ,({\mathbf{x}}_N,y_N)\}$，其中 ${\mathbf{x}}_i\in {\mathbb{R}}^d$, $y_i\in \{-1,+1\}$。
2. 选择惩罚参数 $C>0$。
3. 构造并求解对偶优化问题： ${\max }_{\mathbf{\alpha }}{\sum }_{i=1}^N{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)$ $\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0$ $0\le {\alpha }_i\le C\text{对于所有 }i=1,\dots ,N$ 通常使用 SMO 算法来求解得到最优解 ${\mathbf{\alpha }}^{\ast }=({\alpha }_1^{\ast },\dots ,{\alpha }_N^{\ast }{)}^T$。
4. 根据 ${\mathbf{\alpha }}^{\ast }$ 计算最优权重向量 ${\mathbf{w}}^{\ast }$ 和偏置项 $b^{\ast }$：
   • 计算 ${\mathbf{w}}^{\ast }$： ${\mathbf{w}}^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i$ 重要提示：只有支持向量（即 ${\alpha }_i^{\ast }>0$ 的点）才会对 ${\mathbf{w}}^{\ast }$ 的计算有贡献。
   • 计算 $b^{\ast }$： 选择任意一个满足 $0<{\alpha }_j^{\ast }<C$ 的支持向量 $({\mathbf{x}}_j,y_j)$。 $b^{\ast }=y_j-{\mathbf{w}}^{\ast T}{\mathbf{x}}_j$ 或者更稳定的方式是取所有满足 $0<{\alpha }_j^{\ast }<C$ 的支持向量计算出的 $b$ 值的平均。
5. 构建分离超平面和决策函数：
   • 分离超平面：${\mathbf{w}}^{\ast T}\mathbf{x}+b^{\ast }=0$
   • 分类决策函数： $f(\mathbf{x})=\text{sign}({\mathbf{w}}^{\ast T}\mathbf{x}+b^{\ast })$ 对于新的输入 $\mathbf{x}$，计算 ${\mathbf{w}}^{\ast T}\mathbf{x}+b^{\ast }$ 的符号，来预测其类别为 $+1$ 或 $-1$。