L2損失大規(guī)模線性非平行支持向量順序回歸模型

石勇 李佩佳 汪華東

順序回歸旨在對(duì)具有順序標(biāo)簽結(jié)構(gòu)的樣本進(jìn)行分類.近些年隨著數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)技術(shù)的發(fā)展,順序回歸模型在情感分析、產(chǎn)品評(píng)論、信用評(píng)估、用戶畫像等領(lǐng)域得到了廣泛應(yīng)用[1?3].在這些領(lǐng)域中,其樣本標(biāo)簽包含順序信息,不同的錯(cuò)誤樣本代價(jià)往往不同.如用戶畫像領(lǐng)域中對(duì)年齡的預(yù)估,20歲的青年用戶被錯(cuò)分為30歲和50歲形成的用戶畫像有明顯差異.再如在信用評(píng)估領(lǐng)域,一個(gè)信用值極低的公司被錯(cuò)分為一般低和較高所影響的決策大相徑庭.因此,順序回歸問題受到越來越多的重視.順序回歸在機(jī)器學(xué)習(xí)領(lǐng)域中介于分類問題和回歸問題之間.與分類問題不同,順序回歸問題的標(biāo)簽集合具有順序結(jié)構(gòu)而不僅僅是一個(gè)多類別集合.再者,與回歸問題不同,順序回歸問題的標(biāo)簽不具有度量信息.

在解決順序回歸問題時(shí)一方面需要考慮順序信息,另一方面由于對(duì)不同分錯(cuò)樣本的處理不同,所以在構(gòu)建模型時(shí),對(duì)損失項(xiàng)的特殊處理有助于使預(yù)測標(biāo)簽與實(shí)際標(biāo)簽盡可能接近,提高模型的性能.如此,為了使與真實(shí)標(biāo)簽產(chǎn)生較大偏差的樣本得到更大的懲罰,我們在建模中采用L2損失(均方Hinge損失)作為模型損失函數(shù),旨在最小化真實(shí)值與估計(jì)值的距離的平方,使得訓(xùn)練的模型能更好地處理與真實(shí)標(biāo)簽間的差異.與此同時(shí),L2損失對(duì)離群點(diǎn)較敏感,一個(gè)合適的訓(xùn)練模型算法顯得如此重要.針對(duì)求解算法,Hsieh等研究了標(biāo)準(zhǔn)的線性支持向量分類(Support vector classification,SVC)[11]和支持向量回歸(Support vector regression,SVR)[12]求解算法,并提出了相應(yīng)處理大規(guī)模數(shù)據(jù)的求解算法如對(duì)偶坐標(biāo)下降算法(DCD)和信賴域算法.雖然Hsieh等[11?12]的模型和算法被廣泛應(yīng)用在文本挖掘中,但這些模型和算法主要解決了標(biāo)準(zhǔn)的多分類和回歸問題,而在順序回歸模型中還沒有得到應(yīng)用.所以該文提出能快速求解基于L2損失的非平行支持向量回歸機(jī)的算法.

本文提出一種基于L2損失的線性非平行支持向量順序回歸模型.從目前研究來看,這是在順序回歸領(lǐng)域中第一個(gè)處理大規(guī)模問題的相關(guān)工作.此外,針對(duì)該模型,該文設(shè)計(jì)了兩種求解該模型的算法并比較了兩種算法的性能表現(xiàn).

本文組織結(jié)構(gòu)如下:第1節(jié)介紹基于L1損失的NPSVOR模型.第2節(jié)介紹本文提出的基于L2損失的線性NPSVOR(L2-NPSVOR)模型,并給出其對(duì)偶模型.第3節(jié)研究求解L2-NPSVOR模型的優(yōu)化算法,從原問題和對(duì)偶問題兩個(gè)角度分別給出了信賴域牛頓算法和對(duì)偶坐標(biāo)下降算法.第4節(jié)主要介紹數(shù)值實(shí)驗(yàn),將提出的L2-NPSVOR模型與其他相關(guān)模型進(jìn)行分析比較,驗(yàn)證模型的有效性.最后,對(duì)本文研究工作進(jìn)行總結(jié).

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

