机器学习数学推导（八）支持向量机

支持向量机(SVM)是现代机器学习最优雅的算法之一——它将几何直觉、凸优化理论和核方法完美融合，通过寻找最大间隔超平面实现高效分类。从线性可分到非线性映射，从硬间隔到软间隔，从原始形式到对偶问题， SVM 的数学推导展现了机器学习理论的深度与美感。本章将系统推导 SVM 的完整理论框架，包括拉格朗日对偶、 KKT 条件、 SMO 算法、核函数构造与理论保证。

线性可分支持向量机

几何直觉：最大间隔分类器

考虑二分类问题：，其中。线性分类器定义为：

决策函数为。

函数间隔：样本的函数间隔定义为：

函数间隔为正表示分类正确，且值越大表示越自信。

几何间隔：样本到超平面的几何距离为：

推导：超平面，点到超平面的距离为：

这是高等代数中点到超平面距离的标准公式。加上标签确保正确分类时距离为正。

最大间隔优化问题

硬间隔 SVM的目标是找到间隔最大的分离超平面：

等价地，可固定函数间隔（通过缩放总能做到），转化为：

这是一个凸二次规划问题（ Convex Quadratic Programming, QP）。

支持向量：满足的样本称为支持向量（Support Vectors, SVs），它们位于间隔边界上，决定了超平面的位置。其余样本（）对解无影响。

对偶问题推导

使用拉格朗日乘数法，引入非负乘子：

原始问题：

对偶问题：

步骤 1：对求极小

步骤 2：代入得对偶目标函数

对偶问题：

等价地，写成最小化形式：

KKT 条件

由于原始问题是凸优化且满足 Slater 条件，强对偶性成立。最优解满足 KKT 条件：

原始可行性：
对偶可行性：
互补松弛：
拉格朗日平稳：，

关键洞察：互补松弛条件表明： - 若，则（是支持向量） - 若，则（非支持向量）

下图展示了硬间隔 SVM 的几何原理——找到使间隔最大化的分离超平面，以及支持向量的位置：

因此，决策函数只依赖于支持向量：

求解偏置项

对于任意支持向量，有，因此：

实践中，为数值稳定性，对所有支持向量求平均：

软间隔支持向量机

松弛变量与惩罚参数

现实数据往往不是线性可分的。软间隔 SVM允许部分样本违反间隔约束，引入松弛变量：

：样本在间隔外，分类正确
：样本在间隔内但分类正确
：样本分类错误

优化问题：

其中是惩罚参数： - 大：重视经验风险，接近硬间隔（可能过拟合） - 小：重视结构风险，间隔大但允许更多误分（可能欠拟合）

对偶问题

拉格朗日函数为：

对求导并令为 0：

由于，得。代入得软间隔对偶问题：

与硬间隔的唯一区别是增加了上界约束。

KKT 条件与支持向量分类

软间隔 SVM 的 KKT 条件：

支持向量分为两类： - 边界支持向量：，在间隔边界上（） - 非边界支持向量：，在间隔内或被误分（）

下图展示了不同值下软间隔 SVM 的行为——越大间隔越窄（接近硬间隔），越小间隔越宽但允许更多误分：

核方法与非线性 SVM

特征映射与核函数

对于非线性问题，将输入空间映射到高维特征空间：

在特征空间中进行线性分类：

对偶问题变为：

核函数定义为：

核技巧（Kernel Trick）：无需显式计算，只需计算核函数，从而避免高维甚至无限维特征空间的计算。

常用核函数

1. 线性核：

2. 多项式核：

其中是超参数。

3. 高斯核（RBF 核）：

其中。RBF 核对应无限维特征空间。

下图展示了 SVM 的核心思想：左图展示最大间隔原理，决策边界与支持向量之间的间隔最大化；右图展示软间隔如何通过引入松弛变量允许部分样本违反间隔约束：

下图展示了 SVM 的核心思想：左图展示最大间隔原理，决策边界与支持向量之间的间隔最大化；右图展示 RBF 核如何将非线性可分的数据（同心圆）通过核技巧映射到高维空间实现线性分离：

