顧斌杰, 潘　豐

(江南大學輕工過程先進控制教育部重點實驗室, 江蘇 無錫 214122)

?

改進的v-支持向量回歸機的v解路徑算法

顧斌杰, 潘豐

(江南大學輕工過程先進控制教育部重點實驗室, 江蘇 無錫 214122)

摘要：v-支持向量回歸機(v-support vector regression, v-SVR)的對偶形式與ε-支持向量回歸機的對偶形式相比增加了一個額外的不等式約束,截止目前還沒有找到有效且可行的v-SVR 的v解路徑算法。針對Loosli等人提出的v-SVR的v解路徑算法存在路徑不可更新的問題,提出了改進的v-SVR的v解路徑算法。該算法基于v-SVR的修改形式及Karush-Kuhn-Tucker(KKT)條件,通過引入新的變量和附加項的策略,能夠有效地避免在絕緣增量調(diào)整過程中存在的沖突和異常,并最終經(jīng)過有限次數(shù)迭代擬合出整個v解路徑。理論分析和仿真結(jié)果表明,該算法是有效且可行的。

關鍵詞：機器學習; 模型選擇; v-支持向量回歸機; v解路徑

0引言

由文獻[1]提出的支持向量機(support vector machine, SVM)是一種基于統(tǒng)計學習理論的機器學習算法,它能夠有效地處理小樣本學習問題,具備良好的泛化能力。目前，SVM已經(jīng)成為機器學習領域最為流行的方法之一。然而,仍有一些未解決的問題需要進行深入的研究,其中之一就是如何調(diào)整SVM的參數(shù)使其具備最佳的泛化性能,也就是模型選擇問題[2-4]。

常規(guī)的模型選擇方法首先選定一些候選參數(shù)值,然后采用交叉驗證(cross validation, CV)的方法從上述候選參數(shù)值中選擇最佳的參數(shù)[2]。當搜索空間較大時,常規(guī)的模型選擇方法將會在不同的參數(shù)下訓練SVM很多次,這就極大地限制了常規(guī)的模型選擇方法在實際中的應用。

為了解決上述困難,文獻[5]基于解路徑是分段線性的特點提出了一種新的解路徑方法,稱之為SvmPath算法,該算法能夠擬合懲罰參數(shù)C的整個解路徑,其最大的優(yōu)點是只需要訓練SVM一次;在此基礎上,文獻[6-8]將SvmPath算法推廣到ε-支持向量回歸機(ε-support vector regression, ε-SVR),統(tǒng)稱之為SvrPath算法。文獻[9-10]研究了v-支持向量分類機 (v-support vector classification,v-SVC)參數(shù)v的漸進最佳選擇方法。文獻[11]基于SvmPath算法提出了v-支持向量回歸機 (v-support vector regression,v-SVR)的v解路徑算法,不幸的是,文獻[12-15]指出直接應用該算法將會出現(xiàn)路徑不可更新的問題。針對這個問題,文獻[15]提出了一種有效的v-支持向量回歸機v解路徑算法,稱之為v-SvrPath算法,該算法解決了直接將SvmPath算法應用于v-SVR將會導致路徑不可更新的問題,其缺點是要把回歸問題轉(zhuǎn)換成分類問題后再求出相應的v解路徑。

v-SVR是由文獻[9]提出的一種新的支持向量機形式。給定訓練樣本集合F={(x1,y1),…,(xl,yl)},其中xi∈Rn,yi∈R,i=1,…,l,v-SVR原始問題(primal problem, PP)如下[16-18]:

(1)

v-SVR的對偶問題(dualproblem,DP)如下[18]:

(2)

式中,H是半正定核矩陣,其元素為Hij=K(xi,xj)=φT(xi)φ(xj)=〈φ(xi),φ(xj)〉,〈.,.〉表示內(nèi)積;e是長度為l的全1列向量;y,α和α*都是長度為l的列向量。