在順序回歸問題中,每個(gè)訓(xùn)練樣本均由一個(gè)特征向量和一個(gè)有序標(biāo)簽組成.假設(shè)順序回歸問題有個(gè)不同的具有有序結(jié)構(gòu)的類別,為不失一般性,我們用連續(xù)整數(shù)1,2表示其類別,用表示樣本的數(shù)量.則順序回歸樣本集可以表示為:

文獻(xiàn)[10]提出的非平行支持向量順序回歸模型(NPSVOR),其可以在原空間上學(xué)習(xí)多個(gè)非平行的超平面,對(duì)數(shù)據(jù)分布具有更好的適應(yīng)性.并在性能上優(yōu)于其他基于SVM的方法.對(duì)于類的順序回歸問題,NPSVOR 針對(duì)每個(gè)類別構(gòu)建有序三元分解學(xué)習(xí)一個(gè)超平面,即給定,首先對(duì)每個(gè)索引建立三個(gè)索引集:和.其中是的標(biāo)簽. 然后,學(xué)習(xí)一個(gè)映射,建立如下優(yōu)化模型

在模型式(1)中,第一項(xiàng)為正則項(xiàng),第二項(xiàng)和第三項(xiàng)為L1損失項(xiàng),其中第二項(xiàng)是要求學(xué)習(xí)的超平面盡可能考慮第類樣本,第三項(xiàng)要求其他類樣本離該超平面盡可能遠(yuǎn),且其中標(biāo)簽大于的樣本和標(biāo)簽小于的樣本分別位于該超平面兩側(cè),以更好地利用標(biāo)簽的有序信息.值得強(qiáng)調(diào)的是,學(xué)習(xí)的個(gè)子優(yōu)化模型(1)相互獨(dú)立,因而可并行學(xué)習(xí).

圖1 非平行支持向量順序回歸的幾何解釋(以類別2超平面構(gòu)建為例)Fig.1 Geometric interpretation of NPSVOR(It shows the construction of the 2-th proximal hyperplane)

若第類對(duì)應(yīng)的模型式(1)的解為,那么關(guān)于第類的最優(yōu)超平面即為,其中. 預(yù)測準(zhǔn)則被定義為:

2 基于L2損失的線性非平行支持向量順序回歸機(jī)

本節(jié)將在NPSVOR模型基礎(chǔ)上描述本文提出的基于L2損失(均方Hinge損失)的線性NPSVOR模型.考慮到模型(1)中L1損失對(duì)損失的懲罰是線性關(guān)系,而順序回歸問題建模目標(biāo)是使預(yù)測標(biāo)簽與真實(shí)標(biāo)簽盡可能接近,這促使我們考慮采用L2損失函數(shù),其對(duì)于較大的損失給予更大懲罰,使模型盡可能避免產(chǎn)生較大偏差預(yù)測.

據(jù)此,我們考慮建立L2損失線性NPSVOR模型

對(duì)于具有類的順序回歸問題,L2-NPSVOR由個(gè)子優(yōu)化模型式(3)(或?qū)ε紗栴}式(5))組成.

3 訓(xùn)練算法

在本節(jié)中,我們將針對(duì)L2-NPSVOR模型,從原問題及其對(duì)偶問題兩個(gè)角度,分別設(shè)計(jì)了信賴域牛頓算法和對(duì)偶坐標(biāo)下降算法求解該模型.由于不同k對(duì)應(yīng)的原問題式(3)及其對(duì)偶問題式(5)具有相同形式,為了方便討論,在不引起混淆的情況下,我們將忽略模型式(3)和式(5)中的下標(biāo)k.

3.1 信賴域牛頓法

信賴域牛頓算法(TrustregionNewton method,TRON)[13]是一種求解可微的無約束或有界約束問題的廣義優(yōu)化算法.Ho和Lin等研究了L2損失SVC和SVR以及Logistic回歸問題的TRON算法[12?14].這里將該算法應(yīng)用于L2-NPSVOR模型的求解.

采用TRON算法求解原問題(3),優(yōu)化過程包含兩層迭代:在第步外迭代中,給定,TRON算法構(gòu)造在信賴域半徑下的二次優(yōu)化問題,即

