公众号关注 “ML_NLP”

设为 “星标”，重磅干货，第一时间送达！

转载自 | PaperWeekly

©PaperWeekly 原创 · 作者｜王东伟

单位｜Cubiz

研究方向｜深度学习

本文介绍支持向量机（Support Vector Machine，SVM）。

在上一篇文章关于逻辑回归的叙述中，我们提到了决策边界（decision boundary），它实际上是分割 n 维数据点的一个超平面（hyperplane），比如 n=2 时决策边界为直线，n=3 为平面，n=4 为三维“平面”（有三个维度的超平面）。一般来说，n 维空间的超平面有 n-1 个维度，并且可以把空间分割为两个部分。

严格上，“分割空间”是仿射空间超平面的性质，其他空间类型则未必，更多的细节请参阅 Hyperplane. Wikipedia。

SVM 算法的目标，是找到一个超平面分割不同类别的数据点，并且使得数据点与超平面的最小距离最大。听起来有些拗口，接下来我们以一个简单的例子说明，如图 1 所示，“x”表示正类样本，“o”表示负类样本。

显然，图 1.2 所示的决策边界具有更大的“间隔”（margin），通常具有更稳定的分类性能。粗略地说，大间隔分类器对于未知样本的分类准确率具有更大的均值和更小的方差，比如对于图 1.1 的决策边界，未知的正类样本很大概率会“越过”边界而被错误分类，而图 1.2 的决策边界则给了未知样本“更大的容错空间”。

关于如何得到最大间隔的决策边界，本文后半部分有较严格的数学推导，不过现在先以“提出假设、设定误差函数、求极值点”的思路来理解 SVM 的原理。

对于上述二分类问题，SVM 算法的步骤如下：

假设：
误差函数：
求极值点：

其中 C 为常数，暂时无需理会。注意到，SVM 直接给出样本的分类 y = 1 或者 y = -1，而逻辑回归是给出 y = 1 的概率。其中：

等价于：

这也正是我们使用 {1, -1} 表示正负类的原因，可以让有更简洁的表达。

支持向量机的几何意义

接下来，我们将从几何的角度理解支持向量机。

▲ 图2

如图 2，是分割正负类样本的直线。A 点为正类样本（即），坐标为，AB 为垂线段，为 A 到直线的距离。不难证明向量垂直于直线。由于，并且（因为为单位向量），得到点 B 的坐标：

点 B 位于直线上，即：

整理得到：

同理，对于负类样本可以得到：

进一步得到：

需要指出的是，以上推导基于样本是线性可分的情况（即存在一条线性边界可以完美区分两类数据点），其他情况稍后探讨。

回到误差函数。我们把它分成两部分：

观察表达式，对于正类样本，如果我们希望，只需满足，即；对于负类样本同样可以得到时，。

注意到，对于任意一条以 100% 正确率分割正负类样本的直线，等比缩放和仍然得到同一条直线，意味着我们可以任意调节，使得对于任意样本都有，即。因此，如果我们暂时忽略，仅仅让取得极小值，我们可以得到无数条符合条件的决策边界。

▲ 图3

图 3 显示了其中三条满足取极小值的决策边界。

现在同时让取得极小值。注意到，即我们需要保持的同时，让尽可能小。因为表示数据点到直线的距离，事实上我们只需关注距离直线最近的点，令，则优化目标为（再次强调，仅对于线性可分的情况）：

我们来看几个直观的例子：

显然，图 4.3 的值最大，意味着在保证的条件下，可以取得极小值，也就是误差函数取得极小值，于是，最小化误差函数将使我们得到一个最大间隔的决策边界。事实上，取得极小值将使得，并且图 4.3 虚线上的点都满足，这些点我们称之为“支持向量”（support vectors）！

异常值处理

我们现在对已经有了更多的了解，的目的是尽可能区分正负类样本，并且一旦能完全正确地分割样本它就“满足”了，因此对于线性可分的数据样本，通常它将得到无数条决策边界。同时优化，我们将从得到的“候选边界”中选择一条“最佳边界”（最大间距的决策边界）。但是，假如对所有“候选边界”都不满意怎么办？