下图直观展示了核映射的原理——将输入空间中非线性可分的数据映射到特征空间后变为线性可分：

下图对比了不同核函数在同一数据集上的效果：

4. Sigmoid 核：

（注：Sigmoid 核仅在特定参数下为正定核）

Mercer 定理与正定核

Mercer 定理：对称函数是有效核函数（即存在特征映射使得）当且仅当对任意个样本，核矩阵是半正定的：

即对任意，有。

核函数的性质：

闭性：若是核，则、（）、也是核
函数组合：是核（为任意函数）
核外推：是核，若是径向基函数且满足条件

RBF 核的特征空间

RBF 核对应的特征映射维度是无限维。证明使用泰勒展开：

每个对应多项式核的特征空间，无限求和导致无限维。

下图通过动画展示了不同核函数（线性核、多项式核、RBF 核）在相同数据集上的决策边界差异：

算法：在每个节点，使用线性分类器（如感知机、SVM）找到分裂超平面。

下图展示了参数如何影响软间隔 SVM 的决策边界——越大间隔越小但更重视训练准确率：

下图展示了两种主要的多分类 SVM 策略：

下面的动画展示了 SMO 算法的迭代收敛过程：

SMO 算法

坐标上升与块坐标下降

求解对偶问题需要满足约束和。

坐标上升法：每次优化一个变量，固定其余。但由于等式约束，单独改变一个会违反约束。

SMO 算法（Sequential Minimal Optimization, Platt 1998）：每次选择两个变量 优化，固定其余。

SMO 的两变量子问题

假设选定，固定其余。约束简化为：

$常数$

消元：由，得：

（利用）

代入目标函数，变为关于的单变量二次函数：

无约束最优解：

其中： - 是预测误差 - （）

裁剪：确保满足约束：

其中根据或分两种情况计算（见实现代码）。

更新：

启发式选择策略

第一个变量：选择违反 KKT 条件最严重的样本

第二个变量：选择使最大的样本（即误差差异最大）

SVM 的统计学习理论

VC 维与泛化误差界

对于超平面分类器，VC 维为（是特征维度）。但 SVM 通过最大化间隔，有效降低了复杂度。

间隔理论：设数据集在半径的球内，间隔为，则 SVM 的 VC 维满足：

间隔越大，VC 维越小，泛化能力越强。

下图展示了 SVM 的 Hinge 损失与逻辑回归的交叉熵损失的对比：

结构风险最小化

SVM 实现了结构风险最小化（Structural Risk Minimization, SRM）：

$经验风险复杂度惩罚$

对于软间隔 SVM，目标函数可改写为：

其中是Hinge 损失。

多分类 SVM

One-vs-Rest (OvR)

训练个二分类器，第个分类器将类别与其余类别分离。预测时：

其中是第个分类器的决策值。

One-vs-One (OvO)

训练个二分类器，每个分类器区分一对类别。预测时投票：

DAGSVM 与纠错输出编码

DAGSVM：使用有向无环图组织 OvO 分类器，预测复杂度从降至。

纠错输出编码（ECOC）：为每个类别分配二进制码字，训练多个二分类器对应码字的每一位。预测时选择汉明距离最小的类别。

完整实现

import numpy as np