然后,在內(nèi)層迭代中,求解該模型獲得擬牛頓方向s.TRON 算法根據(jù)近似函數(shù)調(diào)整優(yōu)化半徑,具體調(diào)整方法參見文獻(xiàn)[14].在構(gòu)造二次優(yōu)化問題時(shí),需要計(jì)算梯度和Hessian矩陣.由于連續(xù)可微,存在梯度

其中

其中I為m階的單位矩陣,D為n階對(duì)角矩陣且

對(duì)于算法終止條件,我們考察算法第k次迭代步時(shí)目標(biāo)函數(shù)的梯度相對(duì)初始梯度關(guān)系,以及樣本類別樣本規(guī)模,建立如下終止條件

其中為給定終止精度,表示指標(biāo)集元素個(gè)數(shù),n為訓(xùn)練樣本個(gè)數(shù).

算法1給出了NPSVOR的信賴域牛頓法算法主要步驟.

算法 1.TRON:信賴域牛頓算法求解L2-NPSVOR的子模型式(3)

2)根據(jù)類別k定義.

算法1的效率主要依賴于是否能快速求解子優(yōu)化問題式(7).由于目標(biāo)函數(shù)的廣義Hessian矩陣式(8)是m×m階,對(duì)于高維問題直接計(jì)算該矩陣會(huì)使得內(nèi)存難以存儲(chǔ).同時(shí),由于樣本矩陣X高度稀疏,可采用共軛梯度算法進(jìn)行求解,因此只需要在算法優(yōu)化過程中計(jì)算和存儲(chǔ)Hessian矩陣式(8)與向量的乘積,即

算法2給出了求解問題(7)的共軛梯度算法過程.

算法2.共軛梯度算法近似求解信賴域子問題(7)

3.2 對(duì)偶坐標(biāo)下降算法

坐標(biāo)下降算法(Coordinate descent method,CD)是一種無約束優(yōu)化技術(shù),被用于求解大規(guī)模線性SVM模型.Chang等[9]利用CD算法求解L2損失的線性SVM 模型的原始問題,實(shí)驗(yàn)表明這種方法可以快速獲取模型的解.Hsieh等[11]提出對(duì)偶坐標(biāo)下降算法(Dual coordinate descent method,DCD)求解線性SVM 模型,即在L1和L2損失的線性SVM 的對(duì)偶模型上利用CD算法,并采用Shrinking和隨機(jī)置換優(yōu)化樣本序列的加速技術(shù).當(dāng)數(shù)據(jù)的規(guī)模和特征維度規(guī)模都比較大時(shí),CD算法比其他算法在求解線性SVM模型上能獲得更好的效果[11,16].Yuan等[17]將DCD算法應(yīng)用于求解L1正則化的優(yōu)化問題.Tseng和Yun[18]系統(tǒng)討論了L1正則優(yōu)化問題的分解算法,給出分解算法的一般性框架[12].將DCD算法擴(kuò)展到求解大規(guī)模SVR問題中,但采用了與文獻(xiàn)[11]中不同的Shrinking準(zhǔn)則和算法終止策略,研究表明這種策略在回歸問題中可以快速獲得優(yōu)化模型的解.本節(jié)將利用DCD算法求解基于L2損失的線性NPSVOR,實(shí)現(xiàn)大規(guī)模順序回歸問題的求解.

忽略原問題式(3)的下標(biāo)k,其對(duì)偶問題式(5)可寫為:

其中與對(duì)偶變量相關(guān)

對(duì)偶坐標(biāo)下降算法,每次僅更新一個(gè)變量,同時(shí)固定其他變量.由于目標(biāo)函數(shù)變量中關(guān)于存在不可微項(xiàng),這里對(duì)的變量分別討論.

根據(jù)軟閾值的方法可知,優(yōu)化問題的解為

其中

在算法迭代中,需要判斷優(yōu)化變量是否達(dá)到最優(yōu)性條件,定義優(yōu)化目標(biāo)函數(shù)關(guān)于的投影梯度為

算法3.DCD:坐標(biāo)下降法求解L2-NPSVOR的對(duì)偶問題(5)

