SVM简介

支持向量机（SVM）是在所有知名数据挖掘算法中最健壮、最准确的方法之一，主要包括支持向量的分类器（SVC）、支持向量回归（SVR）。SVM算法之所以有如此大的影响，是因为该方法有坚实的统计学理论基础。
本文将分三篇，由浅入深分别介绍针对线性问题的硬间隔分类器、近似线性问题的软间隔分类器和针对非线性问题的核方法。

线性可分支持向量机

对于两类线性可分问题，SVC要找到一个最优的决策边界，通过硬间隔最大化，找到一个线性分类器。SVC算法假定距离两类样本长度最大的边界是最优的决策边界，即距离两类样本的（硬）间隔（Margin）最大，最大间隔能保证该超平面具有最好的泛化性能，因此SVM算法也称为最大（硬）间隔分类算法。
所谓硬间隔：即将训练样本完全分开，不容有差。

直观上看，间隔就是两个类之间的空间距离或超平面所确定的分离程度。从几何上讲，间隔对应于数据点到超平面的最短距离。最优超平面到两边的最近的样本点之间的距离就是margin，而位于margin上的样本点，就是支持向量的候选集，这也是支持向量机的由来。
对于线性可分问题，有无穷个超平面作为决策边界，但最优超平面只有一个。我们假定x为最优超平面上margin上的样本，令w为最优超平面的法向量，b表示最优超平面的偏移量，其中法向量指向正例的方向，则相应的最优超平面可以被定义为：
$w^T*x+b=0$wT∗x+b=0
这适用于任意n维空间的超平面的计算。
对应的分类决策函数为：

其中sing为符号函数，表示正例是为1，反例为-1。

函数间隔和几何间隔

一个样本点距离超平面的距离长度可以反映出分类预测的确信程度，如果一个正例样本距离超平面很远，且与法向量方向相同（方向相同则距离为正，反之距离为负），则该样本为正样本的概率就大，反之亦然。因此，我们可以使用$｜w^T*x+b｜$｜wT∗x+b｜来相对地反映样本到超平面的距离。通过符号函数的结果与标签y的符号是否一致，可以表示分类是否正确。
因此，可以使用$y_i*(w^Tx+b)$yi​∗(wTx+b)来表示分类预测的正确性和确信度，这就是函数间隔的概念，即：
定义超平面$(w,b)$(w,b)关于训练数据集T的函数间隔为，超平面$(w,b)$(w,b)关于T中所有样本点$(x_i,y_i)$(xi​,yi​)的函数间隔最小值。

函数间隔可以表示分类预测的正确性和确信度，但是选择分离超平面时，仅有函数间隔还不够。因为只要成比例的改变$w$w和$b$b，例如将它们改为$2w$2w和$2b$2b，超平面并没有改变，但函数间隔却成为原来的2倍。因此，我们对函数间隔再除去$||w||$∣∣w∣∣作为约束。

由此给出几何间隔的定义为：超平面$(w,b)$(w,b)关于训练集T的集合间隔为超平面$(w,b)$(w,b)关于T中所有样本点$(x_i,y_i)$(xi​,yi​)的几何间隔之最小值，即

从定义可知，函数间隔和几何间隔关系如下：

如果$||w||$∣∣w∣∣为1，函数间隔和几何间隔相等。如果超平面参数$w$w和$b$b成比例的改变，函数间隔也按此比例改变，而几何间隔不变。

间隔最大化

考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面。具体的，可以表示为下面的约束最优化问题

我们期望找到最大的几何间隔，约束条件是每个样本点到超平面的几何距离都大于或等于该几何间隔。
考虑到几何间隔和函数间隔的关系，再问题可改写为：

函数间隔的取值并不影响最优化问题的解。因此，不妨令函数间隔为1，将问题等价的转换为最大化$\frac{1}{||w||}$∣∣w∣∣1​，进而等同于最小化$||w||$∣∣w∣∣，而为了数学上的计算，我们等价的将问题转化为最小化$\frac{1}{2}||w||^2$21​∣∣w∣∣2，于是就得到下面的线性可分支持向量机学习的最优化问题：

这是一个凸二次规划问题。

凸二次规划

• 凸集
  一个点集（或区域），如果连接其中任意两点$x_1、x_2$x1​、x2​的线段全都包含在该集合内，就称该点集为凸集，否则为非凸集。
  

• 凸函数
  如果一个函数满足：

  • 它的定义域dom(f)是$R^n$Rn上的凸集，并且
  • 对于所有的$x_1, x_2 ∈dom(f) 且 a∈(0,1)$x1​,x2​∈dom(f)且a∈(0,1)，都有
    $f(ax_1+(1-a)x_2) ⩽ af(x_1) + (1-a)f(x_2)$f(ax1​+(1−a)x2​)⩽af(x1​)+(1−a)f(x2​)
    那么函数f为凸函数。
    注意这里的凸函数定义和高数中的凸函数定义是相反的。
    这样的函数，通过求导后，总能找到一个全局最小值，也就是有条件极值问题，使用拉格朗日乘数法。

利用拉格朗日乘数法求解我们的线性分类器的约束优化问题：

其中$a_i$ai​是对应第i个不等式的拉格朗日乘数。
对w和b求偏导并使之为零，就得到最优化条件：

然后可以得出：

带入上面的拉格朗日函数，得等式：

其中，
这里只有距离最优超平面最近的那些支持向量对应的$a_i$ai​非零，其他的$a_i$ai​都等于零。
在确定最优拉格朗日乘子$a_i^*$ai∗​后，我们可以计算拉格朗日函数中的最优权重向量$w^*$w∗：

然后，用一个正的支持向量$x_i$xi​，可以计算出最优偏置$b^*$b∗：

至此，我们的线性分类器的目标优化函数就推导出来了。但是，现实中严格线性可分的情况比较少，这也就意味着这种硬间隔分类器适用性不高，下一篇，我们就将深入了解近似线性可分情况下的软间隔分类器。

记得关注我的微信公众号