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

支持向量机通俗导论（理解SVM的三层境界）第一层、了解SVM支持向量机，因其英文名为supportvectormachine，故一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。1.1、分类标准的起源：Logistic回归理解SVM，咱们必须先弄清楚一个概念：线性分类器。给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点，用y表示类别（y可以取1或者-1，分别代表两个不同的类），一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面（hyperplane），这个超平面的方程可以表示为（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，看了上面的定义之后，问道：请教一下SVMfunctionalmargin为=y(wTx+b)=yf(x)中的Y是只取1和-1吗？y的唯一作用就是确保functionalmargin的非负性？真是这样的么？当然不是，详情请见本文评论下第43楼）当然，有些时候，或者说大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在(不过关于如何处理这样的问题我们后面会讲)，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。换言之，在进行分类的时候，遇到一个新的数据点x，将x代入f(x)中，如果f(x)小于0则将x的类别赋为-1，如果f(x)大于0则将x的类别赋为1。接下来的问题是，如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。1.3、函数间隔Functionalmargin与几何间隔Geometricalmargin在超平面w*x+b=0确定的情况下，|w*x+b|能够表示点x到距离超平面的远近，而通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functionalmargin）的概念。定义函数间隔（用表示）为：而超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值（其中，x是特征，y是结果标签，i表示第i个样本），便为超平面(w,b)关于训练数据集T的函数间隔：=mini(i=1，...n)但这样定义的函数间隔有问题，即如果成比例的改变w和b（如将它们改成2w和2b），则函数间隔的值f(x)却变成了原来的2倍（虽然此时超平面没有改变），所以只有函数间隔还远远不够。事实上，我们可以对法向量w加些约束条件，从而引出真正定义点到超平面的距离--几何间隔（geometricalmargin）的概念。假定对于一个点x，令其垂直投影到超平面上的对应点为x0，w是垂直于超平面的一个向量，为样本x到分类间隔的距离，如下图所示：有，其中||w||表示的是范数。又由于x0是超平面上的点，满足f(x0)=0，代入超平面的方程即可算出：（有的书上会写成把||w||分开相除的形式，如本文参考文献及推荐阅读条目11，其中，||w||为w的二阶泛数）为了得到的绝对值，令乘上对应的类别y，即可得出几何间隔（用表示）的定义：从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以||w||，而且函数间隔y*(wx+b)=y*f(x)实际上就是|f(x)|，只是人为定义的一个间隔度量，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。1.4、最大间隔分类器MaximumMarginClassifier的定义对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。这个间隔如下图中的gap/2所示。通过由前面的分析可知：函数间隔不适合用来最大化间隔值，因为在超平面固定以后，可以等比例地缩放w的长度和b的值，这样可以使得的值任意大，亦即函数间隔可以在超平面保持不变的情况下被取得任意大。但几何间隔因为除上了，使得在缩放w和b的时候几何间隔的值是不会改变的，它只随着超平面的变动而变动，因此，这是更加合适的一个间隔。所以，这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。于是最大间隔分类器（maximummarginclassifier）的目标函数可以定义为：同时需满足一些条件，根据间隔的定义，有其中，s.t.，即subjectto的意思，它导出的是约束条件。回顾下几何间隔的定义可知：如果令函数间隔等于1（之所以令等于1，是为了方便推导和优化，且这样做对目标函数的优化没有影响，至于为什么，请见本文评论下第42楼回复），则有=1/||w||且，从而上述目标函数转化成了这个目标函数便是在相应的约束条件下，最大化这个1/||w||值，而1/||w||便是几何间隔。如下图所示，中间的实线便是寻找到的最优超平面（OptimalHyperPlane），其到两条虚线的距离相等，这个距离便是几何间隔，两条虚线之间的距离等于2，而虚线上的点则是支持向量。由于这些支持向量刚好在边界上，所以它们满足（还记得我们把functionalmargin定为1了吗？上节中：处于方便推导和优化的目的，我们可以令=1），而对于所有不是支持向量的点，则显然有。OK，到此为止，算是了解到了SVM的第一层，对于那些只关心怎么用SVM的朋友便已足够，不必再更进一层深究其更深的原理。第二层、深入SVM2.1、从线性可分到线性不可分2.1.1、从原始问题到对偶问题的求解接着考虑之前得到的目标函数：由于求的最大值相当于求的最小值，所以上述目标函数等价于（w由分母变成分子，从而也有原来的max问题变为min问题，很明显，两者问题等价）：因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。这个问题可以用现成的QP(QuadraticProgramming)优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（LagrangeDuality）变换到对偶变量(dualvariable)的优化问题，即通过求解与原问题等价的对偶问题（dualproblem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。那什么是拉格朗日对偶性呢？简单来讲，通过给每一个约束条件加上一个拉格朗日乘子（Lagrangemultiplier），定义拉格朗日函数（通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出我们的问题）：然后令容易验证，当某个约束条件不满足时，例如，那么显然有（只要令即可）。而当所有约束条件都满足时，则最优值为，亦即最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化，实际上等价于直接最小化（当然，这里也有约束条件，就是≥0,i=1,…,n），因为如果约束条件没有得到满足，会等于无穷大，自然不会是我们所要求的最小值。具体写出来，目标函数变成了：这里用表示这个问题的最优值，且和最初的问题是等价的。如果直接求解，那么一上来便得面对w和b两个参数，而又是不等式约束，这个求解过程不好做。不妨把最小和最大的位置交换一下，变成：交换以后的新问题是原始问题的对偶问题，这个新问题的最优值用来表示。而且有≤，在满足某些条件的情况下，这两者相等，这个时候就可以通过求解对偶问题来间接地求解原始问题。换言之，之所以从minmax的原始问题，转化为maxmin的对偶问题，一者因为是的近似解，二者，转化为对偶问题后，更容易求解。下面可以先求L对w、b的极小，再求L对的极大。2.1.2、KKT条件上文中提到“≤在满足某些条件的情况下，两者等价”，这所谓的“满足某些条件”就是要满足KKT条件。一般地，一个最优化数学模型能够表示成下列标准形式：其中，f(x)是需要最小化的函数，h(x)是等式约束，g(x)是不等式约束，p和q分别为等式约束和不等式约束的数量。同时，得明白以下两点：凸优化的概念：为一凸集，为一凸函数。凸优化就是要找出一点，使得每一满足。KKT条件的意义：它是一个非线性规划（NonlinearProgramming）问题能有最优化解法的必要和充分条件。而KKT条件就是指上面最优化数学模型的标准形式中的最小点x*必须满足下面的条件：经过论证，我们这里的问题是满足KKT条件的（首先已经满足Slatercondition，再者f和gi也都是可微的，即L对w和b都可导），因此现在我们便转化为求解第二个问题。也就是说，原始问题通过满足KKT条件，已经转化成了对偶问题。而求解这个对偶学习问题，分为3个步骤：首先要让L(w，b，a)关于w和b最小化，然后求对的极大，最后利用SMO算法求解对偶问题中的拉格朗日乘子。2.1.3、对偶问题求解的3个步骤（1）、首先固定，要让L关于w和b最小化，我们分别对w，b求偏导数，即令∂L/∂w和∂L/∂b等于零（对w求导结果的解释请看本文评论下第45楼回复）：将以上结果代入之前的L：得到：提醒：有读者可能会问上述推导过程如何而来？说实话，其具体推导过程是比较复杂的，如下图所示：最后，得到：如jerrylead所说：“倒数第4步”推导到“倒数第3步”使用了线性代数的转置运算，由