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

前言

---

动笔写这个支持向量机(support vector machine)是费了不少劲和困难的，原因很简单，一者这个东西本身就并不好懂，要深入学习和研究下去需花费不少时间和精力，二者这个东西也不好讲清楚，尽管网上已经有朋友写得不错了(见文末参考链接)，但在描述数学公式的时候还是显得不够。得益于同学白石的数学证明，我还是想尝试写一下，希望本文在兼顾通俗易懂的基础上，真真正正能足以成为一篇完整概括和介绍支持向量机的导论性的文章。

    本文在写的过程中，参考了不少资料，包括《支持向量机导论》、《统计学习方法》及网友pluskid的支持向量机系列等等，于此，还是一篇学习笔记，只是加入了自己的理解和总结，有任何不妥之处，还望海涵。全文宏观上整体认识支持向量机的概念和用处，微观上深究部分定理的来龙去脉，证明及原理细节，力保逻辑清晰 & 通俗易懂。

    同时，阅读本文时建议大家尽量使用chrome等浏览器，如此公式才能更好的显示，再者，阅读时可拿张纸和笔出来，把本文所有定理.公式都亲自推导一遍或者直接打印下来（可直接打印网页版或本文文末附的PDF）在文稿上演算，从而享受随时随地思考、演算的极致快感。

    OK，还是那句话，有任何问题，欢迎任何人随时不吝指正 & 赐教，感谢。

第一层、了解SVM

---

   

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

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

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

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

                                                           

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

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

    假设函数

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

    而

的图像是

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

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

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

    此外，只和有关，>0，那么，而g(z)只是用来映射，真实的类别决定权还是在于。再者，当时，=1，反之=0。如果我们只从出发，希望模型达到的目标就是让训练数据中y=1的特征，而是y=0的特征。Logistic回归就是要学习得到，使得正例的特征远大于0，负例的特征远小于0，而且要在全部训练实例上达到这个目标。

    接下来，尝试把logistic回归做个变形。首先，将使用的结果标签y = 0和y = 1替换为y = -1,y = 1，然后将（）中的替换为b，最后将后面的替换为（即）。如此，则有了。也就是说除了y由y=0变为y=-1外，线性分类函数跟logistic回归的形式化表示没区别。

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

1.2、线性分类的一个例子

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

    这个超平面可以用分类函数

表示，当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应 y=1 的数据点，f(x)小于0的点对应y=-1的点，如下图所示：

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

    （有一朋友飞狗来自Mare_Desiderii，看了上面的定义之后，问道：请教一下SVM functional margin 为=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）的概念。

    定义函数间隔（用表示）为：

 

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

     = mini  (i=1，...n)

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

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

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

    根据平面几何知识，有

    其中||w||为w的二阶范数（范数是一个类似于模的表示长度的概念），是单位向量（一个向量除以它的模称之为单位向量）。

    又由于  x0 是超平面上的点，满足  f(x0)=0 ，代入超平面的方程，可得，即。

    随即让此式的两边同时乘以，再根据和，即可算出： 

γ

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

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

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

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

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

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

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

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

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

    相当于在相应的约束条件下，最大化这个1/||w||值，而1/||w||便是几何间隔。   

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

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

第二层、深入SVM

---

2.1、从线性可分到线性不可分

2.1.1、从原始问题到对偶问题的求解

    接着考虑之前得到的目标函数：

     由于求的最大值相当于求的最小值，所以上述目标函数等价于（w由分母变成分子，从而也有原来的max问题变为min问题，很明显，两者问题等价）：

    因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。这个问题可以用现成的QP (Quadratic Programming) 优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。

    此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

     那什么是拉格朗日对偶性呢？简单来讲，通过给每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier），定义拉格朗日函数（通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出我们的问题）：

    然后令

    容易验证，当某个约束条件不满足时，例如，那么显然有（只要令即可）。而当所有约束条件都满足时，则最优值为，亦即最初要最小化的量。

    因此，在要求约束条件得到满足的情况下最小化，实际上等价于直接最小化（当然，这里也有约束条件，就是 ≥0,i=

