支持向量机 (SVM)

约 7899 个字 预计阅读时间 26 分钟 总阅读量 次

SVM 是一种二分类模型，监督学习方法，其基本模型是定义在特征空间上的间隔最大 （maximum margin）的线性分类器。通过核技巧（Kernel Trick），SVM 还可以成为一个强大的非线性分类器。

1. 算法解决的问题

SVM 最初是为解决 二分类（Binary Classification）问题 而设计的。它的核心目标是在特征空间中找到一个能够将两类样本分开的最佳决策边界（超平面）。

• 线性可分问题：如下图所示，能将两类样本分开的线有无数条，SVM 要找到的是中间那条“最胖”的边界，即间隔最大的那条。
• 线性不可分问题：当数据点不能被一条直线（或一个平面）完美分开时，SVM 通过引入软间隔和核技巧来处理。
• 多分类问题：可以通过 "一对一" (One-vs-One) 或 "一对剩余" (One-vs-Rest) 的策略来将 SVM 推广到多分类任务。
• 回归问题：SVM 也可以用于回归任务，此时称为支持向量回归（Support Vector Regression, SVR），其目标是找到一个管道，让尽可能多的样本点落在管道内。

我们主要聚焦于其最经典的分类应用。

2. 算法思路 (The Core Idea)

SVM 的思路是：

最大间隔 (Maximum Margin)

在众多可以将两类数据分开的超平面中，哪一个是最好的？SVM 认为，那个距离两边数据点最远的超平面是最好的。这个“距离”就被称为间隔（Margin）。最大化这个间隔，可以使得模型对未知数据的扰动拥有最强的容忍能力，从而获得最好的泛化性能。

支持向量 (Support Vectors)

在定义这个最大间隔时，你会发现，只有那些离决策边界最近的样本点才真正起作用。这些关键的样本点就被称为支持向量。整个决策边界完全由这些支持向量所决定，移动或删除其他非支持向量的样本点，对模型没有任何影响。这也是“支持向量机”这个名字的由来。

软间隔 (Soft Margin)

在现实世界的数据中，数据往往不是“干净”的，存在噪声或异常点，导致数据线性不可分。为了处理这种情况，SVM 引入了软间隔的概念。它允许一些样本点不满足间隔约束，甚至允许一些点被错分（即越过决策边界）。这是通过引入一个惩罚参数 C 来实现的，C 用于权衡“保持最大间隔”和“减少错分样本数量”这两个目标。 * C 越大，对错分的惩罚越重，模型越倾向于把所有点都分对，容易导致过拟合。 * C 越小，对错分的容忍度越高，模型间隔可能更大，泛化性可能更好，但可能欠拟合。

1. 核技巧 (The Kernel Trick)：对于更复杂的、完全非线性的数据（比如同心圆），直线分类器完全无效。SVM 的解决办法是：通过一个非线性映射 \(\phi(x)\)，将原始特征空间的数据映射到一个更高维度的特征空间，并期望在这个高维空间中，数据变得线性可分。
   • 问题：这个高维空间的维度可能非常高甚至是无限维，直接计算映射和点积会产生巨大的计算开销（维度灾难）。
   • 核技巧：SVM 的天才之处在于，它发现我们根本不需要知道这个具体的映射函数 \(\phi(x)\) 是什么，我们只需要知道在高维空间中的向量点积结果即可。核函数 \(K(x_i, x_j)\) 就是这样一个函数，它能在原始低维空间中计算出特征向量 \(x_i, x_j\) 在高维空间中的点积，即 \(K(x_i, x_j) = \phi(x_i)^T \phi(x_j)\)。
   • 常见核函数：
     • 线性核：\(K(x_i, x_j) = x_i^T x_j\) (实际上就是原始空间)
     • 多项式核：\(K(x_i, x_j) = (x_i^T x_j + c)^d\)
     • 高斯核 (RBF核)：\(K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)\)，这是最常用、效果也最好的核函数之一，它可以将数据映射到无限维空间。

3. 算法流程和重难点

SVM 的求解过程是一个凸二次规划 (Convex Quadratic Programming) 问题。

算法流程：