本文針對回歸問題提出一種改進的v-SVR的v解路徑算法?；趘-SVR的修改形式,定理1(詳見第1.1節(jié)) 以及Karush-Kuhn-Tucker(KKT)條件,解決了v-SVR的DP存在的兩個問題。此外,通過引入新的變量和附加項的策略,解決了v解路徑算法在絕緣增量調(diào)整過程中的路徑不可更新問題。理論分析和仿真結(jié)果驗證了本文提出的改進的v-SVR的v解路徑算法能夠盡可能地在絕緣增量調(diào)整過程中存在的路徑不可更新問題以及異常情況并最終經(jīng)過有限次數(shù)迭代擬合出整個v解路徑。

1v-SVR的修改形式及KKT條件

1.1v-SVR的修改形式

為了解決v-SVR的DP存在的兩個問題,下面將引入v-SVR的修改形式及定理1。

為了解決第一個問題,把式(1)中的目標函數(shù)P乘樣本點個數(shù)l,考慮如下的PP:

(3)

顯然,式(3)和式(1)是等價的。

令Qij=Hij/l,則式(3)對應的DP為

(4)

式中，Q是半正定核矩陣。

為了解決第二個問題,可以借助于文獻[17]中的結(jié)論,如定理1所示。

定理 1對于最優(yōu)化問題(4), 當0≤v≤1時,總存在最優(yōu)解使得不等式約束eT(α+α*)≤vl可以用等式約束eT(α+α*)=vl來代替。

定理1的證明詳見文獻[17],此處省略。

基于定理1,考慮如下的DP:

(5)

給定式(5)的解,可得回歸函數(shù)為

(6)

式(5)對應的拉格朗日函數(shù)為

LD=

(7)

1.2KKT條件

依據(jù)凸最優(yōu)化理論,式(7)解的充要條件,即KKT條件如下[18-19]:

(8)

(9)

(10)

令

(11)

(12)

聯(lián)合式(8),式(11)和式(12),可得:

(13)

式(13)將訓練集S劃分成如圖1所示的3個子集:集合SS=SSL∪SSR={i|0<|θi|<1}為間隔支持向量集,集合SE=SEL∪SER={i||θi|=1}為錯誤劃分支持向量集,集合SR={i|θi=0}是保持樣本。

圖1　訓練樣本集合S劃分成3個集合

為了后續(xù)表述方便,設SSL集中的樣本點個數(shù)為p,SSR集中的樣本點個數(shù)為q,SS集中的樣本點個數(shù)為r,則顯然有r=p+q。

2改進的v-SVR的v解路徑算法

本文將改進的v-SVR的v解路徑算法稱為ISvrPath算法,具體的v解路徑算法步驟見第2.1節(jié)。ISvrPath算法主要包括兩部分,第一部分的目標是確定式(5)的初始解;第二部分是針對0≤v≤1,搜索出相應的v解路徑。

2.1ISvrPath算法步驟

步驟 2設置異常為假。

步驟 4計算絕緣增量調(diào)整過程中的最小調(diào)整量Δ?min,詳見第2.3節(jié)(2)。

步驟 6更新逆矩陣N,詳見第2.3節(jié)(4)。

步驟 7若SSL=?而且SEL=?或者SSR=?而且SER=?(詳見第3.1節(jié)假設2),則設置異常為真并取v←v+0.001;否則執(zhí)行步驟8。

步驟 8若v>0而且異常為假,則重復執(zhí)行步驟3到步驟7;否則執(zhí)行步驟9。

步驟 9重復步驟2和步驟8直至v<1。

2.2ISvrPath算法初始化

根據(jù)式(13)可以得到:

(14)

證畢

2.3ISvrPath算法的v解路徑

(1)v的絕緣增量調(diào)整過程

在v逐步增大的過程中,為了保持所有的樣本仍舊滿足KKT條件,SS集中樣本對應的θi,拉格朗日乘子b和ρ也要作相應的調(diào)整。根據(jù)式(9)~式(13),可得:

(15)

(16)

(17)

(18)

比較式(15)和式(16)可以看出,當SSL或者SSR是空集時,式(15)和式(16)不能同時得到滿足,也就是說存在如表1所示的沖突。沖突將會直接導致v解路徑的不可更新問題。

表1　絕緣增量調(diào)整過程中存在的兩種沖突情況

為了解決在絕緣增量調(diào)整過程中可能存在的沖突問題,將式(16)變成

(19)

更進一步,式(15)和式(17)~式(19)可以表示成如下的矩陣形式:

