机器学习笔记（胡浩基课程）上：引言、SVM 与经典方法

没有免费午餐定理

这个定理的核心思想是：如果我们对特征空间没有任何先验假设，那么所有算法的平均表现都是相同的，即没有办法评估算法的优劣。

考虑一个最简单的例子：假设计算机内存中仅有两个存储单元，数据有两个类别标签：

如果已知第一个存储单元的标签是 O，那么在对第二个存储单元的标签进行猜测时，由于没有任何偏好和先验信息，只能随机猜测 O 或 X，因此猜对的概率是 50%。

将这个模型复杂化：不止两个存储单元，而是一个 n \times n 的网格。当算法在猜测某个点的类别时，猜成 O 或 X 都是可能的。尽管我们的直觉往往会倾向于将特征空间中距离较近的样本点视为同一类，但这本身就是一种先验假设。

因此，一个好的算法一定与对特征空间的假设密切相关，必须基于具体情况进行判断。在机器学习领域，没有所谓普遍意义上的"好算法"，但有公认的好的方法，例如支持向量机 (SVM)、神经网络、深度学习算法等。

支持向量机 (SVM)

SVM 可以视为线性模型算法，通过核函数可扩展到非线性情况。在样本数量较少时使用 SVM 通常能得到较好结果，这是因为其背后有一套精美的数学理论支持。

线性模型

问题引入

在线性可分的样本集中，一条直线（在高维空间中是一个超平面）就可以将两组数据分开。那么问题在于：在训练数据集是线性可分的情况下，可以画出无数条这样的分界线（超平面），那么哪一条是最好的？为了解决这一问题，引入了 Margin（间隔）的概念。

在 SVM 中，真正影响超平面位置的是那些离分界面最近的训练样本点，这些点称为支持向量 (Support Vectors)。因此，训练得到的超平面模型只与支持向量有关，这也是支持向量机名称的由来。

数据定义

设训练数据及其类别标签为：

其中，每个 x_i 是一个 m 维向量，表示样本的 m 个特征；y_i 是对应的类别标签。具体地：

这里 y_i 取值为 +1 或 -1，分别代表两个不同的类别。之所以选择 \pm 1 而不是 0/1，是因为后续在统一分类条件时，\pm 1 的乘法性质会带来数学上的便利。

超平面模型

定义一个超平面：

其中：

\underline{w} 为 m 维向量，称为权重向量，它决定了超平面的法向量方向；b 为偏置项（bias），决定了超平面相对于原点的位移。超平面方程

表示所有满足该等式的点 \underline{x} 构成的集合，这是一个 m-1 维的超平面。

我们的目标是用给定的训练数据 (x_i, y_i) 来求出模型参数 (\underline{w}, b)。

机器学习算法的一般步骤

1. 用一个函数（如本例的超平面模型）限定模型形式。
2. 在该模型中留出待定参数 (\underline{w}, b)。
3. 利用训练数据通过某种准则(如最大化间隔)确定这些参数的取值。

线性可分的定义

若训练集 \{(x_i, y_i)\}_{i=1}^N 存在 (\underline{w}, b) 使得：

• 对于正类样本（y_i = +1），它们都位于超平面的一侧（使得 w^{\top} x_i + b \geq 0）
• 对于负类样本（y_i = -1），它们都位于超平面的另一侧（使得 w^{\top} x_i + b < 0）

则称该训练集是线性可分的。

上述两个条件可以综合为一个式子：

SVM的优化问题

支持向量机要解决的优化问题为：

这里需要解释两个关键点。

第一，目标函数是最小化 \|w\|^2：在超平面 w^{\top} x + b = 0 中，点 x_i 到超平面的距离为

对于支持向量（离超平面最近的点），这个距离称为间隔（margin）。最小化 \|w\|^2（等价于最小化 \|w\|）相当于最大化间隔，使得分类边界尽可能远离两类样本，从而提高模型的泛化能力。

第二，约束条件从 \geq 0 变成了 \geq 1：由于 (\underline{w}, b) 和 (k\underline{w}, kb)（k > 0）定义的是同一个超平面，存在缩放不确定性。为了消除这种不确定性并方便数学处理，我们对支持向量（即离超平面最近的那些点）施加约束

这相当于固定了 w 的尺度。对于其他非支持向量的点，由于它们离超平面更远，自然满足 y_i [w^{\top} x_i + b] > 1。因此，对所有点的约束统一写为 y_i [w^{\top} x_i + b] \geq 1。

补充知识

超平面参数的缩放不变性

若 w^T x + b = 0 描述一个超平面，那么对任意正实数 a > 0，a w^T x + a b = 0 仍表示同一超平面。换句话说，如果 (w, b) 是一组参数解，那么 (aw, ab) 也是该超平面的一组参数解。

这是因为方程 aw^T x + ab = 0 两边同时除以 a 后就回到了原方程 w^T x + b = 0，所以满足这两个方程的点集完全相同。这个性质意味着描述同一个超平面的参数 (w, b) 不是唯一的，存在无穷多组等价的参数表示。

点到超平面的距离公式

以二维情况为例，对于平面方程 w_1 x + w_2 y + b = 0，点 (x_0, y_0) 到此平面的距离为：

将其推广到高维超平面 w^T x + b = 0 的情况，任一点 x_0 到该超平面的距离为：

其中

是向量 w 的欧几里得范数。分子 |w^T x_0 + b| 表示点 x_0 代入超平面方程后得到的值的绝对值，分母 \|w\| 起到归一化的作用。

利用缩放性质推导优化问题