3)while不滿足最優(yōu)性條件:do(4)

do步驟5),6),7).

關(guān)于終止條件,我們可以采用文獻(xiàn)[17]的終止條件,即

Shrinking策略[19],是一種算法加速技術(shù),在算法迭代訓(xùn)練時(shí)刪去一些值不變的變量,通過減少優(yōu)化問題的變量規(guī)模實(shí)現(xiàn)對(duì)算法的加速.該策略常被用于SVM 的分解算法,只是不同的算法和模型在具體操作上有所不同.在本文的DCD算法中,也采用了該技術(shù),即考慮在算法的有序迭代中,刪除達(dá)到約束邊界的最優(yōu)變量(即)以及不可微點(diǎn).對(duì)于變量,Shrinking條件為:

其中

這里取梯度違反值絕對(duì)值的最大值式(35)作為Shrinking閾值條件,并考察梯度違反值與初始v0值縮小比例式(32)進(jìn)行算法終止.在后面實(shí)驗(yàn)中,我們將進(jìn)一步對(duì)比在設(shè)計(jì)大規(guī)模線性SVM 的DCD算法中提出的Shrinking技術(shù)和終止策略[11],即對(duì)梯度違反值正負(fù)值分別維持閾值M,m,然后并將作為算法終止條件(具體見文獻(xiàn)[11]),以說明本文算法設(shè)計(jì)的合理性.

4 數(shù)值實(shí)驗(yàn)

為驗(yàn)證提出的L2-NPSVOR模型及算法的有效性,本文在多個(gè)數(shù)據(jù)集上與其他基于SVM 的順序回歸模型進(jìn)行了性能比較.其中比較的模型包括:L1-NPSVOR、SVM、SVR、RedSVM 等.此外,本文還比較了TRON和DCD在L2損失的NPSVOR模型的算法效率.最后本文分析了L2-NPSVOR模型對(duì)參數(shù)的敏感性.TRON和DCD算法均在LIBLINEAR框架基礎(chǔ)上用C++實(shí)現(xiàn)1算法代碼已上傳至https://github.com/huadong2014/LinearNPSVOR/.,實(shí)驗(yàn)平臺(tái)為Intel Xeon 2.0GHz CPU(E5504),4MB cache,內(nèi)存4GB,Linux系統(tǒng).

4.1 實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)備與評(píng)價(jià)標(biāo)準(zhǔn)

針對(duì)大規(guī)模高維稀疏的順序回歸問題,目前還缺少相關(guān)的研究.這里我們收集并整理了部分文本順序回歸數(shù)據(jù)集,這些數(shù)據(jù)來自情感分析、電影評(píng)論、Amazon商品評(píng)論等多個(gè)領(lǐng)域,具體數(shù)據(jù)集如下:

1)TripAdvisor2數(shù)據(jù)集取自http://www.cs.virginia.edu/～hw5x/dataset.html,是一個(gè)酒店評(píng)論數(shù)據(jù)集,最早被用于文本潛在語義分析[20].每條評(píng)論有一個(gè)1至5顆星的打分.

2)Treebank3http://nlp.stanford.edu/sentiment/,來自斯坦福大學(xué)構(gòu)建的情感數(shù)據(jù)庫Treebank,每條數(shù)據(jù)對(duì)應(yīng)一個(gè)來自{very negative,negative,neutral,positive,very positive}的標(biāo)簽.

3)MovieReview[21],電影評(píng)論數(shù)據(jù)集4scale dataset v1.0:http://www.cs.cornell.edu/people/pabo/movie-review-data/.順序標(biāo)簽是從連續(xù)值[0,1]離散化得到,即a)rating≤0.3,b)0.4≤rating≤0.5,c)0.6≤rating≤0.7,d)0.8≤rating.該數(shù)據(jù)集常被用于情感分析.

4)LargeMovie5http://ai.stanford.edu/～amaas/data/sentiment/,是一個(gè)包含8種情感類別的電影評(píng)論數(shù)據(jù).