1. 构建优化问题 (原始问题 Primal Problem)： 对于给定的数据集 \(\{(x_i, y_i)\}_{i=1}^N\)，其中 \(y_i \in \{-1, +1\}\)。超平面可以表示为 \(w^T x + b = 0\)。为了最大化间隔（等价于最小化 \(\|w\|^2\)）并正确分类所有点，同时引入软间隔，我们构建如下的优化目标：

   \[
   \min_{w, b, \xi} \quad \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{N} \xi_i
   \]

   约束条件为：

   \[
   \text{s.t.} \quad y_i(w^T x_i + b) \ge 1 - \xi_i, \quad i=1, ..., N \\
   \xi_i \ge 0, \quad i=1, ..., N
   \]

   • \(\xi_i\) 是松弛变量 (slack variable)，代表了第 \(i\) 个样本点偏离其正确间隔边界的程度。

   上述模型即描述了一个“软间隔支持向量机”。

   如果是硬间隔，那么只需要删除掉松弛变量即可，如下就是最基本的支持向量机模型。

   \[
   \min_{w, b} \quad \frac{1}{2} \|w\|^2 
   \]

   \[
   \text{s.t.} \quad y_i(w^T x_i + b) \ge 1 , \quad i=1, ..., N 
   \]

求解对偶问题 (Dual Problem)

上述原始问题是一个带不等式约束的凸优化问题（二次规划问题），直接求解困难。通过拉格朗日乘子法，我们可以将其转化为其对偶问题。这个转换是 SVM 理论的核心和难点。

• 为什么要转为对偶问题？
• 对偶问题往往更容易求解。

• 最关键的是，转化后，优化变量不再是 \(w\) 和 \(b\)，而是拉格朗arange 乘子 \(\alpha_i\)，并且模型参数的计算和预测都只涉及到样本之间的内积（点积），这直接为使用核技巧铺平了道路。

• 硬间隔的对偶问题形式如下：

\[
\max_{\alpha} \quad \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 (x_i^T x_j)
\]

约束条件为：

\[
\text{s.t.} \quad \sum_{i=1}^{N} \alpha_i y_i = 0, \qquad
0 \le \alpha_i \le C, \quad i=1, ..., N
\]

这个的推导利用KKT条件进行计算：

下面会从软间隔SVM的原始问题出发，通过拉格朗日对偶性，推导出其对偶问题。

从硬间隔开始的推导与之非常类似，结果也非常相似，但是最终并不相同。后面会展开。

---

第0步：回顾原始问题

最小化目标：

\[
\min_{w, b, \xi} \quad \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{N} \xi_i
\]

约束条件：

\[
\begin{align*}
\text{s.t.} \quad & y_i(w^T x_i + b) \ge 1 - \xi_i, \quad i=1, ..., N \quad &(1) \\
& \xi_i \ge 0, \quad i=1, ..., N \quad &(2)
\end{align*}
\]

• \(\frac{1}{2} \|w\|^2\) 是为了最大化间隔。
• \(C \sum \xi_i\) 是对错分样本的惩罚项。
• \(\xi_i\) 是松弛变量，允许样本点在一定程度上违反约束。
• 约束(1)表示每个点都应该被正确分类，并尽量在间隔边界之外。
• 约束(2)表示松弛变量不能为负。

第1步：构建拉格朗日函数

这是一个带不等式约束的优化问题，我们使用拉格朗日乘子法来求解。我们需要为每一个不等式约束引入一个拉格朗日乘子。

• 对于约束(1)，我们引入乘子 \(\alpha_i \ge 0\) (\(i = 1, ..., N\))。
• 对于约束(2)，我们引入乘子 \(\mu_i \ge 0\) (\(i = 1, ..., N\))。

拉格朗日函数的通用形式是 \(L = \text{原始目标} - \sum \text{乘子} \cdot (\text{约束})\)。注意，对于 \(g(x) \le 0\) 形式的约束，我们减去 \(\lambda g(x)\)。

我们将约束改写为 \(\le 0\) 的形式： * 约束(1): \(1 - \xi_i - y_i(w^T x_i + b) \le 0\) * 约束(2): \(-\xi_i \le 0\)

现在构建拉格朗日函数 \(L(w, b, \xi, \alpha, \mu)\):

\[
L = \left(\frac{1}{2} \|w\|^2 + C \sum_{i=1}^{N} \xi_i\right) - \sum_{i=1}^{N} \alpha_i \left[ y_i(w^T x_i + b) - 1 + \xi_i \right] - \sum_{i=1}^{N} \mu_i \xi_i
\]

第2步：转化为对偶问题

原始问题是 \(\min_{w,b,\xi} \max_{\alpha,\mu \ge 0} L(w, b, \xi, \alpha, \mu)\)。 其对偶问题是 \(\max_{\alpha,\mu \ge 0} \min_{w,b,\xi} L(w, b, \xi, \alpha, \mu)\)。

我们先求解内部的最小化问题：\(\min_{w,b,\xi} L\)。为了求最小值，我们计算 \(L\) 对原始变量 \(w, b, \xi_i\) 的偏导数，并令其为 0。