(20)

根據(jù)定理2,M必定存在逆矩陣N,故有

接著,把式(21)分別代入式(17)和式(18),可得

(22)

(23)

此外,將式(21)代入式(19)可得

(24)

(2) 計算最小調(diào)整量Δ?min

在v值的逐步絕緣增量調(diào)整過程中,會使得樣本點在SS集,SE集和SR集之間相互遷移,這勢必會導致SS集,SE集和SR集組成成分的變化。為了解決這個問題,采用的策略是獲取SS集,SE集和SR集的最小變化,也就是說計算最小調(diào)整量Δ?min,使得每次只有某一個樣本在SS集,SE集和SR集之間遷移[15-17]。記賬程序需要考慮如下4種情況:

最后,將4個值中的最大值作為最小調(diào)整量Δ?min,即

(25)

確定最小調(diào)整量Δ?min之后,根據(jù)式(16)和式(24),參數(shù)v可以按照如下規(guī)則更新:

(26)

(27)

最小調(diào)整量Δ?min計算之后,若Δ?min=Δ?4,則意味著ISvrPath算法滿足結(jié)束條件,算法終止。其他情況下,設使得式(25)取最大值時對應的樣本為t,則SS集,SE集和SR集可以按照如下規(guī)則更新:

①當Δ?min=Δ?1時,如果t∈ISSL+,則將樣本t從SEL集移入SSL集;如果t∈ISSL-,則將樣本t從SR集移入SSL集;如果t∈ISSR+,則將樣本t從SER集移入SSR集;如果t∈ISSR-,則將樣本t從SR集移入SSR集。

②當Δ?min=Δ?2時,如果t∈ISEL+,則將樣本t從SSL集移入SEL集;如果t∈ISER+,則將樣本t從SSR集移入SER集。

③當Δ?min=Δ?3時,如果t∈ISR-,則將樣本t從SSL集移入SR集;如果t∈I*SR-,則將樣本點t從SSR集移入SR集。

(4) 更新逆矩陣N

當樣本t移入或者移出SS=SSL∪SSR集,將會改變矩陣M,相應地也會改變逆矩陣N。下面討論如何高效地求解逆矩陣N。

引理2是Sherman-Morrison-Woodbury分塊矩陣求逆公式,其證明詳見文獻[20],此處省略。

當樣本t移入SS集,有兩種情況需要考慮,一是樣本t移入SSL集(對應ωt=1);二是樣本t移入SSR集(對應ωt=-1)。根據(jù)引理2,當樣本t移入SS集,逆矩陣N可以按照如下規(guī)則擴展為

(28)

式中

當樣本t移出SS集,逆矩陣N可以按照如下規(guī)則收縮[21]為

(29)

式中,N t代表逆矩陣N刪除t所對應的行列縮減矩陣;(N*t·Nt*) t的含義類似,需要注意的是t≠*;Ntt代表逆矩陣N第t行和第t列的元素。

3可行性和有限收斂性理論分析

3.1可行性理論分析

通過可行性理論分析,證明了ISvrPath算法能夠盡可能地避免SvrPath算法中存在的路徑不可更新問題。

引理 3矩陣QSSSS是半正定陣。

也就是說矩陣QSSSS是半正定陣。

證畢

假設 1矩陣QSSSS是正定陣。

定理 2在絕緣增量調(diào)整過程中,若κ<0,則矩陣M的行列式總大于0,也就意味著矩陣M一定存在逆矩陣N。

首先定義矩陣

因為

根據(jù)行列式的性質(zhì)可得

det(QSSSS)

由柯西—施瓦茲不等式可得

故有:det(P)≥0。

接著,分別對矩陣M和矩陣P中ρ對應的行,即第二行進行行列式展開,經(jīng)過比較后可得如下等式關系:

det(M)=det(P)+κdet(Mρρ)>0

這就意味著矩陣M一定存在逆矩陣N。

證畢

證明采用反證法,根據(jù)式(21)可得

證畢

定理 3在絕緣增量調(diào)整過程中,若κ<0,則κγρ+1≥0,等號當且僅當SSL或者SSR是空集時成立。

證明根據(jù)式(21)可得:

等號成立時也就意味著det(P)=0,根據(jù)定理2的證明過程有

