概要对偶SVM的动机拉格朗日对偶SVM解决对偶SVM对偶SVM背后的理论
欢迎转载，可以关注博客：/cqy_chen
题目可能不全，因为有字数限制，不好意思，可以参考：
https://www.csie.ntu.edu.tw/~htlin/course/ml15fall/
概要
上节课讲到了线性的支持向量机，采用胖胖的分割线作为分类器。要进行求解，首先将X投影到z空间，然后在z空间进行线性分割就好了。但是如果投影到z空间中的维度很高，或者是无线维，那么好像就不好求解了。
本节课就是讨论如何求解特征转换到高维度或者无线维度的方程。
对偶SVM的动机
所以为啥要用svm的对偶方程去求解呢，就是因为当我们经过特征转化到高维度后，直接采用QP的方式太慢了，或者有的时候会投影到无限多维，这个时候就没法算了。所以能不能在不依赖于空间维度的数量，而是样本数量？如果学习过对偶问题的童鞋应该是知道的，在运筹学中，就相当于影子价格。言归正传，目的如下图：
目的就是SVM的对偶求解不依赖于新产生的维度数量，减少运算复杂度
关于线性对偶可以参考
/cqy_chen/article/details/77872159
将变量个数从d˜+1——>N，而条件个数从
这个怎么做呢？使用熟悉的拉格朗日乘子法啦。
回顾原始的式子：
minw,b12wTwsubjectto:yn(wTzn+b)≥1foralln=1,2,.....N
通过添加拉个朗日乘子后,添加了an个乘子：
L(w,b,a)=12wTw+∑n=1Nan(1−yn(wTzn+b))其中：a1,a1,a3......an≥0
这里我们来看看添加之后的式子和原来的式子会不会是一样的呢？
首先我们令,m=12wTw以及n=∑Nn=1an(1−yn(wTzn+b))则：L(w,b,a)=m+n,原来的最小化我们先将w和b固定住，做最大化，然后再做最小化操作，如下：
minb,w(maxa(m+n))
当我们选择了一个不符合条件的点，就会导致yn(wTzn+b)≤1，由于要使得固定w和b之后的最大化，就会导致n无穷大。
当我们选择了一个符合条件的点的时候，就会导致
当我们最大化之后再进行最小化，只能选择n=0的情况，这个时候和原来的情况是一样一样的，如下图：
拉格朗日对偶SVM
上面式子只是说明了经过变换，拉格朗日式子和原来的求解是一样的。如果是对于非最优的a则有：
上面的这个式子称为拉格朗日对偶问题，这个证明了先固定a,求得最小值，然后求解最大值是原问题的一个解的下确界。
当条件满足kkt条件的时候两个式子是相等的：
对于SVM问题，恰好满足条件，可以通过求解对偶问题来求解原问题。
变成对偶问题之后，有啥好处，因为没有可以在没有条件的情况下去求解w和b了啊
对偶问题是：
maxa(minw,b(12wTw+∑n=1Nan(1−yn(wTzn+b))))
由于先求解里面的最小化，而且是木有任何条件限制的，所以呢，可以直接求解梯度，令为0不就好了么，所以最佳解应该满足：
∂Lb=∑n=1Nan(−yn)=0<==>∑n=1Nanyn=0∂Lw=w+∑n=1Nan(−ynzn)=0<==>w=∑n=1Nanynzn
所以带入b的导数得到：
所以最后我们得到如下式子：
L(w,b,a)=maxa,w=∑Nn=1anynzn,∑Nn=1anyn=0(−12||∑n=1Nanynzn||2+∑n=1Nan)
需要满足如下条件：
1)拉格朗日乘子：a1,a2,a2...an≥0
2)梯度为0：w=∑Nn=1anynzn,∑Nn=1anyn=0
3)线性可分，就是有解：1−yn(wTzn+b)≥0
4)同时我们知道当所选点违反条件的时候，原始的式子里面是趋于无穷大，只有当选择的点满足条件才证明了与原始的式子等同，所以有：an(1−yn(wTzn+b))=0
上面的条件称之为kkt条件，所以我们成功将SVM的问题转换成了对偶问题。
解决对偶SVM
那么我们看到上的式子只是关于a的，主要将
哇咔咔，这是个啥，不就是一个QP问题么？这里有N+1个条件，同时有N个变量，转换成QP问题的标准形式如下：
这里有一个问题，就是Q矩阵，可以看看这是一个资料量大小相关的方阵，假如有1W笔资料就需要1W*1W的大小。而且是一个很稠密的矩阵，这就麻烦了，原来是的SVM问题Q是一个稀疏的矩阵。
对于这种稠密的，很大的Q矩阵一般采用了SMO方法进行优化，可以参考：
/luoshixian099/article/details/51227754
ok，现在假设已经求解出了a,剩下的问题就是要求解
根据我们的限制条件：
w=∑n=1Nanynznan(1−yn(wTzn+b))=0
这就是很easy的一件事情啦。w就直接求出，对于b呢，我们看到只要选择任意一个
这里当an不为0的情况的点，称为支持向量，因为这个时候1−yn(wTzn+b)=0，反之，1−yn(wTzn+b)=0不一定有an=0。所以我们前面说边界上的点是支持向量点的候选集。
对偶SVM背后的理论
上面中我们知道了
当an>0，我们称这些点为支持向量，这个时候得到：
w=∑n=1Nanynzn=∑支持向量anynznb=yn−wTzn,任意的支持向量
所以最后得到的w和b只和支持向量有关，我们对比下以前学习到的PLA；
可以看到，在SVM中，w可以通过支持向量表现出来，而PLA中，w可以通过犯错误的点表现出来。
其实在使用优化算法，GD或者SGD的过程中，w都可以表现成ynzn的形式。只不过在SVM中，只与支持向量有关。
但是其实我们还没做完呢，对比原始的SVM和对偶的SVM：
在原始的SVM中，因为映射到了高维，所以我们想要通过对偶问题来求解，所以只得到了N个变量和
但是在对偶问题求解过程中，真的和高维度的映射么有关系么？
这里在进行QP求解的时候：qn,m=ynymzTnzm就包含了映射到高维度的z了哇，如果采用无线维度的映射，那岂不是Q矩阵没法求解啦？
所以这里还留下了一个问题，如何来避免求解Q。
预知后事如何，请听下回分解。
欢迎转载，可以关注博客：/cqy_chen
