深入理解SVM：从拉格朗日乘子法到核函数

支持向量机（Support Vector Machine, SVM）是机器学习领域中最经典的算法之一。它的理论大厦建立在凸优化、拉格朗日对偶理论以及再生核希尔伯特空间之上。

要真正理解 SVM，不能只停留在“最大化间隔”的直观层面，必须深入其背后的数学引擎。本文将分为两大部分：

1. 优化理论基础：拉格朗日乘子法与 KKT 条件。
2. SVM 推导实战：从硬间隔到软间隔，再到核函数。

第一部分：优化理论基础

在介绍 SVM 之前，我们需要掌握处理带约束优化问题的通用方法。

1. 拉格朗日乘子法与 KKT 条件

我们要解决的是如下通用的优化问题（原始问题）：

$$\begin{aligned} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & h_i(x) = 0, \quad i = 1, \dots, m \quad (\text{等式约束}) \\ & g_j(x) \le 0, \quad j = 1, \dots, n \quad (\text{不等式约束}) \end{aligned}$$

为了处理这些约束，我们构造广义拉格朗日函数，将约束“吸收”到目标函数中：

$$\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^{m} \lambda_i h_i(x) + \sum_{j=1}^{n} \mu_j g_j(x)$$

其中 $\lambda$ 是等式约束乘子（无符号限制），$\mu$ 是不等式约束乘子（必须非负）。

KKT 条件 (Karush-Kuhn-Tucker Conditions)

对于含不等式约束的优化问题，如果 $x^*$ 是局部最优解，它必须满足以下四个核心条件（统称 KKT 条件）：

1. 站定性 (Stationarity)：
   拉格朗日函数的梯度为零。

   $$\nabla_x \mathcal{L}(x^*, \lambda^*, \mu^*) = 0$$

   这意味着在最优点，目标函数的梯度方向由各个约束函数的梯度线性组合而成。

2. 原始可行性 (Primal Feasibility)：
   解必须满足原始的约束条件。

   $$h_i(x^*) = 0, \quad g_j(x^*) \le 0$$

3. 对偶可行性 (Dual Feasibility)：
   不等式约束的乘子必须非负。

   $$\mu_j^* \ge 0$$

   几何解释：$\mu \ge 0$ 保证了目标函数梯度的反方向（下降方向）是被约束边界“挡住”指向可行域内部的，而不是指向外部。

4. 互补松弛性 (Complementary Slackness) —— SVM 的灵魂

   $$\mu_j^* g_j(x^*) = 0, \quad \forall j$$

   这个条件揭示了一个深刻的二元关系：

   • 要么约束无效（$g_j < 0$），此时点在可行域内部，乘子 $\mu_j$ 必须为 0。
   • 要么约束有效（$g_j = 0$），此时点在边界上，乘子 $\mu_j$ 可以大于 0。
   • 这对理解 SVM 的“支持向量”至关重要。
     这是为您补充的“拉格朗日对偶原理”部分，请将其插入到原博客的“1. 拉格朗日乘子法与 KKT 条件”和“KKT 条件”这两个小节之间，作为一个独立的理论支撑环节。

---

2. 拉格朗日对偶原理 (Lagrange Duality)

构造出广义拉格朗日函数 $\mathcal{L}(x, \lambda, \mu)$ 后，我们并不是直接对其求导，而是利用对偶性将原始问题转换为一个更容易求解的新问题。

(1) 原始问题的无约束形式

我们可以将原始的带约束优化问题，等价地写成一个“极小极大”问题：

$$p^* = \min_{x} \left( \max_{\lambda, \mu: \mu \ge 0} \mathcal{L}(x, \lambda, \mu) \right)$$

为什么这样等价？ 让我们看看内部的 $\max$ 操作：

• 如果 $x$ 违反了约束（例如 $g_j(x) > 0$）：
  我们可以取 $\mu_j \to +\infty$，使得 $\mathcal{L} \to +\infty$。
