SVM(Support Vector Machin) 支持向量机详解

吴恩达的课程中跟国内的一些教程中分析问题的思路还是有些不同的，吴恩达的课程从简单的LR开始让我们先去理解优化目标，一步步的引导我们去理解SVM，然后揭开他神秘的面纱，便于理解，是很不错的课程。我学习的国内课程是直接重点讲解，讲到SVM核心内容。在这里我总结下自己学习SVM的一些想法（目标函数的优化，对偶问题，smo求解，其他核函数，SVM回归，最大间隔等）方便以后查看。

引言

SVM 一个支持向量机用于构造一个超平面，或再高或无限维空间，其可以用于分类，回归，或其它任务中设定的超平面的。直观地，可以做一个良好的分离。如下图，能将训练样本划分的超平面可能有很多，但是我们从直观上去看，应该去找两类训练样本最中间的那个（粗体直线）因为这条直线划分超平面对训练样本的容忍性最好。例如：可能训练集外的样本比图中的样本更加接近分类边界，这时中间的线将表现得最好，这个划分超平面所产生的分类结果是最鲁棒的，对未知的样本的泛化能力最强。

最大间隔与支持向量

我们现在的任务是求得这个最鲁棒的超平面。

我们首先可以假设超平面的线性方程如下：

其中决定超平面的因子有w和b：向量 w 为法向量，决定了超平面的方向，b 为位移项，决定了超平面与原点之间的距离。空间中的点距离超平面的距离为：

假设超平面可以将样本正确分类，则有：

若 y = 1
若 y = -1

我们现在不仅仅要求所有样本点可以正确分类而且要求泛化能力增强，所有样本尽量去远离超平面去达到更好地分类效果。跟上面粗体直线一样。所以我们要使距离超平面最近的几个样本点使如下假设成立：

则这几个样本到超平面距离和的（被称为间隔）最小值为：

我们就是要把这个间隔最大化。也就是要找到满足

中的约束参数w 和 b，使得γ最大。其中可等价于：

这个就是支持向量机的基本形态。需要注意的是这个间隔貌似之和w向量有关，其实事实上是b通过约束隐式的影响着w的取值，进而对间隔产生影响。

最优化

接下来我们不谈SVM，谈一下优化算法，因为SVM会用到，在此总结下。最优化问题有三种：

无约束条件优化：

该问题很好解，根据 Fermat 定理，直接找到使目标函数得 0 的点即可即 ∇xf(x)=0∇xf(x)=0 ，如果没有解析解的话，可以使用梯度下降或牛顿方法等迭代的手段来使 x 沿负梯度方向逐步逼近极小值点。详见最优化—梯度下降法.

等式约束条件优化：

当目标函数加上等式约束条件后，问题就变成如下形式：

约束条件会将解的范围限定在一个可行域，此时不一定能找到使得为 0 的点，只需找到在可行域内使得最小的值即可，常用的方法即为拉格朗日乘子法，该方法首先引入 Lagrange Multiplier，构建 Lagrangian 如下：

求解方法如下：首先对 Lagrangian 关于 α 与 x 求：

令导数为 0 ，求得 x 、 α 的值后，将 x 带入 f(x) 即为在约束条件 hi(x) 下的可行解。这样做的意义是什么呢? 接下来看一个直观的示例，对于二维情况下的目标函数是 f(x,y)，在平面中画出 f(x,y) 的等高线，如下图的虚线所示，并只给出一个约束等式 h(x,y)=0，如下图的绿线所示，目标函数 f(x,y)与约束 g(x,y) 只有三种情况，相交、相切或者没有交集，没交集肯定不是解,只有相交或者相切可能是解，但相交得到的一定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，这就意味着只有等高线与目标函数的曲线相切的时候，才可能得到可行解

因此给出结论：拉格朗日乘子法取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即

所以只要满足上述等式，且满足之前的约束即可得到解，联立起来，正好得到就是拉格朗日乘子法。这里只是直观展示了一下拉格朗日乘子法的几何推导，并没有给出详细的证明。

不等式条件约束优化：

当约束加上不等式之后，情况变得更加复杂，首先来看一个简单的情况，给定如下不等式约束问题：

对应的 Lagrangian 与图形分别如下所示：

这时的可行解必须落在约束区域 g(x) 之内，下图给出了目标函数的等高线与约束：

由图可见可行解 x 只能在 g(x)<0 或者 g(x)=0 的区域里取得：

当可行解 x 落在 g(x)<0的区域内，此时直接极小化 f(x)即可；
当可行解 x 落在 g(x)=0即边界上，此时等价于等式约束优化问题.

