趙長(zhǎng)春 姜曉愛

(北京航空航天大學(xué) 航空科學(xué)與工程學(xué)院，北京100191)

金英漢

(西北工業(yè)大學(xué)航天學(xué)院，西安710072)

支持向量機(jī)(SVM，Support Vector Machine)理論是Vapnik等人提出的一種新型的機(jī)器學(xué)習(xí)算法，在分類問題和回歸問題上應(yīng)用較廣泛.由于SVM訓(xùn)練中需要求解二次規(guī)劃問題，在訓(xùn)練大規(guī)模數(shù)據(jù)時(shí)占用內(nèi)存空間較大，文獻(xiàn)［1］提出了序列最小優(yōu)化(SMO，Sequential Minimal Optimization)算法，該算法將問題分解為每次優(yōu)化兩個(gè)樣本的Lagrange乘子，避免了求解二次規(guī)劃問題，提高了訓(xùn)練速度.文獻(xiàn)［2］詳細(xì)介紹了SMO回歸算法的實(shí)現(xiàn)方法，由于該算法訓(xùn)練時(shí)間較長(zhǎng)，出現(xiàn)了許多對(duì)SMO算法的改進(jìn)方法［3－5］，以縮短訓(xùn)練時(shí)間.此外，支持向量機(jī)的參數(shù)選擇對(duì)訓(xùn)練模型的精度和訓(xùn)練速度影響較大，通過選擇最優(yōu)的支持向量機(jī)參數(shù)可以提高訓(xùn)練模型的準(zhǔn)確度和訓(xùn)練效率［6－7］.參數(shù)優(yōu)化方法的實(shí)質(zhì)是利用測(cè)試樣本對(duì)訓(xùn)練模型測(cè)試的精度來判斷是否得到最優(yōu)參數(shù)，參數(shù)尋優(yōu)的過程就是不斷改變參數(shù)值和用新參數(shù)反復(fù)訓(xùn)練模型的過程.因此，研究提高算法自身的訓(xùn)練速度的方法，能在很大程度縮短訓(xùn)練時(shí)間.

本文對(duì)SMO算法的改進(jìn)方法進(jìn)行了研究，提出新的改進(jìn)算法用于非線性數(shù)據(jù)和非線性函數(shù)的回歸，通過改進(jìn)優(yōu)化乘子更新方法、采用雙閾值法、預(yù)存核函數(shù)、增加停機(jī)準(zhǔn)則等方法加快了訓(xùn)練速度，提高了訓(xùn)練結(jié)果穩(wěn)定性，最后對(duì)支持向量機(jī)參數(shù)選擇方法做了討論.

1 支持向量機(jī)回歸

支持向量機(jī)回歸的求解方法是將原始最小化問題轉(zhuǎn)化為求其對(duì)偶最大化問題，對(duì)于樣本集(xi，yi)，i=1，2，…，l，求解的對(duì)偶問題［2］可表示如下:

式中，ε為不敏感損失函數(shù)(示意圖見圖1);C為規(guī)則化參數(shù)，用于平衡回歸函數(shù)的平坦程度;αi，為拉格朗日乘子;k(x，x)=Φ(x)·Φ(x)，ijij記為kij，為滿足Mercer條件的核函數(shù)，Φ(·)為非線性映射.常用的核函數(shù)有線性核函數(shù)、多項(xiàng)式核函數(shù)、徑向基核函數(shù)、Sigmoid核函數(shù)等.

回歸函數(shù)可表示為

式中，b為閾值.

圖1中，ε用于控制回歸逼近誤差范圍，ξ≥0為松弛因子，表示回歸函數(shù)值f(xi)與樣本值yi之差的絕對(duì)值|f(xi)－yi|，當(dāng)絕對(duì)值小于或等于ε時(shí)，取0，當(dāng)絕對(duì)值大于ε時(shí)，取ξ.

圖1 ε不敏感損失函數(shù)示意圖

2 回歸SMO算法理論

作變量代換，令

SMO算法每次只優(yōu)化兩個(gè)變量，固定其他變量值，設(shè)2 個(gè)待優(yōu)化變量分別為，優(yōu)化目標(biāo)函數(shù)可表示成關(guān)于的函數(shù):

式中，η=kuu－2kuv+kvv，當(dāng)核函數(shù)滿足 Mercer條件時(shí)，η≥0成立.

3 SMO算法改進(jìn)

3.1 采用雙閾值blow和bup

文獻(xiàn)［3］中指出，由于閾值b正確性不確定，使得在優(yōu)化中對(duì)已達(dá)到最優(yōu)值的乘子更新，浪費(fèi)執(zhí)行時(shí)間，因此采用雙閾值blow和bup的方法對(duì)算法做了改進(jìn).

令Fi=yi－〈ω，Φ(xi)〉，其中〈·，·〉表示內(nèi)積，有以下5種情況:

根據(jù)式(9)和式(10)可定義b的上、下界，如下:

由于數(shù)值解原因，通常不可能獲得準(zhǔn)確的優(yōu)化結(jié)果，因此，通過增加一項(xiàng)正誤差τ獲取近似優(yōu)化結(jié)果，重新寫式(12)，如下:

查找違反最優(yōu)條件式(13)的樣本作為待優(yōu)化樣本，即滿足如下條件之一的樣本為待優(yōu)化樣本:

3.2 優(yōu)化乘子更新

由于Fu－Fv的值與b無(wú)關(guān)，通過其更新乘子可避免乘子優(yōu)化結(jié)果受不準(zhǔn)確的b值的影響，乘子更新步驟如下:

1)更新優(yōu)化乘子分下面3個(gè)步驟.

①按如下式子進(jìn)行更新:

②如果更新后兩個(gè)乘子符號(hào)相同則得到本次更新結(jié)果，反之，定義調(diào)節(jié)變量Δ=2ε/η，如果根據(jù)Δ更新后的乘子和符號(hào)不改變，按式(16)進(jìn)行:

③如果更新后的乘子符號(hào)發(fā)生改變，則設(shè)置乘子為0或sold，按如下條件進(jìn)行:

2)約束優(yōu)化乘子范圍.

3.3 停機(jī)準(zhǔn)則

目標(biāo)問題與其對(duì)偶問題的對(duì)偶間隙為0時(shí)，達(dá)到全局最優(yōu)解，但數(shù)值求解只能得到近似全局最優(yōu)解，因此將對(duì)偶間隙作為停機(jī)準(zhǔn)則，設(shè)定訓(xùn)練精度在達(dá)到預(yù)定值后停止計(jì)算［8－9］，減少訓(xùn)練時(shí)間.

定義如下關(guān)系:

記目標(biāo)優(yōu)化問題為函數(shù) U(ω，ξ，ξ*)，對(duì)偶問題為函數(shù)W()，則函數(shù)表達(dá)式為

停機(jī)準(zhǔn)則計(jì)算式為

當(dāng)σ小于給定精度后停止訓(xùn)練，能縮短訓(xùn)練時(shí)間，將σ停機(jī)準(zhǔn)則和式(14)的違反條件共同判斷停止訓(xùn)練條件.

3.4 核函數(shù)矩陣計(jì)算和存儲(chǔ)

在訓(xùn)練過程中，為避免重復(fù)計(jì)算核函數(shù)，訓(xùn)練開始時(shí)進(jìn)行核函數(shù)矩陣存儲(chǔ).核函數(shù)矩陣是對(duì)稱矩陣，存儲(chǔ)時(shí)只需存儲(chǔ)對(duì)稱部分，假設(shè)有N個(gè)樣本，則可用大小N(N+1)/2的一維數(shù)組aJ存儲(chǔ)核函數(shù)矩陣，從主對(duì)角元素開始按主對(duì)角線方向順序存儲(chǔ)矩陣元素，如圖2所示，元素kmn在矩陣中的位置與在數(shù)組aJ中位置對(duì)應(yīng)關(guān)系如下:

式中，J為一維數(shù)組元素的下標(biāo);m，n分別為核函數(shù)矩陣元素kmn的行號(hào)和列號(hào).核函數(shù)矩陣對(duì)稱，只需計(jì)算主對(duì)角線和其上方的元素，其下方的元素與上方元素對(duì)稱.規(guī)定m≤n，如果m＞n，交換m和n的值后再計(jì)算.

圖2 核矩陣元素存儲(chǔ)

3.5 改進(jìn)的SMO算法描述

改進(jìn)后的SMO算法具體步驟如下:

2)從整個(gè)樣本中隨機(jī)選擇一個(gè)樣本i，令blow=yi－ ε，bup=yi+ ε，ilow=i，iup=i.

3)SMO算法采用內(nèi)、外兩層循環(huán)選擇待優(yōu)化樣本，步驟如下:

4)優(yōu)化乘子更新步驟:采用3.2節(jié)乘子更新法更新優(yōu)化樣本的乘子.如果優(yōu)化乘子的改變量大于一定值，則更新優(yōu)化樣本乘子和界內(nèi)樣本的誤差值 Fi=yi－〈ω，Φ(xi)〉，并按式(11)在界內(nèi)樣本中尋找新的 blow，bup，ilow，iup.

5)在界內(nèi)樣本或所有樣本遍歷循環(huán)完成若干次迭代后計(jì)算一次停機(jī)準(zhǔn)則σ值.

6)為防止優(yōu)化程序出現(xiàn)死循環(huán)，當(dāng)滿足以下3個(gè)條件之一就結(jié)束算法:優(yōu)化成功的樣本數(shù)量為0、停機(jī)準(zhǔn)則σ小于給定精度、迭代次數(shù)大于給定次數(shù);如果沒有滿足條件的，則轉(zhuǎn)3).