• 如果 $x$ 满足约束（$g_j(x) \le 0$ 且 $h_i(x)=0$）：
  为了最大化 $\mathcal{L}$，最优的 $\mu_j$ 只能取 0（或者当 $g_j(x)=0$ 时取任意值，结果仍为0），此时 $\max \mathcal{L} = f(x)$。

因此，$\minx \max{\lambda, \mu} \mathcal{L}$ 本质上就是在满足约束的区域内寻找 $f(x)$ 的最小值。如果违反约束，目标函数值为无穷大，自然会被 $\min$ 操作排除。

(2) 对偶问题 (Dual Problem)

对偶问题则是将“极小”和“极大”的顺序互换：

$$d^* = \max_{\lambda, \mu: \mu \ge 0} \left( \min_{x} \mathcal{L}(x, \lambda, \mu) \right)$$

这个过程通常分为两步：

1. 求对偶函数：先固定 $\lambda, \mu$，求 $x$ 使得 $\mathcal{L}$ 最小，得到 $g(\lambda, \mu) = \min_x \mathcal{L}(x, \lambda, \mu)$。
2. 求对偶最大值：在满足 $\mu \ge 0$ 的条件下，最大化 $g(\lambda, \mu)$。

(3) 强对偶性 (Strong Duality)

原始问题 $p^$ 和对偶问题 $d^$ 之间存在如下关系：

• 弱对偶性 (Weak Duality)：$d^ \le p^$ 恒成立。即对偶问题的解是原始问题解的下界。
• 强对偶性 (Strong Duality)：$d^ = p^$。

为什么 SVM 能够使用对偶方法求解？
因为 SVM 的优化目标是凸二次规划问题，且满足 Slater 条件（即存在一个 $x$ 严格满足所有不等式约束）。在这些条件下，强对偶性成立。这意味着我们可以放心地去求解对偶问题，其结果等价于原始问题的最优解。

总结：通过对偶原理，我们将一个关于 $x$ 的复杂约束优化问题，转化为了一个关于 $\lambda, \mu$ 的新问题。这不仅简化了求解难度，更重要的是自然地引入了内积形式，为后续的核技巧铺平了道路。

---

第二部分：硬间隔 SVM (Hard Margin)

前提假设：数据是线性可分的（不存在噪声，两类可以被完美分开）。

1. 几何建模

我们需要找到一个超平面 $w^T x + b = 0$ 来分割正负样本（$y_i \in {+1, -1}$）。
为了让分类更稳健，我们希望最大化几何间隔（Geometric Margin），即最近的点到超平面的距离。

• 约束条件：所有点必须分类正确，且位于间隔边界之外。

  $$y_i (w^T x_i + b) \ge 1$$

  (这里我们将函数间隔固定为 1，以消除缩放带来的不确定性)

• 优化目标：最大化距离 $\frac{1}{||w||}$，等价于最小化 $\frac{1}{2}||w||^2$。

原始优化问题 (Primal Problem)：

$$\begin{aligned} \min_{w, b} \quad & \frac{1}{2}||w||^2 \\ \text{s.t.} \quad & 1 - y_i (w^T x_i + b) \le 0, \quad i = 1, \dots, N \end{aligned}$$

2. 拉格朗日对偶性

构造拉格朗日函数（引入乘子 $\alpha_i \ge 0$）：

$$\mathcal{L}(w, b, \alpha) = \frac{1}{2}||w||^2 + \sum_{i=1}^N \alpha_i (1 - y_i (w^T x_i + b))$$

根据强对偶性，我们将“极小化极大”问题转化为对偶问题（Dual Problem）：$\max{\alpha} \min{w, b} \mathcal{L}$。

步骤 A：对 $w, b$ 求偏导并令为 0

