唐輝軍 白 玲 楊志民

1(寧波大紅鷹學(xué)院信息工程學(xué)院 浙江 寧波 315175)2(浙江工業(yè)大學(xué)之江學(xué)院理學(xué)院 浙江 杭州 310023)

基于最佳一致光滑逼近的孿生支持向量機(jī)研究

唐輝軍1白 玲1楊志民2

1(寧波大紅鷹學(xué)院信息工程學(xué)院 浙江 寧波 315175)2(浙江工業(yè)大學(xué)之江學(xué)院理學(xué)院 浙江 杭州 310023)

孿生支持向量機(jī)本質(zhì)為兩個二次規(guī)劃問題，對于其目標(biāo)函數(shù)中約束變量取正號不可微特性，提出一種基于最佳一致逼近的多項(xiàng)式光滑函數(shù)構(gòu)建方法。分別以Bernstain多項(xiàng)式和Chebyshev多項(xiàng)式進(jìn)行正號函數(shù)最佳一致有效光滑逼近。重點(diǎn)突出Chebyshev多項(xiàng)式的最佳一致逼近過程，使用Remez算法構(gòu)造最佳一致Chebyshev多項(xiàng)式，討論各階Chebyshev多項(xiàng)式逼近狀況。最后綜合最佳一致逼近多項(xiàng)式和樣本適應(yīng)度構(gòu)建目標(biāo)優(yōu)化函數(shù)，采用快速Newton-Armijo算法求解目標(biāo)優(yōu)化函數(shù)，基于UCI數(shù)據(jù)驗(yàn)證了方法的優(yōu)越性。

孿生支持向量機(jī) 最佳一致逼近 適應(yīng)度

0 引 言

支持向量機(jī)[1](SVM)被認(rèn)為是能較好地對多角色個體進(jìn)行有效分類和回歸的重要工具。可在不同應(yīng)用領(lǐng)域針對小樣本、非線性模式識別表現(xiàn)出獨(dú)特的優(yōu)勢[2-3]。不少專家和學(xué)者對其進(jìn)行了深入研究和效率改進(jìn)，從提高計(jì)算速度出發(fā)，對分類超平面計(jì)算進(jìn)行效率改進(jìn)成為該領(lǐng)域一個研究熱點(diǎn)。PSVM[4]、GEPSVM[5]等支持向量機(jī)新模型被相繼提出。2007年Jayadeva等人在上述研究成果的基礎(chǔ)上，提出孿生支持向量機(jī)(TWSVM)機(jī)器學(xué)習(xí)新方法[6]，其本質(zhì)上表現(xiàn)為構(gòu)造兩個不平行的分類超平面，按照離哪類近就歸屬哪類的性質(zhì)，解決兩個二次規(guī)劃問題。由于其計(jì)算速度為標(biāo)準(zhǔn)SVM的4倍，TWSVM在圖像檢測、人工識別[7-8]等眾多領(lǐng)域得到了良好應(yīng)用。并且與一般支持向量分類機(jī)、回歸機(jī)相比，孿生支持向量機(jī)無論在正確率計(jì)算、計(jì)算速度、優(yōu)化精度等方面都得到了有效提高[9]。以孿生支持向量分類機(jī)為例，其標(biāo)準(zhǔn)數(shù)學(xué)模型構(gòu)造為：

(1)

在線性分類情況下，按照一般支持向量機(jī)的求解思路，引入拉格朗日參數(shù)，基于KKT條件，對式(1)進(jìn)行對偶空間內(nèi)優(yōu)化求解，計(jì)算結(jié)果得到形如式(2)所示。其中M=D=[B,e2]T，N =S=[A,e1]T，e1,e2均為值為1的列向量。

(2)

對于拉格朗日參數(shù)α和β的尋求，可通過內(nèi)點(diǎn)法[10]、性能更好的TBSVM[11]等相關(guān)算法得到。在非線性分類情況下，依托于SVM中核函數(shù)[12]的引入，也可得到相應(yīng)的數(shù)學(xué)模型。

