支持向量机(SVM) （2）

在上一次的介绍中，我们稍微了解到了关于support vector machine 的一些入门知识。今天，我们将真正进入支持向量机的算法之中，大体的框架如下：

1、最大间隔分类器

2、线性可分的情况（详细)

3、原始问题到对偶问题的转化

4、序列最小最优化算法

1、最大间隔分类器

函数间隔和几何间隔相差一个∥w∥ 的缩放因子（感觉忘记的可以看一下上一篇文章）。按照前面的分析，对一个数据点进行分类，当它的间隔越大的候，分类正确的把握越大。对于一个包含n 个点的数据集，我们可以很自然地定义它的间隔为所有这n 个点的间隔中最小的那个。于是，为了使得分类的把握尽大，我们希望所选择的超平面能够最大化这个间隔值。

        简而言之：

1. 函数间隔明显是不太适合用来最大化的一个量，因为在超平面固定以后，我们可以等比例地缩放w的长度和b 的值，这样可以使得f(x) = wTx+b 的值任意大，亦即函数间隔^γ 可以在超平面保持不变的情况下被取得任意大。

2. 而几何间隔则没有这个问题，因为除上了这个分母，所以缩放w 和b 的时候的值是不会改变的，它只随着超平面的变动而变动，因此，这是更加合适的一个间隔。

最大间隔分类面的公式为：

通过最大化间隔，我们使得该分类器对数据进行分类时具有了最大的把握。但，这个最大分类间隔器到底是用来干嘛的呢？很简单，支持向量机通过使用最大分类间隔来设计决策最优分类超平面，而为何是最大间隔，却不是最小间隔呢？因为最大间隔能获得最大稳定性与区分的确信度，从而得到良好的推广能力（超平面之间的距离越大，分离器的推广能力越好，也就是预测精度越高，不过对于训练数据的误差不一定是最小的）。

2、原始问题到对偶问题

        回忆一下之前得到的优化目标

max 1/∥w∥

s.t. yi(wTxi + b) ≥ 1, i = 1, 2, · · · , n

由于求1/∥w∥的最大值相当于求1/2*∥w∥^2 的最小值，所以上述问题等价于（w 由分母变成分子，从而也有原来的“最大化”问题变为“最小化”问题，很明显，两者问题等价）

min 1/2*∥w∥^2 

s.t. yi(wTxi + b) ≥ 1, i = 1, 2, · · · , n

到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。这个问题可以用任何现成的QP Quadratic Programming 的优化包进行求解。虽然这个问题确实是一个标准的QP 问题，但是它也有它的特殊结构，通过

Lagrange 对偶变换到对偶变量Dual Variable 的优化问题之后，可以找到一种更加有效的方法来进行求解，而且通常情况下这种方法比直接使用通用的QP 优化包进行优化要高效得多。也就说，除了用解决QP 问题的常规方法之外，还可以应用Lagrange 对偶性，通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易解；二者可以自然的引入核函数，进而推广到非线性分类问题。

接下来，你将看到“对偶变量的优化问题”等类似的关键词频繁出现，便是解决此凸优化问题的第二种更为高效的解——对偶变量的优化求解。至于上述提到，关于什么是Lagrange 对偶性？简单地来说，通过给每一个约束条件加上一个Lagrange 乘子，即引入Lagrange 对偶变量，如此我们便可以通过Lagrange 函数将约束条件融和到目标函数里去（也就是说把条件融合到一个函数里头，现在只用一个函数表达式便能清楚的表达出我们的问题）。

L(w, b,) =1/2*∥w∥^2 −Σαi (yi(wTxi + b) − 1) 

然后我们令θ(w) = maxL(w, b,a)

容易验证，当某个约束条件不满足时，例如yi(wTxi + b) < 1，那么我们显然有θ(w) = +∞（只要令αi = +∞即可）。而当所有约束条件都满足时，则有

θ(w) = 1/2*∥w∥*2，亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化1/2*∥w∥^2，实际上等价于直接最小化θ(w)（当然，这里也有约束条件，就是αi ≥ 0, i = 1, 2, · · · , n，因为如果约束条件没有得到满足，θ(w) 会等于无穷大，自然不会是我们所要求的最小值。具体写出来，我们现在的目标函数变成了.

所谓的“满足某些条件”就是要先满足Slater 条件，进而就满足KKT 条件。理由如下3 点所述（观点来自frestyle）：