考虑图 5 的样本分布，如果我们再次忽略，仅让取得极小值，得到的“候选边界”将位于一个狭窄的区域，图 5 显示了其中一条。

▲ 图5

图 5 中的 H 点为异常值（outlier）。显然，我们希望决策边界可以尽可能抵御异常值的干扰，回到最优的位置。事实上，的加入将有效处理异常值问题，我们看它是怎么做到的。

假设 H 点为样本，表示为：

图 6.1 的决策边界将使，即取极小值，但是由于最小距离非常小，最小化整体误差将使得很大，即增大；反之，图 6.2 的决策边界则使得减小，从而减小，与此同时，增大将使得增大。因此，同时优化将得到一条介于两者之间的决策边界。一种具体的情况是，如果样本很多，那么对的影响很小，异常值将几乎被忽略，这正是我们希望的结果。

上述对异常值处理的“效果”，我们通常称之为“正则化”（regularization），它可以避免模型“过拟合”（overfitting），相对的概念还有“欠拟合”（underfitting），后续文章将继续探讨。

现在我们可以说明常数 C 的作用，让我们再看一眼完整的误差函数：

假设 C 取一个很大的值，比如 1000000，则后半部分产生的影响将很小（或者说 ) 的影响很大），于是也就无法起到正则化的作用，会导致过拟合；反之 C 取值很小，则容易欠拟合。

此外，带有正则化项（即）的，我们通常称之为目标函数（objective function）而不是误差函数（loss function），并且更通用的符号表示是，不过本文暂时采用误差函数的表达。

非线性SVM

考虑以下正负类样本，如何找到决策边界？

▲ 图7

我们目前所了解的 SVM 只能拟合线性边界，非线性边界需要对模型做一些“改装”。

具体操作非常简单。假设样本特征数量为 n，数据样本数量为 m，对于任意特定的数据样本，可以得到与所有数据样本的“相似度”（similarity）：

也就是说，对于每一个样本（n 维），我们都可以得到相应的（m 维）。

即为核函数（kernel function），通常我们采用高斯核（Gaussian kernel）：

对于不采用核函数的 SVM，我们通常说它用了线性核（linear kernel）。

通过将替换为，我们可以得到核函数版本的 SVM 模型和误差函数：

关于极值点求解及核函数

为了说明极值点求解及核函数的原理，我们需要做一些看起来有些吓人的数学推导，由于篇幅有限，我将对一些关键的数学原理做简要说明，更详细的推导可参考斯坦福 CS 课程的资料 CS229 Lecture Notes. Andrew Ng. Spring Stanford University. 2020。

之前我们得到了一个优化问题：

其中：

容易得到，上述优化问题等价于：

注意到，我们还没有考虑正则化，比如图 6.2 所示的边界是不被允许的，因为 H 点不满足的约束条件（而）。

因此，考虑到正则化和非线性可分的情况，我们将优化问题调整为：

现在你可以验证，假设 H 点对应，对于合适的，图 6.2 所示的边界将被允许，但是 H 点将带来（类比）的误差值提升作为“惩罚”。事实上，上述优化问题等价于优化 SVM 的误差函数。

以上为带约束的优化问题（constrained optimization problems）。其中一个解决思路是，找到优化问题 D，使得由 D 得到的解，可以得到原问题 P 的解。P 和 D 分别称为 primal problem 和 dual problem（以下翻译为原始问题和对偶问题）。关于 Duality 的严格定义，请参考 Duality(optimization). Wikipedia。

通常我们使用拉格朗日对偶（Lagrange duality）来求解。

对于一般化的带约束的优化问题，

求解步骤如下：

找到该优化问题的替代问题（跟有相同的解）；
得到对偶问题；
求解得到的解。

定义拉格朗日函数如下：

考虑以下函数：

给定一个值，如果满足约束，可以得到：

如果不满足约束，可以得到（读者可自行验证）。

即：

因此我们得到以下优化问题：

容易验证与有相同的解。

