支持向量机（SVM）

Support Vector Machines

支持向量机（SVM）是一种用于 分类和回归任务 的 监督学习算法。它试图找到 最佳边界，即超平面，以 分离数据中的不同类别。当需要进行二元分类，如垃圾邮件与非垃圾邮件或猫与狗的区分时，它非常有用。

SVM 的主要目标是 最大化两个类别之间的边界。边界越大，模型在新数据和未见数据上的表现就越好。

支持向量机（SVM） 算法

ML Lecture 20: Support Vector Machine

SVM 的关键概念

• 超平面（Hyperplane）：在特征空间中分离不同类别的 决策边界，在线性分类中用方程 $wx+b=0$ 表示。

• 支持向量（Support Vectors）：距离超平面最近的数据点，对确定超平面和间隔至关重要。

• 间隔（Margin）：超平面与支持向量之间的距离。SVM 旨在 最大化这个间隔 以获得更好的分类性能。

• 核函数（Kernel）：一种 将数据映射到更高维空间的函数，使支持向量机能够 处理非线性可分数据。

• 硬间隔（Hard Margin）：一种 最大间隔超平面，能够完美分离数据且 不发生误分类。

• 软间隔（Soft Margin）：通过 引入松弛变量允许一定程度的误分类，在数据不能完美分离时平衡间隔最大化和误分类惩罚。

• $C$：一种 正则化项，平衡 间隔最大化 和 误分类惩罚。较高的 $C$ 值会施加更严格的误分类惩罚。

• Hinge Loss：一种 惩罚分类错误点或边界违规的损失函数，并在支持向量机中与正则化结合使用。

• 对偶问题：涉及求解与支持向量相关的拉格朗日乘子，促进核技巧和高效计算。

支持向量机算法是如何工作的？

线性可分

支持向量机算法背后的 关键思想 是通过 最大化它们之间的边界来找到最佳分离两个类别的超平面。这个边界是从超平面到每侧最近的点（支持向量）的距离。

最佳超平面，也称为"硬边界"，是使超平面与两类最近数据点之间的距离最大化的那个。这确保了类之间的清晰分离。因此，从上面的图中，选择 $L2$ 作为硬边界。考虑如下场景，有一个蓝色球位于红色球的边界上，

红色球边界上的蓝色球是蓝色球中的 异常值。SVM 算法具有 忽略异常值 的特点，并找到最大化边界的最佳超平面。SVM 对异常值具有鲁棒性。

一个 软间隔 允许一些错误分类或间隔的违反，以改善泛化能力。SVM 优化以下方程以 平衡间隔最大化和惩罚最小化：

$$\text{Objective Function}=(\frac{1}{\text{margin}})+\lambda \sum \text{penalty}$$

用于违反的惩罚通常是 hinge loss：

• 如果一个数据点被正确分类且在间隔内，则没有惩罚（损失=0）。
• 如果一个点被错误分类或违反间隔，则 hinge loss 与违反的距离成正比增加。

非线性可分

当数据不是线性可分，即 无法用一条直线分开 时，SVM 使用一种称为 核函数 的技术 将数据映射到更高维的空间，使其变得可分。这种转换帮助 SVM 即使对于非线性数据也能找到一个决策边界。

核函数 是一种 将数据点映射到更高维空间 而 不显式计算该空间坐标 的 函数。

这允许 SVM 通过隐式执行映射来高效地处理非线性数据。例如，考虑那些非线性可分的数据点。通过应用核函数，SVM 将数据点转换到更高维空间，在那里它们变得线性可分。

• 线性核（Linear Kernel）：用于线性可分性。
• 多项式核（Polynomial Kernel）：将数据映射到 多项式空间。
• 径向基函数核（Radial Basis Function (RBF) Kernel）：将数据转换到 基于数据点之间距离的空间 中。
  
  将 1D 数据映射到 2D，以便能够分离这两个类别，在这种情况下，新变量 $y$ 被创建为距离原点的函数。

SVM 的数学计算

考虑一个包含两个类别（标记为 +1 和 -1）的二分类问题。有一个训练数据集，其中包含 输入特征向量 $X$ 及其对应的类别标签 $Y$。线性超平面的方程 可以写为：
$$w^{T}x+b=0$$

• $w$ 是 超平面的法向量（垂直于它的方向）。

• $b$ 是偏置项或偏差项，表示 超平面从原点沿法向量 $w$ 的距离。

数据点 $x_i$ 与决策边界之间的距离 可以计算为：
$$d_i=\frac{w^T{x}_i+b}{\Vert w\Vert }$$

其中 $\Vert w\Vert$ 表示权重向量 $w$ 的欧几里得范数。

线性支持向量机分类器