我们的目标是让间隔 d 最大。结合事实一和事实二，可以用 a 去缩放参数 (w, b) \Rightarrow (aw, ab)。由于缩放不改变超平面本身，我们可以选择一个特定的 a 值，使得在支持向量 x_0（即离超平面最近的点）上，有

这样做的目的是消除参数的缩放自由度，将问题规范化。

在这种规范化下，支持向量与超平面的距离变为：

因此，最大化间隔 d 等价于最小化 \|w\|，进而等价于最小化 \|w\|^2（因为 \|w\| 和 \|w\|^2 在正数范围内单调性相同，而平方形式在求导时更方便）。

对于支持向量，满足

对于其他离超平面更远的样本点，代入后的值必然更大，因此满足

约束条件的推导

综合上述分析，我们有两个条件：

对于第二个条件，由于绝对值内的值可正可负，而 y_i 恰好反映了样本点位于超平面的哪一侧：

当 y_i = +1 时，

当 y_i = -1 时，

因此 y_i 与 (w^T x_i + b) 的符号始终相同，它们的乘积 y_i(w^T x_i + b) 恰好等于 |w^T x_i + b|。

结合这两个条件，可以得到统一的约束形式：

至此，SVM 的优化问题形式得证。

凸二次规划问题

上述优化问题是一个凸二次规划问题，具有以下特征：

目标函数 \|w\|^2 是关于 w 的二次函数，且是正定的（Hessian 矩阵为单位矩阵的两倍，正定），因此是严格凸函数。约束条件 y_i (w^T x_i + b) \geq 1 是关于 (w, b) 的线性不等式，定义的可行域是凸集。凸函数在凸集上的优化问题称为凸优化问题。

二次规划问题的一个关键性质是：要么无解（可行域为空），要么只有一个极值点，且局部最优即全局最优。SVM 将分类问题转化为凸优化问题，保证了全局最优解的存在性和唯一性。这一点在机器学习中非常关键，因为非凸优化问题通常只能找到局部最优解，而凸优化问题可以确保找到全局最优解。

以上是支持向量机处理线性可分情况的基本理论框架。

软间隔SVM

问题的提出

当数据线性不可分时，原本的优化问题：

将会无解，因为不存在任何超平面能够使所有样本点都满足约束条件 y_i [w^T x_i + b] \geq 1。为了处理这种情况，需要对原优化问题进行改造。

软间隔SVM的优化问题 (改造后)

最小化目标函数：

约束条件：

松弛变量的含义

这里引入了松弛变量 \xi_i（slack variable），每个样本点 x_i 对应一个 \xi_i。松弛变量的作用是允许某些样本点"违反"原来的硬性约束 y_i [w^T x_i + b] \geq 1。

观察新的约束条件

• 当 \xi_i = 0 时，这就是原来的硬间隔约束
• 当 \xi_i > 0 时，约束被放松了，允许样本点进入间隔区域甚至被错误分类

具体地，若 0 < \xi_i < 1，则样本点位于间隔区域内但仍在正确的一侧，若 \xi_i \geq 1，则样本点被错误分类。

如果 \xi_i 可以任意大，那么约束条件 y_i [w^T x_i + b] \geq 1 - \xi_i 就必定成立，优化问题就变得没有意义了。但 \xi_i 不可能过大，因为目标函数中包含了 C \sum_{i=1}^{N} \xi_i 这一惩罚项，\xi_i 越大，目标函数值就越大，而我们要最小化目标函数。因此，优化过程会自动在"使间隔最大"和"允许少量违反"之间寻找平衡。

正则化项与超参数C

目标函数中的 C \sum_{i=1}^{N} \xi_i 称为正则化项（Regularization Term）。它的作用是对违反约束的样本点进行惩罚，使得本来无解的问题变得可解。

C 用于控制两个目标之间的权衡

• C 越大，对违反约束的惩罚越重，模型越倾向于正确分类所有训练样本，但可能导致过拟合
• C 越小，模型对误分类的容忍度越高，间隔会更大，但训练误差可能增加。

在这个新的优化框架下，已知量是训练数据 x_i, y_i，待求的未知量是 w, b, \xi_i。SVM 的一个优势是所需优化的参数非常少，相比之下，神经网络的参数数量要多得多。

软间隔方法的局限性

软间隔方法虽然可以处理线性不可分数据，但它并没有从根本上解决"用直线（超平面）将数据划分开"的限制。SVM 仍然在尝试找一条线来分类，只不过这条线可能会穿过某些数据点（通过松弛变量容忍错误）。对于本质上非线性分布的数据（如环形分布：圈内是 A 类，圈外是 B 类），这种方法无法有效分开。

我们真正想要的，是一条能够包裹住非线性数据的"曲线"。其他模型（如神经网络、决策树）通常通过增加模型复杂度来实现这一点，而 SVM 则采用了一种不同的方式：将数据映射到高维空间，在那里找一条线。

高维映射与核函数

高维映射的核心思想

SVM 引入了一个高维映射 \phi(x)：

即将原始的低维向量 x 映射为高维向量 \phi(x)，然后在高维空间中寻找一条能完成分类任务的超平面。

核心思想是：在低维空间中原本线性不可分的数据集，经过映射到高维空间后，有可能变得线性可分。一般来说，维度越高，数据越容易被线性分开。

异或问题示例

异或问题是一个经典的线性不可分例子。考虑四个点：(0,0), (1,1), (1,0), (0,1)，其中 (0,0) 和 (1,1) 为一类，(1,0) 和 (0,1) 为另一类。在二维平面上，不存在任何直线能将这两类分开。

对输入向量 x = \begin{bmatrix} a \\ b \end{bmatrix} 进行如下高维映射：