ix
，按最小二乘法，误差累积为

    求解 使达到最小，正好是算术平均。

    由于算术平均是一个历经考验的方法，而以上的推理说明，算术平均是最小二乘的一个特例，所以从另一个角度说明了最小二乘方法的优良性，使我们对最小二乘法更加有信心。

    最小二乘法发表之后很快得到了大家的认可接受，并迅速的在数据分析实践中被广泛使用。不过历史上又有人把最小二乘法的发明归功于高斯，这又是怎么一回事呢。高斯在1809年也发表了最小二乘法，并且声称自己已经使用这个方法多年。高斯发明了小行星定位的数学方法，并在数据分析中使用最小二乘方法进行计算，准确的预测了谷神星的位置。

    说了这么多，貌似跟本文的主题SVM没啥关系呀，别急，请让我继续阐述。本质上说，最小二乘法即是一种参数估计方法，说到参数估计，咱们得从一元线性模型说起。

3.4.2、最小二乘法的解法

    什么是一元线性模型呢？ 请允许我引用这里的内容，先来梳理下几个基本概念：

• 监督学习中，如果预测的变量是离散的，我们称其为分类（如决策树，支持向量机等），如果预测的变量是连续的，我们称其为回归。

• 回归分析中，如果只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。

• 如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。

• 对于二维空间线性是一条直线；对于三维空间线性是一个平面，对于多维空间线性是一个超平面...   

    对于一元线性回归模型, 假设从总体中获取了n组观察值（X1，Y1），（X2，Y2）， …，（Xn，Yn）。对于平面中的这n个点，可以使用无数条曲线来拟合。要求样本回归函数尽可能好地拟合这组值。综合起来看，这条直线处于样本数据的中心位置最合理。 

    选择最佳拟合曲线的标准可以确定为：使总的拟合误差（即总残差）达到最小。有以下三个标准可以选择：        

1. 用“残差和最小”确定直线位置是一个途径。但很快发现计算“残差和”存在相互抵消的问题。

2. 用“残差绝对值和最小”确定直线位置也是一个途径。但绝对值的计算比较麻烦。

3. 最小二乘法的原则是以“残差平方和最小”确定直线位置。用最小二乘法除了计算比较方便外，得到的估计量还具有优良特性。这种方法对异常值非常敏感。　 

     最常用的是普通最小二乘法（ Ordinary  Least Square，OLS）：所选择的回归模型应该使所有观察值的残差平方和达到最小，即采用平方损失函数。 　

     我们定义样本回归模型为：

    其中ei为样本（Xi, Yi）的误差。

    接着，定义平方损失函数Q：

    则通过Q最小确定这条直线，即确定，以为变量，把它们看作是Q的函数，就变成了一个求极值的问题，可以通过求导数得到。

    求Q对两个待估参数的偏导数：

    根据数学知识我们知道，函数的极值点为偏导为0的点。   

    解得：

        

    这就是最小二乘法的解法，就是求得平方损失函数的极值点。自此，你看到求解最小二乘法与求解SVM问题何等相似，尤其是定义损失函数，而后通过偏导求得极值。

   OK，更多请参看陈希孺院士的《数理统计学简史》的第4章、最小二乘法。

3.5、SMO算法

    在上文中，我们提到了求解对偶问题的序列最小最优化SMO算法，但并未提到其具体解法。首先看下最后悬而未决的问题：

    等价于求解：

    1998年，Microsoft Research的John C. Platt在论文《Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines》中提出针对上述问题的解法：SMO算法，它很快便成为最快的二次规划优化算法，特别是在针对线性SVM和数据稀疏时性能更优。

    接下来，咱们便参考John C. Platt的这篇文章来看看SMO的解法是怎样的。

3.5.1、SMO算法的推导

    咱们首先来定义特征到结果的输出函数：

    注：这个u与我们之前定义的实质是一样的。

    接着，重新定义下咱们原始的优化问题，权当重新回顾，如下：

    求导得到：

    代入中，可得。

    通过引入拉格朗日乘子转换为对偶问题后，得：

   s.t：

