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

付三平，于 靜，韓叢英

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

1 預備知識

考慮以下支持向量機模型

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

2 分解技術(shù)及全局算法

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

算法1

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

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

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

0≤αi≤C，i∈B

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

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

di≥0，使得＝0

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

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

3 子問題的解法及收斂性

3．1 求解子問題算法

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

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

算法2

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

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

步5：λk＋1＝λk－，令k＝k＋1，轉(zhuǎn)步2．

3．2 算法2的收斂性

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

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

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

得

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

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

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

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

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

4 有限BFGS方法求解界約束優(yōu)化問

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

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

5 結(jié)束語

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

［1] Osuna E，F(xiàn)reund 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] 袁亞湘，孫文瑜．最優(yōu)化理論與算法［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．