这个映射将二维向量变成了五维向量。对四个点进行映射后的结果为：

其中 x_1 = (0,0)，x_2 = (1,1)，x_3 = (1,0)，x_4 = (0,1)。

我们的目标是将 \phi(x_1), \phi(x_2)（同一类）与 \phi(x_3), \phi(x_4)（另一类）分开，即找到 w 和 b 满足：

一种可行解为：

可以验证：

因此在五维空间中，这四个点确实可以被一个超平面线性分开。

核函数的引入

上面的例子使用了一个人为构造的有限维映射 \phi(x)。但理论上，为了保证任意数据都能在高维空间中线性可分，\phi(x) 可能需要是无限维的。如果 \phi(x) 是无限维向量，那么 w 也会是无限维的，直接计算和存储都不可行。

SVM 绕开了这个问题，我们并不需要知道无限维映射 \phi(x) 的具体形式，只要知道一个核函数（Kernel Function）：

核函数直接计算两个样本点在高维空间中的内积，而不需要显式地计算出 \phi(x_1) 和 \phi(x_2) 各自的坐标。只要能通过 K(x_1, x_2) 得到 \phi(x_1) 和 \phi(x_2) 的内积值，优化问题中的约束条件：

依然可以求解。通过将 w 表示为样本点的线性组合

约束条件中的 w^T \phi(x_i) 就变成了

且只涉及核函数的计算。

总的来说，核函数允许我们无需显式知道 \phi(x) 是什么，只要能构造出一个核函数 K，就相当于用一个"核"计算了两个高维（甚至无限维）向量的内积，结果是一个可直接使用的数值，从而间接地解决了原本无法处理的高维计算问题。

常用核函数

高斯核

高斯核，也称为径向基函数核（RBF Kernel），是最常用的核函数之一，其定义为：

其中 \|x_1 - x_2\|^2 是两个样本点之间的欧氏距离的平方，\sigma 是一个超参数，控制高斯函数的"宽度"。当两个点 x_1 和 x_2 距离很近时，\|x_1 - x_2\|^2 很小，K(x_1, x_2) 接近 1，当两个点距离很远时，K(x_1, x_2) 接近 0。因此，高斯核衡量的是两个样本点的"相似度"。

高斯核对应的隐式映射 \phi(x) 实际上是无限维的。虽然可以通过泰勒展开来分析其形式，但具体的展开过程较为复杂，实际使用中我们只需要知道核函数的形式即可，无需显式计算 \phi(x)。

多项式核

多项式核的定义为：

其中 d 是多项式的阶数，是一个正整数超参数。x_1^T x_2 是原始空间中两个向量的内积，加上常数 1 后取 d 次幂。当 d = 1 时，多项式核退化为线性核（加上一个常数项），当 d 增大时，映射后的空间维度增加，模型的表达能力增强，但也更容易过拟合。

与高斯核不同，多项式核对应的映射 \phi(x) 是有限维的，其维度与原始空间维度和阶数 d 有关。例如，当原始空间为二维、d = 2 时，展开 (x_1^T x_2 + 1)^2 可以得到一个包含常数项、一次项、二次项和交叉项的表达式，对应的 \phi(x) 是一个有限维向量。

核函数的合法性条件

核函数 K 并不可以随便取，它必须满足一定的数学条件，才能保证存在某个映射 \phi 使得 K(x_1, x_2) = \phi(x_1)^T \phi(x_2)。这个充要条件由 Mercer 定理给出：

对称性条件的来源是内积本身的对称性：

因此如果 K 能表示为某个映射的内积，它必须是对称的。

半正定性条件可以用矩阵形式表达。定义核矩阵（Gram 矩阵）K_{ij} = K(x_i, x_j)，则半正定性条件等价于：

对所有向量 c 成立，即核矩阵 K 是半正定矩阵。这个条件的来源是：如果 K(x_i, x_j) = \phi(x_i)^T \phi(x_j)，那么核矩阵可以写成 K = \Phi^T \Phi，其中 \Phi 的列向量是 \phi(x_i)。而任何形如 \Phi^T \Phi 的矩阵都是半正定的，因为

只有同时满足对称性和半正定性，K 才是一个合法的核函数，才能保证存在对应的特征映射 \phi。

从核函数到优化求解

现在我们有了核函数 K，知道它可以隐式地计算高维空间中的内积 \phi(x_1)^T \phi(x_2)。但优化问题中的约束条件是：

这里 \phi(x_i) 是高维的、不可显式表示的，而 w 也是高维空间中的向量。如何用核函数 K 来替代这些无法直接计算的高维量？

解决这个问题需要引入优化理论中的原问题（Primal Problem）与对偶问题（Dual Problem）。通过将原问题转化为对偶问题，可以把优化变量从 (w, b, \xi) 转换为一组拉格朗日乘子，而在对偶问题的表达式中，\phi(x_i) 只以内积 \phi(x_i)^T \phi(x_j) 的形式出现，从而可以用核函数 K(x_i, x_j) 来替代。这一步是连接核函数与求解过程的关键，将在后续内容中详细讨论。

原问题与对偶问题

为了理解如何用核函数来求解 SVM，需要先掌握优化理论中原问题与对偶问题的概念。

原问题

原问题是我们最初想要求解的优化问题，其一般形式为：

最小化目标函数：

满足以下约束条件：

这里 w 是我们要优化的变量，f(w) 是目标函数，g_i(w) \leq 0 是不等式约束，h_i(w) = 0 是等式约束。对于 SVM 来说，f(w) = \frac{1}{2}\|w\|^2，不等式约束来自于分类条件 y_i[w^T x_i + b] \geq 1（可以改写为 1 - y_i[w^T x_i + b] \leq 0 的形式）。