4 仿真實(shí)驗(yàn)及結(jié)果分析

將改進(jìn)的算法與原始的SMO算法做對(duì)比，實(shí)驗(yàn)使用兩個(gè)不同的擬合數(shù)據(jù).通過對(duì)比達(dá)到相同停機(jī)準(zhǔn)則時(shí)的時(shí)間和測(cè)試均方根誤差(RMSE，Root Mean Square Error)來評(píng)價(jià)兩個(gè)算法的優(yōu)越性，RMSE表達(dá)式為

式中，N為測(cè)試樣本總數(shù);yi為樣本目標(biāo)值;為回歸值.

4.1 仿真實(shí)驗(yàn)1

選取文獻(xiàn)［10］中的訓(xùn)練樣本作為算例，該數(shù)據(jù)具有非線性特點(diǎn)，樣本如下:

所選擇的測(cè)試樣本如下:

選用徑向基核函數(shù)，表達(dá)式如下:

參數(shù)設(shè)置基本原則:優(yōu)化的參數(shù)對(duì)(C，γ2)的組合有很多［7］，樣本數(shù)據(jù)變動(dòng)趨勢(shì)較平坦時(shí)，γ2取較大值，常取大于1的值;反之，取較小值，常取小于1的值;C值用于平衡回歸函數(shù)平坦程度，一般取樣本均值附近的值;ε控制回歸函數(shù)逼近誤差范圍，根據(jù)實(shí)際需求取值;較小的τ值會(huì)增加訓(xùn)練時(shí)間，取值應(yīng)當(dāng)比ε取值小1～2個(gè)數(shù)量級(jí);σ取值決定了訓(xùn)練精度，不宜過小，否則會(huì)增加訓(xùn)練時(shí)間.

根據(jù)上述基本原則和多次實(shí)驗(yàn)設(shè)置參數(shù):C=4，γ2=2.1，ε =0.3，τ=0.000 1.采用在不同停機(jī)準(zhǔn)則值下所用的訓(xùn)練時(shí)間和RMSE值作對(duì)比，表1為2種算法的對(duì)比.

表1 2種算法比較

從表1可以看出，與原始算法相比，改進(jìn)后的算法訓(xùn)練時(shí)間明顯縮短，但隨著停機(jī)準(zhǔn)則σ值減小而增加，因?yàn)橥C(jī)準(zhǔn)則σ值越小表示對(duì)偶間隙值越小，則訓(xùn)練時(shí)間會(huì)增加;2種算法的RMSE值隨停機(jī)準(zhǔn)則σ值減小而減小，在相同訓(xùn)練精度條件下，改進(jìn)的算法能有效加快訓(xùn)練速度.

用改進(jìn)的SMO算法訓(xùn)練非線性數(shù)據(jù)的回歸結(jié)果如圖3所示，從圖中可看出，SMO算法對(duì)非線性數(shù)據(jù)擬合效果較好.

4.2 仿真實(shí)驗(yàn)2

選擇函數(shù)進(jìn)行擬合，函數(shù)表達(dá)式如下:

產(chǎn)生100個(gè)隨機(jī)數(shù)點(diǎn)X，代入式(26)得到Y(jié)，組成訓(xùn)練樣本(X，Y)，產(chǎn)生100個(gè)點(diǎn)隨機(jī)數(shù)Xt，代入式(26)得到 Yt，組成測(cè)試樣本(Xt，Yt).

圖3 非線性數(shù)據(jù)回歸結(jié)果(C=4，γ2=2.1)

選用徑向基核函數(shù)，根據(jù)參數(shù)選擇基本原則和多次實(shí)驗(yàn)設(shè)置參數(shù):σ = －2，ε =0.01，τ =0.001.分別固定C值和固定γ2值，在這2種情況下對(duì)比2種算法的支持向量數(shù)目、訓(xùn)練時(shí)間、RMSE值.

從表2、表3可以看出，能得到較小RMSE值的最佳C值為1～1.5之間，最佳 γ2值為0.1;選取最佳 C和 γ2時(shí)，2種算法都能得到較小的RMSE值和較少的支持向量，較小的γ2值和較大的C值都會(huì)增加訓(xùn)練時(shí)間;與原始SMO算法相比，在達(dá)到相同的訓(xùn)練精度條件下，改進(jìn)的算法明顯縮短訓(xùn)練時(shí)間;原始算法使用了隨機(jī)選擇優(yōu)化樣本的方法，所以訓(xùn)練結(jié)果不穩(wěn)定，同時(shí)也增加了訓(xùn)練時(shí)間，而改進(jìn)后的算法使訓(xùn)練結(jié)果具有穩(wěn)定性，使訓(xùn)練速度更快.