$$\begin{aligned} \nabla_w \mathcal{L} &= w - \sum_{i=1}^N \alpha_i y_i x_i = 0 \quad \Rightarrow \quad w = \sum_{i=1}^N \alpha_i y_i x_i \\ \nabla_b \mathcal{L} &= - \sum_{i=1}^N \alpha_i y_i = 0 \quad \Rightarrow \quad \sum_{i=1}^N \alpha_i y_i = 0 \end{aligned}$$

关键发现：最优的法向量 $w$ 仅仅是样本向量的线性组合。

步骤 B：代回函数，消去 $w, b$

将上述结果代回 $\mathcal{L}$，经过化简得到只关于 $\alpha$ 的函数：

$$\mathcal{L}(\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)$$

步骤 C：最终对偶问题

$$\begin{aligned} \min_{\alpha} \quad & \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i^T x_j) - \sum_{i=1}^N \alpha_i \\ \text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\ & \alpha_i \ge 0 \end{aligned}$$

3. 支持向量的诞生

求解出 $\alpha$ 后，根据 KKT 的互补松弛性：$\alpha_i (1 - y_i (w^T x_i + b)) = 0$。

• 如果 $\alpha_i > 0$，则必然有 $1 - y_i (w^T x_i + b) = 0$。
• 这说明该样本点严格位于间隔边界上。这些点就是支持向量（Support Vectors）。
• 其余 $\alpha_i = 0$ 的非支持向量对模型完全没有影响。

---

第三部分：软间隔 SVM (Soft Margin)

现实问题：数据往往存在噪声，或者线性不可分。硬间隔会导致过拟合或无法求解。

1. 引入松弛变量

我们允许部分样本“犯错”（进入间隔内部甚至跑到对面），为此引入松弛变量 $\xi_i \ge 0$。
约束变为：

$$y_i (w^T x_i + b) \ge 1 - \xi_i$$

2. 新的目标函数

我们需要在“最大化间隔”和“最小化错误”之间权衡。引入惩罚系数 $C$：

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

• $C$ 较大：对错误零容忍，容易过拟合（逼近硬间隔）。
• $C$ 较小：容忍更多错误，间隔更宽，容易欠拟合。

3. 软间隔的对偶形式

推导过程与硬间隔几乎完全一致，唯一的区别在于拉格朗日乘子 $\alpha_i$ 的约束范围。

硬间隔约束：$\alpha_i \ge 0$
软间隔约束：$0 \le \alpha_i \le C$

这限制了单个样本对模型的最大影响权重，增强了鲁棒性。

---

第四部分：核函数 (Kernel Function)

现实问题：数据呈非线性分布（如环形数据），在低维空间无法用线性超平面分开。

1. 核心思想：升维

根据 Cover 定理，低维空间线性不可分的数据，映射到高维空间后往往变得线性可分。
设映射函数为 $\phi(x)$，则对偶问题变为：

$$\min_{\alpha} \quad \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \underbrace{\phi(x_i)^T \phi(x_j)}_{\text{高维内积}} - \sum \alpha_i$$

2. 核技巧 (Kernel Trick)

直接计算高维向量 $\phi(x)$ 再做内积，计算量极其巨大（甚至无穷维）。
如果存在函数 $K(x, z)$ 满足：

$$K(x, z) = \phi(x)^T \phi(z)$$

我们就可以不用显式知道 $\phi(x)$ 是什么，直接在低维空间计算 $K(x, z)$ 来等效高维内积。

3. 常用核函数

• 线性核 (Linear Kernel)：$K(x, z) = x^T z$
  • 适用于特征维数高、线性可分的情况。
• 多项式核 (Polynomial Kernel)：$K(x, z) = (x^T z + 1)^d$
• 高斯核 / RBF 核：$K(x, z) = \exp(-\gamma ||x - z||^2)$
  • 最常用。相当于映射到无穷维空间。
  • $\gamma$ 控制高斯的宽度：$\gamma$ 越大，模型越关注局部，易过拟合；$\gamma$ 越小，模型越平滑。

参考

https://avanti1980.github.io/course-ml/pages/svm.html

---

那么，什么是支持向量？

