《SVM算法》由会员分享，可在线阅读，更多相关《SVM算法（3页珍藏版）》请在金锄头文库上搜索。
1、 SVM 算法SVM假设空间中有两类点，x1,.xn, 为他们的坐标。y1,.,yn 为他们的类别, yi=1 or -1 。如图所示。SVM 试图找到一个超平面 wx+b=0 将空间中的两类点分开，且所有点到该平面的最小距离 min_i |wxi+b|/|w|最大。用数学表达一下：w*,b*= max_w, bmin |wxi+b|/|w| s.t. yi(wxi+b)0 forall xi (1)其中点 xi 到平面 wx+b=0 的距离为|wxi+b|/|w|。读者可以自证yi(wxi+b)0 是为了保证所有点分类正确。对于 yi=1 的点 xi,满足 yi(wxi+b)0 = wxi+
2、b0,即 xi 在正的半空间内，而对于 yi=-1 的 xi，他们在负的半空间内由于一个平面的表示方式不唯一，wx+b=0 和 cwx+cb=0 是同一个平面，所以这里要作规范化。假设 SVM 得到的平面是 wx+b=0，离平面最近的点是 x*1,x*2.,x*k(由于点 x1.,xn 已经给定，所以，这个平面已经唯一存在。x*1,x*2.,x*k 也是固定的)我们调整 w,b，使得|wxi*+b|=1, forall xi*.这样，w,b 就唯一确定了。将这带入(1)，有w*,b*= max 1/|w| = min 1/2 wws.t. yi(wxi+b)=1 forall xi (2)注意
3、，|wxi*+b|=1,意味着|wxi+b|=1,而|y|=1，所以 yi(wxi+b)=1 forall xi记 L(a,w,b)=1/2 ww + sum_i ai1-yi(wxi+b),(2)的对偶问题描述为：max_a min_w,b L(a,w,b)s.t. ai=0 (3)由 min_w,b L(a,w,b)，我们有dL/dw=0 = w=sum_i(ai xi yi), (4)dL/db=0 = sum_i(ai yi)=0 (5)将(4)(5)带入(3),a*= max_a 1/2 ww + sum_i ai - wsum_i(ai xi yi) + bsum_i(ai yi)
4、=max_a 1/2 ww + sum_i ai - ww=max_a -1/2 sum_i(ai xi yi)sum_i(ai xi yi) + sum_i a_i因此我们得到了(2)的对偶问题的简化形势：max_a -1/2 sum_i(ai xi yi)sum_i(ai xi yi) + sum_i a_is.t. ai=0当两类问题不可分的时候，会引入松弛变量 d=0此时 SVM 的目标函数为w*,b*= min 1/2 ww + Csum_i dis.t. yi(wxi+b)=1-di forall xi di=0 (6)C0 是一个预先定义好的常量。Csum_i di=0，要使得目
5、标函数最小，那么一方面 1/2 ww 要小，也就是 margin 要大；另一方面 Csum_i di，也就是最好没有松弛变量，还句话说，点要尽量落在 margin 的两个超平面两侧。同样，我们对 di 引入乘子 ei=0;令 L(w,b,a,d,e)=1/2 ww + Csum_i di + sum_i ai1-yi(wxi+b) + sum_i(ei di) , (6)的对偶问题为max_a,e min_w,b,d L(w,b,a,e)ei=0ai=0令导数0dL/dw=0 = w= sum_i(ai xi yi) dL/db=0 = sum_i(ai yi)=0dL/dd=0 = C-ai-ei=0 forall i通过最后一个式子削去 ei,我们得到了最后简化好的对偶形式max_a -1/2 sum_i(ai xi yi)sum_i(ai xi yi) + sum_i a_is.t. C=ai=0sum_i ai yi=0关键词关键词(Tag): svm 算法算法 svm 介绍介绍