class SVM:
    def __init__(self, C=1.0, kernel='linear', gamma=0.1, degree=3, 
                 coef0=0, tol=1e-3, max_iter=1000):
        self.C = C
        self.kernel_type = kernel
        self.gamma = gamma
        self.degree = degree
        self.coef0 = coef0
        self.tol = tol
        self.max_iter = max_iter
        
    def kernel(self, X1, X2):
        """计算核矩阵"""
        if self.kernel_type == 'linear':
            return X1 @ X2.T
        elif self.kernel_type == 'poly':
            return (self.gamma * X1 @ X2.T + self.coef0) ** self.degree
        elif self.kernel_type == 'rbf':
            X1_norm = np.sum(X1 ** 2, axis=1).reshape(-1, 1)
            X2_norm = np.sum(X2 ** 2, axis=1).reshape(1, -1)
            K = X1_norm + X2_norm - 2 * X1 @ X2.T
            return np.exp(-self.gamma * K)
        elif self.kernel_type == 'sigmoid':
            return np.tanh(self.gamma * X1 @ X2.T + self.coef0)
        
    def fit(self, X, y):
        """SMO 算法训练 SVM"""
        N, d = X.shape
        self.X = X
        self.y = y
        self.alpha = np.zeros(N)
        self.b = 0
        self.K = self.kernel(X, X)
        self.errors = self._decision_function(X) - y
        
        num_changed = 0
        examine_all = True
        iter_count = 0
        
        while (num_changed > 0 or examine_all) and iter_count < self.max_iter:
            num_changed = 0
            if examine_all:
                for i in range(N):
                    num_changed += self._examine_example(i)
            else:
                non_bound_indices = np.where((self.alpha > 0) & (self.alpha < self.C))[0]
                for i in non_bound_indices:
                    num_changed += self._examine_example(i)
            
            if examine_all:
                examine_all = False
            elif num_changed == 0:
                examine_all = True
            
            iter_count += 1
        
        # 提取支持向量
        sv_indices = np.where(self.alpha > 1e-5)[0]
        self.support_vectors_ = X[sv_indices]
        self.support_labels_ = y[sv_indices]
        self.support_alpha_ = self.alpha[sv_indices]
        
        return self
    
    def _decision_function(self, X):
        """计算决策函数值"""
        K = self.kernel(self.X, X)
        return (self.alpha * self.y) @ K + self.b
    
    def _examine_example(self, i2):
        """检查并优化第 i2 个样本"""
        y2 = self.y[i2]
        alpha2 = self.alpha[i2]
        E2 = self.errors[i2]
        r2 = E2 * y2
        
        # 检查 KKT 条件
        if (r2 < -self.tol and alpha2 < self.C) or (r2 > self.tol and alpha2 > 0):
            # 选择第二个变量
            non_bound = np.where((self.alpha > 0) & (self.alpha < self.C))[0]
            if len(non_bound) > 1:
                # 启发式选择：最大|E1 - E2|
                i1 = np.argmax(np.abs(self.errors - E2))
                if self._take_step(i1, i2):
                    return 1
            
            # 随机选择非边界样本
            for i1 in np.roll(non_bound, np.random.randint(len(non_bound))):
                if self._take_step(i1, i2):
                    return 1
            
            # 随机选择所有样本
            for i1 in np.roll(range(len(self.y)), np.random.randint(len(self.y))):
                if self._take_step(i1, i2):
                    return 1
        
        return 0
    
    def _take_step(self, i1, i2):
        """优化 alpha[i1]和 alpha[i2]"""
        if i1 == i2:
            return False
        
        alpha1, alpha2 = self.alpha[i1], self.alpha[i2]
        y1, y2 = self.y[i1], self.y[i2]
        E1, E2 = self.errors[i1], self.errors[i2]
        s = y1 * y2
        
        # 计算边界 L 和 H
        if y1 != y2:
            L = max(0, alpha2 - alpha1)
            H = min(self.C, self.C + alpha2 - alpha1)
        else:
            L = max(0, alpha1 + alpha2 - self.C)
            H = min(self.C, alpha1 + alpha2)
        
        if L == H:
            return False
        
        # 计算 eta
        k11 = self.K[i1, i1]
        k12 = self.K[i1, i2]
        k22 = self.K[i2, i2]
        eta = k11 + k22 - 2 * k12
        
        if eta > 0:
            # 正常情况
            alpha2_new = alpha2 + y2 * (E1 - E2) / eta
            alpha2_new = np.clip(alpha2_new, L, H)
        else:
            # eta <= 0 的退化情况（理论上不应发生）
            return False
        
        if abs(alpha2_new - alpha2) < 1e-5:
            return False
        
        alpha1_new = alpha1 + s * (alpha2 - alpha2_new)
        
        # 更新阈值 b
        b1 = E1 + y1 * (alpha1_new - alpha1) * k11 + y2 * (alpha2_new - alpha2) * k12 + self.b
        b2 = E2 + y1 * (alpha1_new - alpha1) * k12 + y2 * (alpha2_new - alpha2) * k22 + self.b
        
        if 0 < alpha1_new < self.C:
            b_new = b1
        elif 0 < alpha2_new < self.C:
            b_new = b2
        else:
            b_new = (b1 + b2) / 2
        
        # 更新错误缓存
        delta_b = b_new - self.b
        delta_alpha1 = alpha1_new - alpha1
        delta_alpha2 = alpha2_new - alpha2
        
        self.errors += y1 * delta_alpha1 * self.K[:, i1] + y2 * delta_alpha2 * self.K[:, i2] + delta_b
        self.errors[i1] = 0
        self.errors[i2] = 0
        
        self.alpha[i1] = alpha1_new
        self.alpha[i2] = alpha2_new
        self.b = b_new
        
        return True
    
    def predict(self, X):
        """预测"""
        decision = self._decision_function(X)
        return np.sign(decision)
    
    def score(self, X, y):
        """计算准确率"""
        return np.mean(self.predict(X) == y)