$$\hat{y}=\{\begin{array}{ll}+1:& w^{T}x+b\ge 0\\ -1:& w^{T}x+b<0\end{array}$$

$\hat{y}$ 是一个 数据点的预测标签。

对于线性可分数据集，目标是在 保证所有数据点都被正确分类的前提下，找到能够最大化两类数据之间间隔的超平面。优化问题：

$${\text{minimize}}_{w,b}\frac{1}{2}\Vert w{\Vert }^2$$

受约束于：

$$y_i(w^T{x}_i+b)\ge 1fori=1,2,3,\cdots ,m$$

其中，$y_i$ 是每个训练实例的类别标签（+1 或 -1），$x_i$ 是第 $i$ 个训练实例的特征向量，$m$ 是训练实例的总数。

条件 $y_i(w^T{x}_i+b)\ge 1$ 确保每个数据点被正确分类，并且位于边界之外。

线性 SVM 分类器中的软间隔

在有离群值或不可分数据的情况下，SVM 通过 引入松弛变量 $\zeta$ 允许一些误分类。优化问题被修改为：

$${\text{minimize}}_{\mathbf{w},b}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{\zeta }_i$$

• 第一项 $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$：对应 最大化间隔（越小间隔越大）。
• 第二项 $C\sum {\zeta }_i$：对 误分类（或违反间隔约束）的惩罚。

满足约束条件：
$$y_i(w^T{x}_i+b)\ge 1-{\zeta }_i\text{and}{\zeta }_i\ge 0fori=1,2,\dots ,m$$

• $C$ 是一个正则化参数，用于控制最大间隔和误分类惩罚之间的权衡。​
• $\zeta$ 是松弛变量，表示每个数据点对间隔的违反程度。

关于 $C$ 的作用：

• 如果 $C$ 很大：惩罚系数大，SVM 会 尽量减少训练集上的误分类。结果是模型趋向于 低偏差（bias）高方差（variance），容易 过拟合。

• 如果 $C$ 很小：容忍更多的误分类，优化时更重视间隔最大化。结果是模型 高偏差（bias）低方差（variance），可能 欠拟合，但泛化性更好。

RBF SVM 参数 $C$ 和 $\gamma$

RBF SVM parameters

• $\gamma$ 决定“边界形状的复杂度”（由 核函数 决定）。
• $C$ 决定“错误容忍度与间隔大小的平衡”（由 目标函数 决定）。

$\gamma$ 参数定义了 单个训练样本的影响范围。

$$K(x_i,x_j)=\exp (-\gamma \Vert x_i-x_j{\Vert }^2)$$

• 低 $\gamma$ → 每个样本的 影响范围大 → 决策边界更平滑（模型复杂度低）。
• 高 $\gamma$ → 每个样本 只影响自己附近 → 决策边界会变得弯曲、复杂（容易过拟合）。

直观比喻：可以把 $\gamma$ 想成“探照灯的照射半径的倒数”：

• 半径大（$\gamma$ 小）：灯光覆盖大范围 → 决策边界更平滑。
• 半径小（$\gamma$ 大）：灯光只照亮自己脚下 → 决策边界容易紧贴数据点。

模型的性能对 $\gamma$ 参数非常敏感。如果 $\gamma$ 太大，支持向量影响区域的半径仅包括支持向量本身，无论使用 $C$ 进行多少正则化，都无法防止过拟合。

$C$ 参数在 SVM 中充当 正则化参数，它在 训练样本的正确分类 和 决策函数的间隔最大化 之间进行权衡。对于较大的 C 值，如果决策函数能更好地正确分类所有训练点，则可以接受较小的间隔。较低的 C 会鼓励更大的间隔，从而得到更简单的决策函数，但代价是训练精度。

$$\min \frac{1}{2}\Vert w{\Vert }^2+C\sum {\xi }_i$$

• 大 $C$ → 惩罚误分类更重 → 更倾向于正确分类所有训练点 → 容易过拟合。
• 小 $C$ → 更关注间隔最大化，即便训练集上有些点分错了 → 泛化性更好。

直观比喻：

• 大 $C$：老师对错误零容忍 → 学生必须全对 → 结果可能死记硬背（过拟合）。
• 小 $C$：老师宽容 → 学生允许错几题，但更注重理解（更大间隔，泛化好）。

Gamma 与 C 的关系：$\gamma$ 控制“单个样本的影响力大小”（即边界的形状复杂度）。$C$ 控制“是否允许牺牲一些样本的分类正确性来换取更大的间隔”。

• 如果 $\gamma$ 太大（过于局部化），边界会高度复杂，即使 $C$ 很小（想要正则化），也可能过拟合。
• 如果 $\gamma$ 太小，边界太平滑，即使 $C$ 很大，也可能欠拟合。