• 6.3 从原始优化问题到对偶问题

    6.3 从原始优化问题到对偶问题

    对于上述得到的目标函数,求1/||w||的最大值相当于求||w||^2的最小值,因此很容易将原来的目标函数转化为:

    10.png

    即变为了一个带约束的凸二次规划问题,按书上所说可以使用现成的优化计算包(QP优化包)求解,但由于SVM的特殊性,一般我们将原问题变换为它的对偶问题,接着再对其对偶问题进行求解。为什么通过对偶问题进行求解,有下面两个原因:

    1. * 一是因为使用对偶问题更容易求解;
    2. * 二是因为通过对偶问题求解出现了向量内积的形式,从而能更加自然地引出核函数。

    对偶问题,顾名思义,可以理解成优化等价的问题,更一般地,是将一个原始目标函数的最小化转化为它的对偶函数最大化的问题。对于当前的优化问题,首先我们写出它的朗格朗日函数:

    11.png

    上式很容易验证:当其中有一个约束条件不满足时,L的最大值为 ∞(只需令其对应的α为 ∞即可);当所有约束条件都满足时,L的最大值为1/2||w||^2(此时令所有的α为0),因此实际上原问题等价于:

    12.png

    由于这个的求解问题不好做,因此一般我们将最小和最大的位置交换一下(需满足KKT条件) ,变成原问题的对偶问题:

    13.png

    这样就将原问题的求最小变成了对偶问题求最大(用对偶这个词还是很形象),接下来便可以先求L对w和b的极小,再求L对α的极大。

    (1)首先求L对w和b的极小,分别求L关于w和b的偏导,可以得出:

    14.png

    将上述结果代入L得到:

    15.png

    (2)接着L关于α极大求解α(通过SMO算法求解,此处不做深入)。

    16.png

    (3)最后便可以根据求解出的α,计算出w和b,从而得到分类超平面函数。

    17.png

    在对新的点进行预测时,实际上就是将数据点x*代入分类函数f(x)=w’x+b中,若f(x)>0,则为正类,f(x)<0,则为负类,根据前面推导得出的w与b,分类函数如下所示,此时便出现了上面所提到的内积形式。

    18.png

    这里实际上只需计算新样本与支持向量的内积,因为对于非支持向量的数据点,其对应的拉格朗日乘子一定为0,根据最优化理论(K-T条件),对于不等式约束y(w’x+b)-1≥0,满足:

    19.png