# 示例使用
if __name__ == '__main__':
    from sklearn.datasets import make_classification, make_moons
    from sklearn.model_selection import train_test_split
    import matplotlib.pyplot as plt
    
    # 线性可分数据
    X, y = make_classification(n_samples=100, n_features=2, n_redundant=0, 
                                n_informative=2, n_clusters_per_class=1, 
                                random_state=42)
    y = 2 * y - 1  # 转为{-1, +1}
    
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
    
    # 线性核
    svm_linear = SVM(C=1.0, kernel='linear')
    svm_linear.fit(X_train, y_train)
    print(f"线性核准确率: {svm_linear.score(X_test, y_test):.4f}")
    
    # 非线性数据
    X, y = make_moons(n_samples=100, noise=0.1, random_state=42)
    y = 2 * y - 1
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
    
    # RBF 核
    svm_rbf = SVM(C=1.0, kernel='rbf', gamma=1.0)
    svm_rbf.fit(X_train, y_train)
    print(f"RBF 核准确率: {svm_rbf.score(X_test, y_test):.4f}")

Q&A 精选

Q1：为什么 SVM 要最大化间隔？

A：几何直觉上，间隔越大，分类器对噪声越鲁棒。统计学习理论表明，间隔与 VC 维成反比（），间隔越大，模型复杂度越低，泛化能力越强。这是 SVM 优于其他线性分类器的核心原因。

Q2：对偶问题比原始问题有什么优势？

A：1) 对偶问题只依赖于样本内积，便于核技巧；2) 约束从个不等式简化为个盒约束和 1 个等式；3) 对偶最优解的稀疏性（大多数）使预测高效。

Q3：为什么只有支持向量影响决策边界？

A：由 KKT 互补松弛条件，非支持向量满足且，对决策函数无贡献。这是 SVM 的关键优势：预测只依赖少数关键样本。

Q4：软间隔的参数如何选择？

A：通过交叉验证。越大，越重视训练误差（接近硬间隔，易过拟合）；越小，越重视间隔（易欠拟合）。常用网格搜索：。

Q5：RBF 核的参数如何影响模型？

A：控制核函数的宽度。越大，核函数越窄，单个样本影响范围越小，模型越复杂（易过拟合）；越小，影响范围越广，模型越平滑（易欠拟合）。

Q6：为什么 SVM 对特征缩放敏感？

A：SVM 通过欧氏距离计算间隔（），不同特征尺度会影响的各分量贡献。标准化（如 Z-score）使各特征公平竞争，避免大量纲特征主导决策边界。

Q7： SVM 能处理多标签分类吗？

A：标准 SVM 是二分类器。对于多标签（每个样本属于多个类别），可训练个独立的 OvR SVM，每个判断样本是否属于该类。