5)Amazon產(chǎn)品評(píng)論,有8個(gè)數(shù)據(jù)集,來自兩個(gè)數(shù)據(jù)資源網(wǎng)站:其中4個(gè)數(shù)據(jù)集來自文獻(xiàn)[20],包括AmazonMp3,VideoSurveillance,Mobilephone,Cameras6http://sifaka.cs.uiuc.edu/～wang296/Data/index.html;另外4個(gè)數(shù)據(jù)集(Electronics,Health-Care,AppsAndroid,HomeKitchen)[22?23]來自 A-mazon產(chǎn)品評(píng)論數(shù)據(jù)集7Amazon product reviews datasets:http://jmcauley.ucsd.edu/data/amazon/,所有數(shù)據(jù)均是文本評(píng)論,且有5個(gè)類別.由于實(shí)際數(shù)據(jù)集類別樣本分布不均衡,為了不影響模型測試表現(xiàn),這里對(duì)數(shù)據(jù)集進(jìn)行降采樣得到平衡數(shù)據(jù)集.

以上數(shù)據(jù)集均為文本數(shù)據(jù),故本文對(duì)這些數(shù)據(jù)進(jìn)行下列預(yù)處理:詞干化、去停用詞、刪除詞頻小于3次的詞,以及在所有文本出現(xiàn)的頻率大于50%或出現(xiàn)少于2次的詞.此外,我們采用unigram,bigram作為特征,利用TF-IDF技術(shù)提取文本特征.為了方便實(shí)驗(yàn)算法分析和方法比較,將每個(gè)數(shù)據(jù)集隨機(jī)劃分為兩部分,即取20%條數(shù)據(jù)作為測試集,剩余80%條數(shù)據(jù)作為訓(xùn)練集.數(shù)據(jù)集的統(tǒng)計(jì)描述見表1所示,其特征包括樣本規(guī)模、特征維數(shù)、訓(xùn)練集非零元素個(gè)數(shù)等.

關(guān)于評(píng)價(jià)標(biāo)準(zhǔn),由于順序回歸問題與普通多分類問題不同,預(yù)測標(biāo)準(zhǔn)是預(yù)測標(biāo)簽與真實(shí)標(biāo)簽盡可能接近,因此,這里采用平均絕對(duì)誤差(Mean absolute error,MAE)和平均均方誤差(Mean square error,MSE)作為評(píng)價(jià)準(zhǔn)則,即給定預(yù)測標(biāo)簽和實(shí)際標(biāo)簽,MAE和MSE定義如下

該指標(biāo)被廣泛用于刻畫順序回歸模型預(yù)測與實(shí)際標(biāo)簽的接近程度[6?7,24?25].

4.2 L2-NPSVOR與其他模型比較

本節(jié)我們測試線性L2-NPSVOR的泛化效果,并與其他SVM相關(guān)方法比較,比較方法具體如下:

1)SVC[11],將順序回歸看成普通多分類問題處理的樸素方法.文獻(xiàn)[11]給出了線性SVM模型的DCD算法,在算法中采用了隨機(jī)置換和Shinking加速技術(shù).該算法已經(jīng)實(shí)現(xiàn)并集成在著名的LIBLINEAR軟件包中,采用one-vs-all的方式策略進(jìn)行多分類預(yù)測.

2)SVR[12],將順序回歸標(biāo)簽看成普通數(shù)值,采用數(shù)值回歸的方式進(jìn)行處理,同樣屬于一種樸素方法.SVR模型預(yù)測值是連續(xù)的數(shù)值,本文對(duì)預(yù)測后的連續(xù)數(shù)值按照相鄰的整數(shù)離散成相應(yīng)的類別標(biāo)簽.文獻(xiàn)[12]給出了線性SVR的DCD求解算法,并在LIBLINEAR中實(shí)現(xiàn),這里僅對(duì)預(yù)測函數(shù)作了修改.

3)RedSVM[7],對(duì)于p類順序回歸問題,其學(xué)習(xí)一個(gè)線性映射將樣本映射到一維實(shí)數(shù)軸上,在該數(shù)軸上尋找p?1個(gè)具有最大劃分間隔的閾值點(diǎn),將直線分成p個(gè)連續(xù)的區(qū)間段進(jìn)行預(yù)測.文獻(xiàn)[7]提出一種處理順序回歸的框架,將順序回歸問題轉(zhuǎn)化為一個(gè)二元分類問題,對(duì)樣本通過擴(kuò)展將其轉(zhuǎn)化為二分類樣本,其中當(dāng),否則.

