关键词:  支持向量机;增量式学习;减量式学习;可行性分析;收敛性分析

    由 Vapnik 等人提出的支持向量机(support vector machine,简称 SVM) [1] 目前已成为解决分类、回归和其他统计学习问题的一种流行的技术,其中,支持向量机的训练需要求解一个与问题样本数目同样多参数的凸二次规划问题,特别是对于大规模数据集的训练存在着一定的困难.目前已经提出了一些实用的批处理方法,比如工作集选择法 [2] 、样本对迭代计算法 [3] 、闭包球法 [4] 、梯度下降法 [5,6] 、类感知器法 [7] 、切平面计算法 [8] 、束捆计算法 [9,10] 等.而在实际的问题环境中(例如网络数据安全分析、传感器网络数据分析、金融数据分析等),训练样本数据大多为在线环境下增量提供.以网络数据安全分析为例,给定的网络数据流一般不够稳定,亦即数据分布随着时间的变化也会跟着变化,那么如果这样的异常分布数据出现在训练样本中,并且训练样本集很大,批处理算法将会因重新计算而失效.增量和减量式算法对这种情形更适用,因为增量式(减量式)算法的优点正是能够吸收(剔除)额外的数据而不需要对所有数据重新计算,所以,有必要对支持向量机设计相应的增量和减量式算法.

