svdd算法详解

4.3.3实现技术（1）KKT条件，工作集选取及停止准则在求最小包围球的过程中，迭代没有结束前，每轮迭代会有一个新点被选中，核集中加入新的点后，在核集中的点是下面三种情况之一：1.核向量，满足KKT条件；2.处在球内的非核向量，对应的i为0，也满足KKT条件；3.在(,)ttBcR外面。刚加入进来的点0l违反KKT条件。加入新的训练点后，参照传统SVM方法对核集中的样本点检查是否违反KKT条件的算法推导如下：原始问题的KKT条件：22(||()||)0iiiRcx（4.16）加上已知条件0ii，0iiC根据i的不同，有三种情况：0i，有22||()||0iiRcx，又iC，则0i，因此有22||()||icxR（4.17）0iC，有22||()||0iiRcx，又0i，则0i，因此有22||()||icxR（4.18）iC，有22||()||0iiRcx，又0i，则0i，因此有22||()||icxR（4.19）每次迭代以对KKT条件破坏最多的两个样本为工作集，因此，选取以下两个样本下标2argmax(||()|||)iiscxC2argmin(||()|||0)iitcx若记2||()||sigcx，2||()||tigcx则根据KKT条件，我们有stgg。实际中我们考虑(0)stgg，因此在算法停止前，都有stgg（4.20）在运算的过程中因为有,(,)2(,)(,)titsijijiisssijSxSgkxxkxxkxx,(,)2(,)(,)tittijijiitttijSxSgkxxkxxkxx所以实际上是：(,)(,)2ititiitiisxSxSkxxkxx（2）规模为2问题的解析解找出核集中违反KKT条件的训练点后，更新其对应的Lagrange因子值。这里我们依然采用SMO算法，解规模为2的原问题的对偶问题。不失一般性，在（4.14）对偶问题中将,st看成待求变量，其他看成已知参数，得到求解,st的优化问题如下：22,max{22[()()]()}ssstttststssttiiistLkkkxxxconst（4.21）S.t.st,0,stC其中oldoldst，1()miiicx222max(2)2()ttsstttttstLkkk,,2()()()2()()tsiittiiististxxxxconst若记,()()()(()())oldoldoldjjiijssttistxxxcxx则,()()ssiiistxx，,()()ttiiistxx2222222222sstsstssttttsttstststtLkkkkkkconst2(2)2()stsstttssststtkkkkkconst因为()()oldoldoldoldssstststssststkkkk()(()())()(()())oldoldoldoldoldoldssstttssttxcxxxcxxoldoldoldoldssstssssttstkkkk11(,)(,)mmoldoldoldoldiisssststiitssttttiiKxxkkKxxkk11(,)(,)(2)mmoldiisiitstsstttiiKxxKxxkkk211(2)2[(,)(,)(2)]mmoldstsstttiisiitstssttttiiLkkkKxxKxxkkkconst令0tL，可得11(,)(,)2mmiitiisoldiittstssttKxxKxxkkk（4.22）有20stssttkkk，在迭代结束前都有11(,)(,)0mmiitiisiiKxxKxx则当20stssttkkk，11[(,)(,)]mmiisiittiiLKxxKxxconst,L为线性函数，因为0iC，()()0ttstcxcx，所以tC。最后，由优化问题的等式约束得出st（4.23）这样就得出了,st的解析解，不过这是在没有考虑优化问题的不等式约束0,stC的情况下得到的解析解。存在不等式约束为0,stC，因此，考虑不等式约束，需要对求出的,st进行如下裁剪：若0s，则0,st若0t，则0,ts若sC，则,stCC若tC，则,tsCC