支持向量机通俗导论（理解SVM的三层境界）(1)

àì夳堔傛蜴生んèń 2022-07-16 15:07 114阅读 0赞

## 第一层、了解SVM ##

支持向量机，因其英文名为support vector machine，故一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

### 1.1、分类标准的起源：Logistic回归 ###

理解SVM，咱们必须先弄清楚一个概念：线性分类器。

给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点，用y表示类别（y可以取1或者-1，分别代表两个不同的类），一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面（hyper plane），这个超平面的方程可以表示为（ wT中的T代表转置）：

![20131107201104906][]

可能有读者对类别取1或-1有疑问，事实上，这个1或-1的分类标准起源于logistic回归。

Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。

假设函数

![1365174192_8325.png][]

其中x是n维特征向量，函数g就是logistic函数。

而 ![1365174223_1807.png][]的图像是

![1365174236_6175.png][]

可以看到，将无穷映射到了(0,1)。

而假设函数就是特征属于y=1的概率。

![1365174921_9452.png][]

从而，当我们要判别一个新来的特征属于哪个类时，只需求![1365175136_8232.png][]即可，若![1365175136_8232.png][]大于0.5就是y=1的类，反之属于y=0类。

此外，![1365175136_8232.png][]只和![1365175161_1760.png][]有关，![1365175169_2349.png][]>0，那么![1365175178_8905.png][]，而g(z)只是用来映射，真实的类别决定权还是在于![1365175189_9269.png][]。再者，当![1365175205_2324.png][]时，![1365175215_8446.png][]=1，反之![1365175233_9165.png][]=0。如果我们只从![1365175266_3733.png][]出发，希望模型达到的目标就是让训练数据中y=1的特征![1365175288_2654.png][]，而是y=0的特征![1365175299_9597.png][]。Logistic回归就是要学习得到![1365175329_6408.png][]，使得正例的特征远大于0，负例的特征远小于0，而且要在全部训练实例上达到这个目标。

接下来，尝试把logistic回归做个变形。首先，将使用的结果标签y = 0和y = 1替换为y = -1,y = 1，然后将![1365175711_9116.png][]（![1365175723_3132.png][]）中的![20140826150648949][]替换为b，最后将后面的![1365175737_9557.png][]替换为![1365175737_9557.png][]（即![1365175756_2693.png][]）。如此，则有了![1365175767_8636.png][]。也就是说除了y由y=0变为y=-1外，线性分类函数跟logistic回归的形式化表示![1365175792_4997.png][]没区别。

进一步，可以将假设函数![1365175830_5193.png][]中的g(z)做一个简化，将其简单映射到y=-1和y=1上。映射关系如下：

![1365175998_9759.png][]

### 1.2、线性分类的一个例子 ###

下面举个简单的例子，如下图所示，现在有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是 -1 ，另一边所对应的y全是1。

![20140829134124453][]

这个超平面可以用分类函数![20131107201211968][]表示，当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应 y=1 的数据点，f(x)小于0的点对应y=-1的点，如下图所示：

![20140829134548371][]

注：有的资料上定义特征到结果的输出函数![20131120103601656][]，与这里定义的![20131107201211968][]实质是一样的。为什么？因为无论是![20131120103601656][]，还是![20131107201211968][]，不影响最终优化结果。下文你将看到，当我们转化到优化![1351141837_7366.jpg][]的时候，为了求解方便，会把yf(x)令为1，即yf(x)是y(w^x + b)，还是y(w^x – b)，对我们要优化的式子max1/||w||已无影响。

（有一朋友飞狗来自Mare\_Desiderii，看了上面的定义之后，问道：请教一下SVM functional margin 为![20131111154113734][]=y(wTx+b)=yf(x)中的Y是只取1和-1 吗？y的唯一作用就是确保functional margin的非负性？真是这样的么？当然不是，详情请见本文评论下第43楼）

当然，有些时候，或者说大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在(不过关于如何处理这样的问题我们后面会讲)，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。

换言之，在进行分类的时候，遇到一个新的数据点x，将x代入f(x) 中，如果f(x)小于0则将x的类别赋为-1，如果f(x)大于0则将x的类别赋为1。

接下来的问题是，如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。

### 1.3、函数间隔Functional margin与几何间隔Geometrical margin ###