4)L1-NPSVOR[10],基于L1損失的NPSVOR,屬于有序分解模型,根據(jù)標(biāo)簽有序信息,對(duì)每個(gè)類別均構(gòu)造一個(gè)三劃分并學(xué)習(xí)一個(gè)超平面,從而構(gòu)建了優(yōu)化模型式(1),可直接將文獻(xiàn)[11]的DCD算法直接擴(kuò)展求解其對(duì)偶問題.

表1 數(shù)據(jù)集特征描述Table 1 Data statistics

5)L2-NPSVOR(TRON),即L2損失的NPSVOR,采用信賴域牛頓法(見算法1)求解,共軛梯度算法(算法2)求解信賴域子問題式(7).

6)L2-NPSVOR (DCD),即L2損失的NPSVOR,采用對(duì)偶坐標(biāo)下降法(見算法3)求解,終止條件為式(32),Shrinking策略為式(33)和式(34).

該實(shí)驗(yàn)在訓(xùn)練集上進(jìn)行5-折交叉驗(yàn)證進(jìn)行參數(shù)選擇,參數(shù)選擇范圍設(shè)定在.以MAE作為交叉驗(yàn)證選參的標(biāo)準(zhǔn),通過參數(shù)選擇后的最優(yōu)參數(shù)作為模型訓(xùn)練的參數(shù).關(guān)于實(shí)驗(yàn)參數(shù)設(shè)置方面,基于DCD算法求解的模型終止精度均設(shè)為0.1,和均采用0向量作為初始化,TRON的終止精度設(shè)定為0.001.另外,為公平起見,在NPSVOR算法中該實(shí)驗(yàn)固定參數(shù)值為0.1,,并與其他模型中的采用同樣的選參方式,除RedSVM模型8需要注意的是,因?yàn)槟壳斑€沒有針對(duì)順序回歸問題提出的大規(guī)模求解算法,RedSVM模型只有非線性模型的求解算法,故本文對(duì)線性RedSVM算法求解時(shí)采用文獻(xiàn)[7]中DCD算法對(duì)RedSVM的線性版本進(jìn)行實(shí)現(xiàn).,其他模型均采用有偏置項(xiàng)模型.實(shí)驗(yàn)數(shù)據(jù)集如表1所示.表2給出了各模型在不同數(shù)據(jù)集上MAE、MSE值和訓(xùn)練時(shí)間(Time),表中每行最好的結(jié)果均已經(jīng)加粗顯示.表2的最后列出了各方法在所有數(shù)據(jù)集上關(guān)于MAE、MSE和訓(xùn)練時(shí)間的平均排序,以方便比較各模型之間的性能.

從表2的結(jié)果中,通過觀察可以得到以下幾點(diǎn)結(jié)論:

1)根據(jù)各方法在所有數(shù)據(jù)集上平均排序可以看出,L2-NPSVOR較其他方法在MAE和MSE上,取得了最好的預(yù)測效果.雖然L2-NPSVOR在TRON和DCD算法得到的預(yù)測效果接近,但DCD在總體上得到了更好的MAE和MSE值,算法的訓(xùn)練時(shí)間相對(duì)TRON優(yōu)勢明顯.

2)RedSVM模型在非線性情況下表現(xiàn)突出[4],但在大規(guī)模數(shù)據(jù)集的表現(xiàn)略低于樸素方法線性L1/L2-SVC.

3)對(duì)比L1-NPSVOR和L2-NPSVOR,采用L2損失的模型在MAE、MSE優(yōu)于L1-NPSVOR模型,這與我們的預(yù)期一致,即順序回歸問題預(yù)測要求預(yù)測標(biāo)簽與實(shí)際標(biāo)簽盡可能接近,L2損失對(duì)于損失偏差較大的樣本給予更大的懲罰,可得到預(yù)測偏差更小的模型.此外,基于L2損失的NPSVOR在DCD算法下可以得到更快的優(yōu)化速度.

