林轩田机器学习技法（MachineLearningTechniques）笔记（二）

林轩田机器学习技法&＃xff08;Machine Learning Techniques&＃xff09;笔记&＃xff08;一&＃xff09;
林轩田机器学习技法&＃xff08;Machine Learning Techniques&＃xff09;笔记&＃xff08;三&＃xff09;

Dual Support Vector Machine

P6 2.1

L1 讲的是线性支持向量机&＃xff0c;接下来L2讲的是对偶支持向量机。

上节就讲了下求non-linear SVM的方法&＃xff0c;转换到z空间的时候&＃xff0c;QP问题会有 d^~ &＃43; 1 个变数&＃xff08;和N个常数&＃xff09;来解&＃xff0c;要解决 d^~ 很大&＃xff0c;甚至是无穷的问题&＃xff0c;让SVM不依赖于d^~ &＃xff1a;

我们可以把original的SVM转成等效的SVM

这就是对偶问题&＃xff1a;

我们可以仿照之前regularization&＃xff0c;引入λ&＃xff0c;将条件问题转换为非条件问题&＃xff0c;而λ的个数就是N


定义拉格朗日函数&＃xff0c;相关文献通常把 λ 写成 α

把SVM转换成右式子

如果满足不了 s.t. 的&＃xff08;b,w&＃xff09;那么1-yn(wTzn&＃43;b)就是整数&＃xff0c;选取max的话&＃xff0c;就会到达无穷大&＃xff0c;因为最终要到是min&＃xff0c;这样就会筛掉这种不满足 s.t. 的&＃xff08;b,w&＃xff09;
如果满足了的话&＃xff0c;yn(wTzn&＃43;b)会是个非负数&＃xff0c;因为有个max且a>&＃61;0&＃xff0c;所以 yn(wTzn&＃43;b)&＃61;0&＃xff08;注意可以不要$\sum$&＃xff0c;因为a>&＃61;0&＃xff0c;只能是每一项都&＃61;0&＃xff0c;才可以求和&＃61;0&＃xff09;&＃xff0c;那么式子就是 12wTw\frac{1}{2} w^Tw21​wTw。
这样即有效地筛掉不满足 s.t. 的数据&＃xff0c;又能找到最小的12wTw\frac{1}{2} w^Tw21​wTw。

P7 2.2
上节把SVM转成拉格朗日式子&＃xff0c;那么&＃xff0c;如何找到该式子的下限&＃xff1f;对于任何(b,w)来说&＃xff0c;都有这个&＃xff1a;

因为对于任何都成立&＃xff0c;所以取右式子最大的&＃xff0c;还是成立的&＃xff1a;

右式成为拉格朗日的对偶(dual)问题&＃xff0c;如果解决了这个问题&＃xff0c;也就找出SVM的下限。

因为满足绿色的三个条件&＃xff0c;所以是个强关系&＃xff08;对于QP问题&＃xff09;&＃xff0c;所以就可以直接等同了&＃xff0c;也说明了有组(b,w,α)满足等式两边&＃xff1a;

现在没有什么限制了&＃xff0c;所以开始解这个&＃xff1a;

因为是min&＃xff0c;所以要求&＃xff1a;

因此我们可以加上这个限制&＃xff0c;并把式子化一化&＃xff1a;

可以看出最后一项是 b*0 &＃xff0c;所以变成&＃xff1a;

同样&＃xff0c;因为min&＃xff0c;所以要给L求个w的偏导&＃61;0&＃xff0c;得出w为一个固定的数&＃xff0c;然后开始化简&＃xff0c;min可以不用看了&＃xff0c;是因为max有了下面一系列规定之后&＃xff0c;式子里头没有b和w&＃xff0c;剩下的就只用考虑 α 就可以了。

最后成这个满足最佳化的4个条件为KKT。补充一下&＃xff1a;第四点&＃xff08;哈利波特和伏地魔必须活一个&＃xff09;那个&＃xff0c;yn(wTzn&＃43;b)&＃61;1的话&＃xff08;说明点正好在分界线上&＃xff0c;这些α>&＃61;0点就是SV&＃xff09;&＃xff0c;式子自然为0&＃xff0c;>1的话&＃xff0c;根据2.1最后那个图&＃xff0c;使得2.1那个图的式子取min&＃xff0c;那么αn就只能取0了&＃xff0c;所以最终这里的式子也是0。

