SVM——对偶学习算法

对偶问题

上一篇z,g分别代表一个二元函数和一个一元函数，一般情况下，我们用x代表一个函数的自变量，而这个x本身可以是多维的。而且，同一个函数可能同时既有等式约束条件，又有不等式约束条件。

主问题

考虑在d维空间上有m个等式约束条件和n个不等式约束条件的极小化问题，这样的问题可以写作：

我们把上述问题称为“原始最优化问题”，也可以叫做“原始问题”或“主问题”。

为了解决原始问题，我们引入拉格朗日乘子 $\lambda=(\lambda _1,\lambda _2,...,\lambda _m)^T$λ=(λ1​,λ2​,...,λm​)T和$\mu =(\mu _1,\mu _2,...,\mu _n)^T$μ=(μ1​,μ2​,...,μn​)T，构造拉格朗日函数：

然后，再设：

由上式子得出：

这里的：

我们称为主问题的对偶问题，$\lambda$λ和$\mu$μ称为对偶变量

强对偶及求解对偶问题

设对偶问题的最优解为$d^*$d∗，显然有$d^*&lt;=p^*$d∗<=p∗。
若$d^*==p^*$d∗==p∗，则我们将主问题和对偶问题的关系称为强对偶性，否则称为弱对偶性。显然，强对偶性如果成立，我们就可以通过最优对偶问题来打到优化主问题的目的了。

强对偶性成立

如果主问题是凸优化问题，也就是说当 （1、2、3需要同时成立）：

1. 拉格朗日函数中的$f(x)$f(x)和$g_j(x)$gj​(x)都是凸函数；
2. $h_i(x)$hi​(x)是仿射函数；
3. 主问题可行域中至少有一点是的不等式约束严格成立。即存在x,对所有j，均有$g_j(x)&lt;0$gj​(x)<0
   注意：当主问题和对偶问题存在强对偶性时，存在$x^*, \lambda ^*$x∗,λ∗和$\mu ^*$μ∗，分别为主问题的解和对偶问题的解的充分必要条件：它们满足KKT条件。

通过对偶问题求解主问题

当强对偶性成立时，为了解决主问题：
4. 构造拉格朗日函数，引入非负参数的拉格朗日算子去给目标函数加上限制；
5. 求拉格朗日函数对主变量的极小——将拉格朗日函数对主变量求偏导，令其为零后得出主变量与对偶变量的数值关系，由此把对主变量进行极小化的拉格朗日函数转化为一个对偶变量的函数；
6. 求上面第2步得出的函数对对偶变量的极大
由此一来，就将解主问题转化成极大极小问题，接下来，我们用这个方法求解线性可分SVM的目标函数。

线性可分SVM的对偶问题

主问题

SVM的主问题：

主问题的强对偶性

判断线性可分SVM主问题是否是强对偶的：

1. $f(w,b)=\frac{||w||^2}{2}$f(w,b)=2∣∣w∣∣2​是凸函数；
2. $g_i(w,b)=1-y_i(wx_i+b)$gi​(w,b)=1−yi​(wxi​+b)也是凸函数（线性函数是凸函数）；
3. 想想我们是如何构造不等式约束条件的——对于所有位于最大分割超平面两侧，距离最大分割超平面距离为$||w||$∣∣w∣∣的辅助超平面上的点$x^*$x∗，有$1-y^*(w^x+b)=0$1−y∗(wx+b)=0，而对这两个辅助平面之外的点$x^**$x∗∗，则有$1-y^**(wx^**+b)&lt;0$1−y∗∗(wx∗∗+b)<0。因此，主问题可行域中，至少有一点使得不等式条件严格成立。
   所以，线性可分SVM 的目标函数可以通过求解其对偶问题来求解。

使用对偶算法求解线性可分SVM的步骤

步骤1：对主问题构造拉格朗日函数

引入拉格朗日乘子$\alpha_i&gt;=0$αi​>=0，其中$i=1,2,...m$i=1,2,...m，得到拉格朗日函数：

步骤2：求拉格朗日函数对于 $w,b$w,b 的极小

补充知识：

我们先将拉格朗日函数对 $w$w 和$b$b 求偏导，然后分别令两个偏导结果为0，之后得出了下列数值关系：

将这两个等式带入拉格朗日函数，得：

步骤3：求$min_w,bL(w,b,\alpha)$minw​,bL(w,b,α)对$\alpha$α的极大

也就是对偶问题：

步骤4：由对偶问题求$\alpha_1,\alpha_2,...,\alpha_m$α1​,α2​,...,αm​

步骤5：由$\alpha^*$α∗求$w$w

由步骤1已知：

$x_i$xi​，$y_i$yi​已知，$\alpha_i^*$αi∗​已由上一步求出，将它们带入上式，求$w$w。

步骤6：由于求$w$w求$b$b

$\alpha_1*,\alpha_2^*,...\alpha_m^*$α1​∗,α2∗​,...αm∗​都已经求出来了。
因为$\alpha_i(1-y_i(wx_i+b))=0;i=1,2,...m$αi​(1−yi​(wxi​+b))=0;i=1,2,...m是整体约束条件；又因为对于所有支持向量$(x_s,y_s)$(xs​,ys​)，都有$1-y_s(wx_s+b)=0$1−ys​(wxs​+b)=0，因此，所有大于0的$\alpha_k^*$αk∗​所对应的$(x_k,y_k)$(xk​,yk​)必然是支持向量。否则，如果$\alpha_k^*&gt;0,1-y_k(wx_k+b)&lt;0$αk∗​>0,1−yk​(wxk​+b)<0，则$\alpha_k^*(1-y_k(wx_k+b))<0，不符合约束条件。

注意：

那么既然哪些$(x,y)$(x,y)对是支持向量都已经清楚了，理论上讲，我们随便找一个支持向量$(x_s,y_s)$(xs​,ys​)，把它和$w$w带入：$y_s(wx_s+b)=1$ys​(wxs​+b)=1，求出b即可。

为了更加鲁棒，我们可以求所有支持向量的均值：

步骤7：求最终结果

SMO(Sequetial Minimal Optimization)算法

先看一下优化目标：

一共有m个参数需要优化，这是一个典型的二次规划问题，我们可以直接用二次规划方法求解。或者，为了节约开销我们也可以用 SMO 算法。SMO 是一种动态规划算法，它的基本思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这一个优化参数的极值。

然而，我们的优化目标有约束条件：

如果一次只能优化一个参数，就没法体现约束条件了。改进一下：

步骤1：

选择两个需要更新的变量$\alpha_i$αi​和$\alpha_j$αj​，固定他们以外的其他变量。这样约束条件：

其中：

这样由此得出：$\alpha_j=\frac{(c-\alpha_iy_i)}{y_j}$αj​=yj​(c−αi​yi​)​，也就是我们可以用$\alpha_i$αi​的表达式代替$\alpha_j$αj​，将这个替代式带入优化目标函数。就相当于把目标问题转化成了一个单变量的二次规划问题，仅有的约束是：$c&gt;=\alpha_i&gt;=0$c>=αi​>=0

步骤2：

对于仅有一个约束条件的最优化问题，我们完全可以在$\alpha_i$αi​上，对问题函数$T(\alpha_i)$T(αi​)求（偏）导，令导数为零，从而求出变量值$\alpha_{inew}$αinew​

确定新值后，更新$\alpha_i$αi​和$\alpha_j$αj​

步骤3：

多次迭代上面1-2步，直到收敛。

SMO算法可以自己研究推导过程、以及如何选每次$\alpha_i,\alpha_j$αi​,αj​来提高效率等。