SVDD算法详解.pdf

《SVDD算法详解.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.3.3实现技术（1）KKT条件，工作集选取及停止准则在求最小包围球的过程中，迭代没有结束前，每轮迭代会有一个新点被选中，核集中加入新的点后，在核集中的点是下面三种情况之一：1.核向量，满足KKT条件；2.处在球内的非核向量，对应的为0，也满足KKT条件；i3.在B(c,R)外面。刚加入进来的点0违反KKT条件。ttl加入新的训练点后，参照传统SVM方法对核集中的样本点检查是否违反KKT条件的算法推导如下：原始问题的KKT条件：22(R

2、

3、c(x)

4、

5、)0（4.16）iii加上已知条件0，C

6、0iiii根据的不同，有三种情况：i220，有R

7、

8、c(x)

9、

10、0，又C，则0，因此有iiiii22

11、

12、c(x)

13、

14、R（4.17）i220C，有R

15、

16、c(x)

17、

18、0，又0，则0，因此有iiiii22

19、

20、c(x)

21、

22、R（4.18）i22C，有R

23、

24、c(x)

25、

26、0，又0，则0，因此有iiiii22

27、

28、c(x)

29、

30、R（4.19）i每次迭代以对KKT条件破坏最多的两个样本为工作集，因此，选取以下两个样本下标2sargmax(

31、

32、c(

33、x)

34、

35、

36、C)ii2targmin(

37、

38、c(x)

39、

40、

41、0)ii若记22g

42、

43、c(x)

44、

45、，g

46、

47、c(x)

48、

49、siti则根据KKT条件，我们有gg。实际中我们考虑gg(0)，因此在算stst法停止前，都有gg（4.20）st在运算的过程中因为有gsijk(xi,xj)2ik(xi,xs)k(xs,xs)i,jStxiStgtijk(xi,xj)2ik(xi,xt)k(xt,xt)i,jStxiSt所以实际上是：ik(xi,xt)ik(x

50、i,xs)xiStxiSt2（2）规模为2问题的解析解找出核集中违反KKT条件的训练点后，更新其对应的Lagrange因子值。这里我们依然采用SMO算法，解规模为2的原问题的对偶问题。不失一般性，在（4.14）对偶问题中将,看成待求变量，其他看成已知参st数，得到求解,的优化问题如下：st22maxL{sksstktt2stkst2[s(xs)t(xt)]i(xi)}const（4.21）is,tS.t.,0,Cststmoldold其中st，c

51、i(xi)i1222maxL(2)kk2()kttsstttttst2(t)(xs)i(xi)2t(xt)i(xi)constis,tis,toldoldold若记j(xj)i(xi)(xj)(cs(xs)t(xt))is,t则s(xs)i(xi)，t(xt)i(xi)is,tis,t2222Lk2kkk2k2k222constsstsstsstttts

52、ttstststt2(2kkk)2(kk)conststsstttssststtoldoldoldold因为kk()k()kssstststssststoldoldoldoldoldold(x)(c(x)(x))(x)(c(x)(x))ssstttssttoldoldoldoldkkkkssstssssttstmmoldoldoldoldiK(xi,xs)sksstkstiK(xi,xt)skst

53、tktti1i1mmoldiK(xi,xs)iK(xi,xt)(2kstkssktt)ti1i1mm2oldL(2kstkssktt)t2[iK(xi,xs)iK(xi,xt)(2kstkssktt)t]tconsti1i1L令0，可得tmmiK(xi,xt)iK(xi,xs)oldi1i1（4.22）tt2kkkstssttmm有2kstkssktt0，在迭代结束前都有iK(xi,xt)iK(xi,xs)0i1

54、i1mm则当2kstkssktt0，L[iK(xi,xs)iK(xi,xt)]tconst,L为线性函数，i1i1tt因为0C，c(x)c(x)0，所以C。istt最后，由优化问题的等式约束得出（4.23）