1. 对 \(w\) 求偏导：

   \[
   \frac{\partial L}{\partial w} = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0 \quad \implies \quad w = \sum_{i=1}^{N} \alpha_i y_i x_i \quad (3)
   \]

   这个结果非常重要！它表明最优的权重向量 \(w\) 是所有训练样本向量的线性组合，其系数由 \(\alpha_i\) 和 \(y_i\) 决定。

2. 对 \(b\) 求偏导：

   \[
   \frac{\partial L}{\partial b} = - \sum_{i=1}^{N} \alpha_i y_i = 0 \quad \implies \quad \sum_{i=1}^{N} \alpha_i y_i = 0 \quad (4)
   \]

   这成为了对偶问题的一个核心约束条件。

3. 对 \(\xi_i\) 求偏导：

   \[
   \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \quad \implies \quad C = \alpha_i + \mu_i \quad (5)
   \]

   这个关系式连接了惩罚参数 \(C\) 和两个拉格朗日乘子。

第3步：代入并简化

现在，我们将上面求导得到的三个关系式 (3), (4), (5) 代回到拉格朗日函数 \(L\) 中，以消去原始变量 \(w, b, \xi_i\)。

\[
L = \frac{1}{2} \|w\|^2 + C \sum \xi_i - \sum \alpha_i y_i w^T x_i - \sum \alpha_i y_i b + \sum \alpha_i - \sum \alpha_i \xi_i - \sum \mu_i \xi_i
\]

我们逐项简化： * \(\frac{1}{2} \|w\|^2 = \frac{1}{2} w^T w = \frac{1}{2} \left(\sum_i \alpha_i y_i x_i\right)^T \left(\sum_j \alpha_j y_j x_j\right) = \frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j (x_i^T x_j)\) * \(\sum \alpha_i y_i w^T x_i = w^T \sum \alpha_i y_i x_i = w^T w = \|w\|^2\) * \(\sum \alpha_i y_i b = b \sum \alpha_i y_i = b \cdot 0 = 0\) (根据式(4)) * \(C \sum \xi_i - \sum \alpha_i \xi_i - \sum \mu_i \xi_i = \sum (C - \alpha_i - \mu_i) \xi_i = \sum 0 \cdot \xi_i = 0\) (根据式(5))

将这些简化的结果代回 \(L\)：

\[
\begin{align*}
\min_{w,b,\xi} L &= \frac{1}{2} \|w\|^2 - \|w\|^2 + \sum \alpha_i \\
&= \sum \alpha_i - \frac{1}{2} \|w\|^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 (x_i^T x_j)
\end{align*}
\]

第4步：最终的对偶问题

现在我们得到了只关于 \(\alpha\) 的表达式。对偶问题就是最大化这个表达式，并附加上我们在推导中得到的约束。

