林轩田机器学习技法笔记2：Dual Support Vector Machine

0. 前言

上一节课我们介绍了支持向量机、margin、怎么解支持向量机等。这一节课我们将会研究支持向量机的对偶问题。

1. Motivation of Dual SVM

上一节课中我们讲到，求解线性支持向量机的QP问题中变量数量为dˆ+1$\hat{d}+1$，则dˆ+1$\hat{d}+1$越大，相应求解这个QP问题也变得很困难。当dˆ$\hat{d}$无限大的时候，问题将会变得难以求解。因此，我们将此问题转换成一个对偶问题，同样是二次规划，只不过变量个数变成N个，有N+1个限制条件。对偶SVM的好处就是问题只跟N有关，与dˆ$\hat{d}$无关，这样当dˆ$\hat{d}$无穷大时仍能求解。

这个转换过程非常的复杂，这里将不会赘述，只讲概念和原理上进行简单的推导。
之前在使用regularization时，使用拉格朗日极值法把条件问题转换成非条件问题，这里同样可以这么处理。
使用拉格朗日极值将左图转换为右图，其中αn${\alpha }_n$为拉格朗日系数。

我们利用拉格朗日函数，把SVM构造成一个非条件问题：

问题中巧妙的使用了最小化中包含了最大化，这里进行解释一下。首先我们规定拉格朗日因子αn≥0${\alpha }_n\ge 0$。如果说b，w是不好的，那么中间这个max就会使得an$a_n$为无穷大，因为根据SVM的限定条件可得：(1−yn(wTzn+b))≥0$(1-y_n(w^T{z}_n+b))\ge 0$,是个正值。此时，最好的结果就是无穷大，我们在外面套了个min自然就选不到这种情况了。如果说b，w是好的，那么我们的问题就转化成min12wTw$\frac{1}{2}{w}^{T}w$了。

2. Lagrange Dual SVM

通过上一部分的分析，我们已经可以得到我们最后的目的是：

同样的，等式也可以转换成：

上述不等式表明，我们对SVM的min和max做了对调，满足这样的关系，这叫做Lagrange dual problem。不等式右边是SVM问题的下界，我们接下来的目的就是求出这个下界。
经过推导，SVM对偶问题的解已经转化为无条件形式：

首先，令L(b,w,α)对参数b的梯度为零，再令L(b,w,α)对参数w的梯度为零，最后化解得到：

其中，满足最佳化的条件称之为Karush-Kuhn-Tucker(KKT)：

3. Solving Dual SVM

这一部分我们继续上一部分的优化，首先，将max问题转化为min问题：

这是一个convex的QP问题，且有N个变量αn${\alpha }_n$，限制条件有N+1个。则根据上一节课讲的QP解法，找到Q，p，A，c对应的值，用软件工具包进行求解。

得到αn${\alpha }_n$之后，再根据之前的KKT条件，就可以计算出w和b了。

值得注意的是，计算b值，αn>0时，有yn(wTzn+b)=1$y_n(w^T{z}_n+b)=1$成立。yn(wTzn+b)=1$y_n(w^T{z}_n+b)=1$正好表示的是该点在SVM分类线上，即fat boundary。也就是说，满足αn>0的点一定落在fat boundary上，这些点就是Support Vector。

4. Messages behind Dual SVM

上一部分末尾我们降到，αn>0${\alpha }_n>0$的点一定落在分类线边界上，这些点称之为support vector，其实分类线上的点不一定都是支持向量，但是满足αn>0${\alpha }_n>0$的点，一定是支持向量。

我们对SVM和PLA进行一个比较：

发现两者非常相似，都是由ynzn$y_n{z}_n$线性组合而成。
总结一下，本节课和上节课主要介绍了两种形式的SVM，一种是Primal Hard-Margin SVM，另一种是Dual Hard_Margin SVM。Primal Hard-Margin SVM有dˆ$\hat{d}$+1个参数，有N个限制条件。当dˆ$\hat{d}$+1很大时，求解困难。而Dual Hard_Margin SVM有N个参数，有N+1个限制条件。当数据量N很大时，也同样会增大计算难度。两种形式都能得到w和b，求得fattest hyperplane。通常情况下，如果N不是很大，一般使用Dual SVM来解决问题。

这节课提出的Dual SVM的目的是为了避免计算过程中对dˆ$\hat{d}$的依赖，而只与N有关。但是，Dual SVM并没有真的消除对dˆ$\hat{d}$的依赖，因为在计算qn,m=ynymzTnzm$q_{n,m}=y_n{y}_m{z}_n^T{z}_m$的过程中，由z向量引入了dˆ$\hat{d}$，实际上复杂度已经隐藏在计算过程中了。所以，我们的目标并没有实现。下一节课我们将继续研究探讨如何消除对dˆ$\hat{d}$的依赖。

5. 总结

这一节课我们介绍了SVM的另外一种形式：Dual SVM。这种向量机能移除计算过程对dˆ$\hat{d}$的依赖。SVM可以看作是这样一个问题：找出所有的support vector，然后用它们算出margin，其他的数据点一点都不重要。