式(2)應(yīng)用了從對偶空間中解決孿生支持向量機(jī)的解決問題。但文獻(xiàn)[13-14]通過計(jì)算分析表明，TWSVM事實(shí)上可直接基于原始數(shù)值空間求解優(yōu)化問題，在原始空間內(nèi)引入正號函數(shù)形成光滑孿生支持向量機(jī)模型(STWSVM)，進(jìn)而通過對正號函數(shù)進(jìn)行逼近，將原模型進(jìn)行光滑化，從而達(dá)到采用梯度算法快速求解目的。Chen等人[15]采用Sigmoid函數(shù)作為光滑函數(shù)，對孿生支持向量的目標(biāo)函數(shù)作光滑處理，并采用快速算法求解相應(yīng)的模型。實(shí)驗(yàn)結(jié)果都表明了其有效性。文獻(xiàn)[16,17] 基于光滑孿生支持向量機(jī)的光滑逼近要求，在總結(jié)了大量使用方法的基礎(chǔ)上，提出了使用多項(xiàng)式光滑逼近方式，并且基于一定的標(biāo)準(zhǔn)數(shù)據(jù)集計(jì)算取得了比Sigmoid函數(shù)更好的效率優(yōu)化結(jié)果。

光滑函數(shù)的選擇是解決這一問題的關(guān)鍵所在，本文在總結(jié)光滑孿生支持向量機(jī)數(shù)學(xué)形式的基礎(chǔ)上，提出一種基于最佳一致逼近的光滑函數(shù)，通過樣本數(shù)據(jù)的重要度設(shè)置樣本數(shù)據(jù)適應(yīng)度，最后基于最佳一致光滑逼近函數(shù)和適應(yīng)函數(shù)構(gòu)建新的目標(biāo)優(yōu)化函數(shù)。相關(guān)數(shù)據(jù)集的實(shí)驗(yàn)驗(yàn)證，證明了最佳一致孿生支持向量機(jī)的可行性。

1 光滑孿生支持向量機(jī)

按照所采用光滑方法的不同，其一般運(yùn)算過程為將式(1)中的松弛變量ξ(1)、ξ(2)由1范式改變?yōu)?范式。

(3)

式(3)中對ξ(1)、ξ(2)具有一定的約束條件，引入正號函數(shù)[x]+=max(0,x)，根據(jù)KTT條件設(shè)置ξ(1)、ξ(2)優(yōu)化取值，進(jìn)而引入光滑逼近函數(shù)p(x)，其表示了通過一定的函數(shù)轉(zhuǎn)換，把式(3)轉(zhuǎn)變?yōu)閮蓚€無約束優(yōu)化問題。

(4)

式(4)變成了可微的目標(biāo)函數(shù)優(yōu)化問題，可采用具有快速收斂能力的相關(guān)算法求解該模型。光滑孿生支持向量機(jī)在原始空間更具優(yōu)勢，理論分析和實(shí)驗(yàn)驗(yàn)證[15]都表明了其有效性和可行性。

在非線性情況下，基于核函數(shù)的孿生支持向量機(jī)一對超平面求解目標(biāo)函數(shù)可以表示為：

(5)

基于同樣的原理，將式(5)轉(zhuǎn)換成為無約束目標(biāo)函數(shù)為：

(6)

2 最佳一致逼近光滑函數(shù)

光滑函數(shù)的選擇是求解式(4)和式(6)數(shù)學(xué)模型的關(guān)鍵，文獻(xiàn)[16,17]指出，基于多項(xiàng)式插值的光滑函數(shù)構(gòu)建是解決約束不可微問題的重要方法。但對于多項(xiàng)表達(dá)式的尋求，目前還沒有普遍的方法來構(gòu)造完成，并且逼近誤差達(dá)不到計(jì)算需求。最佳一致逼近具有逼近速度快、精度誤差小等特點(diǎn)，為解決上述問題提供了一個良好方法。

(7)

Bn(f)隨著參數(shù)n的增大逼近了目標(biāo)函數(shù)f(x)，顯然，正號函數(shù)滿足在區(qū)間上的連續(xù)，基于逼近精度需求，考慮函數(shù)在對稱區(qū)間[-1,1]逼近，通過變量替代變換到計(jì)算區(qū)間，可得到與其對應(yīng)Bernstein多項(xiàng)式為：

(8)

表1表示了Bernstain多項(xiàng)式在區(qū)間[-1,1]上對正號函數(shù)的逼近多項(xiàng)式?？梢钥吹?，隨著逼近的逐次迭代，計(jì)算多項(xiàng)式復(fù)雜度也得到了較大的提高。