最后是funtime小练习巩固&＃xff0c;感觉挺有意思的&＃xff0c;②要去看回 L(b,w,α) 的定义&＃xff0c;就知道了yn和zn&＃61;1&＃xff0c;然后w&＃61;∑αnynzn\sumα_ny_nz_n∑αn​yn​zn​就出来了。③是因为sigma的每一项都要是0&＃xff08;KKT下&＃xff09;&＃xff0c;所以就 &＃61; 0&＃xff0c;对于α2(w-3)的问题&＃xff0c;感觉可以不用管具体w和yn&＃xff0c;zn怎么弄的&＃xff0c;总之整体要为0就是了。

P8 2.3

把上节的式子简单化简一下&＃xff0c;max->min&＃xff0c;然后把平方化开。不加上w &＃61; … 的条件是因为这个十字关注点是在 αn 上。然后发现这是个凸(convex)QP问题&＃xff0c;有N个变量&＃xff08;αn&＃xff09;&＃xff0c;然后又N&＃43;1的条件(constraint)&＃xff08;N个αn要大于零&＃xff0c;1个∑n&＃61;1Nynαn&＃61;0\sum_{n&＃61;1}^N y_nα_n&＃61;0∑n&＃61;1N​yn​αn​&＃61;0&＃xff0c;共N&＃43;1个&＃xff09;&＃xff0c;然后开始套QP。

注&＃xff1a;一般QP输入的时候可以不用把"&＃61;"拆成两个不等式&＃xff0c;直接写&＃xff0c;然后范围bound也可以直接写。

然而&＃xff0c;注意到q是dense的&＃xff0c;稠密的矩阵&＃xff0c;即里面的值很多不是非零的&＃xff0c;计算量和存储量很大&＃xff0c;所以要用一个专门为SVM设计的方法。

通过KKT的4个条件&＃xff0c;我们可以推出w和b。特别的&＃xff0c;当αn>0α_n>0αn​>0的时候&＃xff0c;1−yn∗(wTzn&＃43;b)&＃61;11-y_n*(w^Tz_n&＃43;b) &＃61; 11−yn​∗(wTzn​&＃43;b)&＃61;1&＃xff0c;而&＃xff1d;1 恰好表示点是在SVM胖胖的边界上的(fat boundary)&＃xff0c;至于为什么嘛。。估计又得看看超平面了。

P9 2.4

我们在上节知道了α > 0 的时候&＃xff0c;点在边界上。但是在分类线上的点不一定支持向量&＃xff08;可能有α &＃61; 0的情况&＃xff09;&＃xff0c;所以现在称α>0的点为support vectors&＃xff08;SV&＃xff09;&＃xff0c;仅针对这些SV&＃xff08;就是α>0的&＃xff09;做研究&＃xff0c;范围可能会缩小一些。

因此 w和b 都可以只靠SV算出来&＃xff0c;因为不是SV的话&＃xff0c;即 α &＃61; 0 的话&＃xff0c;它俩没有意义。

SVM和PLA的式子很像&＃xff0c;他们都是ynzny_nz_nyn​zn​的线性组合&＃xff0c;其他的w也差不多&＃xff0c;可以说&＃xff0c;w是资料表现出来的。SVM中的w是只由SV表示的&＃xff0c;PLA则是由犯错的点表示出来。哲学上&＃xff0c;我们要知道要用什么东西&＃xff0c;来表现我们的w。

对比两种SVM的表示方法&＃xff1a;原始(primal)和对偶(dual)&＃xff0c;hard-margin就是ooxx严格分类不容出错的意思。一般是用Dual SVM。

最后&＃xff1a;虽然说dual svm只和N有关&＃xff0c;但其实 d^~藏在了q中&＃xff0c;接下来会讲解怎么避开这个 d^~。

最最后的总结&＃xff1a;