对偶问题

对偶问题是通过拉格朗日方法从原问题推导出的另一个优化问题。首先构造拉格朗日函数：

这个函数将原问题的目标函数和约束条件整合在一起。其中 \alpha_i 和 \beta_i 称为拉格朗日乘子：\alpha_i 对应第 i 个不等式约束，\beta_i 对应第 i 个等式约束。

用向量形式可以简写为：

其中：

\alpha = [\alpha_1, \dots, \alpha_K]^T 和 \beta = [\beta_1, \dots, \beta_M]^T 分别是对应的拉格朗日乘子向量。

对偶函数与对偶问题的定义

定义对偶函数为：

这里 \inf_w 表示对所有可能的 w 取下确界（即最小值，如果最小值存在的话）。

对偶函数的含义是：在给定 \alpha, \beta 的情况下，对所有 w 的取值求拉格朗日函数的最小值。换句话说，每组固定的 (\alpha, \beta) 都会对应一个关于 w 的最小化问题，求解后得到一个只依赖于 (\alpha, \beta) 的函数值 \theta(\alpha, \beta)。

对偶问题的定义为：

最大化：

满足约束：

或用向量形式简写为 \alpha \geq 0。

这里 \alpha_i \geq 0 的约束是必须的，它与不等式约束 g_i(w) \leq 0 相对应。而等式约束对应的乘子 \beta_i 没有符号限制。

原问题与对偶问题的关系

对偶问题的求解过程可以理解为一个"先最小后最大"的过程：

• 首先固定 (\alpha, \beta)，对 w 求 L(w, \alpha, \beta) 的最小值，得到 \theta(\alpha, \beta)
• 然后在 \alpha \geq 0 的约束下，对 (\alpha, \beta) 求 \theta(\alpha, \beta) 的最大值

原问题则可以理解为"先最大后最小"的过程。可以证明，在一定条件下（如满足 Slater 条件的凸优化问题），原问题和对偶问题的最优值相等，这称为强对偶性。SVM 的优化问题恰好满足这些条件，因此可以通过求解对偶问题来得到原问题的解。

对偶问题的优势在于：在对偶问题的表达式中，优化变量从原来的 w（可能是高维甚至无限维）变成了拉格朗日乘子 \alpha（维度等于样本数量 N），并且 w 只以内积的形式出现，从而可以用核函数替代。

弱对偶定理

设 w^* 是原问题的最优解，\alpha^*, \beta^* 是对偶问题的最优解，则有如下不等式成立：

这个不等式称为弱对偶性（Weak Duality），它说明对偶问题的最优值总是不超过原问题的最优值。换句话说，对偶问题提供了原问题最优值的一个下界。

定理的证明

证明分为两个步骤。

第一步，根据对偶函数的定义：

\inf_w 表示对所有可能的 w 取下确界（最小值），因此对于任意特定的 w^*，下确界必然小于等于在该特定点的函数值。

第二步，分析 L(w^*, \alpha^*, \beta^*) 的值。根据拉格朗日函数的定义：

现在分析后面两个求和项的符号。

由于 w^* 是原问题的最优解，它必然满足原问题的所有约束条件：

同时，由于 \alpha^*, \beta^* 是对偶问题的解，满足对偶问题的约束：

现在考察求和项

对于第一个求和 \sum_{i=1}^{K} \alpha_i^* g_i(w^*)，每一项都是 \alpha_i^* \geq 0 与 g_i(w^*) \leq 0 的乘积，非负数乘以非正数得到非正数，因此每一项 \alpha_i^* g_i(w^*) \leq 0，整个求和

对于第二个求和 \sum_{i=1}^{M} \beta_i^* h_i(w^*)，由于 h_i(w^*) = 0（等式约束在最优解处必须严格满足），无论 \beta_i^* 取何值，每一项 \beta_i^* h_i(w^*) = 0，整个求和等于零。

综合以上分析：

因此：

结合第一步的结论 \theta(\alpha^*, \beta^*) \leq L(w^*, \alpha^*, \beta^*)，得到：

即：

证毕。

弱对偶性的意义

弱对偶性告诉我们，对偶问题的最优值 \theta(\alpha^*, \beta^*) 提供了原问题最优值 f(w^*) 的一个下界。两者之间的差

称为对偶间隙（Duality Gap）。在一般情况下，对偶间隙可能大于零，此时通过求解对偶问题只能得到原问题最优值的一个近似下界。

然而，在满足一定条件（如 Slater 条件）的凸优化问题中，对偶间隙为零，即 f(w^*) = \theta(\alpha^*, \beta^*)，这称为强对偶性（Strong Duality）。SVM 的优化问题是凸二次规划问题，满足强对偶性条件，因此可以通过求解对偶问题来精确地得到原问题的最优解。

强对偶定理

强对偶定理

对于某些特定类型的优化问题，可以证明对偶间隙为零，即 G = 0。

强对偶定理：如果目标函数 f(w) 是一个凸函数，约束函数 g(w) 为线性函数（即 g(w) = Ax + b 的形式），那么该优化问题的原问题与对偶问题的间隙为 0。

换句话说，如果 w^* 是原问题的最优解，而 \alpha^*, \beta^* 是对应对偶问题的最优解，则有：

回顾 SVM 的优化问题：

• 目标函数 f(w) = \frac{1}{2}\|w\|^2 是关于 w 的二次函数，且 Hessian 矩阵正定，因此是严格凸函数
• 约束条件 y_i(w^T x_i + b) \geq 1 是关于 (w, b) 的线性函数。