由表1構(gòu)造的多項(xiàng)式結(jié)合文獻(xiàn)[18]對其的精度分析可知，Bernstain多項(xiàng)式對整體的逼近性質(zhì)要求較好，但收斂速度較慢，提高精度伴隨著多項(xiàng)式次數(shù)的提高，這對復(fù)雜函數(shù)下的多項(xiàng)式逼近工作量較大。但由于正號函數(shù)并不復(fù)雜，構(gòu)造表1中Bernstain多項(xiàng)式逼近正號函數(shù)不失為一種方法。

表1 Bernstain多項(xiàng)式最佳逼近

與Bernstain多項(xiàng)式逼近相比，Chebyshev逼近是構(gòu)造最佳逼近多項(xiàng)式的一種較為理想的有效方式。其在構(gòu)建過程中更強(qiáng)調(diào)整體精度性且迭代次數(shù)計(jì)算并不復(fù)雜。其表示對于f(x)∈C[a,b]，要尋求f(x)的n次最佳一致逼近代數(shù)多項(xiàng)式pn(x)，問題的關(guān)鍵在于確定具有n+2個點(diǎn)的交錯點(diǎn)組{xi}，如果點(diǎn)組存在，則滿足：

(9)

其中η=Δ(f,pn)或者-Δ(f,pn)。由介值定理可知，f(x)-pn(x)在C[a,b]上至少有n+1個零點(diǎn)，pn(x)就是以這n+1個零點(diǎn)為插值點(diǎn)的n次拉格朗日插值多項(xiàng)式。

式(9)是一個關(guān)于n+2個變元a0,a1,…,an,η的n+2階線性方程組，存在唯一的解，從而求得最佳逼近多項(xiàng)式pn(x)和最佳逼近|η|。由于尋找交錯點(diǎn)組并不容易，這里應(yīng)用Remez最佳一致近似算法[14]來求解。其有以下3步構(gòu)成：

(1) 在區(qū)間[a,b]上選擇n+2由小到大的初始點(diǎn)列{x0,x1,…,xn+1}作為交錯點(diǎn)組，設(shè)置迭代計(jì)算精度ε>0。

(2) 計(jì)算式(5)中的方程組，得到{a0,a1,…,an},進(jìn)而構(gòu)建pn(x)，計(jì)算最佳逼近|η|。

(3) 若Δ(f,pn)=|f(x)-pn(x)|∞-|η|≤ε，則迭代終止，否則利用單一交換、同時交換等方法計(jì)算替換新的交錯點(diǎn)組，返回步驟(2)。

依據(jù)Remez算法，對光滑孿生支持向量機(jī)中的正號函數(shù)進(jìn)行最佳一致Chebyshev多項(xiàng)式逼近。設(shè)定初始迭代區(qū)間范圍[-1,1]，應(yīng)用單一交換方法，計(jì)算正號函數(shù)多項(xiàng)式逼近取值過程，其二次多項(xiàng)式逼近結(jié)果如表2所示。

表2 多項(xiàng)式最佳逼近

同理可分別計(jì)算得到最佳一致n次Chebyshev多項(xiàng)式，由于Remez算法為逐次逼近近似求解，其并沒有統(tǒng)一的n次多項(xiàng)式表示，表3羅列了n取值不超過5時的Chebyshev多項(xiàng)式及其誤差精度。

表3 Chebyshev多項(xiàng)式最佳逼近

從表3可以看出，Remez算法的收斂速度相當(dāng)快，經(jīng)過3次迭代就可以計(jì)算得到結(jié)果。圖1表示了樣條插值多項(xiàng)式(黑線)、最佳一致五次Bernstain多項(xiàng)式(細(xì)線)、二次Chebyshev多項(xiàng)式(虛線)正號函數(shù)逼近效果，從圖形可以知道，最佳一致逼近Chebyshev多項(xiàng)式相比插值多項(xiàng)式、Bernstain多項(xiàng)式取得了良好的逼近效果。

圖1 最佳一致逼近光滑函數(shù)

為了綜合考慮樣本離群點(diǎn)對孿生支持向量機(jī)的影響，在基于文獻(xiàn)[13]的加權(quán)系數(shù)設(shè)計(jì)方式上，這里采用基于距離公式建立各個樣本點(diǎn)的適應(yīng)度，為了有效表示中心點(diǎn)，離群點(diǎn)及對分類超平面的影響，依據(jù)離群點(diǎn)的位置重要度指標(biāo)形成一個數(shù)值向量g1、g2。其值設(shè)置為：

(10)

綜合式(4)，式(10)，在原始空間內(nèi)對線性孿生支持向量機(jī)求值，通過構(gòu)造最佳一致二次多項(xiàng)式光滑逼近目標(biāo)函數(shù)內(nèi)的正號函數(shù)，得到在區(qū)間內(nèi)的具體優(yōu)化目標(biāo)為：