最大化目标： $$ \max_{\alpha} \quad W(\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 (x_i^T x_j) $$

约束条件： 1. 来自式(4): \(\sum_{i=1}^{N} \alpha_i y_i = 0\) 2. 来自乘子的定义: \(\alpha_i \ge 0\) 3. 来自式(5): \(C = \alpha_i + \mu_i\)。又因为 \(\mu_i \ge 0\)，所以 \(C - \alpha_i \ge 0\)，即 \(\alpha_i \le C\)。

将约束 2 和 3 合并，我们得到 \(0 \le \alpha_i \le C\)。

这就得到了你问题中提到的最终对偶问题形式：

\[
\boxed{
\begin{align*}
\max_{\alpha} \quad & \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 (x_i^T x_j) \\
\text{s.t.} \quad & \sum_{i=1}^{N} \alpha_i y_i = 0 \\
& 0 \le \alpha_i \le C, \quad i=1, ..., N
\end{align*}
}
\]

这就是启用核技巧的关键：注意到目标函数和决策函数都只依赖于样本的内积 \(x_i^T x_j\)，我们可以轻松地用核函数 \(K(x_i, x_j)\) 替换它。

---

补充：SVM 下的 KKT条件及其含义

对于这个优化问题，其 KKT (Karush-Kuhn-Tucker) 条件给出了最优解必须满足的一系列性质，这也揭示了“支持向量”的本质。KKT 条件包括： 1. 主问题可行性: \(y_i(w^T x_i + b) \ge 1 - \xi_i\) 和 \(\xi_i \ge 0\) 2. 对偶问题可行性: \(\alpha_i \ge 0, \mu_i \ge 0\) 3. 互补松弛条件 (Complementary Slackness): * \(\alpha_i [y_i(w^T x_i + b) - 1 + \xi_i] = 0 \quad (6)\) * \(\mu_i \xi_i = 0 \quad (7)\) 4. 拉格朗日平稳性 (Stationarity): \(\nabla L = 0\) (即我们求导得到的关系式 (3), (4), (5))

根据互补松弛条件，我们可以分析最优解 \(\alpha_i^*\) 的含义： * 情况 1: \(\alpha_i = 0\) * 根据(5)，\(\mu_i = C > 0\)。根据(7)，\(\mu_i \xi_i = 0 \implies \xi_i = 0\)。 * 将 \(\xi_i=0\) 代入(1)得到 \(y_i(w^T x_i + b) \ge 1\)。 * 含义: 这些样本点被正确分类，并且离决策边界较远（在间隔边界之外或之上）。它们对模型没有贡献，不是支持向量。

• 情况 2: \(0 < \alpha_i < C\)

  • 根据(6)，\(\alpha_i > 0 \implies y_i(w^T x_i + b) - 1 + \xi_i = 0\)。
  • 根据(5)，\(\mu_i = C - \alpha_i > 0\)。根据(7)，\(\mu_i \xi_i = 0 \implies \xi_i = 0\)。
  • 结合起来得到 \(y_i(w^T x_i + b) = 1\)。
  • 含义: 这些样本点正好在间隔边界上。它们是典型的支持向量。

• 情况 3: \(\alpha_i = C\)

  • 根据(5)，\(\mu_i = C - C = 0\)。此时对 \(\xi_i\) 没有约束（(7)式 \(\mu_i\xi_i=0\) 自动满足）。
  • 根据(6)，\(y_i(w^T x_i + b) = 1 - \xi_i\)。
  • 因为 \(\xi_i \ge 0\)，所以 \(y_i(w^T x_i + b) \le 1\)。
  • 含义: 这些样本点是在间隔边界之内的。
    • 如果 \(0 < \xi_i \le 1\)，该点在间隔内但仍被正确分类。
    • 如果 \(\xi_i > 1\)，该点被错误分类。
  • 这些违反间隔约束的点也是支持向量。

综上所述，只有 \(\alpha_i > 0\) 的样本点才是支持向量，它们是决定最终决策边界的关键。

---

算法复杂度

• 训练复杂度： SVM 的主要计算开销在训练阶段，即求解二次规划问题。

  • 其复杂度大致在 \(O(N^2 \cdot d)\) 到 \(O(N^3 \cdot d)\) 之间，其中 \(N\) 是训练样本的数量，\(d\) 是特征维度。
  • 由于这个较高的复杂度，SVM 不适合处理超大规模的数据集（例如，样本数超过几十万）。在实践中，高效的 SMO 算法使其复杂度更接近二次方。

• 推理复杂度： SVM 的推理（预测）过程非常快。

  • 复杂度为 \(O(N_{sv} \cdot d)\)，其中 \(N_{sv}\) 是支持向量的数量。
  • 由于支持向量的数量通常远小于总训练样本数 \(N\)，所以 SVM 的预测速度很快，适合在线应用。

总结：SVM 是一个基于严格数学推导的强大分类器，它通过最大化间隔来寻找最优决策边界，并利用精妙的核技巧处理非线性问题。它的主要缺点是训练时间长、对大规模数据不友好，以及需要仔细选择核函数和参数 C。

kernel 函数 （核函数）

好的，我们来深入探讨核函数（Kernel Function）这个SVM的“灵魂”组件。你要求以硬间隔（Hard Margin）SVM为例，这非常好，因为它能让我们更清晰地看到核函数是如何无缝接入算法框架的。

---

1. 核函数要解决的问题：处理非线性（线性不可分）

我们已经知道，SVM的核心是寻找一个线性的决策边界。但如果数据本身是线性不可分的，怎么办？

例如下面这种情况：

在二维平面上，你无论如何也画不了一条直线能把红蓝两类点分开。

2. 核技巧的核心思想：升维与“偷懒”

核技巧（The Kernel Trick）的思路分为两步：

1. 升维打击 (Lifting the Dimension)：我们通过一个非线性映射函数 \(\phi(x)\)，将原始低维空间（比如上图的二维空间）中的数据点 \(x\)，映射到一个更高维的特征空间 \(\mathcal{F}\) 中。我们期待在这个高维空间里，数据变得线性可分。

   • 原始空间 \(\mathbb{R}^d\): \(x \in \mathbb{R}^d\)
   • 映射函数 \(\phi\): \(\mathbb{R}^d \to \mathcal{F}\)
   • 新特征空间 \(\mathcal{F}\): \(\phi(x) \in \mathcal{F}\) (维度可能非常高，甚至是无限维)

2. “偷懒”的计算 (The "Trick"): 直接计算高维映射 \(\phi(x)\) 并在此空间中进行运算，通常会带来巨大的计算量，即“维度灾难”。核技巧的精髓在于：我们发现，在SVM的整个计算流程中，我们根本不需要知道 \(\phi(x)\) 的具体形式，我们只需要知道样本在高维空间中的内积（点积）结果即可！

为此，我们定义了核函数。

---

3. 核函数的定义

核函数 \(K(x_i, x_j)\) 是一个函数，它接收两个在原始低维空间中的向量 \(x_i, x_j\)，并能直接计算出它们经过高维映射 \(\phi\) 后的内积结果。

数学表示为： $$ K(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle = \phi(x_i)^T \phi(x_j) $$

这个等式是核技巧的核心。它允许我们在低维空间中进行计算，却能获得高维空间中的内积结果，从而完美地绕开了维度灾难。

---

4. 核函数在硬间隔SVM中的应用（推导展开）

问题复习

1. 原始问题 (Primal Problem):

\[
\min_{w, b} \quad \frac{1}{2} \|w\|^2
\]

约束条件: \(y_i(w^T x_i + b) \ge 1\)

观察：在原始问题中，优化变量是 \(w\) 和 \(b\)。我们并没有看到直接可以替换的内积项，因此核函数无法直接应用于原始问题。

2. 对偶问题 (Dual Problem):

之前推导出，硬间隔SVM的对偶问题是：

\[
\boxed{
\begin{align*}
\max_{\alpha} \quad & \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 \color{red}{(x_i^T x_j)} \\
\text{s.t.} \quad & \sum_{i=1}^{N} \alpha_i y_i = 0 \\
& \alpha_i \ge 0
\end{align*}
}
\]

关键点出现了！ 对偶问题的目标函数中，唯一的变量 \(\alpha_i\) 是和样本点 \(x_i\) 的内积（点积）\(x_i^T x_j\) 紧密耦合的。整个优化过程只依赖于样本点之间的内积，而与原始的 \(w\) 无关。

内积替换

既然对偶问题只依赖于内积 \(x_i^T x_j\)，而核函数 \(K(x_i, x_j)\) 正是用来计算高维空间内积 \(\phi(x_i)^T \phi(x_j)\) 的。那么，如果我们想在高维空间中训练一个线性SVM，我们只需将对偶问题中的 \(x_i^T x_j\) 直接替换为核函数 \(K(x_i, x_j)\) 即可。

1. "核化"的对偶问题 (Kernelized Dual Problem):

\[
\boxed{
\begin{align*}
\max_{\alpha} \quad & \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 \color{blue}{K(x_i, x_j)} \\
\text{s.t.} \quad & \sum_{i=1}^{N} \alpha_i y_i = 0 \\
& \alpha_i \ge 0
\end{align*}
}
\]

我们仅仅做了一个替换，就将整个优化问题从原始的线性空间提升到了高维的非线性特征空间。

2. "核化"的决策函数 (Kernelized Decision Function):

我们不仅要在训练中应用核函数，在做预测时也同样需要。原始的决策函数是：

\[
f(x) = \text{sign}(w^T x + b)
\]

根据 \(w = \sum \alpha_i y_i x_i\)（这是对偶推导中的关键一步），我们代入得到：

\[
f(x) = \text{sign}\left(\left(\sum_{i=1}^{N} \alpha_i y_i x_i\right)^T x + b\right) = \text{sign}\left(\sum_{i=1}^{N} \alpha_i y_i \color{red}{(x_i^T x)} + b\right)
\]

同样地，我们看到了内积项。将其替换为核函数：

\[
\boxed{
f(x) = \text{sign}\left(\sum_{i=1}^{N} \alpha_i y_i \color{blue}{K(x_i, x)} + b\right)
}
\]

（注意：实际求和时只需对支持向量进行，即那些 \(\alpha_i > 0\) 的样本。）

总结：通过将训练（求解对偶问题）和预测（使用决策函数）中出现的所有内积运算都替换为核函数，我们便完成了SVM的非线性化改造。整个过程优雅且高效，因为我们始终在低维空间进行计算，却享受了高维空间带来的强大分类能力。

---

补充

考虑硬间隔的对偶问题

问得非常好！这是一个典型的“看似相同，实则不同”的陷阱，能问出这个问题，说明你思考得非常深入。

简单直接的回答是：不，它们不一样。 它们的对偶问题在形式上极其相似，但有一个至关重要的区别：对偶变量 α 的约束条件不同。

• 硬间隔SVM：约束是 \(\alpha_i \ge 0\)。
• 软间隔SVM：约束是 \(0 \le \alpha_i \le C\)。

这个上限 \(C\) 的有无，是两者在对偶问题上的根本区别。下面，我们就来推导一下硬间隔SVM的对偶问题，你自然就能明白为什么了。

---

硬间隔SVM的对偶问题推导

硬间隔SVM的目标是找到一个最大间隔超平面，同时要求所有样本点都被完美地、严格地分开，不允许任何一个点进入间隔区，更不允许被错分。

最小化目标： $$ \min_{w, b} \quad \frac{1}{2} |w|^2 $$

约束条件： $$ \text{s.t.} \quad y_i(w^T x_i + b) \ge 1, \quad i=1, ..., N $$

注意到，这里没有松弛变量 \(\xi_i\)，也没有惩罚参数 \(C\)。

第1步：构建拉格朗日函数

我们只有一个不等式约束，所以只需要引入一组拉格朗日乘子 \(\alpha_i \ge 0\)。

将约束改写为 \(1 - y_i(w^T x_i + b) \le 0\)。

拉格朗日函数 \(L(w, b, \alpha)\) 为：

\[
L = \frac{1}{2} \|w\|^2 - \sum_{i=1}^{N} \alpha_i \left[ y_i(w^T x_i + b) - 1 \right]
\]

第2步：转化为对偶问题（求解内部最小化）

对偶问题是 \(\max_{\alpha \ge 0} \min_{w,b} L(w, b, \alpha)\)。我们同样先对 \(w\) 和 \(b\) 求偏导并令其为 0。

1. 对 \(w\) 求偏导：

   \[
   \frac{\partial L}{\partial w} = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0 \quad \implies \quad w = \sum_{i=1}^{N} \alpha_i y_i x_i
   \]

   （这一步和软间隔完全一样）

2. 对 \(b\) 求偏导：

   \[
   \frac{\partial L}{\partial b} = - \sum_{i=1}^{N} \alpha_i y_i = 0 \quad \implies \quad \sum_{i=1}^{N} \alpha_i y_i = 0
   \]

   （这一步也和软间隔完全一样）

注意，因为原始问题中没有变量 \(\xi_i\)，我们不会对 \(\xi_i\) 求导。这就是区别的根源！在软间隔中，正是对 \(\xi_i\) 的求导产生了 \(C = \alpha_i + \mu_i\) 这个关系，从而导出了 \(\alpha_i \le C\) 的约束。

第3步：代入并简化

将上面求导得到的两个关系式代回到拉格朗日函数 \(L\) 中。这一步的代数运算与软间隔的情况完全相同：

\[
L = \frac{1}{2} \|w\|^2 - \sum \alpha_i y_i w^T x_i - b\sum \alpha_i y_i + \sum \alpha_i
\]

将 \(w\) 和 \(\sum \alpha_i y_i = 0\) 代入：

\[
\begin{align*}
\min_{w,b} L &= \frac{1}{2} \|w\|^2 - w^T w - 0 + \sum \alpha_i \\
&= \sum \alpha_i - \frac{1}{2} \|w\|^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 (x_i^T x_j)
\end{align*}
\]

目标函数的形式是一模一样的！

第4步：最终的硬间隔对偶问题

现在我们最大化这个只关于 \(\alpha\) 的表达式，并附上约束条件。

最大化目标： $$ \max_{\alpha} \quad \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 (x_i^T x_j) $$

约束条件： 1. 来自对 \(b\) 的求导: \(\sum_{i=1}^{N} \alpha_i y_i = 0\) 2. 来自拉格朗日乘子的定义: \(\alpha_i \ge 0\)

这就得到了硬间隔SVM的对偶问题。

---

总结与对比

现在我们把两者并列放在一起，区别就一目了然了。

特性	硬间隔 (Hard-Margin) SVM	软间隔 (Soft-Margin) SVM
原始问题	- 无松弛变量 \(\xi\) - 无惩罚参数 \(C\) - 约束：\(y_i(\dots) \ge 1\)	- 有松弛变量 \(\xi\) - 有惩罚参数 \(C\) - 约束：\(y_i(\dots) \ge 1 - \xi_i\)
对偶目标函数	\(\max_{\alpha} \sum \alpha_i - \frac{1}{2} \sum\sum \alpha_i \alpha_j \dots\)	\(\max_{\alpha} \sum \alpha_i - \frac{1}{2} \sum\sum \alpha_i \alpha_j \dots\)
对偶约束	1. \(\sum \alpha_i y_i = 0\) 2. \(\alpha_i \ge 0\)	1. \(\sum \alpha_i y_i = 0\) 2. \(0 \le \alpha_i \le C\)

核心原因解释：

1. 来源不同：\(\alpha_i \le C\) 这个约束，是软间隔SVM独有的。它来源于拉格朗日函数对松弛变量 \(\xi_i\) 求导后得到的关系式 \(C - \alpha_i - \mu_i = 0\)。因为 \(\mu_i\)（\(\xi_i \ge 0\) 约束的乘子）必须大于等于0，所以必然有 \(\alpha_i \le C\)。

2. 物理含义不同：

   • 在硬间隔中，\(\alpha_i\) 可以被认为是样本点 \(i\) 对决策边界的“拉力”。因为模型“死板地”要求所有点都必须在间隔之外，所以没有对这个“拉力”设置上限。
   • 在软间隔中，参数 \(C\) 本质上是一个“容错预算”。它限制了模型为满足一个异常点而扭曲整个决策边界的程度。这个限制在对偶问题中就体现为对 \(\alpha_i\) 的上限。\(C\) 限制了单个样本点对决策边界的最大影响力。如果 \(\alpha_i = C\)，就意味着这个点是一个“问题点”（在间隔内或被错分），模型已经用足了预算来处理它，但不能再为它付出更多了。

所以，结论是：虽然它们对偶问题的目标函数长得一样，但约束域 (Feasible Region) 是不同的，这使得它们是两个完全不同的优化问题，其解也自然不同。

核函数举例

你不需要关心数据具体是如何映射到高维空间的，也不需要实际执行这个映射。你只需要关心一件事：选择一个合适的核函数，用它来计算低维向量之间的“内积结果”，然后将这个结果直接代入到SVM对偶问题的优化目标（我们常说的损失函数）中去求解即可。

这正是核技巧被称为“技巧(Trick)”的原因——它是一种聪明的“偷懒”方式，用低维的计算成本，换来了高维空间的分类能力。

---

常见的核函数

这里是一些在SVM中广泛使用的核函数：

名称 (Name)	数学表达式 \(K(x_i, x_j)\)	特点与说明
线性核 (Linear Kernel)	\(x_i^T x_j\)	这是最简单的核函数，实际上没有进行任何维度映射。适用于数据本身就是线性可分的情况。速度快，参数少。
多项式核 (Polynomial Kernel)	\((\gamma \cdot x_i^T x_j + r)^d\)	通过多项式将数据映射到高维空间。d是多项式的次数，γ和r是调节参数。d越大，模型越复杂。适合图像处理等领域。
高斯核 / 径向基函数核 (Gaussian / RBF Kernel)	\(\exp(-\gamma \|x_i - x_j\|^2)\)	最常用、最强大的核函数。它可以将数据映射到无限维空间。参数γ定义了单个训练样本的影响范围，γ越小影响范围越大。它非常灵活，几乎可以处理任何形状的数据分布，但需要小心调参以防过拟合。
Sigmoid 核	\(\tanh(\gamma \cdot x_i^T x_j + r)\)	灵感来源于神经网络中的激活函数。在特定参数下，其表现类似多层感知机。在实践中不如RBF核常用。

---

一个简单的例子：多项式核如何“升维”

让我们用一个具体的例子来看看这个计算过程，以及维度是如何变化的。

• 假设我们的原始数据是2维的。
  • 取两个样本点：\(x_1 = (1, 2)\) 和 \(x_2 = (3, 4)\)。
• 选择一个简单的多项式核。
  • 我们选择次数 \(d=2\) 的多项式核，并简化参数让 \(\gamma=1, r=0\)。
  • 此时核函数为：\(K(x_i, x_j) = (x_i^T x_j)^2\)

现在，我们通过两种方式来计算 \(x_1\) 和 \(x_2\) 在这个核函数下的结果。

方法一：使用核技巧（我们实际在做的事）

1. 在低维空间计算内积: $$ x_1^T x_2 = (1 \cdot 3) + (2 \cdot 4) = 3 + 8 = 11 $$
2. 代入核函数: $$ K(x_1, x_2) = (11)^2 = \mathbf{121} $$

看！ 整个过程非常简单，只需要一次内积和一次平方运算。我们根本没管“高维空间”长什么样。

方法二：显式地进行维度映射（为了理解原理）

现在，我们把幕后发生的事情揭示出来，看看这个核函数对应的高维映射 \(\phi(x)\) 到底是什么。

对于核函数 \(K(x_i, x_j) = (x_i^T x_j)^2\)，如果 \(x=(a, b)\)，那么它对应的一个高维映射是：

\[
\phi(x) = \phi((a, b)) = (a^2, \sqrt{2}ab, b^2)
\]

这个映射将一个 2维 向量转换成了一个 3维 向量。

这是怎么做到的？

必须强调的是，我们在SVM中不需要知道这高维映射是什么！！！

这里只是举个例子。

我们先把 \(K(x_i, x_j)\) 完全用低维向量的分量 \(a, b\) 来表示。

1. 计算内积 \(x_i^T x_j\): $$ x_i^T x_j = a_i a_j + b_i b_j $$

2. 对内积进行平方: $$ K(x_i, x_j) = (x_i^T x_j)^2 = (a_i a_j + b_i b_j)^2 $$

3. 利用初中数学的完全平方公式 \((p+q)^2 = p^2 + 2pq + q^2\) 将其展开: $$ (a_i a_j + b_i b_j)^2 = (a_i a_j)^2 + 2(a_i a_j)(b_i b_j) + (b_i b_j)^2 $$

   整理一下得到：

   \[
   K(x_i, x_j) = a_i^2 a_j^2 + 2 a_i b_i a_j b_j + b_i^2 b_j^2
   \]

现在我们得到了一个展开的多项式。核技巧的定义是 \(K(x_i, x_j) = \phi(x_i)^T \phi(x_j)\)。这意味着，我们上面得到的这个多项式，必然可以被写成两个高维向量 \(\phi(x_i)\) 和 \(\phi(x_j)\) 的内积形式。我们在SVM里不需要知道它是什么，只需用低维的结果带进去算就可以了，但是在这里多算一下：

让我们来寻找这个形式。一个内积的形式是： $$ \phi(x_i)^T \phi(x_j) = (\text{第1分量}_i \cdot \text{第1分量}_j) + (\text{第2分量}_i \cdot \text{第2分量}_j) + \dots $$

“连连看”的游戏：把展开式和这个内积形式对应起来：

\[
\underbrace{a_i^2 a_j^2}_{\text{第1项}} + \underbrace{2 a_i b_i a_j b_j}_{\text{第2项}} + \underbrace{b_i^2 b_j^2}_{\text{第3项}}
\]

现在，我们把所有带下划线的部分组合起来，看看 \(\phi(x_i)\) 和 \(\phi(x_j)\) 分别是什么：

• 对于 \(x_i = (a_i, b_i)\)，它对应的分量是：\(a_i^2\), \(\sqrt{2}a_ib_i\), \(b_i^2\)。
• 对于 \(x_j = (a_j, b_j)\)，它对应的分量是：\(a_j^2\), \(\sqrt{2}a_jb_j\), \(b_j^2\)。

因此，我们就反推出了高维映射函数 \(\phi(x)\) 的形式： 如果 \(x = (a, b)\)，那么 \(\phi(x) = (a^2, \sqrt{2} ab, b^2)\)。

我们来验证一下： $$ \begin{align} \phi(x_i)^T \phi(x_j) &= (a_i^2, \sqrt{2}a_ib_i, b_i^2) \cdot (a_j^2, \sqrt{2}a_jb_j, b_j^2) \ &= a_i^2 a_j^2 + 2a_i b_i a_j b_j + b_i^2 b_j^2 \ &= (a_i a_j + b_i b_j)^2 \ &= (x_i^T x_j)^2 \ &= K(x_i, x_j) \end{align} $$ 验证成功！现在我们用这个“笨办法”来计算一遍：

1. 将 \(x_1\) 和 \(x_2\) 映射到高维空间:

   • \(\phi(x_1) = \phi((1, 2)) = (1^2, \sqrt{2}\cdot1\cdot2, 2^2) = (1, 2\sqrt{2}, 4)\)
   • \(\phi(x_2) = \phi((3, 4)) = (3^2, \sqrt{2}\cdot3\cdot4, 4^2) = (9, 12\sqrt{2}, 16)\)

2. 在高维空间计算内积:

   \[
   \begin{align*}
   \phi(x_1)^T \phi(x_2) &= (1 \cdot 9) + (2\sqrt{2} \cdot 12\sqrt{2}) + (4 \cdot 16) \\
   &= 9 + (24 \cdot 2) + 64 \\
   &= 9 + 48 + 64 \\
   &= \mathbf{121}
   \end{align*}
   \]

结论

• 维度变化：我们通过一个二次多项式核，将原始的 2维 空间映射到了 3维 空间。
• 结果对比：两种方法得到的结果完全一样（都是121）。
• 效率差异：核技巧（方法一）的计算量远小于显式映射（方法二）。