因此 SVM 满足强对偶定理的条件，原问题和对偶问题的最优值相等。这意味着我们可以通过求解对偶问题来得到原问题的精确解。

KKT条件

KKT 条件（Karush-Kuhn-Tucker 条件）是强对偶性成立时最优解必须满足的一组条件。其中最关键的一条是互补松弛条件：

对于任意 i = 1, \dots, K，有如下互补关系成立：

这意味着要么 \alpha_i^* = 0，要么 g_i(w^*) = 0，两者至少有一个为零。

• 如果某个不等式约束 g_i(w) \leq 0 在最优解处是"松弛"的（即 g_i(w^*) < 0，严格小于零，约束没有起作用），那么对应的拉格朗日乘子 \alpha_i^* = 0
• 只有当约束是"紧"的（即 g_i(w^*) = 0，约束恰好取等号，起到了限制作用）时，对应的 \alpha_i^* 才可能大于零。

对于 SVM 来说，约束条件是 1 - y_i(w^T x_i + b) \leq 0，此时KKT 条件意味着只有那些使约束取等号的样本点（即 y_i(w^T x_i + b) = 1，恰好位于间隔边界上的点）对应的 \alpha_i^* 才可能非零。这些点正是支持向量。因此，KKT 条件从理论上解释了为什么 SVM 的解只依赖于支持向量。

原问题与对偶问题总结

原问题

对偶问题

首先构造拉格朗日函数：

对偶问题为：

KKT条件

对于任意 i = 1, \dots, K，必须满足互补松弛条件：

即要么 \alpha_i^* = 0，要么 g_i(w^*) = 0。

回到SVM的核心问题

在掌握了原问题与对偶问题的理论框架之后，现在可以回到最初提出的问题：在 SVM 的约束条件

其中 \phi(x_i) 是高维（甚至无限维）的映射，无法显式计算。如何只用核函数 K(x_i, x_j) = \phi(x_i)^T \phi(x_j) 来代替 \phi(x_i)，从而解决这个优化问题？

因此通过将原问题转化为对偶问题，然后再求解对偶问题间接求得原问题的解。在对偶问题的表达式中，\phi(x_i) 只以内积 \phi(x_i)^T \phi(x_j) 的形式出现，因此可以用核函数 K(x_i, x_j) 来替代，从而避免了显式计算高维映射。

SVM原问题转化为对偶问题

SVM原问题的形式

SVM 的原问题可以写成如下形式：

将其与标准形式的原问题进行对比：

根据强对偶定理，当 f(w) 是凸函数且当所有约束条件是线性的时候，原问题和对偶问题具有相同的最优值。SVM 的约束条件 y_i [w^T \phi(x_i) + b] \geq 1 - \xi_i 和 \xi_i \geq 0 都是关于优化变量 (w, b, \xi) 的线性函数，因此约束条件的线性性是满足的。

那我们接下来只需要验证目标函数是否为凸函数:

凸函数的定义

凸函数的几何定义是：函数图像上任意两点之间的连线段总是位于函数图像的上方（或重合）。对于任意的 w_1, w_2 以及任意的 \lambda \in [0, 1]，满足

不等式左边是函数在 w_1 和 w_2 的凸组合点 \lambda w_1 + (1-\lambda)w_2 处的函数值，右边是函数值 f(w_1) 和 f(w_2) 的凸组合。凸函数的这个性质保证了局部最小值就是全局最小值，这对优化问题的求解至关重要。

证明范数平方是凸函数

首先证明 f(w) = \|w\|^2 = w^T w 是凸函数。需要验证对于任意 w_1, w_2 和 \lambda \in [0, 1]，不等式

成立。

计算不等式左边：

展开这个二次型：

计算不等式右边：

现在比较左右两边。将右边减去左边：

整理系数，对于 w_1^T w_1 项：

对于 w_2^T w_2 项：

因此：

由于 \lambda \in [0, 1]，所以 \lambda \geq 0 且 1 - \lambda \geq 0，因此 \lambda(1 - \lambda) \geq 0。同时 \|w_1 - w_2\|^2 \geq 0（范数的平方总是非负）。所以右边减去左边的结果非负，即：

这就证明了 f(w) = \|w\|^2 是凸函数。

目标函数整体的凸性

SVM 的目标函数是

已经证明了 \|w\|^2 是凸函数，而 \sum_{i=1}^{N} \xi_i 是关于 \xi_i 的线性函数，线性函数既是凸函数也是凹函数。凸函数的非负线性组合仍然是凸函数（\frac{1}{2} > 0，C > 0），因此整个目标函数是凸函数

综上，SVM 的优化问题满足强对偶定理的条件：目标函数是凸函数，约束条件是线性的。因此原问题和对偶问题具有相同的最优值，可以通过求解对偶问题来得到原问题的解。

补充1: 证明线性项是凸函数

设 f(\xi) = C \sum_{i=1}^{N} \xi_i，对任意 \lambda \in [0,1] 和任意两个向量 \xi^{(1)}, \xi^{(2)}，计算不等式两边。

左边：

右边：

左右两边完全相等，即

满足凸函数定义中的不等式（取等号的情况），因此 C \sum_{i=1}^{N} \xi_i 是凸函数。

补充2: 凸函数的加法性质

如果 f_1(w) 和 f_2(w) 都是凸函数，那么它们的和

也一定是凸函数。这个性质可以直接从凸函数的定义推导：对于任意 w_1, w_2 和 \lambda \in [0,1]，

