改進(jìn)的v-支持向量回歸機(jī)的v解路徑算法

顧斌杰, 潘　豐

(江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室, 江蘇 無(wú)錫 214122)

?

改進(jìn)的v-支持向量回歸機(jī)的v解路徑算法

顧斌杰, 潘豐

(江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室, 江蘇 無(wú)錫 214122)

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

關(guān)鍵詞：機(jī)器學(xué)習(xí); 模型選擇; v-支持向量回歸機(jī); v解路徑

0引言

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

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

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

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

(1)

v-SVR的對(duì)偶問(wèn)題(dualproblem,DP)如下[18]:

(2)

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

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

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

1.1v-SVR的修改形式

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

為了解決第一個(gè)問(wèn)題,把式(1)中的目標(biāo)函數(shù)P乘樣本點(diǎn)個(gè)數(shù)l,考慮如下的PP:

(3)

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

令Qij=Hij/l,則式(3)對(duì)應(yīng)的DP為

(4)

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

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

定理 1對(duì)于最優(yōu)化問(wèn)題(4), 當(dāng)0≤v≤1時(shí),總存在最優(yōu)解使得不等式約束eT(α+α*)≤vl可以用等式約束eT(α+α*)=vl來(lái)代替。

定理1的證明詳見(jiàn)文獻(xiàn)[17],此處省略。

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

(5)

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

(6)

式(5)對(duì)應(yīng)的拉格朗日函數(shù)為

LD=

(7)

1.2KKT條件

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

(8)

(9)

(10)

令

(11)

(12)

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

(13)

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

圖1　訓(xùn)練樣本集合S劃分成3個(gè)集合

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

2改進(jìn)的v-SVR的v解路徑算法

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

2.1ISvrPath算法步驟

步驟 2設(shè)置異常為假。

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

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

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

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

步驟 9重復(fù)步驟2和步驟8直至v<1。

2.2ISvrPath算法初始化

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

(14)

證畢

2.3ISvrPath算法的v解路徑

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

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

(15)

(16)

(17)

(18)

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

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

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

(19)

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

(20)

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

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

(22)

(23)

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

(24)

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

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

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

(25)

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

(26)

(27)

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

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

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

③當(dāng)Δ?min=Δ?3時(shí),如果t∈ISR-,則將樣本t從SSL集移入SR集;如果t∈I*SR-,則將樣本點(diǎn)t從SSR集移入SR集。

(4) 更新逆矩陣N

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

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

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

(28)

式中

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

(29)

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

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

3.1可行性理論分析

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

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

也就是說(shuō)矩陣QSSSS是半正定陣。

證畢

假設(shè) 1矩陣QSSSS是正定陣。

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

首先定義矩陣

因?yàn)?/p>

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

det(QSSSS)

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

故有:det(P)≥0。

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

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

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

證畢

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

證畢

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

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

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

而det(QSSSS)>0,故要求

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

證畢

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

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

其中

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

證畢

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

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

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

證畢

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

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

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

3.2有限收斂性理論分析

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

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

(30)

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

證明在絕緣增量調(diào)整過(guò)程中,設(shè)第k-1次調(diào)整時(shí)的能量函數(shù)為W[k-1](α(*)),而第k次調(diào)整時(shí)的能量函數(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,容易驗(yàn)證:

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

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

證畢

證明采用反證法。

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

證畢

4仿真實(shí)驗(yàn)研究

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

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

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

表2　仿真實(shí)驗(yàn)中采用的3個(gè)標(biāo)準(zhǔn)回歸測(cè)試數(shù)據(jù)集

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

4.1ISvrPath算法驗(yàn)證實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2ISvrPath算法比較實(shí)驗(yàn)

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

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

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

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

5結(jié)論

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

事實(shí)上,ISvrPath算法能夠推廣到更加廣泛的含有多個(gè)等式約束的一類機(jī)器學(xué)習(xí)算法上,如排列支持向量機(jī)和v-SVC等。

參考文獻(xiàn)：

[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支持向量回歸機(jī)的v解路徑算法[J]. 軟件學(xué)報(bào), 2012, 23(10): 2643-2654.)

[16] Deng N Y, Tian Y J.Supportvectormachines:anewmethodindatamining[M]. Beijing: Science Press, 2004: 254-259. (鄧乃揚(yáng), 田英杰. 數(shù)據(jù)挖掘中的新方法—支持向量機(jī)[M]. 北京: 科學(xué)出版社, 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]. 北京: 清華大學(xué)出版社, 2011: 167-181.)

顧斌杰(1980-),男,講師,博士研究生,主要研究方向?yàn)闄C(jī)器學(xué)習(xí)算法、工業(yè)過(guò)程建模。

E-mail:gubinjie1980@126.com

潘豐(1963-),男,教授,博士,主要研究方向?yàn)楣I(yè)過(guò)程建模及優(yōu)化控制。

E-mail:pan_feng_63@163.com

網(wǎng)絡(luò)優(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

作者簡(jiǎn)介：

中圖分類號(hào)：TP 181

文獻(xiàn)標(biāo)志碼：A

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

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

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