(11)

(12)其中R為求得的最佳一致多項(xiàng)式系數(shù)。式(11)、式(12)表示了無約束條件下的二次規(guī)劃求值，可采用Newton-Armijo算法求解優(yōu)化模型。其一般計(jì)算流程為：

(1) 設(shè)定初始點(diǎn)(w(0),γ0)，設(shè)置算法精度ε,設(shè)置循環(huán)計(jì)算的初始值k=1。

(2) 計(jì)算關(guān)于當(dāng)前迭代點(diǎn)的偏導(dǎo)函數(shù)g(k)的值，判斷是否滿足終止條件‖g(k)<ε‖，否則轉(zhuǎn)(3)。

(3) 求新的迭代點(diǎn)的(w(k),γk)值，根據(jù)迭代公式求搜索方向d(k)。

(4) 基于步驟(3)中的尋求目標(biāo)d(k),依據(jù)全局搜索策略步長ak。

(5) 基于上述步驟，迭代公式(w(k+1),γk+1)= (w(k),γk)+d(k)ak，轉(zhuǎn)(2)。

3 實(shí) 驗(yàn)

為驗(yàn)證模型有效性，以BUTWSVCM表示最佳一致二次Chebyshev多項(xiàng)式光滑逼近孿生支持向量分類機(jī)，以DUTWSVCM表示對偶空間內(nèi)的孿生支持向量機(jī)分類機(jī)，BETWSVCM表示Bernstein五次多項(xiàng)式逼近分類機(jī)。所有實(shí)驗(yàn)在都在Intel(R)Core(TM)i5-2450MCPU,4GB內(nèi)存和MATLABr2011b的環(huán)境中進(jìn)行 應(yīng)用Newton-Armijo算法求解優(yōu)化模型。設(shè)置Remez算法精度ε=1.0E-3，線性算法對數(shù)據(jù)集的測試結(jié)果對比見表4所示。采用一般高斯徑向基函數(shù)作為核函數(shù)，從UCI數(shù)據(jù)集中各取100條數(shù)據(jù)作為測試數(shù)據(jù)，非線性算法下的訓(xùn)練和測試結(jié)果見表5所示。

表4 線性算法計(jì)算結(jié)果

表5 非線性算法計(jì)算結(jié)果 %

從表4、表5中可以看到， BUTWSVM取得了更好的計(jì)算速度和精度。采用最佳一致光滑逼近函數(shù)求解孿生支持向量機(jī)可以得到滿意的結(jié)果。

依據(jù)表1、表3的多項(xiàng)式表達(dá)方式，選取同一UCI數(shù)據(jù)集，對n(n<6)次最佳一致多項(xiàng)式逼近效果和準(zhǔn)確率開展計(jì)算分析，計(jì)算結(jié)果如表6所表示。其表明，相比較于其他同類多項(xiàng)式，Bernstein五次多項(xiàng)式、Chebyshev二次多項(xiàng)式取得了良好效果。也間接驗(yàn)證了表4、表5的結(jié)果最佳性。

表6 最佳一致多項(xiàng)式分類準(zhǔn)確率 %

4 結(jié) 語

孿生支持向量機(jī)與一般支持向量機(jī)相比，在計(jì)算效率方面得到了有效提升。本文針對孿生支持向量機(jī)原始空間優(yōu)化求值的需求，構(gòu)建最佳一致光滑逼近方法孿生支持向量機(jī)計(jì)算模型。給出了最佳一致二次多項(xiàng)式的推導(dǎo)和計(jì)算過程，定義了孿生支持向量機(jī)光滑數(shù)學(xué)模型，基于樣本位置計(jì)算了個體適應(yīng)度。通過實(shí)驗(yàn)仿真可以得到最佳一致光滑多項(xiàng)式能夠有效地逼近原始空間內(nèi)的正號函數(shù)，計(jì)算準(zhǔn)確率和速度都達(dá)到了優(yōu)化要求。最佳一致光滑逼近函數(shù)的建立，對于優(yōu)化孿生支持向量機(jī)計(jì)算過程進(jìn)而達(dá)到快速求解目的，提高計(jì)算分析準(zhǔn)確率具有重要的作用。

[1] Vapnik V N.The Nature of Statistical Learning Theory[M].Springer-Verlag,New York,1995.