而det(QSSSS)>0,故要求

也就是說必須有:zSS=eSS或者zSS=-eSS,根據(jù)zSS和eSS的定義,可知SSL或者SSR是空集時成立。

證畢

證明若SSL集是空集,則矩陣M變成

根據(jù)式(22)和式(23)可得

其中

類似地,若SSR集是空集,同理可證:

證畢

推理 2在絕緣增量調(diào)整過程中,必定有:Δ?min<0。

證明根據(jù)第2.3節(jié)(2)中的描述容易驗證:Δ?1<0,Δ?2<0,Δ?3<0和Δ?4<0。

根據(jù)式(25),可得

證畢

假設 2在絕緣增量調(diào)整的過程中,當SSL集是空集時,SEL集是非空集;或者當SSR集是空集時,SER集是非空集。

簡單地說,在絕緣增量調(diào)整的過程中,假設2不會出現(xiàn)SSL集和SEL集均為空集或者SSR集和SER集均為空集兩種情形。本文中稱這兩種情形為異常。事實上,從仿真實驗中可以看出異常情況是很少出現(xiàn)的。如果在增量調(diào)整過程中出現(xiàn)了異常,根據(jù)定理3和定理4以及第2.3節(jié)(2)中的描述,此時的最小調(diào)整量為

這就意味著訓練集合S的組成成分不存在任何變化,即對應的解將不會隨著Δ?的變化而變化。因此,v解路徑算法到此結(jié)束。

3.2有限收斂性理論分析

通過有限收斂性理論分析,證明了ISvrPath算法經(jīng)過有限次數(shù)迭代可以擬合出整個v解路徑。

首先定義如下的能量函數(shù)W:

(30)

定理 5在絕緣增量調(diào)整過程中,能量函數(shù)W是單調(diào)遞增的。

證明在絕緣增量調(diào)整過程中,設第k-1次調(diào)整時的能量函數(shù)為W[k-1](α(*)),而第k次調(diào)整時的能量函數(shù)為W[k](α(*))。

首先,根據(jù)式(22)、式(23)和式(27)以及能量函數(shù)W的定義式(30),可得

其次,根據(jù)式(9)、式(15)和式(21)可以分別得到

因此有

接著,根據(jù)式(21)和式(24)可得

從而有

因此有

最后,根據(jù)推理2,式(25)以及第2.3.2節(jié)中的情況4,容易驗證:

此外,根據(jù)式(21)以及定理3的證明過程可得

綜上可得:W[k](α(*))>W[k-1](α(*)),這就意味著在絕緣增量調(diào)整過程中,能量函數(shù)W是單調(diào)遞增的。

證畢

證明采用反證法。

定義在絕緣增量調(diào)整過程中生成的能量函數(shù)序列為(W[1],W[2],W[3],…)。

證畢

4仿真實驗研究

為了評估ISvrPath算法的性能,仿真實驗研究分成兩部分:一是ISvrPath算法驗證實驗；二是ISvrPath算法與文獻[6]中的SvrPath算法和文獻[15]中的v-SvrPath算法的比較實驗。

仿真實驗采用的軟件是Matlab2010a,電腦配置為主頻3.10 GHz, 處理器為Intel?CoreTMi5-2400,內(nèi)存為4GB。

表2列出了在仿真實驗中采用的3個標準回歸測試數(shù)據(jù)集的特性(可從http:∥archive.ics.uci.edu/ml/datasets.html獲取)。

表2　仿真實驗中采用的3個標準回歸測試數(shù)據(jù)集

由于采用徑向基核函數(shù)時,QSSSS是正定陣,故在仿真實驗中全部采用徑向基核函數(shù),即:K(xi,xj)=exp(-‖xi-xj‖2/2σ2),其中,σ是核寬度參數(shù)。同時,為了方便起見,參數(shù)κ設置為固定值,即κ=-1(容易驗證κ僅與det(QSSSS)有關,故κ能夠決定Δ?min的大小,但不會導致SS集,SE集和SR集組成成分的變化)。此外,根據(jù)廣義交叉驗證(generalized cross validation, GCV)準則[6,10,15],同時為了方便與文獻[6]和文獻[15]進行比較,將懲罰參數(shù)C設置為100,核寬度參數(shù)σ分別設置為0.707 1,2.236 1和7.071 1。

