SVM被许多人认为是有监督学习中最好的算法，去年的这个时候我就在尝试学习。不过，面对长长的公式和拗口的中文翻译最终放弃了。时隔一年，看到Andrew讲解SVM，总算对它有了较为完整的认识，总体思路是这样的：1.介绍间隔的概念并重新定义符号；2.分别介绍functional margins与geometric margins；3.由此引出最大间隔分类器，同时将最优化问题转化为凸函数的优化问题；4.补充了拉格朗日对偶性的知识；5.利用拉格朗日对偶性，推导最大间隔分类器最优化的对偶问题，即SVM的最优化公式，并指明公式中的内积；6.由内积引出核函数的重要性——当特征向量维度极高时利用核函数大大缩短计算时间；7.利用正则化解决线性不可分与异常点的问题；8.介绍SMO算法以高效地解SVM。

最大间隔分类器

1.假设、模型、符号

我们先假设所有数据都是线性可分的（之后会去除这个假设），通过下图直观地感受一下这个分类器。虽然A、B、C三个点被分到了同一类，但我们认为点A的分类是最有把握的，因为它距离分类线最远（即间隔最大）。因此，这个分类器最基础的部分就是如何计算间隔。不过，在介绍间隔之前我们先看一下模型及其符号：可以看到它和逻辑回归的模型很像，不过g(z)由逻辑函数变为了一个分段函数。另外，输出变量由{1,0}变为了{1,-1}，θTx变为了wTx+b，这些改动都是为了最后推导公司可以更加优雅。

2.functional margins

由最大间隔分类器的模型我们知道：wTx+b>0 ==> y=1；wTx+b<0 ==> y=-1；而wTx+b=0则被成为分隔超平面(separating hyperplane)。这样，当每个样本都被正确分类时，functional margins的值将总是大于0，并且这个值越大代表分类的可信度越高。值得注意的是，我们可以对参数w和b同时放大/缩小任意相同的倍数，虽然不会影响分类的结果，但是functional margins的值却会发生变化。如图所示，geometric margins就是数据点到分隔超平面的垂直距离，计算过程这里就忽略了，其中比较关键的一步是：分隔超平面wTx+b=0的法向量就是w，需要自己证明。最终，每个样本的geometric margins公式为：由这个公式首先我们可以得到geometric margins与functional margins的关系：相较于functional margins，即使对w和b同时放大/缩小任意相同的倍数，geometric margins的值也不会改变。这一点很重要，会在之后的公式推导中用到。由于||w||是一个非凸函数，将导致难以求解，因此我们需进行一些转化，首先，由之前的结论“随意同时缩放w和b不会改变geometric margins的大小”，我们可以让functional margins为1原始的最优化目标就变成了最大化1/||w||，也相当于最小化||w||2，因此就转化为了凸优化问题：可以用二次规划的软件求解。

拉格朗日对偶性

这一部分主要是最优化理论的内容，其核心思想是可以通过拉格朗日对偶性将原始最优化问题转化为它的对偶问题（这样做的目的是因为对偶问题可以提升求解的效率），我也只是勉强看懂推导的过程，因此只会简单地罗列公式：

1.原始最优化问题

将原始问题进行适当的变形：和原始最优化问题相比，对偶最优化问题只是颠倒了max和min的顺序，并且我们有：在这个假设下，一定会存在w*、α*、β*使得w*是原始问题的解并且α*、β*是对偶问题的解。此外，还有一些有用的关系会成立，它们被称为：Karush-Kuhn-Tucker (KKT) conditions：其中αi*gi(w)=0被称为KKT dual complementarity condition。它暗示了只有当gi(w)=0时才有可能有αi>0，这是SVM只有很少数support vectors的原因；在之后的SMO算法的收敛验证中也会用到这个条件。

SVM

让我们回到前面讨论的最大间隔分类器：利用拉格朗日对偶性，求解最大间隔分类器最优化问题的对偶问题，就是SVM了，让我们来进行推导：回忆一下KKT dual complementarity condition，只有当gi(w)=0时才可能有αi>0，同时gi(w)=0对应着距离分隔超平面最近的点（回顾推导最大间隔分类器最优化公式的过程），即下图中虚线穿过的三个点：而这三个点就是SVM中的SV：support vector。将（2）与（3）带入（1）中，可得：最终，SVM对应的最优化问题为：求得α后，我们可以通过α得到模型中需要的参数w与b：也可以直接用α求得模型的线性组合结果：那么问题来了，为什么我们要这么“折腾”地用拉格朗日对偶性把原本清晰的最大间隔分类的优化问题转化成SVM的这个样子？其中一个很大原因就是接下来要说的核函数。

Kernels

有时我们希望将低维的向量特征映射到高维以增加分类的准确性，比如添加二次、三次项到模型中：因为算法可以被完全地表达为特征向量内积的形式<x, z>，所以只要将映射后的内积<Φ(x), Φ(z)>替换掉原本的内积即可。给定一个特征映射规则Φ，我们将kernel定义为：当输入空间的维度非常高时（甚至是无限维度），我们可以核函数来大大缩减计算量，比如：由此我们可以看到计算<Φ(x), Φ(z)>需要O(n2)的时长，而直接计算K(x,z)只需要O(n)的时长，当维度极高时，这个优势将极为明显！接下来看几个常用的kernels：特征映射函数Φ甚至可以映射到无限维，比如Gaussian kernel：当然，不是随便写一个函数就能作为核函数，核函数成立的条件是：为了解决上述两个问题，我们将优化问题调整为：注：当ξ>1时，即可允许分类是错误的，然后我们将ξ作为惩罚添加到目标函数中。令人惊喜的是，在添加了L1正则化项之后，只是在对偶问题中对αi的限制中增加了一个αi≤C。需要注意的是：b*的计算需要被改变（详见Platt的paper）现在，就只剩下求解对偶问题了。

SMO算法

首先了解坐标上升算法 Coordinate ascent：其核心思想是一次只在一个维度上使得函数最大化，所以它的循环次数可能会比较多，但是循环内部的计算会比较简单。对于这个问题，我们无法直接使用坐标上升：因此，我们将坐标上升修改为，每次选定两个坐标：判断收敛的方法是，KKT conditions是否满足tolerance参数。（详见Fast Training of Support Vector Machines using Sequential Minimal Optimization）我们可以得到：W是关于α2的一个二次函数。而二次函数求导获得最大值是很简单的，再考虑上边界的限制后，α2的新值为：而α1的最优值可以由α2计算获得。

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：斯坦福CS229机器学习课程笔记五：支持向量机 Support Vector Machines

关键词：