4)在算法的訓(xùn)練時(shí)間上,基于DCD算法的L2-NPSVOR獲得了除SVR外最快的訓(xùn)練速度.盡管SVR在時(shí)間上具有優(yōu)勢,但其在順序回歸上的預(yù)測結(jié)果相對(duì)較差,這也說明將順序回歸問題等同于數(shù)值回歸存在一定的缺陷.

4.3 TRON與DCD算法比較

本文針對(duì)NPSVOR提出了信賴域牛頓算法和對(duì)偶坐標(biāo)下降算法,這里我們對(duì)算法效率進(jìn)行比較.假設(shè)原問題的優(yōu)化目標(biāo)函數(shù)為,通過觀察算法訓(xùn)練過程中目標(biāo)函數(shù)值與最優(yōu)值目標(biāo)函數(shù)值的接近程度,即來比較算法效率.為說明本文算法設(shè)計(jì)的合理性,考慮以下四種情形:

表2 方法在各數(shù)據(jù)集上測試結(jié)果,包括MAE、MSE和最優(yōu)參數(shù)下的訓(xùn)練時(shí)間(s)Table 2 Test results for each dataset and method,including MAE,MSE and training time(s)

TRON:即本文給出的信賴域牛頓算法1,在算法中NPSVOR各子模型獨(dú)立求解,均初始化,可分布并行求解各子模型.為方便比較,這里僅考慮串行求解方式.

TRON(WS):在利用TRON算法求解NPSVOR各子模型時(shí),可采用暖啟動(dòng)策略(Warm start,WS).由于在NPSVOR模型中,每個(gè)子模型的超平面是基于有序三元分解建立的,其是根據(jù)標(biāo)簽的有序結(jié)構(gòu)信息得到,因而相鄰類別對(duì)應(yīng)的超平面相對(duì)比較接近,對(duì)應(yīng)的解具有相似的結(jié)構(gòu),即.如果依次求解對(duì)應(yīng)的模型,在求解第k+1個(gè)子模型時(shí),可以利用第k個(gè)模型的解作為其初始解,這樣可以利用順序回歸的特有性質(zhì)來加速模型的求解.

DCD-M:即本文給出的對(duì)偶坐標(biāo)下降算法3.算法中采用了Yuan等[17]給出的終止準(zhǔn)則和Shrinking策略,即采用最優(yōu)梯度違反值的絕對(duì)值最大值式(35)作為判斷最優(yōu)性條件的閾值.

DCD-Mm:Hsieh等[11]在設(shè)計(jì)線性SVM的對(duì)偶坐標(biāo)下降算法中,根據(jù)梯度投影的最大幅度值作為終止條件的判斷依據(jù),并根據(jù)上下振幅值作為Shrinking閾值,將該策略應(yīng)用到文本的DCD算法中,即Shrinking條件為,當(dāng)時(shí),

在訓(xùn)練集上進(jìn)行訓(xùn)練,記錄目標(biāo)函數(shù)值變化情況.由于L2-NPSVOR對(duì)于每個(gè)類別均需要求解一個(gè)子優(yōu)化模型,圖2僅展示類別3對(duì)應(yīng)的子優(yōu)化模型(即k=3)絕對(duì)目標(biāo)函數(shù)差訓(xùn)練時(shí)間的變化.

從圖2中,我們可以觀察到:1)采用暖啟動(dòng)的TRON算法TRON(WS)在其中6個(gè)數(shù)據(jù)集上有較為明顯的加速,但在短的訓(xùn)練時(shí)間內(nèi),加速不明顯.2)目標(biāo)函數(shù)的在DCD-M算法優(yōu)化下在給出的8個(gè)數(shù)據(jù)集中比TRON算法高效并且獲得了更低的目標(biāo)函數(shù)值,DCD-M算法優(yōu)勢明顯.3)DCD-Mm采用文獻(xiàn)[11]的終止條件和Shrinking策略,實(shí)驗(yàn)表明目標(biāo)函數(shù)值過早趨于平穩(wěn),并且不能夠及時(shí)有效終止算法.