4.1ISvrPath算法驗證實驗

(1)Triazines數(shù)據(jù)集

Triazines數(shù)據(jù)集的目標是學習一個回歸方程用于預測定性結(jié)構活動關系。Triazines數(shù)據(jù)集是由具有60個連續(xù)屬性的186個實例組成。表3列出了在訓練集大小分別為40,80,120，160,進行50次實驗后得到絕緣增量調(diào)整過程中迭代、沖突和異常次數(shù)的平均值。

表3　ISvrPath算法在Triazines數(shù)據(jù)集上的測試結(jié)果

從表3中可以看出,沖突次數(shù)和異常次數(shù)都是很少的,也就是說ISvrPath算法能夠盡可能地避免表1中存在的沖突情況。此外,經(jīng)過有限次數(shù)迭代ISvrPath算法能夠擬合出整個v解路徑。

在數(shù)據(jù)集大小為40,核寬度參數(shù)σ為2.236 1的條件下,Triazines數(shù)據(jù)集中間隔支持向量個數(shù)隨著v解路徑的變化過程如圖2所示。從圖2中可以看出,在v的絕緣增量調(diào)整過程中,間隔支持向量的個數(shù)很少會出現(xiàn)等于0的情況,即SS集為空集的情況。因此,ISvrPath算法能夠有效地避免路徑不可更新問題。

圖2　Triazines數(shù)據(jù)集中間隔支持向量　　個數(shù)隨著v解路徑的變化過程

(2) Auto MPG數(shù)據(jù)集

Auto MPG數(shù)據(jù)集來源于StatLib圖書館,該數(shù)據(jù)集由Carnegie Mellon大學維護。Auto MPG數(shù)據(jù)集由398個實例組成,其目標是在3個多值離散屬性和5個連續(xù)屬性基礎上預測城市循環(huán)油耗。表4列出了在訓練集大小分別為80,160,240，320,進行50次實驗后得到絕緣增量調(diào)整過程中迭代、沖突和異常次數(shù)的平均值。

表4　ISvrPath算法在Auto MPG數(shù)據(jù)集上的測試結(jié)果

從表4中可以看出,異常次數(shù)明顯少于沖突次數(shù),也就是說異常是極少出現(xiàn)的。同樣,經(jīng)過有限次數(shù)迭代ISvrPath算法能夠擬合出整個v解路徑。

在數(shù)據(jù)集大小為80,核寬度參數(shù)σ為2.236 1的條件下,Auto MPG數(shù)據(jù)集中間隔支持向量個數(shù)隨著v解路徑的變化過程如圖3所示。從圖3中可以看出,在v的絕緣增量調(diào)整過程中,很少會出現(xiàn)SS集為空集的情況。因此,ISvrPath算法能夠有效地避免路徑不可更新問題。

圖3　Auto MPG數(shù)據(jù)集中間隔支持向量　個數(shù)隨著v解路徑的變化過程

(3) Housing數(shù)據(jù)集

Housing數(shù)據(jù)集也是來源于StatLib圖書館并由Carnegie Mellon大學維護。該數(shù)據(jù)集是由具有13個連續(xù)屬性和1個二值屬性的506個實例組成,關注的是波士頓郊區(qū)的房價。表5列出了在訓練集大小分別為120,240,360，480,進行50次實驗后得到絕緣增量調(diào)整過程中迭代、沖突和異常次數(shù)的平均值。

表5　ISvrPath算法在Housing數(shù)據(jù)集上的測試結(jié)果

從表5中同樣也可以看出,異常次數(shù)明顯少于沖突次數(shù),也就是說異常是極少出現(xiàn)的。同樣,經(jīng)過有限次數(shù)迭代ISvrPath算法能夠擬合出整個v解路徑。

在數(shù)據(jù)集大小為120,核寬度參數(shù)σ為2.236 1的條件下,Housing數(shù)據(jù)集中間隔支持向量個數(shù)隨著v解路徑的變化過程如圖4所示。從圖4中同樣可以看出,在v的絕緣增量調(diào)整過程中,很少會出現(xiàn)SS集為空集的情況。因此,ISvrPath算法能夠有效地避免路徑不可更新問題。

