支持向量機子問題的算法研究

付三平，于 靜，韓叢英

（山東科技大學信息科學與工程學院，山東青島266590）

1 預備知識

考慮以下支持向量機模型

其中y＝［y1，…∈｛－1，1｝，α＝［α1，…αn] ，α∈Rn為列向量，e＝（1，…，1）T∈Rn，C≥0，可以根據具體實驗取值，但大多數情況下取C＝10，G是實對稱半正定矩陣，且Gij＝yiyjK（αi，αj），i，j＝1，…，n，函數K：Rn×Rn→R為核函數．常用核函數有：多項式核函數：K（s，t）＝（1＋sTt）d，高斯核函數：K（s，t）＝，e＝2．718 28…，σ∈R且不為零．E．Osuna［1]奠定了工作集方法的理論基礎，隨后產生了SVMlight［2]和libSVM［3]算法，并且被廣泛應用．然而，工作集方法在算法的收斂速度和每個迭代步求解二次規劃子問題的計算代價之間不易取得平衡．鑒于工作集方法的缺陷，2003年Zanni［4]等人提出將SVMlight算法中的二次規劃子問題并行求解．2006年，Serafini［5]等人對文獻［4] 作了詳細的論述，文獻［5] 中給出了其他迭代步的詳細并行求解思路，大大提高了算法效率．本文是在工作集方法和并行化方法結合的基礎上，不直接利用投影梯度法求子問題，而是采用乘子罰函數［6－7]先將子問題轉化成只含界約束的二次規劃問題［8－10]，再利用有限記憶擬牛頓（BFGS），方法［11－12]求解界約束優化問題．

2 分解技術及全局算法

文獻［4－5] 給出了問題（1）的全局分解解法，算法中變量αi被分成兩種類型：αB集合代表自由（基）變量，αN集合代表固定（非基）變量．集合B稱為工作集，集合N稱為非工作集．根據集合B和N把α，y，G，e分解成如下：

算法1

步1：令α1是（1）式的初始可行點，nsp，nc為兩個整數，且n≥nsp≥nc≥0，nc為偶數．任意選擇nsp作為工作集B的指標且令k＝1．

步2：計算GBB的元素，令q＝－eB，t＝－．

步3：解決子問題．其中αB∈Rnsp，

0≤αi≤C，i∈B

步4：更新梯度．▽f（αk＋1）＝▽f（αk）＋如果滿足KKT條件，則終止；否則，轉步5．

步5：更新工作集B．解出下面關于d的解，找出其元素不為零的指標，

di≥0，使得＝0

di≤0，使得＝C，｜｛di｜di≠0｝｜≤nc．

算法1的詳細步驟見參考文獻［5] ．本文的重點是對步3中的子問題求解進行修改，下面給出步3中子問題的解法及其收斂性的證明．

3 子問題的解法及收斂性

3．1 求解子問題算法

對子問題（2）式，記其增廣拉格朗日函數為g（αB，λ，σ），則

其中Q＝GBB＋＝q－λyB－σtyB，c＝λt＋．令x＝αB，x∈，則（2）式可以變形成如下形式的優化問題：

算法2

步1：初始化．x0∈為給定初始點，λ0為初始乘子，σ0為初始罰因子且為非負實數，常數a＞1，η∈（0，1），精度ε＞0．令k＝1．

步2：以xk為初始點，求解界約束問題（3）式，得到一個解xk＋1．

步5：λk＋1＝λk－，令k＝k＋1，轉步2．

3．2 算法2的收斂性

把子問題（2）式寫成如下一般形式：

定理1 假設原問題（4）式的可行域為X且非空，如果｛λk｝有界，則算法1或者有限終止或者產生的點列｛xk｝的任何聚點是原問題的解．

證明 反證法．假設定理不成立，即算法不有限終止且產生點列存在某個聚點不是原問題的解．設x是原問題的可行點，則h（x）＝0．由xk＋1的定義，則

得

令f＊表示原問題的最優解，那么f＊＝（x）．對（5）式兩邊同時關于x求下確界得

因為｛λk｝有界，所以必存在上極限點假設λk→．假設是｛xk｝的任意聚點，由f（x）和h（x）的連續性，對（6）式兩邊取上極限，

由于算法不有限終止，所以σk→∞．為了使（7）式成立，h（xk＋1）→0，即＝0．

因為原問題的可行域是有界閉集，則ˉx是可行點，f＊≤．可得

所以點列｛xk｝的任何聚點是原問題（4）式的解，與假設矛盾，定理得證．

4 有限BFGS方法求解界約束優化問

在算法2中，把（3）式抽象成一般的界約束優化模型：

其中F：Rnsp→R是連續可微的，x，l，u∈Rnsp且l＜u（在本文中li＝0，ui＝C）．針對（8）式的求解，利用文獻［9] 中的修正子空間有限記憶BFGS方法．其主要思想是用積極集法把變量分成有效變量和非有效變量，再使用修正的有限記憶BFGS方法更新有效變量．（8）式求解過程參考文獻［9] 的算法2．1．

5 結束語

本文主要介紹了一種求解大規模支持向量機問題分解算法，對子問題，利用增廣拉格朗日函數將二次規劃子問題的求解轉化成只含界約束的二次規劃求解．利用修正的子空間有限記憶BFGS算法求解界約束問題，不僅節約了內存而且提高了計算效率．當外部循環次數比較大時，每一次迭代中子問題的求解對于整個問題的優化至關重要．

［1] Osuna E，Freund R，Girosi F．An improved training algorithm for support vector machines．Proceedings of IEEE Workshop on Neural Networks and Signal Processing［J] ．Amelia Island，1997：276－285．

［2] Joachims T．Maling large－scale SVM learning practical［C] ／／Massachusettes Intitute of Technology press，1999：169－184．

［3] Chih C C，Chih J L，LIBSVM：A library for support vector machines［EB／OL] ．（2001）［2011－11－9] ．http：／／www，csie，ntu．edu．tw／－cjlin／libsvm．

［4] Zanghitati G，Zanni L．A parallel solover for large quadratic programs in training support vector machines［J] ．Parallel Computer，2003，29：535－551．

［5] Zanni L，Serafini T，Zanghitati G，Parrllel sofeware for training large scale support vector machines on multiprocessor system［J] ．Journal of Machine Learning Research，2006，7：1 467－1 492．

［6] 袁亞湘，孫文瑜．最優化理論與算法［M] ．北京：科學出版社1997．

［7] Gasimov R N．Augmented lagrangian duality and nondifferentiable optimization methods in nonconvex programming［J] ．Journal of Global Optimization，2002，24，187－203．

［8] Xiao Y H，Li D H．An active set limited memory BFGS algorithm for largescale bound constrained optimization［J] ．Mathematical Methods of Operations Research，2008，67：443－454．

［9] Xiao Y H，Zhang H C．Modified subspace limited memory BFGS algorithm for large－scale bound constrained optimization［J] ．Journal of Computational and Applied Mathematics，2008，222：429－439．

［10] Xiao Y H，Wei Z X．A new subspace limited memory BFGS algorithm for large－scale bound constrained optimization［J] ．Applied Mathematics and Computation，2007，185：350－359．

［11] Xiao Y H，Wei Z X，Wang Z G．A limited memory BFGS－type method for large－scale unconstrained optimization［J] ．Journal of Computational and Applied Mathematics，2008，56：1 001－1 009．

［12] Byrd R H，Nocedal J，Schnabel R B．Representations of quasinewton matrices and their use in limited memory methods［J] ．Mathematical Programming，1994，63：129－156．