之前博客续http://blog.csdn.net/mosbest/article/details/52017312 上面的博客讲到，svm线性形式为 只需将上面的表达式转化为 标准的 二次规划形式，输入参数，相应的软件就可以帮我们把最佳解求出来．可是，上面的方程仅仅适用于 线性可分的数据，如果遇到非线性的数据，那么就应该用之前讲的，将ｘ映射到高维的函数上处理，使用映射函数 Φ(x) ，那么svm的表达式和求解方法变为 由于二次规划的复杂度与特征数目( d˜+1 即自由度)有很大关系，当自变量映射到高维的时候， d˜+1 就会变大，甚至无穷．那么用二次规划的软件来求解时，估计要算到天荒地老． 所以，我们的目标就是让 SVM的复杂度不依靠 d˜+1 ！ 所以，引出 对偶形式的SVM. 我们SVM原来的形式是: 我们现在引入拉格朗日函数 从而得到 其实上面的方程与SVM 最初的形式是等价的． 因为，当 yn(wTzn+b)<１ ，那么 １－yn(wTzn+b)>0 ，由于要求 alla>=0max ，那么我们得到的 maxalla>=0L(b,w,a) 最大值一定为 无穷大． 当 yn(wTzn+b)＞＝１ ，那么 １－yn(wTzn+b)＜＝0 ，由于要求 alla>=0max ，那么我们得到的 maxalla>=0L(b,w,a) 最大值一定０． 当我们把上面两种情况取最小值时，得到的一定是 yn(wTzn+b)＞＝１ 情况的结果． 所以， 和 是等价的．我们就把原来的形式转化为了svm=min( maxalla>=0L(b,w,a))
我们又可以将上面的形式转化一下，
上面是弱对偶形式，因为连接符为”>=”，所以不一定会”=”．不过对于二次规划问题，如果有 １．函数是凸的 ( wTw 本就是图函数) ２．映射函数 Φ(x) 是存在的,即进行映射后可以线性分割．(如果不是，我们就没必要做了) ３．条件是线性的（条件 yn(wTzn+b)＞＝１ 本就是线性的） 由于我们这上面三个条件都满足，那么就可以变成强对偶，即 存在 （b,w,a）使得两边相等．
所以，我们就得到 求里面的最小情况，就让其对w,b求偏导 对b求偏导，化简
对w求偏导．化简最终得到的形式为 KKT条件是说，最优解必须满足 求取以上等式之后，就可以得到最优解． 很显然我们本就满足以上条件． 现在来求取最优解 现在我们把我们表达式都转化为求 α 的形式，将我们的表达式化简为 只是对 α 求最佳解，所以这里我们只有N个变量，而线性形式有 d+1 个，有时ｄ可能趋近无穷大． 我们用二次规划软件求解 通过求出的 α 就可以求出b和w了． 利用 求出ｗ． 利用 当某 αn>0 时，剩下的就必须为０．则 我们选出一个 αn>0 的情况对应的点就行了．当然，为了防止波动太大，可以把 αn>0 都求一边，然后取平均值． 发现， αn>0 时有 yn(wTzn+b)＝１ 其实这就是最大边界．则 αn>0 对应的点就是支持向量． αn>0 的点一定最大边界上面，但是最大边界上面的点不一定都 αn>0
可是对偶方法一能让模型不依靠 d 吗？你有没有发现，对偶模型的Ｑ放在二次规划软件，如果z向量太长，那么计算Q就会非常的复杂 如上图，就是对偶模型最终形式，我们最后是要把他丢到二次规划的软件里计算的．当映射函数很复杂,即z域的z变量很长，那么计算zTz其实非常复杂，即 qm,n 的计算非常复杂．那么最终他的复杂度依然为 O(d) 要想真正减少运输量，最终方法是 用核函数kernel.