圖4　Housing數(shù)據(jù)集中間隔支持向量　　個數(shù)隨著v解路徑的變化過程

4.2ISvrPath算法比較實驗

為了評估ISvrPath算法的性能,將ISvrPath算法與SvrPath算法和v-SvrPath算法進行比較。SvrPath算法中的參數(shù)ε設置為ε=1,其余參數(shù)設置與ISvrPath算法相同,v-SvrPath算法中的參數(shù)設置與ISvrPath算法完全相同。

驗證數(shù)據(jù)集的大小如表2所示,首先在SvrPath算法、v-SvrPath算法和ISvrPath算法給出的v解路徑算法的基礎上,按照GCV準則進行模型選擇,然后在如表2所示測試數(shù)據(jù)集大小的基礎上,比較了3種算法的最小回歸均方誤差(minimum regression error, MRE),結(jié)果如表6所示。

表6　SvrPath算法、v-SvrPath算法和ISvrPath算法的

從表6中可以看出,ISvrPath算法的MRE小于v-SvrPath算法的MRE,原因是ISvrPath算法是直接針對回歸問題求解相應的v解路徑,而v-SvrPath算法需要將回歸問題轉(zhuǎn)換成分類問題之后才能求解相應的v解路徑。此外,ISvrPath算法與SvrPath算法相比具有更小的MRE,原因是ISvrPath算法能在絕緣增量調(diào)整過程中自動調(diào)整相應的參數(shù)。

5結(jié)論

本文針對現(xiàn)有的v解路徑算法存在路徑不可更新的弊端,提出了改進的v-SVR的v解路徑算法。首先基于v-SVR的修改形式以及定理1,解決了對偶問題存在的兩個問題;再通過引入新的變量和附加項的策略,解決了v解路徑算法中存在的路徑不可更新問題。通過理論分析以及對標準回歸測試數(shù)據(jù)集的仿真研究,驗證了ISvrPath算法能夠有效地避免在絕緣增量調(diào)整過程中存在的沖突和異常,并經(jīng)過有限次數(shù)迭代擬合出整個v解路徑。

事實上,ISvrPath算法能夠推廣到更加廣泛的含有多個等式約束的一類機器學習算法上,如排列支持向量機和v-SVC等。

參考文獻：

[1] Vapnik V N.Thenatureofstatisticallearningtheory[M]. New York: Springer, 1999: 3-30 .

[2] Anguita D, Ridella S, Rivieccio F. K-fold generalization capability assessment for support vector classifiers[C]∥Proc.oftheIEEEInternationalJointConferenceonNeuralNetworks, 2005: 855-858.

[3] Bousquet O, Elisseeff A. Stability and generalization[J].JournalofMachineLearningResearch, 2002, 2(3): 499-526.

[4] Keerthi S S, Sindhwani V, Chapelle O. An efficient method for gradient-based adaptation of hyperparameters in SVM models[C]∥Proc.oftheTwentiethAnnualConferenceonNeuralInformationProcessingSystems, 2007: 673-680.

[5] Hastie T, Rosset S, Tibshirani R, et al. The entire regularization path for the support vector machine[J].JournalofMachineLearningResearch, 2004, 5: 1391-1415.

[6] Gunter L, Zhu J. Computing the solution path for the regularized support vector regression[C]∥Proc.oftheAdvancesinNeuralInformationProcessingSystems, 2005: 483-490.

[7] Gunter L, Zhu J. Efficient computation and model selection for the support vector regression[J].NeuralComputation, 2007, 19(6): 1633-1655.

[8] Wang G, Yeung D Y, Lochovsky F H. A new solution path algorithm in support vector regression[J].IEEETrans.onNeuralNetworks, 2008, 19(10): 1753-1767.

[9] Sch?lkopf B, Smola A J, Williamson R C, et al. New support vector algorithms[J].NeuralComputation,2000,12(5):1207-1245.

[10] Steinwart I. On the optimal parameter choice forv-support vector machines[J].IEEETrans.onPatternAnalysisandMachineIntelligence, 2003, 25(10): 1274-1284.