[2] Shawe-Taylor J,Sun S.A review of optimization meth- odologies in support vector machines[J].Neurocomputing,2011,74:3609-3618.

[3] Wu J X.Efficient HIK SVM learning for Image Classification[J].IEEE Transactions on Image Processing,2012,21(10):4442-4453.

[4] Fung G,Mangasarian O L.Proximal Support Vector Machine Classifiers[C]//Proc 7thACM SIFKDD Intl Conference on Knowledge Discovery and Data Mining,2001:77-86.

[5] Mangasarian O L,Wild Edward W.Multi-surface proximal support vector machine classification via generalized eigenvalues[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(1):69-74.

[6] Jayadeva K R,Suresh C.Twin support vector machines for pattern classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(5):905-910.

[7] Kumar M A,Gopal M.Application of smoothing technique on twin support vector machines[J].Pattern Recognition Letters,2008,29(13):1842-1848.

[8] Khemehandani R,Jadeva S Chajndra.Optimal kernel selection in twin support vector machines[J].Optimization Letter,2009,3:77-88.

[9] Cong H H,Yang C F,Pu X R.Efficient Speaker Recognition based on Multi-class Twin Support Vector Machines and GMMs[C]//2008 IEEE Conference on Robotics,Automation and Mechatronics,2008:348-352.

[10] 袁玉萍,鐘萍,鄒艷華.基于預(yù)測-校正原對偶內(nèi)點(diǎn)法的多分類支持向量機(jī)學(xué)習(xí)算法[J].南京大學(xué)學(xué)報,2009,45(4):494-498.

[11] Shao Y H,Zhang C H,Wang X B,et al.Improvements on twin support vector machines[J].IEEE Transactions on Neural Networks,2011,22(6):962-968.

[12] Jayadeva R K.Optimal kernel selection in twin support vector machines[J].Optimal Letter,2009,3:77-88.

[13] Wang Z,Shao Y H,Wu T R.A GA-based model selection for smooth twin parametric-margin support vector machine[J].Pattern Recognition,2013,46:2267-2277.

[14] 黃華娟.孿生支持向量機(jī)關(guān)鍵問題的研究[D].中國礦業(yè)大學(xué),2014.

[15] Chen X B,Yang J,Liang J,et al.Smooth twin support vector regression[J].NeuralComputing & Applications,2012,21:505-513.

[16] 熊金志,胡金蓮,袁華強(qiáng),等.一類光滑支持向量機(jī)新函數(shù)的研究[J].電子學(xué)報,2007(2):8-10.

[17] 陳衛(wèi)東,范艷峰.基于三次樣條插值的支持向量機(jī)研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(7):1722-1725.

[18] 蔣爾雄.數(shù)值逼近[M].上海:復(fù)旦大學(xué)出版社,2007.

RESEARCH ON TWIN SUPPORT VECTOR MACHINES BASED ON BEST UNIFORM SMOOTHING APPROXIMATION

Tang Huijun1Bai Ling1Yang Zhimin2

1(CollegeofInformationEngineering,NingboDahongyingUniversity,Ningbo315175,Zhejiang,China)2(CollegeofZhijiang,ZhejiangUniversityofTechnology,Hangzhou310023,Zhejiang,China)

The essence of twin support vector machines(TWSVM) is to optimise two quadratic programming problems. As the positive constrained variable of objective function was not differentiable, this paper presented a constructing method of polynomial smoothing function based on best uniform approximation. Bernstein and Chebyshev polynomial were established to effectively achieve the best uniform smoothing approximation of the positive function. The best uniform approximation of Chebyshev polynomial is emphasized. The best uniform Chebyshev polynomial was established by applying the Remez algorithm, and each order of the Chebyshev polynomial approximation was discussed. Finally, the objective optimal function based on best uniform approximation polynomial and the degree of sample adaption could be got, and the fast Newton-Armijo algorithm was used for solving the objective optimal function. On the basis of UCI data, we validated the advantages of the method.

Twin support vector machines Best uniform approximation Degree of adaption

2015-12-07。國家自然科學(xué)基金項(xiàng)目(10926198)；浙江省公益技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目(2016C33G2620016)；寧波市自然科學(xué)基金項(xiàng)目(2015A610135)。唐輝軍，講師，主研領(lǐng)域：數(shù)據(jù)挖掘，計(jì)算機(jī)仿真。白玲，碩士生。楊志民，教授。

TP18

A

10.3969/j.issn.1000-386x.2017.04.030