Lecture 09 支持向量机（SVM）
主要内容
- 支持向量机（SVM）作为最大间隔分类器
- 硬间隔 SVM 目标函数推导
- SVM 目标函数作为正则化损失函数
1. 最大间隔分类器：动机
线性二分类问题的新突破
1.1 开篇：线性 SVM
- 在第一部分中，我们将考虑 SVM 的基本设置，称为线性硬间隔 SVM。这些定义现在看来没有多大意义，但是在后面的学习中我们将回到这个定义上。
- 请记住：SVM 比最初出现时的功能更强大。
- 现在，我们将数据建模为线性可分的，即存在一个能够完美分离各个类别的超平面。
- 我们将考虑一次性使用所有数据进行训练。
1.2 SVM 是一个线性二分类器
- 如果 $s\ge 0$，预测为 $A$
- 如果 $s< 0$，预测为 $B$
其中 $s=b+\sum_{i=1}^{m}x_iw_i$
SVM 是一个线性分类器：$s$ 是输入的一个线性函数，并且分类边界是线性的。
1.3 SVM 和感知器
- 在给定学习到的参数值的情况下，SVM 会像感知器一样预测。
- SVM 的不同之处在于：学习参数的方式。
- 感知器：最小化感知器损失函数
- SVM：选择参数的不同标准
1.4 选择分类边界
- SVM 是一个线性二分类器：选择参数意味着选择一个分类边界（超平面）。
- 2D 情况下：
我们应该选择哪个边界？
- 假设数据集是线性可分的，那么感知器将找到一个可以完美分离各个类别的边界。这可以是任何这样的边界，例如图中的 A 或 B。
-
对于感知器而言，所有这样的边界都一样好，因为对于每个感知器而言，其损失函数都为零。
- 但是它们对我们来说看起来并不一样好。A 边界似乎更可靠。当新数据点到达时，B 边界可能会对其分类错误。
目标是找到最安全的边界
- 从直觉上看，最可靠的边界应当位于两个类别之间，并且尽可能远离这两个类别。
- SVM 的目标函数捕捉到了这一点，SVM 的目标是找到使得不同类别之间间隔最大化的分类边界。
1.5 最大间隔分类器
- SVM 是一个线性二分类器。SVM 的训练目标是找到使间隔最大化的分类边界。
- 因此，SVM 又称为最大间隔分类器。
- 训练数据是固定的，因此间隔是由分类边界的位置和方向定义的，而分类边界的位置和方向则是由 SVM 参数定义的。
- 我们的下一步是通过将间隔宽度表示为一个参数（和数据）的函数来形式化我们的目标。
2. 最大间隔分类器：推导
关于 SVM 目标函数的几何推导
2.1 间隔宽度
- 尽管间隔可以被视为两条虚线之间的空间，但更方便的做法是，将间隔宽度定义为分类边界与最近数据点之间的距离。
-
这个分类边界恰好在 “两个类别之间”：到最近的红色点和蓝色点的距离相同。
- 问题： 为了达到最大间隔必须这样。为什么？
- 落在间隔边界上的数据点称为 支持向量。
- 我们希望最大化分类边界到支持向量的距离。
- 但是，在此之前，让我们推导出任意一个点到一个超平面的距离的表达式。
2.2 一个点到超平面的距离
第一部分
- 考虑到任意一个点 $X$（可以来自任意一个类别，并且不需要是离分类边界最近的点），令 $X_p$ 表示点 $X$ 在分类边界上的投影。
-
现在，令 $\boldsymbol r$ 表示向量 $X_p-X$。注意，$\boldsymbol r$ 垂直 于分类边界，并且 $\|\boldsymbol r\|$ 就是要求的 距离。
- 分类边界由参数 $\boldsymbol w$ 和 $b$ 定义
- 根据之前线性代数的讲义，回忆 $\boldsymbol w$ 是一个垂直于分类边界的向量
- 图中，$\boldsymbol w$ 的起点是分类边界上一个任意的点
- $\|\boldsymbol w\|=\sqrt{w_1^2+…+w_m^2}$
第二部分
- 向量 $\boldsymbol r$ 和 $\boldsymbol w$ 平行，但是通常两者长度不同。简单来说，$\boldsymbol r=\boldsymbol w\dfrac{\|\boldsymbol r\|}{\|\boldsymbol w\|}$
-
接下来，点 $X$ 和点 $X_p$ 可以被视为向量 $\boldsymbol x$ 和 $\boldsymbol x_p$。
通过向量加法，我们可以得到 $\boldsymbol x+\boldsymbol r=\boldsymbol x_p$ 或者 $\boldsymbol x+\boldsymbol w\dfrac{\|\boldsymbol r\|}{\|\boldsymbol w\|}=\boldsymbol x_p$
- 现在，我们将等式两边都乘上 $\boldsymbol w’$，然后加上 $b$，得到：
$\boldsymbol w’\boldsymbol x+b+\boldsymbol w’\boldsymbol w\dfrac{\|\boldsymbol r\|}{\|\boldsymbol w\|}=\boldsymbol w’\boldsymbol x_p+b$ - 因为 $\boldsymbol x_p$ 落在分类边界上，我们可以得到：
$\boldsymbol w’\boldsymbol x+b+\|\boldsymbol w\|^2\dfrac{\|\boldsymbol r\|}{\|\boldsymbol w\|}=0$ - 化简即可得到点 $X$ 到分类边界的距离为：
$\|\boldsymbol r\|=-\dfrac{\boldsymbol w’\boldsymbol x+b}{\|\boldsymbol w\|}$
第三部分
- 然而，如果我们将点取到分类边界的另一侧，向量 $\boldsymbol r$ 和 $\boldsymbol w$ 将会 反向平行，得到 $\boldsymbol r=-\boldsymbol w\dfrac{\|\boldsymbol r\|}{\|\boldsymbol w\|}$
-
在这种情况下，距离为 $\|\boldsymbol r\|=\dfrac{\boldsymbol w’\boldsymbol x+b}{\|\boldsymbol w\|}$
- 我们一会将再回到这里，现在我们可以将两种情况的结果结合起来：
距离为 $\|\boldsymbol r\|=\pm \dfrac{\boldsymbol w’\boldsymbol x+b}{\|\boldsymbol w\|}$
2.3 使用标签对类别进行编码
- 训练数据是一个集合 \(\{\boldsymbol x_i,y_i\}, i=1,...,n\)，其中 $\boldsymbol x_i$ 是一个 $m$ 维的实例，$y_i$ 是对应的二分类标签，被编码为 $-1$ 或 $1$。
- 给定一个完美的分类边界，$y_i$ 编码了每一个 $\boldsymbol x_i$ 位于边界的哪一侧。
-
因此，第 $i$ 个点到一个完美边界的距离可以被编码为：
\[\|\boldsymbol r_i\|=\dfrac{y_i(\boldsymbol w'\boldsymbol x_i+b)}{\|\boldsymbol w\|}\]
2.4 最大间隔目标
- 第 $i$ 个点到一个完美边界的距离可以被编码为：$\|\boldsymbol r_i\|=\dfrac{y_i(\boldsymbol w’\boldsymbol x_i+b)}{\|\boldsymbol w\|}$
- 间隔宽度是到最近点的距离
- 因此，SVM 的目标是最大化 $\left(\min\limits_{i=1,…,n}\dfrac{y_i(\boldsymbol w’\boldsymbol x_i+b)}{\|\boldsymbol w\|}\right)$ 作为 $\boldsymbol w$ 和 $b$ 的一个函数
思考： 这样做的问题在哪里？
2.5 表示形式不唯一
- 一个分类边界（例如：2D 空间里的一条直线）是一系列点的集合，满足 $\boldsymbol w’\boldsymbol x+b=0$ ，对于某些给定的 $\boldsymbol w$ 和 $b$
- 然而，同样的点集也满足 $\tilde{\boldsymbol w’}\boldsymbol x+\tilde b=0$ ，其中 $\tilde{\boldsymbol w}=\alpha \boldsymbol w$ ，$\tilde b=\alpha b$ ，任意 $\alpha>0$
- 同样的边界和本质上相同的分类器可以由无限多种参数的组合来表达。而这会造成分歧。
2.6 消除分歧
- 考虑一个 “备选” 的分类边界，我们应该用哪一个参数组合表示它？
- 对于人类来说，这无关紧要
- 而数学 / 机器需要一个精确的答案
-
一种消除分歧的可能做法是：测量到最近点（$i^*$）的距离，缩放参数使得
\[\dfrac{y_{i^*}(\boldsymbol w'\boldsymbol x_{i^*}+b)}{\|\boldsymbol w\|}=\dfrac{1}{\|\boldsymbol w\|}\] - 对于一个给定的 “备选” 边界和固定的训练数据点，存在唯一的缩放 $\boldsymbol w$ 和 $b$ 的方式，使得上面的等式成立。
2.7 约束目标函数
-
SVM 目标是最大化 $\left(\min\limits_{i=1,…,n}\dfrac{y_i(\boldsymbol w’\boldsymbol x_i+b)}{\|\boldsymbol w\|}\right)$
- 引入（任意）额外要求 $\dfrac{y_{i^*}(\boldsymbol w’\boldsymbol x_{i^*}+b)}{\|\boldsymbol w\|}=\dfrac{1}{\|\boldsymbol w\|}$
- $i^*$ 表示距离分类边界最近的样本的索引
- $i^*$ 表示距离分类边界最近的样本的索引
- SVM 目标是找到：
\(\begin{array}{cc}\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w}\|\boldsymbol w\| \\\; \text{s.t.}\quad y_i(\boldsymbol w'\boldsymbol x_i+b)\ge 1 \;\text{for}\;i=1,...,n\end{array}\)
2.8 硬间隔 SVM 的目标函数
-
现在，我们有了一个主要的结果：SVM 目标是找到
\(\begin{array}{cc}\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w}\|\boldsymbol w\| \\\; \text{s.t.}\quad y_i(\boldsymbol w'\boldsymbol x_i+b)\ge 1 \;\text{for}\;i=1,...,n\end{array}\)
- 注意 1：参数 $b$ 是通过影响影响约束条件渐接优化的
- 注意 2：所有的点都被限制在间隔边界上或者外部
- 因此，这个版本的 SVM 被称为硬间隔 SVM
3. SVM 的目标函数作为正则化损失函数
将我们得到的目标函数与其他机器学习方法的目标函数联系起来
3.1 在之前课程中
- 选择 / 设计模型
- 选择 / 设计损失函数
- 寻找可以在训练数据上将差异最小化的参数值
- 损失函数 度量了单个样本的预测值与真实值之间的差异
- 训练误差 是在全部训练样本上的平均损失
对于感知器和 ANN，我们定义了损失函数，目标是在训练中最小化损失 但是，SVM 应当怎样匹配这种模式呢？
3.2 SVM 作为正则化的 ERM
- 回忆岭回归的目标函数：
最小化 $\left(\sum_{i=1}^{n}(y_i-\boldsymbol w’\boldsymbol x_i)^2+\lambda\|\boldsymbol w\|^2\right)$
- 硬间隔 SVM 的目标函数：
\(\begin{array}{cc}\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w}\|\boldsymbol w\| \\\; \text{s.t.}\quad y_i(\boldsymbol w'\boldsymbol x_i+b)\ge 1 \;\text{for}\;i=1,...,n\end{array}\)
- 约束条件可以理解为损失：
$l_{\infty} =\begin{cases}0\quad\;\, 1-y_i(\boldsymbol w’\boldsymbol x_i+b)\le0 \\
\infty\quad 1-y_i(\boldsymbol w’\boldsymbol x_i+b)>0\end{cases}$
3.3 硬间隔 SVM 的损失函数
- 约束条件可以理解为损失：
\(l_{\infty} =\begin{cases}0\quad\;\, 1-y_i(\boldsymbol w'\boldsymbol x_i+b)\le0 \\ \infty\quad 1-y_i(\boldsymbol w'\boldsymbol x_i+b)>0\end{cases}\) - 换而言之，对于每个数据点：
- 如果它在分类边界的正确的一侧，并且到分类边界的距离至少有 $\dfrac{1}{\|\boldsymbol w\|}$，那么我们接受它，损失为 $0$。
- 如果该点在错误的一侧，或者距离分类边界太近，那么我们立即给予其无穷大的损失，因此完全禁止这类解。
总结
- 支持向量机（SVM）作为最大间隔分类器
- 硬间隔 SVM 的目标函数推导
- SVM 作为正则化的 ERM
下节内容：软间隔 SVM
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 欢迎转载，并请注明来自：YEY 的博客 同时保持文章内容的完整和以上声明信息！