2001 年,Cauwenberghs 和 Poggio [11] 针对标准的支持向量机给出了一种精确的增量和减量式学习算法(C&P算法).为了对 C&P 算法有更深入的认识,2006 年,Laskov 等人 [12] 对该算法增量式部分给出了部分理论分析结果(也就是本文可行性分析中的定理 1 和定理 4),并将它扩展到了一分类支持向量机,设计了增量式一分类支持向量机算法;2008 年,顾彬等人 [13] 将该算法扩展到排列支持向量机上,并给出了相应算法的理论分析,包括可行性以及收敛性分析;2010 年,Karasuyama 等人 [14] 扩展了 C&P 算法,使之能同时处理多个样本的增量式学习;2012年,顾彬等人 [15] 扩展了 C&P算法,使之能处理  支持向量分类机.本文试图在上述工作的基础上,从理论分析与实验验证的角度,全面讨论 C&P 算法的可行性及有限收敛性.本文第 1 节介绍增量和减量式标准支持向量机算法.第 2 节证明该算法的可行性,该分析将确保 C&P 算法的每步调整都是可靠的.第 3 节证明算法的有限收敛性,该分析将确保 C&P 算法通过有限步调整最终收敛到问题的最优解.第 4 节的实验数据进一步验证上述理论分析的结果.最后对本文内容进行总结和展望.

    1 增量和减量式标准支持向量机算法

    当训练集增加新样本或删除原始的某些样本时,为了获得更新后的训练样本集的最优解,增量式(减量式)学习算法需要设计相应的增量(减量)更新法则,使得更新后的训练样本集仍然满足 KKT 等价条件 [16] .而增量式标准支持向量机算法更新法则的基本思想是:令新增样本为(x c ,y c ),在严格保持原先样本集S={(x 1 ,y 1 ),…,(x l ,y l )}中所有样本满足 KKT 等价条件的情况下,逐步增加新增样本(x c ,y c )的权值  c ,如此反复,直至新增样本也满足 KKT 条件.相似地,减量式标准支持向量机算法更新法则的基本思想是:令待删除样本为(x c ,y c ),在严格保持 S-{(x c ,y c )}中所有样本满足 KKT 等价条件的情况下,逐步减少待删样本(x c ,y c )的权值  c ,如此反复,直至  c =0.1.1 KKT等价条件根据凸优化理论 [17] ,通过优化问题(1)的求解,同样可以得到标准支持分类机 [1] 的解:0, 1 1 11min K( , )2 il l li j i j i j i i iCi j i iW y y x x b y           ≤ ≤(1)其中 ,b 是拉格朗日乘子 .根据 KKT 定理 [16] , 对 W 求一阶偏导 , 可以导出下列的 KKT 等价条件 :10,  0K( , ) 1 0, 00,0i Ri j i j i j i i Sji Eli iiSg y y x x yb C SC Sy         ≥ 对于对于≤ 对于 (2)公式 (2) 即称为标准支持分类机的 KKT 等价条件 .相应地 , 公式 (2) 将训练集 S 划分成 3 个子集 :S R ,S S 和 S E [11] , 其中 ,S S 为边缘支持向量集 ,S E 为错分支持向量集 ,S R 为剩余向量集

    1.2 绝缘更新法则当向训练集 S={(x 1 ,y 1 ),…,(x l ,y l )} 中增加一个新样本 (x c ,y c ), 并且  c 和 g c 不满足 KKT 条件时 , 那么需要相应地调整  c 和  S , 以找到扩增样本集的最优解 . 相似地 , 当从训练集 S 中删除样本 (x c ,y c ), 且  c >0 时 , 那么相应地也需要调整  c 和-{( , )} ,c cS x y 以找到收缩样本集的最优解 . 其中 ,  S =[  1 ,…,  l ] T 表示训练集 S 中所有样本对应的  乘子向量 ; 相应地 ,-{( , )}c cS x y 表示集合 S-{(x c ,y c )} 中所有样本对应的  乘子向量 . 本节将针对调整  c 介绍绝缘更新法则 ,其基本原则是 : 在  c 的调整过程中 , 保证集合 S 或 S-{(x c ,y c )} 内的所有样本都满足 KKT 等价条件 .在对  c 的调整过程中 , 为了保证集合 S 或 S-{(x c ,y c )} 内的所有样本都满足 KKT 等价条件 , 那么仅有边缘支持向量集 S S ={i  S:g i =0   i >0   i >C} 中的 |S S | 个样本对应的  乘子以及拉格朗日乘子 b 可以调整 . 根据 KKT 条件(2), 则可以获得如下 |S S |+1 个线性方程 :00SSi j ij i c icj Sj j c cj Sg Q y b Qy y             (3)其中 ,Q ij =y i y j K(x i ,x j ).可以看出 , 线性方程组 (3) 含有一个自由度 .更进一步地 , 线性方程组 (3) 可以变换为S SccS S cb yQQ            (4)其中 ,0SS S STSS S SyQy Q     .这样 , 可以得到  c 和SS 与 b 的线性变化关系 . 其中 ,SS 表示边缘支持向量集 S S 中的所有样本对应的  乘子向量 :S SccSbSccb         (5)其中 ,1,SSccbcS cSyR R QQ              .相应地 , 也可以得到  c 与 g i 的线性变化关系 :ci i cg      (6)其中 , , .Sc c ci ic ij j i bj SQ Q y i S       

    1.3 增量式标准支持向量机算法绝缘更新法则不能直接给出问题的最优解 , 问题在于 : 随着  c 值的增加 , 会改变集合 S S ,S R 和 S E 的组成成分 .解决方法是捕获集合 S S ,S R 和 S E 的最小变化 , 即计算最大调整量max ,c  使得正好某一样本在集合 S S ,S R 和 S E 间要进行迁移 . 具体需考虑如下 3 种情形 :(1) S S 中样本对应的权值  i 到达边界 ( 上界或者下界 ).首先 , 计算集合 { : 0}, { : 0}.S SS S c cS i S iI i S I i S        这样 , 可能的权更新是    (7)那么 , 在集合 S S 中的某个样本移动到集合 S R 或 S E 之前存在一个最大可能更新值 :maxmin .SS SSSSicci I Ii   (2)  在 S R 或 S E 中的某个样本的 g i 函数到达 0.计算集合 { : 0}, { : 0}.E RS S c cE i R iI i S I i S        那么 , 在集合 S R 或 S E 里的某个样本移动到 S S 集合之前存在一个最大可能更新值 :,min .R ES SR ESicci I Iig   (3)  新增样本 ( x c , y c ) 满足 KKT 条件 .那么 , 可以在样本 ( x c , y c ) 达到 KKT 条件之前存在一个最大可能更新值 :,min , .gcc cccgC         最后 ,3 个值中的最小值 :,max ,min{ , , }R ESSS gc c c c         (8)将构成   c 的最大调整量 .基于   c 的最大调整量的计算法则 , 当一个新样本 ( x c , y c ) 增加到集合 S 时 , 扩增样本集的最优解可以通过算法 1 求解获得 .算法 1 .  增量式标准支持向量机算法 .输入 : S ,( x c , y c ),  S ;输出 :  S ,  c .1.  初始化新样本 ( x c , y c ) 的 Lagrange 乘子为 0;2.  如果样本 ( x c , y c ) 满足 KKT 条件 , 那么算法结束 ;3.  否则 , 应用最大调整量maxc  , 使得恰好有一个样本在 S R , S S 和 S E 间移动 ;4.  更新矩阵 R , 如果样本 ( x c , y c ) 满足 KKT 条件 , 那么跳到步骤 2; 否则 , 跳到步骤 3.1.4 减量式标准支持向量机算法与增量式标准支持向量机算法相似 , 减量式支持向量机算法需要计算最小调整量minc  , 使得正好某一样本在集合 S S , S R 和 S E 间要进行迁移 , 相应地 , 也需考虑如下 3 种情形 :(1)  S S 中样本对应的权值  i 到达边界 ( 上界或者下界 ).首先 , 计算集合 { : 0}, { : 0}.S SS S c cS i S iI i S I i S        这样 , 可能的权更新是 :max,,SSSiiSiC i Ii I      (9)那么 , 在集合 S S 中的某个样本移动到集合 S R 或 S E 之前存在一个最大可能更新值 :maxmax .SS SS SSicci I Ii   (2)  在 S R 或 S E 中的某个样本的 g i 函数到达 0.计算集合 { : 0}, { : 0}.E RS S c cE i R iI i S I i S        那么 , 在集合 S R 或 S E 中的某个样本移动到 S S 集合之前存在一个最大可能更新值 (3)  待删除样本 (x c ,y c ) 的系数  c =0.那么 , 可以在样本 (x c ,y c ) 的系数  c 到达 0 之前存在一个最大可能更新值 :,max , .gcc cccg        最后 ,3 个值中的最小值 :,min ,max{ , , }R ESSS gc c c c         (10)将构成   c 的最小调整量 .基于   c 的最小调整量的计算法则 , 当一个样本 (x c ,y c ) 从训练集合 S 中删除时 , 收缩样本集的最优解可以通过算法 2 求解获得 .算法 2 .  减量式标准支持向量机算法 .输入 :S,(x c ,y c ),  S ;输出 :-{( , )} .c cS x y1.  如果待删除样本 (x c ,y c ) 的系数  c =0, 那么算法结束 ;2.  否则 , 应用最小调整量min ,c  使得恰好有一个样本在 S R ,S S 和 S E 间移动 ;3.  更新矩阵 R, 如果  c =0, 那么跳到步骤 1; 否则 , 跳到步骤 2.1.5 矩阵R的更新 c 的调整将改变边缘支持向量集 S S , 所以矩阵 R 相应地也会发生调整 . 对于集合 S S 的变化有以下两种情形 :第 1 种是增加一个样本到集合 S S ;第 2 种是从集合 S S 移出一个样本 .对于第 1 种情形 , 矩阵 R 根据如下规则扩展 :0 1,0 01 1S STt tb bt tS SttRR                        其中 ,t 代表增加到集合 S S 的一个样本 .对于第 2 种情形 , 矩阵 R 根据如下规则进行收缩 :i,jS S , 并且 it,jt, 有1,ij ij tt it tjR R R R R  其中 ,t 代表集合 S S 中一个移出的样本 .2 可行性分析为了说明 C&P 算法 ( 增量式支持向量机算法和减量式支持向量机算法 ) 的每步计算是可靠的 , 需要回答绝缘更新过程中一些关键的问题 , 这些问题具体包括 :1) 在调整  c 过程中 , 边缘支持向量集 S S 始终不为空 ( 定理 1);2) 矩阵 Q 始终存在逆矩阵 ( 定理 2);3) 对矩阵 R 的更新策略是正确的 ( 定理 3);4) 向边缘支持向量集 S S 新加入 ( 移出 ) 一个样本 t 后 , 在紧接着的调整中 ,t 不会反向移出 ( 加入 ) 边缘支持向量集 S S ( 定理 4 和定理 5).需要说明的是 : 首先 , 增量式标准支持向量机算法 ( 算法 1) 和减量式标准支持向量机算法 ( 算法 2) 使用相同的绝缘更新法则 , 故本节在证明过程中并没有明显区分这两种算法 , 并且本节所证明的结论对于这两种算法都成立 ; 其次 , 定理 1 和定理 4 在文献 [12] 的第 4 节中已有证明 , 本文为了全面探讨 C&P 算法的可行性 , 重新组织了其证明过程 ; 最后 , 除了定理 1 和定理 4, 其余结论皆为本文的工作 .定理 1 .  在  c 的调整过程中 , 边缘支持向量集 S S 始终不为空 .证明 : 如果 S S =, 可以改变 b 的值使一个样本移入集合 S S , 从而使 S S 不为空 . 这样 , 需要考虑改变 b 值的方向 ,使得移入 S S 的样本在接下来的调整中不会移出 . 假设 S S ={(x t ,y t )}, 根据公式 (5) 可以证明 ,ct 的正负号由 y t y c 决定 ; 再结合公式 (2), 可得 b 值的改变方向必须为 y c 才能保证移入 S S 的样本在接下来的调整中不会移出 . 据此 , 又定义可行性条件 { : 0}, { : 0}.R ES SR i c E i cI i S y y I i S y y         那么 , 在 S R 或 S E 中的一个样本移入 S S 之前 , 最大可能的 b 的绝对值可以表示为,| | min | |R ES SRES Sii I Ib g    ; 在候选样本 c 移入 S S 之前 , 最大可能的 b 的绝对值可以表示为 |b c |=g c , 那么 b 的最后改变值为, *min{| |,| |}R ES S ccb y b b     . 定理得证 .  □引理 1 .  矩阵 Q 是半正定的 .证明 : 令  =(  1 ,…,  n )0, 那么有1 1 1 1( ) ( ) 0.n n n nTi j ij i i i i i ii j i iQ Q y x y x                       ≥引理得证 .  □假设 1 : 矩阵 Q 是正定的 .如引理 1 的证明 , 当且仅当 { y 1  ( x 1 ),…, y n  ( x n )} 是线性无关时 , 矩阵 Q 才是正定的 . 而实际上 ,{ y 1  ( x 1 ),…,y n  ( x n )} 是线性相关的可能性是相当小的 [2] . 例如 , 如果2|| ||( , ) ei jx xi jK x x , 其中 , x i  x j , 那么矩阵 Q 便是正定的 , 因为矩阵 Q 的行数和列数相比较被核函数影射到的空间维数是相当小的 , 所以矩阵 Q 趋向于正定 , 故假设 1 一般情况下成立 [2] .定理 2 .  矩阵 Q  始终存在逆矩阵 .证明 : 根据定理 1 可知 , 在调整  c 的过程中 , 集合 S S 始终不为空 , 则不失一般性 , 假设 S S 存在 n 个样本 , 那么 ,1def1 11 1100.nTnn n nny yy Q Q yQy Qy Q Q             通过假设 1 可知 Q 正定 , 那么必存在 Q 1 , 并且 Q 1 也是正定的 .因为1 11 0 00T T T Tny Q y y Q yI y Q y Q                   ,所以有 det( Q )=det( Q )( y T Q 1 y )0,那么易知 , 矩阵 Q  始终存在逆矩阵 .  □引理 2 .  当向集合 S S 增加一个样本 t 时 , 相应地 , 0.tt 证明 : 首先证明结论 ( ) ( ) 0.Stt t j j jj Sy x y x    假设结论不成立 , 那么有 ( ) ( ),Stt t j j jj Sy x y x      把它带入公式 (6), 可以得到 0,ct  这与前提条件向集合S S增加一个样本 t 相矛盾 . 基于此 , 进一步有                                                       2( ) ( ) 0.SSj Stt t j j jj Sy x y x                       □引理 3 .  当向集合 S S 移出一个样本 t 时 , 相应地 , R tt >0.根据逆矩阵的定义和假设 1, 可以很容易地得出该结论 .定理 3 .  对于集合 S S 增加一个样本或移出一个样本 t 的两种情形 , 其相应的矩阵 R 的两种更新策略均是正确的 .证明 : 对于集合 S S 增加一个样本 t , 我们可以证明 :11 11 1 11 1111000 1 10 0 00 0 01 1Tt tn tt tn tttt tn n nn ntn nt t tn tty y yy Q Q QR IQ Ry Q Q Qy Q Q Q                                                                                          0 0 0 00 0 0 0I 0,0 10 0 0 00 0 0tttt                其中 , 等号 1 应用了公式 (6),I 为相应的单位矩阵 . 对于集合 S S 移出一个样本 t, 我们可以证明 :\ * * \ \ * * \( ) ( )tt t t tt tt t t ttttQQ R Q R R R Q R Q R IR             □定理 4 .  向集合 S S 新加入一个样本 t 后 , 在紧接着的调整中 t 不会反向移出集合 S S .证明 : 假设前面一次调整记为 k, 则下次调整记为 k+1, 那么有 ,[ 1][ 1]1 11 1 1[ 1][ 1][ 1]0100 0 01 1Tk t tc cb bk t tc ckttk t tnc ncn n nktc tcty yQ QRRQ QQ Q                                                                                            [ ] [ ][ ] [ ]11 1 1 1 1[ ] [ ]10 1 1 0 1Tk t t k tcb b b b bk t t k tctct tt tk t t k tncn n n n ntcyQQQ                                                                                                        .      于是有 ,[ 1].ktcttt 又因为                         所以 ,[ 1].kctttt 这意味着向集合 S S 新加入一个样本 t 后 , 在紧接着的调整中 ,t 不会反向移出 S S . 因为对于 t 加入 S S 有两种方式 : 一是从 S R 移向 S S , 二是从 S E 移向 S S . 对于第 1 种方式 , 有 0, 0k kt tg    且 0kt  , 那么通过引理 2 可得[ 1]0kt ;对于第 2 种方式 , 有 , 0k kt tC g    且 0,kt  那么通过引理 2 可得[ 1]0kt . 所以在紧接着的调整中 ,t 不会反向移出 S S .  □定理 5 .  从集合 S S 移出一个样本 t 后 , 在紧接着的调整中 ,t 不会反向加入集合 S S .证明 : 假设前面一次调整记为 k, 则下次调整记为 k+1, 那么有 : [ 1]1 1 1[ 1]1 1 111[ 1]( 1) ( 1)1[ ]1[ ]1 21kb c ct t t tnkc c kn nttnt t nt tnkn c n cnkb t tckt tcny yR R R RQ QR RRR R R RQ QR QR Q                                                        [ 1] [ 1][ ]1 1[ ]2 2[ ][ ]1[ 1] 1 11 1 11,( ) ( ) (tttk kS Skt t tt tckt k tt tcttkknt tcnt t nt tt tck k k k k ktt tc tj j t tc tj j j t tc t t tc ttt j S j SR R R QR R R QRR QR R R QyQ Q y Q Q R Q y R Q RR                                        [ 1] [ 1]11 1 11 2)1( ) ,k kS St tt tck kk ct ttj j t j tt tc t tt tt tj jt t ttt tt tt j S j SR R QQ R R R Q Q R Q R y RR R R                          其中 , 等号 1 应用了ct 的定义 , 等号 2 应用了等式[ 1]11kStt tt tj jt t tj SQ R Q R y R  . 类似于定理 4 后面的分析 , 可以得出结论 : 从集合 S S 移出一个样本 t 后 , 在紧接着的调整中 t 不会反向加入集合 S S .  □3 有限收敛性分析有限收敛性将确保 C&P 算法 ( 增量式支持向量机算法和减量式支持向量机算法 ) 在有限步后收敛到问题的最优解 . 在证明过程中 , 我们首先证明了增量式支持向量机算法在绝缘调整过程中 , 目标函数 W 是严格单调递减的 ( 见定理 6); 而减量式标准支持向量机算法在调整过程中 , 目标函数 W 是严格单调递增的 ( 见定理 7). 在此基础上 , 证明了增量式支持向量机算法和减量式标准支持向量机算法经过有限步迭代后 , 将收敛于相应问题的最优解 ( 见定理 7).引理 4 .  在绝缘更新过程中 ,iS S , ,ci证明 : 根据公式 (5),iS S , 我们有               假设存在一个样本 iS S , 使得 ,ci   那么必然有 det(Q)=0, 这与定理 2 相矛盾 . 所以 iS S , ;ci   并根据公式 (6), 也有 iSS S , .ci    □引理 5 .  对于增量式标准支持向量机算法 , 相应的最大调整量max0;c   对于减量式标准支持向量机算法 ,相应的最小调整量min0.c  根据第 1.3 节和第 1.4 节的内容以及引理 4, 较容易推导出引理 5 的结论 .定理 6 .  对于增量式标准支持向量机算法 , 调整过程中 , 目标函数 W 是严格单调递减的 .证明 : 假设前面一次调整记为 k, 则下一次调整记为 k+1, 并令 0, 0,R ES S     c =1, 那么有 ,1 1 2 2 1 21 2[ 1] [ ] [ ] [ ] [ ] [ ] [ ],[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ][ ] [ ] [ ] [ ] [ ] [1( )( )2( ) ( ) ( )12k k k k k k ki i c i i c i ii i Sk k k k k k k k kb c i i i c i i ci S i Sk k k k ki i c i ii S i SW Qb yW g                                    ] [ ] 2[ ] [ ] [ ] [ ] [ ] 2[ ] [ ] [ ] [ ] [ ]( )1( )212.k kck k k k kc c c ck k k k kc c c cW gW g             容易验证[ ] [ ] [ ]012,k k kc c cg      因此根据引理 5 可知 ,W [K+1] W [K] <0.  □定理 7 .  对于减量式标准支持向量机算法 , 调整过程中 , 目标函数 W 是严格单调递减的 .证明 : 假设前面一次调整记为 k, 则下一次调整记为 k+1, 与定理 6 的证明相似 , 我们可以证明出相似的结论 :[ 1] [ ] [ ] [ ] [ ] [ ]12.k k k k k kc c c cW W g         在减量式标准支持向量机算法的调整过程中 , 有[ ] [ ] [ ]0, 0, 0.k k kc c cg      ≤故 W [K+1] W [K] >0. 定理得证 .  □定理 8 .  对于增量式标准支持向量机算法以及减量式标准支持向量机算法 , 经过有限步迭代后 , 将收敛于相应问题的最优解 .证明 : 关于增量式标准支持向量机算法以及减量式标准支持向量机算法有限收敛性的证明 , 下文仅针对增量式标准支持向量机算法给出了证明 , 相似地 , 可以证明减量式标准支持向量机算法的有限收敛性 .如果[1] [2] [3] [1] [2] [3], , ,...), , , ( ( ,...)c c c c c cg g g    ,(W [1] ,W [2] ,W [3] ,…) 被定义为增量式标准支持向量机算法调整过程中生成的 3 个序列 , 那么为了证明定理 , 我们只需证明序列[1] [2] [3], , ( ,...)c c c   和[1] [2] [3], , ( ,...)c c cg g g 是有限序列且收敛到问题对应的 KKT 条件 .假设[ ] [ ]), ) ( (k kc cg  和 (W [K] ) 序列是 3 个无限序列 , 由定理 6 我们有 W [K] =W [K+1] W [K] <0, 那么 (W [K] ) 必须是一个无限的单调递减序列 . 进一步地 , 易证每个 W [K] 对应着唯一一个边缘支持向量集 S S , 而边缘支持向量集 S S 的组合数是有限的 , 所以 (W [K] ) 序列是一个有限序列 . 因此[ ]( )kc 和[ ]( )kcg 也是有限序列 , 它们可以表示为[1] [2], , (c c [ ].., ) .c和[1] [2] [ ], ,..., ) (c c cg g g. 根据引理 4 和引理 5, 容易验证[ ]0kc   和[ ] [ ] [ ]0,k k kc c cg       那么[1] [2] [ ], ,..., ) (c c c  和[1] [2] [ ], ,..., ) (c c cg g g是两个有限单调递增序列 .接下来 , 假设[1] [2] [ ], ,..., ) (c c c  和[1] [2] [ ], ,..., ) (c c cg g g不收敛到问题对应的 KKT 条件 , 也就是[ ]cC  并且[ ]0,cg 而这与绝对增量调整终止在第  步的调整事实不符 . 因此 , 序列[1] [2] [ ], ,..., ) (c c c  和[1] [2] [ ], ,..., ) (c c cg g g收敛到问题对应的 KKT 条件 .  □

    4 实 验

    本文基于 MATLAB 实现了增量式标准支持向量机算法 (incremental support vector machine, 简称 ISVM) 和减量式标准支持向量机算法 (decremental support vector machine, 简称 DSVM). 实验中 , 对可行性与有限收敛性分析中的主要结论都分别作了验证 , 这些结论包括 :1)  边缘支持向量集 S S 不为空 ;2)  矩阵 Q 始终存在逆矩阵 ;3)向边缘支持向量集 S S 新加入 ( 移出 ) 一个样本 t 后 , 在紧接着的调整中 t 不会反向移出 ( 加入 ) 边缘支持向量集 ;4)ISVM 和 DSVM 在有限步内能收敛到相应问题的最优解 .所有实验在 3.2GHz,Pentium-4, 具有 1GB 的内存和 MATLAB7.5 平台的机器上进行 . 表 1 给出了在实验中使用的 4 个标准数据集的特性 ( 这些数据集可以从 http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ 获得 ).实验中使用了 3 种核函数 , 分别为 : 线性 (linear) 核 K(x i ,x j )=x i ,x j ; 多项式 (polynomial) 核 K(x i ,x j )=(x i ,x j +1) d , 其中 ,d=2; 高斯 (Gaussian) 核 K(x i ,x j )=exp(||x i x j || 2 /2  2 ), 其中 ,  =0.707. 

    4.1 Sonar数据Sonar 数据集的任务是区别来自金属圆筒返回的声纳信号还是来自粗糙的圆柱形岩石返回的声纳信号 . 该数据集包含具有 60 个连续数值属性的 208 个实例样本 .为了说明在 ISVM 和 DSVM 学习中边缘支持向量集 S S 不为空、矩阵 Q 存在逆矩阵以及向边缘支持向量集 S S 新加入 ( 移出 ) 一个样本 t 后 , 在紧接着的调整中 ,t 不会反向移出 ( 加入 ) 边缘支持向量集 , 实验分别在数据量为 50,100,150,200 的基础上 , 分别尝试 200 次 ISVM 和 DSVM 学习 , 测试结果均验证了上述的结论 . 图 1 说明了ISVM 和 DSVM 在不同训练数据大小情况下的平均迭代次数 , 数据结果验证了算法的有限收敛性 , 尤其是算法在高斯核下具有更快速的收敛性 .Fig.1 Average numbers of iterations on Sonar dataset图 1 Sonar 数据集上的平均迭代次数

    4.2 Ionosphere数据Ionosphere 数据集收集来自 16 个高频天线的相控阵的雷达数据 . 数据的目标是来自大气层的自由电子 , 数据的标签是 “ 好 ”(“ 好 ” 表示雷达数据反映了大气层的结构 ) 和 “ 坏 ”. 这个数据集包含具有 34 个连续数值属性的351 个实例样本 .实验分别在数据量为 80,160,240,320 的基础上 , 分别尝试 200 次 ISVM 和 DSVM 学习 , 测试结果验证了如下的结论 : 边缘支持向量集 S S 不为空、矩阵 Q 存在逆矩阵以及向边缘支持向量集 S S 新加入 ( 移出 ) 一个样本 t后 , 在紧接着的调整中 ,t 不会反向移出 ( 加入 ) 边缘支持向量集 . 图 2 说明了 ISVM 和 DSVM 在不同训练数据大小情况下的平均迭代次数 , 数据结果验证了算法的有限收敛性

    4.3 Diabetes数据Diabetes 数据集是给 21 岁及以上皮玛族裔本土美国妇女的诊断信息 . 该数据集由 768 位妇女的诊断信息构成 , 其中 ,268 个病人被诊断为患糖尿病 , 而另 500 人被诊断为非患糖尿病 . 数据集拥有 8 个特征 , 其中 6 个特征是各种临床检测的连续数值属性 , 剩下的 2 个属性是年龄和怀孕次数的离散数值信息 .实验分别在数据量为 170,340,510,680 的基础上 , 分别尝试 200 次 ISVM 和 DSVM 学习 , 测试结果验证了如下的结论 : 边缘支持向量集 S S 不为空、矩阵 Q 存在逆矩阵以及向边缘支持向量集 S S 新加入 ( 移出 ) 一个样本 t后 , 在紧接着的调整中 ,t 不会反向移出 ( 加入 ) 边缘支持向量集 . 图 3 说明了 ISVM 和 DSVM 在不同训练数据大小情况下的平均迭代次数 , 数据结果验证了两种算法的有限收敛性

    4.4 Breast cancer数据Breast cancer 数据集来自 Wolberg 博士的临床病例 , 因此数据反映了病例的时间先后信息 . 该数据集包含具有 10 个数值属性的 683 个实例样本 .实验分别在数据量为 150,300,450,600 的基础上 , 分别尝试 200 次 ISVM 和 DSVM 学习 , 测试结果验证了 :边缘支持向量集 S S 不为空 ; 矩阵 Q 存在逆矩阵 ; 向边缘支持向量集 S S 新加入 ( 移出 ) 一个样本 t 后 , 在紧接着的调整中 ,t 不会反向移出 ( 加入 ) 边缘支持向量集 . 图 4 说明了 ISVM 和 DSVM 在不同训练数据大小情况下的平均迭代次数 , 数据结果验证了算法的有限收敛性 . 同时 , 算法在高斯核下也具有更快速的收敛性

    5 结 论

    C&P 算法是一种精确的增量式和减量式支持向量机算法 , 在留一估计、受限制学习 ( 内存有限 ) 、在线学习等任务中有着广泛的应用前景 . 为了更好地认识该算法 , 本文从理论上较为全面地分析了 C&P 算法的可行性与有限收敛性 , 并通过实验数据验证了理论分析的结果 , 为全面认识 C&P 算法开展了富有成效的工作 .本文的分析主要针对 C&P 算法 , 也可以扩展到其他基于 KKT 等价条件的支持向量机算法 , 例如回归支持向量机的增量式和减量式算法 [18] 、标准支持向量机的解路径算法 [19] 、回归支持向量机的解路径算法 [20] 等 .本文讨论的增量式和减量式标准支持向量机算法 (C&P 算法 ) 有一个隐含的假设 , 即假设每次仅有一个样本到达或离开边界 . 然而 , 算法在实际计算过程中是否有多个样本同时到达或离开边界 ? 这个回答是显然的 . 在进一步的工作中 , 希望针对该情形给出相应健壮的更新策略 , 并进一步回答算法的可行性以及有限收敛性 .

    References :[1] Vapnik V. Statistical learning theory. In: Wiley Series on Adaptive and Learning Systems for Signal Processing Communicationsand Control. John Wiley & Sons, 1998.[2] Lin CJ. On the convergence of the decomposition method for support vector machines. IEEE Trans. on Neural Network, 2001,12(6):12881298. [doi: 10.1109/72.963765][3] Frieß TT, Cristianini N, Campbell C. The kernel-adatron algorithm: A fast and simple learning procedure for support vectormachines. In: Proc. of the ICML’98. San Francisco: Morgan Kaufmann Publishers, 1998. 188196. http://www.isn.ucsd.edu/pubs/nips00_inc.pdf[4] Tsang IW, Kwok JT, Lai KT. Core vector regression for very large regression problems. In: Proc. of the ICML 2005. 2005.912919. [doi: 10.1145/1102351.1102466][5] Zhang T. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In: Proc. of the ICML 2004.2004. 919926. [doi: 10.1145/1015330.1015332] [6] Lee S, Wright SJ. ASSET: Approximate stochastic subgradient estimation training for support vector machines. In: Proc. of theInt’l Conf. on Pattern Recognition Applications and Methods. 2012. 223228. http://pages.cs.wisc.edu/~sklee/papers/asset_icpram12.pdf[7] Mangasarian OL, Musicant DR. Successive overrelaxation for support vector machines. IEEE Trans. on Neural Networks, 1999,10:10321037. [doi: 10.1109/72.788643][8] Joachims T, Finley T, Yu CNJ. Cutting-Plane training of structural SVMs. Machine Learning, 2009,77(1):2759. [doi: 10.1007/s10994-009-5108-8][9] Teo CH, Vishwanthan SVN, Smola AJ, Le QV. Bundle methods for regularized risk minimization. The Journal of MachineLearning Research, 2010,11(1):311365.[10] Franc V, Sonnenburg S. Optimized cutting plane algorithm for support vector machines. In: Proc. of the Int’l Conf. on MachineLearning. 2008. 320327. [doi: 10.1145/1390156.1390197][11] Cauwenberghs G, Poggio T. Incremental and decremental support vector machine learning. In: Advances in Neural InformationProcessing Systems 13. MIT Press, 2001. http://www.isn.ucsd.edu/pubs/nips00_inc.pdf[12] Laskov P, Gehl C, KrAuger S, Mäuller KR, Bennett K, Parrado-Hern E. Incremental support vector learning: Analysis,implementation and applications. Journal of Machine Learning Research, 2006,7(9):19091936.[13] Gu B, Wang JD, Chen HY. On-Line off-line ranking support vector machine and analysis. In: Proc. of the Int’l Joint Conf. onNeural Networks (IJCNN 2008). IEEE Press, 2008. 13641369. [doi: 10.1109/IJCNN.2008.4633975][14] Karasuyama M, Takeuchi I. Multiple incremental decremental learning of support vector machines. IEEE Trans. on NeuralNetworks, 2010,21(7):10481059. [doi: 10.1109/TNN.2010.2048039][15] Gu B, Wang JD, Yu YC, Zheng GS, Huang YF, Xu T. Accurate on-line ν-support vector learning. Neural Networks, 2012,27:5159. [doi: 10.1016/j.neunet.2011.10.006][16] Kuhn HW, Tucker AW. Nonlinear programming. In: Proc. of the 2nd Berkeley Symp. Berkeley: University of California Press,1995. 481492. http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bsmsp/1200500249[17] Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004.[18] Ma JS, Theiler J, Perkins S. Accurate on-line support vector regression. Neural Computation, 2003,15(11):26832703. [doi: 10.1162/089976603322385117][19] Hastie T, Rosset S, Tibshirani R, Zhu J. The entire regularization path for the support vector machine. The Journal of MachineLearning Research, 2004,5(10):13911415.[20] Gunter L, Zhu J. Efficient computation and model selection for the support vector regression. Neural Computation, 2007,19(6):16331655. [doi: 10.1162/neco.2007.19.6.1633]