且

    注：这里得到的min函数与我们之前的max函数实质也是一样，因为把符号变下，即由min转化为max的问题，且yi也与之前的等价，yj亦如此。

    经过加入松弛变量后，模型修改为：

    从而最终我们的问题变为：

    下面要解决的问题是：在上求上述目标函数的最小值。为了求解这些乘子，每次从中任意抽取两个乘子和，然后固定和以外的其它乘子，使得目标函数只是关于和的函数。这样，不断的从一堆乘子中任意抽取两个求解，不断的迭代求解子问题，最终达到求解原问题的目的。

    而原对偶问题的子问题的目标函数可以表达为：

    其中

    为了解决这个子问题，首要问题便是每次如何选取和。实际上，其中一个乘子是违法KKT条件最严重的，另外一个乘子则由另一个约束条件选取。

    根据KKT条件可以得出目标函数中取值的意义：

    这里的还是拉格朗日乘子：

1. 对于第1种情况，表明是正常分类，在间隔边界内部（我们知道正确分类的点）；

2. 对于第2种情况，表明了是支持向量，在间隔边界上；

3. 对于第3种情况，表明了是在两条间隔边界之间；

    而最优解需要满足KKT条件，即上述3个条件都得满足，以下几种情况出现将会出现不满足：

• <=1但是<C则是不满足的，而原本=C

• >=1但是>0则是不满足的，而原本=0

• =1但是=0或者=C则表明不满足的，而原本应该是0<<C

    也就是说，如果存在不满足KKT条件的，那么需要更新这些，这是第一个约束条件。此外，更新的同时还要受到第二个约束条件的限制，即

。

    因此，如果假设选择的两个乘子和，它们在更新之前分别是、，更新之后分别是、，那么更新前后的值需要满足以下等式才能保证和为0的约束：

    其中，是常数。

    两个因子不好同时求解，所以可先求第二个乘子的解（），得到的解（）之后，再用的解（）表示的解（）。

    为了求解，得先确定的取值范围。假设它的上下边界分别为H和L，那么有：

    接下来，综合和这两个约束条件，求取的取值范围。

    当y1 != y2时，根据可得，所以有，，如下图所示：

    当y1 = y2时，同样根据可得：，所以有，，如下图所示：

    如此，根据y1和y2异号或同号，可得出的上下界分别为：

    回顾下第二个约束条件，令上式两边乘以y1，可得

    其中，。

    因此可以用表示，，从而把子问题的目标函数转换为只含的问题：

    对求导，可得

    化简下：

    然后将、、和代入上式可得：

    令（表示预测值与真实值之差），

，然后上式两边同时除以，得到一个关于单变量的解：

    这个解没有考虑其约束条件，即是未经剪辑时的解。

    然后考虑约束可得到经过剪辑后的的解析解为：

    求出了后，便可以求出，得。

    那么如何选择乘子和呢？

• 对于，即第一个乘子，可以通过刚刚说的那3种不满足KKT的条件来找；

• 而对于第二个乘子可以寻找满足条件 ：的乘子。

    而b在满足下述条件：

    下更新b：

    且每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。

    最后更新所有，y和b，这样模型就出来了，从而即可求出咱们开头提出的分类函数：

    此外，这里也有一篇类似的文章，大家可以参考下。

3.5.2、SMO算法的步骤

    综上，总结下SMO的主要步骤，如下：

    意思是，

1. 第一步选取一对和，选取方法使用启发式方法；

2. 第二步，固定除和之外的其他参数，确定W极值条件下的，由表示。

    假定在某一次迭代中，需要更新，对应的拉格朗日乘子，，那么这个小规模的二次规划问题写为：

    那么在每次迭代中，如何更新乘子呢？引用这里的两张PPT说明下：

    知道了如何更新乘子，那么选取哪些乘子进行更新呢？具体选择方法有以下两个步骤：

1. 步骤1：先“扫描”所有乘子，把第一个违反KKT条件的作为更新对象，令为a1；

2. 步骤2：在所有不违反KKT条件的乘子中，选择使|E1 −E2|最大的a2进行更新，使得能最大限度增大目标函数的值（类似于梯度下降. 此外，而，求出来的E代表函数ui对输入xi的预测值与真实输出类标记yi之差）。

    最后，每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。

    综上，SMO算法的基本思想是将Vapnik在1982年提出的Chunking方法推到极致，SMO算法每次迭代只选出两个分量ai和aj进行调整，其它分量则保持固定不变，在得到解ai和aj之后，再用ai和aj改进其它分量。与通常的分解算法比较，尽管它可能需要更多的迭代次数，但每次迭代的计算量比较小，所以该算法表现出较好的快速收敛性，且不需要存储核矩阵，也没有矩阵运算。