圖2 TRON,TRON(WS),DCD-M and DCD-Mm在8個(gè)數(shù)據(jù)集上的比較(這里展示了類別3對(duì)應(yīng)的優(yōu)化問題).橫坐標(biāo)是時(shí)間,縱坐標(biāo)為L2-NPSVOR 原問題目標(biāo)函數(shù)的的值Fig.2 Comparison of TRON,TRON(WS),DCD-M and DCD-Mm on eight datasets(Show the optimization model for rank 3).The horizontal axis is training time in seconds and the vertical axis is the difference between

4.4 L1-NPSVOR和L2-NPSVOR參數(shù)敏感性

參數(shù)選擇通常十分耗時(shí),故我們期望得到的模型對(duì)參數(shù)不敏感,即參數(shù)值的變化不會(huì)有較大的測試結(jié)果變化.本節(jié)實(shí)驗(yàn)將比較L1-NPSVOR和L2-NPSVOR關(guān)于MAE和MSE隨參數(shù)值C改變的變化情況(限定并記為C),采用DCD算法求解.實(shí)驗(yàn)選擇與第4.3節(jié)相同的8個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),參數(shù)C的變化范圍設(shè)定為{2?5,2?4,···,25},采用 5 折交叉驗(yàn)證得到每個(gè)參數(shù)值下的測試MAE/MSE值.MAE和MSE變化趨勢分別如圖3和圖4所示.

圖3 L1/L2-NPSVOR的MAE分別隨參數(shù)C變化Fig.3 Test MAE results of L1/L2-NPSVOR change with parameterCon eight datasets

圖4 L1/L2-NPSVOR的MSE分別隨參數(shù)變化Fig.4 Test MSE results of L1/L2-NPSVOR change with parameteron eight datasets

從圖3和圖4中可以觀察得到,基于L2損失的NPSVOR在MAE/MSE上隨參數(shù)C變化相對(duì)平穩(wěn),變化幅度均低于采用L1損失的對(duì)應(yīng)結(jié)果,尤其是在參數(shù)值C較小的情況下,在此情形下,L1-/L2-NPSVOR均在訓(xùn)練數(shù)據(jù)集上出現(xiàn)欠擬合問題,但是由于L2損失對(duì)損失的懲罰要高于L1損失,故欠擬合問題嚴(yán)重性相對(duì)較弱一些.另外,從圖4中最后3個(gè)數(shù)據(jù)集(Apps Android、Electronics和Health Care)對(duì)比看出,L2損失在MSE上有顯著地提高.以上結(jié)果表明,L2損失對(duì)參數(shù)C的敏感性低于L1損失,即利用L2損失,可以更容易選出較合適的參數(shù).

5 結(jié)束語

本文針對(duì)大規(guī)模、高維、稀疏的順序回歸問題,考慮到L2損失的引入對(duì)偏離較大的點(diǎn)給予更大的懲罰,使得預(yù)測標(biāo)簽與真實(shí)標(biāo)簽更加接近,而線性模型的提出能成功解決大規(guī)模數(shù)據(jù)面對(duì)的速度及內(nèi)存消耗問題,所以本文提出基于L2損失的線性非平行支持向量順序回歸模型—L2-NPSVOR.另外本文從原問題及其對(duì)偶問題兩個(gè)角度,分別設(shè)計(jì)了信賴域牛頓算法和對(duì)偶坐標(biāo)下降算法求解該模型.其中在TRON算法中,考慮到順序回歸相鄰的超平面具有相似的解,在算法求解時(shí)提出暖啟動(dòng)的方法.最后,為驗(yàn)證模型及算法的有效性,本文在收集的大量文本順序回歸數(shù)據(jù)上對(duì)提出的模型及算法進(jìn)行了分析和比較.結(jié)果表明,相比其他基于SVM的順序回歸模型,L2-NPSVOR在性能上表現(xiàn)最優(yōu);關(guān)于求解算法,TRON算法能夠獲得比DCD更加精確的解,但當(dāng)樣本維數(shù)遠(yuǎn)遠(yuǎn)高于樣本數(shù)時(shí),DCD算法比TRON更加高效.