支持向量机的对偶问题。
上节讲到可以用非线性变换将xn映射到zn,在z空间上求解SVM。
那要求解的w的维度变成新的d,如果d很大,那么QP求解变难。
希望将问题转化成对等的,只用求解N个变量的问题
之前讲正则化的时候,(间接地)使用了拉格朗日乘子法,将lamda看成c的一种替代,将有约束优化问题化为无约束的。
现在使用同样的方式来去掉SVM的约束条件。这里的lamda是未知的,看做变量。
SVM问题的拉格朗日函数:
那么问题变成
注意到这里,将约束条件包含进了目标函数。
现在证明两个问题是等价的:
首先看简化后的问题,对
如果w,b不满足原始的st条件,也就是说存在样本点,使得
如果w,b满足原始的st条件,那么最大化L就是每个alpha都为0, 然后再对objective求最小。
将这些组w,b放在一起求最小,就可以忽略那么不满足st条件的wb了,也就是求原始目标函数(object)的最小。
那么现在要求解这个新的问题
对固定的alpha',显然下式成立
那么右边加一个max,同样成立
右边式子就叫做这个拉格朗日问题的对偶问题。
那么能不能把左式的求解换成右式的求解呢?对于SVM来说因为满足下面三条绿色的条件,所以左右两边其实是相等的。所以两边最优解是一样的。
下面就来求解对偶问题。
首先看min的问题。
因为min是无约束优化,那么最佳的b、w肯定满足 它们的偏导为0。把这个条件作为约束加到外面去并不影响求解最优的点。因为bw就是要满足最优的条件。。(绕
这样就分别把w,b求导后的条件限制放到max问题中了。
这里通过限制条件,去掉了b
通过限制条件,w表示成 alpha的函数,min中的问题和b、w无关了,去掉min,直接拿出来
那么问题化简成
理论证明...对偶问题的最优解(b,w,alpha)满足KKT条件:
那么标准的hard-margin svm的对偶问题的形式如下
就可以通过QP来求解了
那如果N很大的话,Q矩阵因为是稠密的所以也会特别占用内存。
由求得的alpha,得到w和b.
其中b只需要选择一个alpha_n不为零的代进去算就好了。
那些alpha>0对应的样本点就是在边界上的点,也就是支持向量。
在w和b的计算中,不是SV的点没有起到作用,所以SVM的学习是通过对偶问题求解得到的SV来进行的。
和PLA的类比:
它们的w最后都可以表示成yz的线性组合。称w是可以被data表示的。
在SVM中,w只用被SV表示。
总结一下,hard-margin的SVM有两种形式的写法,原始的SVM和它的对偶问题:
注意到对偶问题中,Q的每个元素表示成了z向量的内积,在高维转换后,这种内积运算计算量就比较大了,要怎么办呢?且听下回分解。