当约束区域包含目标函数原有的的可行解时，此时加上约束可行解扔落在约束区域内部，对应 g(x)<0的情况，这时约束条件不起作用；当约束区域不包含目标函数原有的可行解时，此时加上约束后可行解落在边界 g(x)=0 上。下图分别描述了两种情况，右图表示加上约束可行解会落在约束区域的边界上。

以上两种情况就是说，要么可行解落在约束边界上即得 g(x)=0 ，要么可行解落在约束区域内部，此时约束不起作用，另 λ=0消去约束即可，所以无论哪种情况都会得到：

还有一个问题是 λ 的取值，在等式约束优化中，约束函数与目标函数的梯度只要满足平行即可，而在不等式约束中则不然，若 λ≠0，这便说明可行解 x 是落在约束区域的边界上的，这时可行解应尽量靠近无约束时的解，所以在约束边界上，目标函数的负梯度方向应该远离约束区域朝向无约束时的解，此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同：

上式需要满足的要求是拉格朗日乘子 λ>0，这个问题可以举一个形象的例子，假设你去爬山，目标是山顶，但有一个障碍挡住了通向山顶的路，所以只能沿着障碍爬到尽可能靠近山顶的位置，然后望着山顶叹叹气，这里山顶便是目标函数的可行解，障碍便是约束函数的边界，此时的梯度方向一定是指向山顶的，与障碍的梯度同向，下图描述了这种情况 :

可见对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是 KKT 条件。接下来给出形式化的 KKT 条件首先给出形式化的不等式约束优化问题：

列出 Lagrangian 得到无约束优化问题：

经过之前的分析，便得知加上不等式约束后可行解 xx 需要满足的就是以下的 KKT 条件：

满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多，其实很好理解:

拉格朗日取得可行解的必要条件；
这就是以上分析的一个比较有意思的约束，称作松弛互补条件；
初始的约束条件；
不等式约束的 Lagrange Multiplier 需满足的条件。
主要的KKT条件便是 3 和 4，只要满足这俩个条件便可直接用拉格朗日乘子法， SVM 中的支持向量便是来自于此，需要注意的是 KKT 条件与对偶问题也有很大的联系。

优化内容参考 ooon 。

对偶问题

我们现在开始求解：

来得到划分超平面模型

这个本身是一个凸二次规划问题，可以用现成的优化计算包求解，但我们可以有更高效的方法。根据以上最优化讲述的内容，我们可以对其使用拉格朗日乘子法得到其对偶问题，具体来说，对式的每条约束添加拉格朗日乘子，则该问题的拉格朗日函数可写为：

其中令对和的偏导为零可得

与上式联立可把和消去可以得到对偶问题：

解出α后，求出w和b可以得到模型如下，（经过最优化的讲解到这里），我们可以看出需要解不等式约束，所以需要满足KKT条件，即如下要求：

对于任意的样本，总有或者是，若α=0，则该样本将不会在上面左侧式子的求和中出现，也就不会对f(x)有任何影响；若，则必有，所对应的样本位于最大间隔边界上，是一个支持向量。这里显示出支持向量机的一个重要的性质：训练完成后，大部分的训练样本都不需要保留，最终的模型仅与支持向量有关。

SMO算法：

在求解此二次规划的问题时，我们可以使用高效的SMO算法，当然也不乏其他高效算法。

SMO的基本思路是先固定之外的所有参数，然后求上的极值。由于存在约束，若固定之外的其他变量，则可由其他变量导出，于是SMO每次选择两个变量，并且固定其他参数，这样在参数初始化后。SMO不断执行如下两个步骤直至收敛：

选取一对需更新的变量和
固定和以外的参数，求解下式获取更新后的

内容摘取西瓜书

核函数

在之前的讨论中，我们假设训练样本都是线性可分的，即存在一个划分超平面能将训练样本正确分类，但是在现实任务中，原始空间样本也许不存在一个能正确划分两类样本的超平面，例如：异或问题就不是线性可分的。

对与这样的问题，我们可以把原始数据映射到更高维的特征空间，使得样本在这个特征空间内线性可分，如上图。只要原始数据是有限维，那么就一定存在一个高维特征空间使其线性可分。那么核函数就充当了这个角色，把原始特征升维到高维特征空间，使其线性可分。

核函数定义：通过某非线性变换 φ( x) ，将输入空间映射到高维特征空间。特征空间的维数可能非常高。如果支持向量机的求解只用到内积运算，而在低维输入空间又存在某个函数 K(x, x′) ，它恰好等于在高维空间中这个内积，即K( x, x′) =<φ( x) ⋅φ( x′) > 。那么支持向量机就不用计算复杂的非线性变换，而由这个函数 K(x, x′) 直接得到非线性变换的内积，使大大简化了计算。这样的函数 K(x, x′) 称为核函数。

则升维后模型可表示为：