[11] Loosli G, Gasso G, Canu S. Regularization paths forv-SVM andv-SVR[C]∥Proc.ofthe4thInternationalSymposiumonNeuralNetworks, 2007: 486-496.

[12] Gu B, Wang J D, Yu Y C. An effective regularization path forv-support vector classification[C]∥Proc.ofthe3rdInternationalConferenceSymposiumonIntelligentInformationTechnologyApplication, 2009: 90-93.

[13] Gu B, Wang J D, Yu Y C, et al. Accurate on-linev-support vector learning[J].NeuralNetworks, 2012, 27：51-59.

[14] Gu B, Wang J D, Zheng G S, et al. Regularization path forv-support vector classification[J].IEEETrans.onNeuralNetworksandLearningSystems, 2012, 23(5): 800-811.

[15] Gu B, Wang J D. Effectivev-path algorithm forv-support vector regression[J].JournalofSoftware, 2012, 23(10): 2643-2654. (顧彬, 王建東. 有效的v支持向量回歸機的v解路徑算法[J]. 軟件學報, 2012, 23(10): 2643-2654.)

[16] Deng N Y, Tian Y J.Supportvectormachines:anewmethodindatamining[M]. Beijing: Science Press, 2004: 254-259. (鄧乃揚, 田英杰. 數(shù)據(jù)挖掘中的新方法—支持向量機[M]. 北京: 科學出版社, 2004: 254-259. )

[17] Chang C C, Lin C J. Trainingv-support vector regression: theory and algorithms[J].NeuralComputation, 2002, 14(8): 1959-1977.

[18] Martin M. On-line support vector machines for function approximation[C]∥Proc.ofthe13thEuropeanConferenceonMachineLearning, 2002: 282-294.

[19] Ma J, Theiler J, Perkins S. Accurate on-line support vector regression[J].NeuralComputation,2003,15(11):2683-2703.

[20] Golub G H, Van Loan C F.Matrixcomputations[M]. London: John Hopkins University Press, 1996:174-182.

[21] Diehl C P, Cauwenberghs G. SVM incremental learning, adaptation and optimization[C]∥Proc.oftheInternationalJointConferenceonNeuralNetworks, 2003: 2685-2690.

[22] Bertsekas D P.Convexoptimizationtheory[M]. Beijing: Tsinghua University Press, 2011: 167-181. (博賽克斯. 凸優(yōu)化理論[M]. 北京: 清華大學出版社, 2011: 167-181.)

顧斌杰(1980-),男,講師,博士研究生,主要研究方向為機器學習算法、工業(yè)過程建模。

E-mail:gubinjie1980@126.com

潘豐(1963-),男,教授,博士,主要研究方向為工業(yè)過程建模及優(yōu)化控制。

E-mail:pan_feng_63@163.com

網(wǎng)絡優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150817.1421.002.html

Improvedvsolution path forv-support vector regression

GU Bin-jie, PAN Feng

(KeyLaboratoryofAdvancedProcessControlforLightIndustry(MinistryofEducation),

JiangnanUniversity,Wuxi214122,China)

Abstract:In comparison with the dual formulation of ε-support vector machine, the dual of v-support vector regression (v-SVR) has an extra inequality constraint. To date, there is no effective and feasible v solution path for v-SVR. To solve the infeasible updating path problem of the v solution path for v-SVR, which was first proposed by Loosli et al, an improved v solution path for v-SVR is proposed. Based on the modified formulation of v-SVR and the Karush-Kuhn-Tucker (KKT) conditions, the strategy of using a new introduced variable and an extra term can avoid the conflicts and exceptions effectively during the adiabatic incremental adjustments. Finally, the proposed algorithm can fit the entire v solution path within the finite number of iterations. Theoretical analysis and simulation results demonstrate that the proposed algorithm is effective and feasible.

Keywords:machine learning; model selection; v-support vector regression (v-SVR); v solution path

作者簡介：

中圖分類號：TP 181

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2016.01.32

基金項目：國家自然科學基金(61273131)；江蘇省產(chǎn)學研聯(lián)合創(chuàng)新資金項目(BY2013015-39)資助課題

收稿日期：2014-10-30；修回日期：2015-06-01；網(wǎng)絡優(yōu)先出版日期：2015-08-17。