在超平面w\*x+b=0确定的情况下，|w\*x+b|能够表示点x到距离超平面的远近，而通过观察w\*x+b的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用(y\*(w\*x+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。

定义函数间隔（用![20140829135049264][]表示）为：

![20131107201248921][]

而超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值（其中，x是特征，y是结果标签，i表示第i个样本），便为超平面(w, b)关于训练数据集T的函数间隔：

> >      ![20131111154113734][]= min![20131111154113734][]i  (i=1，…n)

但这样定义的函数间隔有问题，即如果成比例的改变w和b（如将它们改成2w和2b），则函数间隔的值f(x)却变成了原来的2倍（虽然此时超平面没有改变），所以只有函数间隔还远远不够。

事实上，我们可以对法向量w加些约束条件，从而引出真正定义点到超平面的距离–几何间隔（geometrical margin）的概念。

假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，![20140829135315499][]为样本x到分类间隔的距离，如下图所示：

###  ###

![geometric_margin.png][]

有![20131107201720515][]，其中||w||表示的是范数。

又由于 x0 是超平面上的点，满足 f(x0)=0 ，代入超平面的方程![20131107201104906][]即可算出：

![20131107201759093][]  
γ

（有的书上会写成把||w|| 分开相除的形式，如本文参考文献及推荐阅读条目11，其中，||w||为w的二阶泛数）

为了得到![20140829135315499][]的绝对值，令![20140829135315499][]乘上对应的类别 y，即可得出几何间隔（用![20140829135609579][]表示）的定义：

![20131107201919484][]

从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以||w||，而且函数间隔y\*(wx+b) = y\*f(x)实际上就是|f(x)|，只是人为定义的一个间隔度量，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。

### 1.4、最大间隔分类器Maximum Margin Classifier的定义 ###

对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。这个间隔如下图中的gap / 2所示。

![20140829135959290][]

通过由前面的分析可知：函数间隔不适合用来最大化间隔值，因为在超平面固定以后，可以等比例地缩放w的长度和b的值，这样可以使得![20131107201211968][]的值任意大，亦即函数间隔![20131111154113734][]可以在超平面保持不变的情况下被取得任意大。但几何间隔因为除上了![20131111154326078][]，使得在缩放w和b的时候几何间隔![20131111154137453][]的值是不会改变的，它只随着超平面的变动而变动，因此，这是更加合适的一个间隔。所以，这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。

于是最大间隔分类器（maximum margin classifier）的目标函数可以定义为：

![20131111160612687][]

同时需满足一些条件，根据间隔的定义，有

![1351141813_4166.jpg][]

其中，s.t.，即subject to的意思，它导出的是约束条件。

回顾下几何间隔的定义![20131107201919484][]可知：如果令函数间隔![20131111154113734][]等于1（之所以令![20131111154113734][]等于1，是为了方便推导和优化，且这样做对目标函数的优化没有影响，至于为什么，请见本文评论下第42楼回复），则有![20131111154137453][] = 1 / ||w||且![20140829140642940][]，从而上述目标函数转化成了

![1351141837_7366.jpg][]

这个目标函数便是在相应的约束条件![20140829140642940][]下，最大化这个1/||w||值，而1/||w||便是几何间隔![20131111154137453][]。

如下图所示，中间的实线便是寻找到的最优超平面（Optimal Hyper Plane），其到两条虚线的距离相等，这个距离便是几何间隔![20131111154137453][]，两条虚线之间的距离等于2![20131111154137453][]，而虚线上的点则是支持向量。由于这些支持向量刚好在边界上，所以它们满足![20131111155244218][]（还记得我们把 functional margin 定为 1 了吗？上节中：处于方便推导和优化的目的，我们可以令![20131111154113734][]=1），而对于所有不是支持向量的点，则显然有![20131111155205109][]。

![20140829141714944][]

OK，到此为止，算是了解到了SVM的第一层，对于那些只关心怎么用SVM的朋友便已足够，不必再更进一层深究其更深的原理。

[20131107201104906]: /images/20220709/49c7b2dab7544586aa15d96294c48099.png
[1365174192_8325.png]: https://img-my.csdn.net/uploads/201304/05/1365174192_8325.png
[1365174223_1807.png]: https://img-my.csdn.net/uploads/201304/05/1365174223_1807.png
[1365174236_6175.png]: https://img-my.csdn.net/uploads/201304/05/1365174236_6175.png
[1365174921_9452.png]: https://img-my.csdn.net/uploads/201304/05/1365174921_9452.png
[1365175136_8232.png]: https://img-my.csdn.net/uploads/201304/05/1365175136_8232.png
[1365175161_1760.png]: https://img-my.csdn.net/uploads/201304/05/1365175161_1760.png
[1365175169_2349.png]: https://img-my.csdn.net/uploads/201304/05/1365175169_2349.png
[1365175178_8905.png]: https://img-my.csdn.net/uploads/201304/05/1365175178_8905.png
[1365175189_9269.png]: https://img-my.csdn.net/uploads/201304/05/1365175189_9269.png
[1365175205_2324.png]: https://img-my.csdn.net/uploads/201304/05/1365175205_2324.png
[1365175215_8446.png]: https://img-my.csdn.net/uploads/201304/05/1365175215_8446.png
[1365175233_9165.png]: https://img-my.csdn.net/uploads/201304/05/1365175233_9165.png
[1365175266_3733.png]: https://img-my.csdn.net/uploads/201304/05/1365175266_3733.png
[1365175288_2654.png]: https://img-my.csdn.net/uploads/201304/05/1365175288_2654.png
[1365175299_9597.png]: https://img-my.csdn.net/uploads/201304/05/1365175299_9597.png
[1365175329_6408.png]: https://img-my.csdn.net/uploads/201304/05/1365175329_6408.png
[1365175711_9116.png]: https://img-my.csdn.net/uploads/201304/05/1365175711_9116.png
[1365175723_3132.png]: https://img-my.csdn.net/uploads/201304/05/1365175723_3132.png
[20140826150648949]: https://img-blog.csdn.net/20140826150648949
[1365175737_9557.png]: https://img-my.csdn.net/uploads/201304/05/1365175737_9557.png
[1365175756_2693.png]: https://img-my.csdn.net/uploads/201304/05/1365175756_2693.png
[1365175767_8636.png]: https://img-my.csdn.net/uploads/201304/05/1365175767_8636.png
[1365175792_4997.png]: https://img-my.csdn.net/uploads/201304/05/1365175792_4997.png
[1365175830_5193.png]: https://img-my.csdn.net/uploads/201304/05/1365175830_5193.png
[1365175998_9759.png]: https://img-my.csdn.net/uploads/201304/05/1365175998_9759.png
[20140829134124453]: /images/20220709/66d9d03644774f299fb349e9685c6677.png
[20131107201211968]: /images/20220709/54c0fe747484473394bdb442db5044f8.png
[20140829134548371]: /images/20220709/6c96ba7112d244ed907be7bca0c90255.png
[20131120103601656]: https://img-blog.csdn.net/20131120103601656
[1351141837_7366.jpg]: https://img-my.csdn.net/uploads/201210/25/1351141837_7366.jpg
[20131111154113734]: /images/20220709/1e669c6d52a646deb957022c8df7d0ed.png
[20140829135049264]: /images/20220709/9d5e3fdf20a04ac98392e6ebfef21dcd.png
[20131107201248921]: /images/20220709/42590666e7684cc9a8b8783cdda87fb9.png
[20140829135315499]: /images/20220709/d0f9eddee1d4435090943878a32f03f0.png
[geometric_margin.png]: /images/20220709/a696cf94373c46db91c4cabd97c59fb5.png
[20131107201720515]: /images/20220709/9c1c99663ecf45cbbc4e7a94660b16ed.png
[20131107201759093]: /images/20220709/857f7fcd874c4ea2b077c01b87263279.png
[20140829135609579]: /images/20220709/09acd4a1347c475d8eb22f61cf8e0592.png
[20131107201919484]: /images/20220709/e66c4ebacdd341c3b835d65648d6918d.png
[20140829135959290]: /images/20220709/0544c3cf442f4ddd9585480d5d5d0809.png
[20131111154326078]: https://img-blog.csdn.net/20131111154326078
[20131111154137453]: /images/20220709/609126ab31954e068170b265d7d4f129.png
[20131111160612687]: /images/20220709/24086d65d5664fdb8252d741b351b267.png
[1351141813_4166.jpg]: https://img-my.csdn.net/uploads/201210/25/1351141813_4166.jpg
[20140829140642940]: /images/20220709/64841e72a2cf4a16a4b8ebff52ef8b88.png
[20131111155244218]: https://img-blog.csdn.net/20131111155244218
[20131111155205109]: /images/20220709/8aa6c09af34e42e08638e4a2ac25f13b.png
[20140829141714944]: /images/20220709/0691cb0d67104e6ab4237458761fb505.png