支持向量机（SVM）中“支持向量”的数学推导

在支持向量机（SVM）中，“支持向量”（Support Vectors）是训练集中最靠近决策超平面的那些样本点。它们是最难分类的点，也是唯一决定超平面位置的点。

我们可以通过从线性分类器的定义出发，利用拉格朗日乘子法来揭示其数学本质。

1. 问题的数学描述

假设我们有一组数据 ${ (xi, y_i) }{i=1}^n$，其中 $x_i \in \mathbb{R}^d$，$y_i \in {+1, -1}$。线性超平面可以定义为：

$$w^T x + b = 0$$

为保证分类的鲁棒性，SVM 要求所有样本点不仅要分类正确，还要距离超平面有一定的间隔（Margin）。通过缩放 $w$ 和 $b$，我们可以令距离超平面最近的点满足：

$$|w^T x_i + b| = 1$$

由此得到所有样本必须满足的约束条件：

$$y_i (w^T x_i + b) \geq 1, \quad i=1,2,\dots,n$$

2. 优化目标与拉格朗日函数

SVM 的目标是最大化间隔 $\frac{2}{|w|}$，等价于最小化 $\frac{1}{2} |w|^2$。这是一个带约束的凸优化问题，我们引入拉格朗日乘子 $\alpha_i \geq 0$ 来构建拉格朗日函数：

$$\mathcal{L}(w, b, \alpha) = \frac{1}{2} \|w\|^2 - \sum_{i=1}^n \alpha_i \big[ y_i (w^T x_i + b) - 1 \big]$$

3. KKT 条件：支持向量的数学定义

根据优化理论，该问题的解必须满足 KKT（Karush-Kuhn-Tucker）条件。其中最关键的一条是对合互补条件（Complementary Slackness）：

$$\alpha_i \big[ y_i (w^T x_i + b) - 1 \big] = 0$$

这个等式意味着，对于每一个样本 $i$，只有两种情况：

1. $\alpha_i = 0$：此时 $y_i (w^T x_i + b) > 1$，这些点处于“间隔之外”，它们对损失函数没有贡献。如果删除这些点，最终生成的超平面不会有任何变化。
2. $\alpha_i > 0$：为了满足等式，必须有 $y_i (w^T x_i + b) - 1 = 0$，即 $y_i (w^T x_i + b) = 1$。这些点恰好落在间隔边界上。

结论：这些对应的 $\alpha_i > 0$ 的样本点 $x_i$ 就被称为支持向量。

4. 权重 $w$ 是如何构成的？

对 $\mathcal{L}(w, b, \alpha)$ 关于 $w$ 求偏导并令其为 0，我们可以得到：

$$w = \sum_{i=1}^n \alpha_i y_i x_i$$

由上式可见：

• 超平面的法向量 $w$ 是样本点的线性组合。
• 由于大部分样本的 $\alpha_i = 0$，所以实际上 $w$ 仅由支持向量（$\alpha_i > 0$ 的点）决定。

5. 总结：支持向量的特性

• 稀疏性：在一个庞大的数据集中，支持向量通常只占极少一部分。这意味着 SVM 具有极高的模型压缩能力，训练完成后，你只需要保存这些支持向量即可。
• 决定性：超平面的位置完全由支持向量“支撑”起来。移动非支持向量不会改变模型；但移动任何一个支持向量，超平面都会随之改变。

---

总结

SVM 的推导逻辑环环相扣，展现了数学的对称美：

1. 几何直观：将分类问题转化为最大化间隔的凸二次规划问题。
2. 拉格朗日对偶：将复杂的原始问题转化为易于求解的对偶问题，并自然引入了内积形式。
3. 软间隔：通过 $C$ 和 $\xi$ 处理噪声，实现偏差与方差的权衡。
4. 核技巧：通过 $K(x, z)$ 巧妙解决非线性问题，实现从低维到高维的“降维打击”。

理解了 KKT 条件和对偶性，你就真正掌握了 SVM 的灵魂。