进一步，得到对偶问题：

注意到，对偶问题的约束仅有，且，因此更容易求解。

可以证明：

以下用一个简单的例子说明上述不等式。假如在上处处连续，，。固定，则对于任意，都有，即；固定，则对于任意，都有，即，因此，。在满足一定条件下，，比如马鞍形函数。

现在我们的目标是找到使得，而是否存在涉及两个条件：Slater's condition 和 Karush–Kuhn–Tucker conditions（以下简称斯莱特条件和 KTT 条件）。

斯莱特条件。对于以下优化问题：

当和为凸函数（convex），并且存在使得：

则其满足强对偶性（strong duality）。

满足强对偶性的优化问题，其原始问题和对偶问题的最优解对应的目标函数值相等，即。

对于如所示形式的优化问题，KTT 条件如下：

对于所示形式的优化问题，如果其满足强对偶性（比如满足斯莱特条件），以及相应的拉格朗日函数关于为严格凸函数，那么可以证明：

(1) 如果存在是对偶问题的解，则是原始问题的解；

(2) 和分别为原始问题和对偶问题的解满足 KTT 条件。

结论（1）告诉我们，可以通过求解对偶问题得到原始问题的解。结论（2）则提供了极值点的判断依据。注意到 KKT 条件（2），它意味着当时，，这将让 SVM 的优化结果得到少数的“支持向量”，下文将进一步说明。

我们可以对结论（1）作简单证明。

对于满足强对偶性的问题，令和分别为原始问题和对偶问题的解，可以得到：

即：

也就是说，是的极小值点，如果是严格凸函数，则极小值点是唯一的。

以上，容易得到结论（1）。

现在，回到 SVM 的优化问题：

把上述约束条件转化为的形式，注意到该优化问题有 2m 个的约束，并且没有的约束，我们可以得到拉格朗日函数：

于是，得到对偶问题：

对于，我们需要固定，令偏导数为零：

由以上方程可以得到关于的表达式，代入，可以得到对偶问题的最终表达式：

其中，表示内积。求解上述问题可以采用基于梯度的迭代算法，并用 KTT 条件判断目标函数值是否收敛。SMO 是目前比较流行且高效的 SVM 优化算法，详情请参阅 SMO 的论文 Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. John C. Platt. Microsoft Research. 1998。

现在，假设我们得到了对偶问题的极值点，在推导对偶问题表达式的过程，注意到：

可以得到决策边界的另一种表达式：

事实上，最终得到的只有一小部分非零，这些非零的对应的就是支持向量。因此，我们的预测模型只需要计算与少数支持向量的内积。

核函数

假如我们需要对样本进行特征组合，得到更高维的样本，比如进行如下特征映射：

注意到前文得到的对偶优化问题和预测模型都可以表示为的函数，我们只需将替换为。一般地，为特征映射，我们定义核函数为：

以特征数量 n=3 为例，考虑以下核函数：

可以看到上述核函数隐性地把 ,映射到高维向量，因此我们无需分别计算，这将减小计算复杂度，比如上述例子从减小为。

一个常用的核函数是：

我们称之为 RBF 核（Radial basis function kernel）或高斯核（Gaussian kernel）。通过泰勒展开可以得到 σ=1 的 RBF：

可以看到 RBF 实际上将 x 映射到无限维空间。

从另一个角度看待核函数。容易发现，RBF 的取值跟的距离成负相关，值域为，当时取最大值，因此 RBF 也可以视为的相似度（similarity）表示。

关于的作用。从相似度的角度理解核函数的作用，可以发现我们实际上通过计算输入与所有训练样本的相似度来确定它的所属分类，最终我们会发现只需用到其中的部分训练样本就可以判断的分类，这是支持向量的另一个理解角度。是高斯函数的标准差，它决定了训练样本的影响范围，比如当很小时，由于影响范围极小，导致我们几乎需要用所有训练样本来确定的分类，因此得到的支持向量的数量会很大。因此，太小的值会导致过拟合，太大会导致欠拟合。

在一些机器学习的工具库中，RBF 通常表示为：