Q8： SMO 算法为什么高效？

A：SMO 避免了求解大规模 QP 问题（复杂度），通过分解为小的两变量子问题（解析解，）。选择违反 KKT 条件最严重的变量对，加速收敛。实践中比通用 QP 求解器快数十倍。

Q9： SVM 与逻辑回归的区别？

A： | 维度 | SVM | 逻辑回归 | |------|-----|----------| | 损失 | Hinge Loss | Cross-Entropy | | 输出 | 决策值（距离） | 概率 | | 稀疏性 | 支持向量（稀疏） | 所有样本参与 | | 核方法 | 天然支持 | 需修改 | | 多分类 | OvR/OvO | Softmax |

SVM 适合硬分类与非线性边界，逻辑回归适合概率预测与大规模数据。

Q10：如何可视化 SVM 的决策边界？

A：对于 2D 数据：

def plot_svm_boundary(svm, X, y):
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                         np.linspace(y_min, y_max, 200))
    Z = svm._decision_function(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    plt.contourf(xx, yy, Z, levels=[-1, 0, 1], alpha=0.3, colors=['blue', 'white', 'red'])
    plt.contour(xx, yy, Z, levels=[-1, 0, 1], linewidths=[1, 2, 1], colors='k')
    plt.scatter(X[:, 0], X[:, 1], c=y, edgecolors='k', cmap='bwr')
    plt.scatter(svm.support_vectors_[:, 0], svm.support_vectors_[:, 1], 
                s=200, facecolors='none', edgecolors='k', linewidths=2)
    plt.show()

Q11：SVM 能做回归吗？

A：可以。Support Vector Regression (SVR) 引入-不敏感损失：

只惩罚误差超过的样本，其余视为"支持向量"。

Q12：SVM 的时间复杂度是多少？

A： - 训练：SMO 算法平均到（取决于支持向量数量） - 预测：，是支持向量数（通常）

对于大规模数据（），考虑线性 SVM（LibLinear）或随机梯度下降 SVM。

✏️ 练习题与解答

练习 1：几何间隔与函数间隔

题目：设超平面为，样本点。计算该样本的函数间隔和几何间隔。

解答：

函数间隔：

几何间隔：

练习 2：KKT 条件验证

题目：在软间隔 SVM 中，若某样本满足，，判断这是否违反 KKT 条件。

解答：

KKT 条件要求：

但题目给出，违反了 KKT 条件。正确情况应该是边界支持向量。

练习 3：核函数验证

题目：证明是有效核函数，并给出对应的特征映射（设）。

解答：

对于，：

构造特征映射：

验证：，因此是有效核函数。

练习 4：软间隔目标函数的等价形式

题目：证明软间隔 SVM 等价于最小化 Hinge Loss 加正则项：

解答：

原始问题中，约束和等价于。

为最小化目标，最优的（Hinge Loss）。代入即得等价形式。

练习 5：VC 维与间隔的关系

题目：数据集在半径的球内，SVM 找到的间隔为。根据间隔理论，估计该 SVM 的 VC 维上界。

解答：

间隔越大，VC 维越小，泛化能力越强。这解释了为什么最大化间隔能提升泛化性能。

参考文献

Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273-297.
Vapnik, V. N. (1998). Statistical Learning Theory. Wiley.
Platt, J. C. (1998). Sequential minimal optimization: A fast algorithm for training support vector machines. Technical Report MSR-TR-98-14, Microsoft Research.
Sch ö lkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press.
Cristianini, N., & Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines. Cambridge University Press.
Burges, C. J. C. (1998). A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2), 121-167.
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer. [Chapter 12: Support Vector Machines]

支持向量机以其坚实的理论基础、优雅的数学形式和卓越的实战性能，成为机器学习的里程碑算法。从间隔最大化到核技巧，从对偶理论到 SMO 算法， SVM 完美诠释了理论与实践的统一。理解 SVM 不仅是掌握经典算法的需要，更是通往深度学习（许多现代损失函数借鉴 Hinge Loss）和核方法高级主题的必经之路。