用改進(jìn)的SMO算法對(duì)非線性函數(shù)回歸的結(jié)果見圖4，從圖中可看出，SMO算法對(duì)非線性函數(shù)回歸效果較好，隨機(jī)測(cè)試樣本測(cè)試誤差較小.

表2 固定C=1.2情況下2種算法比較

表3 固定γ2=0.1情況下2種算法比較

圖4 非線性函數(shù)回歸結(jié)果(C=1.2，γ2=0.1)

5 結(jié)論

通過仿真實(shí)驗(yàn)，驗(yàn)證了支持向量機(jī)算法具有較強(qiáng)的非線性數(shù)據(jù)擬合功能，改進(jìn)的SMO算法在訓(xùn)練速度和結(jié)果穩(wěn)定性上得到提高.

實(shí)驗(yàn)表明，參數(shù)C和γ2，停機(jī)準(zhǔn)則σ值對(duì)訓(xùn)練模型精度和訓(xùn)練速度影響較大，參數(shù)選擇具有數(shù)據(jù)依賴性，仿真實(shí)驗(yàn)1中數(shù)據(jù)分布值域廣，數(shù)據(jù)變化趨勢(shì)較平坦，則γ2取較大值，仿真實(shí)驗(yàn)2中數(shù)據(jù)分布值域窄，數(shù)據(jù)變化較劇烈，則γ2取較小值，參數(shù) C取值大致位于最大值和最小值的中間;停機(jī)準(zhǔn)則σ值越小，訓(xùn)練時(shí)間越長(zhǎng)，精度越高，可根據(jù)訓(xùn)練要求取不同值，如何更好地選擇參數(shù)C和γ2是值得繼續(xù)研究的方向.

References)

［1］ Platt J C.Fast training of support vector machines using sequential minimal optimization［R］.MSR-TR-98-14，1998

［2］ Smola A J，Scholkopf B.A tutorial on support vector regression［R］.NC2-TR-1998-030，1998

［3］ Shevade S K，Keerthi S S，Bhattacharyya C，et al.Improvements to SMO algorithm for SVM regression［J］.IEEE Transactions on Neural Networks，2000，11(5):1188 －1193

［4］ Flake G W，Lawrence S.Efficient SVM regression training with SMO［J］.Machine Learning，2002，46(1-3):271 －290

［5］ 張浩然，韓正之.回歸支持向量機(jī)的改進(jìn)序列最小優(yōu)化學(xué)習(xí)算法［J］.軟件學(xué)報(bào)，2003，14(12):2006 －2013 Zhang Haoran，Han Zhengzhi.An improved sequential minimal optimization learning algorithm for regression support vector machine［J］.Journal of Software，2003，14(12):2006 －2013(in Chinese)

［6］ 劉勝，李妍妍.自適應(yīng)GA-SVM參數(shù)選擇算法研究［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2007，28(4):398 －402 Liu Sheng，Li Yanyan.Parameter selection algorithm for support Vector machines based on adaptive genetic algorithm ［J］.Journal of Harbin Engineering University，2007，28(4):398 － 402(in Chinese)

［7］ 閆國(guó)華，朱永生.支持向量機(jī)回歸的參數(shù)選擇方法［J］.計(jì)算機(jī)工程，2009，35(14):218 －220 Yan Guohua，Zhu Yongsheng.Parameters selection method for support vector machine regression ［J］.Computer Engineering，2009，35(14):218 －220(in Chinese)

［8］ 董磊，任章，李清東.基于SMO-SVR的飛機(jī)舵面損傷故障趨勢(shì)預(yù)測(cè) ［J］.北京航空航天大學(xué)學(xué)報(bào)，2012，38(10):1300－1305 Dong Lei，Ren Zhang，Li Qingdong.Fault prediction for aircraft control surface damage based on SMO-SVR ［J］.Journal of Beijing University of Aeronautics and Astronautics，2012，38(10):1300－1305(in Chinese)

［9］ 王書舟，傘冶，張?jiān)什?基于支持向量機(jī)改進(jìn) SMO算法的直升機(jī)旋翼自轉(zhuǎn)著陸過程建模［J］.航空學(xué)報(bào)，2009，30(1):46－51 Wang Shuzhou，San Ye，Zhang Yunchang.Modeling for landing process of helicopter with rotator self-rotating based on modified SMO algorithm of support vector machine［J］.Acta Aeronautica et Astronautica Sinica，2009，30(1):46 －51(in Chinese)

［10］ 王定成.支持向量機(jī)建模預(yù)測(cè)與控制［M］.北京:氣象出版社，2009:48－49 Wang Dingcheng.Prediction and control based on support vector machine modelling［M］.Beijing:Meteorological Press，2009:48－49(in Chinese)