因此，SVM 原问题中的目标函数 \frac{1}{2}\|w\|^2 + C \sum_{i=1}^{N} \xi_i 作为两个凸函数的和，也是凸函数，满足构建对偶问题的前提条件。

约束条件的标准化

接下来检验约束条件是否为线性的，以及是否符合标准形式。标准原问题的约束条件形式为：

而 SVM 的原始约束条件为：

这些约束都是 "\geq" 形式的，因此需要进行变形成标准形式的 \leq 0 。

一种处理方法是对 \xi_i 做变量替换。令 \xi_i' = -\xi_i，则原来的 \xi_i \geq 0 变为 \xi_i' \leq 0，原来的 1 - \xi_i 变为 1 + \xi_i'。变换后的优化问题为：

这里目标函数中的 C \sum \xi_i 变成了 -C \sum \xi_i'，因为 \xi_i = -\xi_i'。

两边乘以 -1 并移项：

现在所有的约束条件都是 g_i(\cdot) \leq 0 的形式。第一组约束

共有 N 个，第二组约束 \xi_i' \leq 0 也有 N 个，总共 2N 个不等式约束，没有等式约束（即 h_i = 0 的约束不存在）。

这些约束函数关于优化变量 (w, b, \xi') 都是线性的（或仿射的），因此满足强对偶定理的条件。至此，已经验证了 SVM 的优化问题同时满足目标函数凸性和约束条件线性性，可以将原问题转化为对偶问题求解。

为了后续推导的简洁，通常仍然使用原始的变量记号 \xi_i（而不是 \xi_i'），直接在原问题的形式上构造拉格朗日函数。约束条件的符号变换只是为了说明其符合标准形式，实际推导中会引入拉格朗日乘子来处理这些约束。

SVM对偶问题的构造

对偶问题的形式

根据拉格朗日对偶理论，SVM 的对偶问题为：

对比标准的对偶问题形式：

在标准对偶问题中只有一组拉格朗日乘子 \alpha_i（对应不等式约束）和 \beta_i（对应等式约束），而在 SVM 对偶问题中引入了两组乘子 \alpha_i 和 \beta_i，它们分别对应 SVM 的两个不等式约束条件。

对偶问题形式的解释

在标准对偶问题中，\inf_w 表示对原问题的优化变量 w 取最小值。对于 SVM，原问题的目标函数是：

这里的待优化变量实际上包括 (w, \xi, b) 三部分，而不仅仅是 w。因此，在 SVM 的对偶问题中，需要对 (w, \xi, b) 全部取 \inf。

由于之前将 SVM 的约束条件整理成了标准形式，只有 g_i \leq 0 形式的不等式约束，没有 h_i = 0 形式的等式约束。SVM 有两组不等式约束：

• 第一组：g_i^{(1)}(w, \xi, b) = 1 + \xi_i - y_i [w^T \phi(x_i) + b] \leq 0，共 N 个，对应拉格朗日乘子 \alpha_i。

• 第二组：g_i^{(2)}(\xi) = \xi_i \leq 0，共 N 个，对应拉格朗日乘子 \beta_i。

将这些代入拉格朗日函数的标准形式 L = f + \sum \alpha_i g_i，就得到了 SVM 对偶问题中的表达式。由于两组约束都是不等式约束，所以 \alpha_i \geq 0 和 \beta_i \geq 0 都需要满足。

求解对偶函数：令偏导数为零

接下来要做的是找到使拉格朗日函数 L(w, \xi, b, \alpha, \beta) 关于 (w, \xi, b) 最小的点，即求解：

这里需要注意 w 是一个高维向量（维度与 \phi(x) 相同，可能是无限维），所以对 w 求导是向量求导，结果是一个与 w 同维度的向量：

这个向量称为 f 关于 w 的梯度，记作 \nabla_w f 或 \frac{\partial f}{\partial w}。

例1：范数平方对向量的导数

若 f(w) = \frac{1}{2} \|w\|^2，则：

证明如下

将 \|w\|^2 展开：

所以：

对 w 的每个分量分别求偏导：

因此：

例2：线性函数对向量的导数

若 f(w) = w^T X，其中 X 是一个固定向量，那么：

证明如下

这是向量内积的形式，展开来看：

对 w 的每个分量求偏导：

因此：

线性函数 w^T X 对 w 的导数就是系数向量 X 本身。

求解SVM对偶问题

对拉格朗日函数求偏导

回顾 SVM 的拉格朗日函数：

为了求 \inf_{w, \xi, b} L，需要对 w、\xi_i、b 分别求偏导并令其为零。

对 w 求偏导：

这里用到了两个向量求导结果：\frac{\partial}{\partial w}(\frac{1}{2}\|w\|^2) = w，以及 \frac{\partial}{\partial w}(w^T \phi(x_i)) = \phi(x_i)。由此得到：

因此最优的 w 可以表示为所有样本点映射 \phi(x_i) 的线性组合，组合系数是 \alpha_i y_i。

对 \xi_i 求偏导：

由此得到：

对 b 求偏导：

由此得到：

这个条件要求所有 \alpha_i y_i 的和为零，是一个关于 \alpha_i 的等式约束。

将关系式代入拉格朗日函数

现在将上述三个条件代入拉格朗日函数，消去 w、\xi、b，得到只关于 \alpha（和 \beta）的对偶函数。

首先，利用 C = \alpha_i + \beta_i，即 \beta_i = C - \alpha_i，可以化简拉格朗日函数中与 \xi_i 相关的项：

因此，所有包含 \xi_i 的项都消掉了，拉格朗日函数化简为：

接下来，利用 \sum_{i=1}^{N} \alpha_i y_i = 0，可以消去与 b 相关的项：

因此，拉格朗日函数进一步化简为：

将其记为三部分之和：

计算②和③

对于②，将 w = \sum_{i=1}^{N} \alpha_i y_i \phi(x_i) 代入：

由于 \alpha_i 和 y_i 都是标量，转置不改变它们，只有 \phi(x_i) 是向量需要转置。展开双重求和：

这里出现了 \phi(x_i)^T \phi(x_j)，这正是核函数的定义：

因此：

对于③，同样将 w = \sum_{j=1}^{N} \alpha_j y_j \phi(x_j) 代入：

因此

由于核函数的对称性 K(x_j, x_i) = K(x_i, x_j)，所以：

对偶函数的最终形式

将①、②、③合并：

在这个最终表达式中，\phi(x_i) 只以核函数 K(x_i, x_j) = \phi(x_i)^T \phi(x_j) 的形式出现，完全不需要显式计算高维映射 \phi。这就是核技巧的作用。

约束条件的简化

原来的约束条件是 \alpha_i \geq 0 和 \beta_i \geq 0，由于

且

可以得到

结合 \alpha_i \geq 0，约束条件简化为

同时，从对 b 的偏导条件得到

因此，SVM 的对偶问题最终形式为：

这个问题的优化变量只有 \alpha = (\alpha_1, \alpha_2, \dots, \alpha_N)，共 N 个标量，而不再涉及高维的 w。目标函数是关于 \alpha 的二次函数（注意有负号，所以是凹函数，但我们是求最大化，等价于最小化一个凸函数），约束条件是线性的，因此这仍然是一个凸优化问题，保证有全局最优解。

SMO算法

为了求解这个凸优化问题，可以使用序列最小优化算法（Sequential Minimal Optimization，SMO）。SMO 算法的基本思想是：每次只选取两个变量 \alpha_i 和 \alpha_j 进行优化，固定其他所有变量。

选取两个变量的原因是约束条件的存在

如果只改变一个 \alpha_i，就会破坏这个等式约束，而同时改变两个变量，可以通过适当调整使等式约束继续满足。通过反复迭代这个过程，最终收敛到全局最优解。

从对偶问题的解到实际预测

问题的提出

现在已经将 SVM 问题转化为对偶问题，通过 SMO 算法可以求得最优的 \alpha_i。但问题还未结束：已知所有的 y_i，核函数也已确定，求得 \alpha 之后，如何进一步得到 w 和 b，从而对新样本进行分类？

根据之前推导的关系式

理论上求得 \alpha 后就可以计算 w。但这里有一个根本性的问题：\phi(x_i) 是高维（甚至无限维）的映射，无法显式计算。我们引入核函数的目的就是为了避免直接计算 \phi(x_i)，如果还要再通过这个公式来求 w，就又回到了原点。

而 SVM 的巧妙之处在于它实际上不需要显式求出 w。分类的最终目的是对于一个新的测试样本 x，判断它属于哪一类

测试流程的分析

对于测试样本 x，分类规则为：

可以看到，我们只需要知道 w^T \phi(x) + b 的值（或者说它的符号），而不需要单独知道 w 是什么。

将 w = \sum_{i=1}^{N} \alpha_i y_i \phi(x_i) 代入 w^T \phi(x)：

这里 \phi(x_i)^T \phi(x) 正是核函数 K(x_i, x) 的定义，可以直接计算而无需知道 \phi 的具体形式。因此，w^T \phi(x) 可以完全用核函数表示，避开了显式计算 \phi。

利用KKT条件求b

现在还剩下 b 需要确定。这里要用到 KKT 条件。

回顾 KKT 条件中的互补松弛条件，对于 i = 1, \dots, N：

现在选取一个满足 0 < \alpha_i < C 的样本点（这样的点一定存在，它们就是支持向量）。

由于

当 0 < \alpha_i < C 时，有

根据 KKT 条件：

• 因为 \beta_i \neq 0，所以 \xi_i = 0
• 因为 \alpha_i \neq 0，所以 1 + \xi_i - y_i (w^T \phi(x_i)) - y_i b = 0

将 \xi_i = 0 代入第二个等式：

所以:

解出 b：

将 w^T \phi(x_i) = \sum_{j=1}^{N} \alpha_j y_j K(x_j, x_i) 代入：

这个公式中同样只涉及核函数，不需要显式计算 \phi。实际应用中，为了数值稳定性，通常会对所有满足 0 < \alpha_i < C 的样本点计算 b 值，然后取平均。

SVM算法总结

训练阶段

输入：训练样本 (x_i, y_i)，i = 1, \dots, N

第一步，求解对偶优化问题：

使用 SMO 算法求解，得到最优的 \alpha_1^*, \alpha_2^*, \dots, \alpha_N^*。

第二步，计算 b：找一个满足 0 < \alpha_i < C 的样本点，利用公式：

输出：参数 \alpha_1^*, \alpha_2^*, \dots, \alpha_N^* 和 b

测试阶段

输入：测试样本 x

计算判别函数值：

根据符号进行分类：

输出：预测标签 y

在整个训练和测试过程中，高维映射 \phi 被完全消除了，所有计算都通过核函数 K 完成。即使 \phi 是无限维的，只要核函数 K 能在有限时间内计算，SVM 就能正常工作。

常用核函数介绍

线性核

线性核对应的映射就是恒等映射 \phi(x) = x，即不做任何映射。使用线性核的 SVM 就是在原始特征空间中寻找线性分界面，适用于数据本身线性可分或近似线性可分的情况。

多项式核

参数 d 是多项式的阶数，d 越大，对应的特征空间维度越高，模型的表达能力越强，但也更容易过拟合。d 是需要调节的超参数。

高斯径向基核

高斯核是最常用的核函数之一，对应的特征空间是无限维的。参数 \sigma（有时写作 \gamma = \frac{1}{2\sigma^2}）控制高斯函数的宽度：\sigma 越小，核函数衰减越快，模型越复杂，容易过拟合；\sigma 越大，核函数衰减越慢，模型越平滑。\sigma 是需要调节的超参数。

Tanh核

其中双曲正切函数形式为

这个核函数与神经网络中的激活函数形式类似，因此使用 Tanh 核的 SVM 与某些神经网络模型有一定的联系。参数 \beta 和 b 是需要调节的超参数。需要注意的是，Tanh 核并不对所有参数取值都满足 Mercer 条件（半正定性），使用时需要谨慎选择参数。

核函数的选择

实际应用中，高斯核（RBF）通常是首选，因为它能够处理各种非线性情况，且只有一个超参数需要调节。线性核适用于特征维度很高（如文本分类）或样本量很大的情况。多项式核在某些特定问题（如图像处理）中效果较好。核函数和超参数的最终选择通常通过交叉验证来确定。

评价函数的两个指标

在训练完分类器之后，需要评估其性能。常用的评价指标有两个：ROC 曲线和 EER（等错误率）。

基本概念：四个概率指标

在二分类问题中，样本有正类和负类两种真实标签，分类器的预测也有正类和负类两种输出。因此会产生四种情况：

• TP（True Positive，真正率）：正样本被正确识别为正的比例
• FN（False Negative，假负率）：正样本被错误识别为负的比例
• FP（False Positive，假正率）：负样本被错误识别为正的比例
• TN（True Negative，真负率）：负样本被正确识别为负的比例

这四个指标之间存在如下约束关系：

对于所有正样本，它们要么被正确识别为正（TP），要么被错误识别为负（FN），两者之和必然为 1。对于所有负样本，它们要么被错误识别为正（FP），要么被正确识别为负（TN），两者之和也必然为 1。

ROC曲线

对于一个固定的分类系统，存在一个基本规律：当 TP 增加时，FP 也会增加。这意味着如果一个系统试图把更多的正样本识别为正，那么它也倾向于把更多的负样本错误地识别为正。换句话说，在不改变模型本身的情况下，我们对正负样本的鉴别能力是一个固定的水平，只能在"放进更多正样本"和"挡住更多负样本"之间做权衡。

以 SVM 为例，测试样本的判断标准为：

如果想要放进更多的正样本（提高 TP），可以将阈值从 0 改为 -1（或更小的值）：

降低阈值后，更多的样本会被判定为正类。这确实会让更多的正样本被正确识别（TP 增加），但同时也会让更多的负样本被错误地识别为正（FP 增加）。

通过调整阈值 t，可以得到不同的 TP 和 FP 组合。四个指标之间的变化关系为：

关系 (3) 是分类器本身的特性，降低阈值会同时增加 TP 和 FP。

ROC 曲线（Receiver Operating Characteristic curve）就是以 FP 为横轴、TP 为纵轴，通过改变阈值 t 绘制出的曲线。曲线越靠近左上角（FP 低而 TP 高），说明分类器性能越好。理想的分类器在 FP = 0 时就能达到 TP = 1，对应 ROC 曲线经过点 (0, 1)。

评价标准

当有多个分类器需要比较时，可以绘制各自的 ROC 曲线。衡量曲线优劣的常用标准有两个：

第一个是 AUC（Area Under Curve），即 ROC 曲线下方的面积。AUC 越大，分类器性能越好。AUC = 1 表示完美分类器，AUC = 0.5 表示分类器是随机猜测。

第二个是 EER（Equal Error Rate，等错误率），即 ROC 曲线与对角线（FP = 1 - TP，或等价地 FP = FN）的交点对应的错误率。在这个点上，假正率等于假负率，即 FP = FN。EER 越小，分类器性能越好。

多类问题的处理方法

之前讨论的 SVM 都是二分类问题，标签 y \in \{+1, -1\}。当面对多类分类问题时，需要对 SVM 进行扩展。

处理方法概述

多类问题的处理方法主要有三种：

• 直接构造多类 SVM
• 一类 vs 其他类（One-vs-Rest, OvR）
• 一类 vs 另一类（One-vs-One, OvO）

一类vs其他类

以三类问题（C_1, C_2, C_3）为例，构造三个二分类 SVM：

每个 SVM 负责判断样本是否属于某一特定类。对于一个新的测试样本，分别用三个 SVM 进行预测，选择置信度最高的那个类别作为最终预测结果。

比如说，若 \text{SVM}_1 输出 y = +1（属于 C_1），\text{SVM}_2 输出 y = -1（不属于 C_2），\text{SVM}_3 输出 y = -1（不属于 C_3），则 x \in C_1。

对于 n 类问题，需要构造 n 个 SVM 分类器。

一类vs另一类

仍以三类问题为例，构造所有两两类别之间的二分类 SVM：

对于一个新的测试样本，用所有 SVM 进行预测，采用投票机制：每个 SVM 为其预测的类别投一票，最终选择得票最多的类别作为预测结果。

对于 n 类问题，需要构造 \frac{n(n-1)}{2} 个 SVM 分类器。例如 10 类问题需要 45 个分类器，100 类问题需要 4950 个分类器。虽然分类器数量较多，计算复杂度较高，但这种方法通常能获得最好的分类效果，因为每个分类器只需要区分两个类别，任务相对简单，训练也更充分。