1. 在凸优化问题中，d∗ 和p∗ 相同的条件是Slater 条件，该条件保证鞍点        Saddle Point 存在。

2. 至于KKT 条件，首先原问题的最优值可以通过求Lagrange 函数的鞍点（如果有的话）来得到，再者，KKT 条件里面进一步引入了更强的前提，也就是在满足Slater 条件的同时（前面说了，Slater条件保证鞍点存在），f(·) 和gi(·) 都是可微的，这样鞍点不仅存在，而且能通过对Lagrange 函数求导得到，

3. 所以KKT 条件是一个点是最优解的条件，而不是d∗ = p∗ 的条件，当然这个KKT 条件对后边简化对偶问题很关键。

那KKT 条件的表现形式是什么呢？据维基百科：KKT 条件的介绍，一般地，一个最优化数学模型能够表示成下列标准形式

这里的问题是满足KKT 条件的（首先已经满足Slater 条件，再者f(·) 和gi(·) 也都是可微的，即L 对w 和b 都可导），因此现在我们便转化为求解第二个问题。也就是说，现在，咱们的原问题通过满足一定的条件，已经转化成了对偶问题。而求解这个对偶学习问题，分为3 个步骤，首先要让L(w, b,) 关于

w 和b 最小化，然后求对 的极大，最后利用SMO 算法求解对偶因子。

第一步首先固定，要让L 关于w 和b 最小化，我们分别对w 和b 求偏导数=0。

从上面的最后一个式子，我们可以看出，此时的Lagrange 函数只包含了一个变量，那就是αi，然后下文的第2 步，求出αi 了便能求出w 和b，由此可见，上文第1.2 节提出来的核心问题：分类函数f(x) = wTx + b也就可以轻而易举的求出来了。由此看出，使用Lagrange 定理解凸最优化问题可以使用一个对偶变量表示，转换为对偶问题后，通常比原问题更容易处理，因为直接处理不等式约束是困难的，而对偶问题通过引入Lagrange 乘子（又称为对偶变量）来解。

第二步求对 的极大，即是关于对偶变量 的优化问题，从上面的式子得到

如前面所说，这个问题有更加高效的优化算法，即我们常说的SMO 算法。

3、序列最小最优化算法SMO

实际上，关于 的求解过程即是我们常说的SMO 算法，这里简要介绍下。

要解决的是在参数 上求W 的最大值的问题，至于xi 和yi 都是已知数。其中C 是一个参数，用于控制目标函数中两项（“寻找间隔最大的超平面”和“保证数据点偏差量最小”）之间的权重。和上文最后的式子对比一下，可以看到唯一的区别就是现在对偶变量 多了一个上限C，关于C的由来在下一次的博文中会有。

4、线性不可分的情况

OK，为过渡到下节2.2节所介绍的核函数，让我们再来看看上述推导过程中得到的一些有趣的形式。首先就是关于我们的超平面，对于一个数据点x 进行分类，实际上是通过把x 代入到f(x) = wTx + b 算出结果然后根据其正负号来进行类别划分的。而前面的推导中我们得到

，因此分类函数为

这里的形式的有趣之处在于，对于新点x 的预测，只需要计算它与训练数据点的内积即可（⟨·, ·⟩ 表示向量内积），这一点至关重要，是之后使用核函数进行非线性推广的基本前提。此外，所谓“支持向量”也在这里显示出来——事实上，所有非支持向量所对应的系数 都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。

为什么非支持向量对应的 等于零呢？直观上来理解的话，就是这些“后方”的点——正如我们之前分析过的一样，对超平面是没有影响的，由于分类完全有超平面决定，所以这些无关的点并不会参与分类问题的计算，因而也就不会产生任何影响了。

        通过Lagrange 乘数法得到的优化目标：

注意到如果xi 是支持向量的话，(2.1.23)式中红颜色的部分是等于0 的（因为支持向量的函数间隔等于1），而对于非支持向量来说，函数间隔会大于1，因此红颜色部分是大于零的，而αi 又是非负的，为了满足最大化，αi 必须等于0。这也就是这些非支持向量的点的局限性。从上述所有这些东西，便得到了一个最大间隔分类器，这就是一个简单的支持向量机。当然，到目前为止，我们的支持向量机还比较弱，只能处理线性可分的情况，不过，在得到了目标函数的对偶形式之后，通过核函数推广到非线性可分的情况就变成了一件非常容易的事情。