【数之道25】机器学习必经之路-SVM支持向量机的数学精华

【数之道】SVM第二节：求解SVM决策超平面

在决策超平面上随机选择两个点xo和xp,满足等式5和6。等式5-等式6得到等式7，等式7的含义可以被认为是向量w和向量(xo-xp)（即向量xpo）的乘积为0,即向量w与决策超平面垂直。

回到间隔边界上，展开等式4，||xm-xn||*cosθ就是我们要求的间隔距离L。最后可以得到L的表达式：L=2/||w||

于是间隔距离最大化问题又转换为向量w长度的最小化问题。

现在来看约束条件：

当数据点处于决策超平面上方时，yi=1,wxi+b≥1；当数据点处于决策超平面下方时，yi=-1,wxi+b≤-1。所以约束条件可以总结为：yi*(wxi+b)≥1（*）。

所以，优化问题可以描述为：

为了去除根号，同时优化后续计算，将目标表达式平方后除以2。

因此，最终的优化问题可以描述为：

如果约束条件是等式，可以直接使用拉格朗日乘子法求解；如果约束条件是不等式，则要增加一个非负项。如本例中，在右边添加pi^2，将不等式约束转换为等式约束，这之后再使用拉格朗日乘子法，得到拉格朗日方程式：

为求该拉格朗日方程式的极值，分别对w,b,λi和pi求偏导，使求导结果为0，得到下图中的四个等式：

将等式4左右两边再乘以一个pi，将等式3代入到等式4中得到新的等式4：

根据约束条件，新等式4的括号内非负，则新等式4若要成立，只有两种可能：

①括号内式子大于0，λi=0；

②括号内式子等于0，λi可以≠0。

拉格朗日乘子λi可以被视为违背约束条件（*）的惩罚系数。违背约束条件（yi*(wxi+b)≥1）时，yi*(wxi+b)-1＜0。

由于我们的目标是最小化||w||，所以λi应该取正值，这样越是违背约束条件，λi(yi*(wxi+b)-1-pi^2)的值越接近负无穷,L值越大，和优化目标相违背。

也可以借助可视化来帮助理解为什么λi是≥0的：

最后得到下列五个条件，即之前提到的KKT条件（非常重要）：

基于KKT条件，就可以求解最终的决策超平面了。但在SVM模型中，为了求解的效率和更方便的应用核技巧Kernel Trick，我们往往会将原问题转换为其自身的对偶问题再求解。

如上图黄色部分所示，因为新目标函数通过设置惩罚因子，容许一部分违背约束条件的解的存在，所以求解该函数得到的最优解实际上比完全不容许违背约束条件的原方程组的最优解更小。

根据之前的KKT条件，λi≥0、gi(w*,b*)≥0，

所以f(w*)减去一个非负数一定小于等于其自身。同时由于f(w*)是原问题的最优解的值，有：

现在要找一个最优的λi*，使得q(λi*)与f(w*)尽可能接近。寻找最优的λi*等同于求解下面这个最优化问题，也是SVM原问题的对偶问题：

q(λi*)<f(w*)时叫“弱对偶”，q(λi*)=f(w*)时叫“强对偶”。当强对偶成立时，我们就可以通过求解对偶问题，得到原问题的解。

满足slater条件时，强对偶成立。并且可以证明，当q(λi*)=f(w*)时，对偶问题和原问题同时得到最优解：

可视化解释对偶性：

改变λ的大小，可以清楚地看到拉格朗日方程（x^2-λ(x-1)）的变化，也能看到其最小值(-λ^2/4+λ)的变化趋势：

把不同λ取值下的拉格朗日方程的最小值轨迹(-λ^2/4+λ)画出来，就得到了下图中的黄色曲线：

这个最小值轨迹落在原问题极值下方，说明q(λ)是原问题的下界。为了找到最优的下界，对q(λ)求最大值，得到当λ=2，x=1时，取到最大值1。这个极值解对应的极值与原问题f(x)的求得的极值相等，所以强对偶成立，所以我们可以通过求解原问题的对偶问题来求解原问题。

回到之前的SVM对偶问题的求解：

先对最小化部分求解。可以直接代入之前的KKT条件结果，得到更简洁的目标函数：

因为对于决策超平面上下的数据点，yi*(wxi+b)-1要么大于0要么小于0，而与λi的乘积为0，所以这些数据点对应的λi都为0，0乘任何数都为0，所以这些数据点的取值对w的取值毫无影响，所以只有间隔边界上的“支持向量”才参与w的取值的计算。

之所以我们绕了这样一大圈去求对偶问题，除了对偶问题从目标函数表达式和约束条件上更简洁以外，更主要的原因是因为对偶问题有一个非常好的特征，也就是最优解仅根据支持向量的点积结果所决定，也可以理解为仅由支持向量的空间相似度所决定。而这就为我们下一期的Kernel Trick铺平了道路。

既然我们只需要得到空间相似度结果，而这直接就可以通过核函数求得，那为什么还需要绕一圈去寻找维度转化函数了呢？这个问题将在下期进一步讨论。