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

石勇 李佩佳 汪華東

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

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

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

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

1 非平行支持向量回歸機

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

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

在模型式(1)中,第一項為正則項,第二項和第三項為L1損失項,其中第二項是要求學習的超平面盡可能考慮第類樣本,第三項要求其他類樣本離該超平面盡可能遠,且其中標簽大于的樣本和標簽小于的樣本分別位于該超平面兩側,以更好地利用標簽的有序信息.值得強調的是,學習的個子優化模型(1)相互獨立,因而可并行學習.

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

若第類對應的模型式(1)的解為,那么關于第類的最優超平面即為,其中. 預測準則被定義為:

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

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

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

對于具有類的順序回歸問題,L2-NPSVOR由個子優化模型式(3)(或對偶問題式(5))組成.

3 訓練算法

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

3.1 信賴域牛頓法

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

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

然后,在內層迭代中,求解該模型獲得擬牛頓方向s.TRON 算法根據近似函數調整優化半徑,具體調整方法參見文獻[14].在構造二次優化問題時,需要計算梯度和Hessian矩陣.由于連續可微,存在梯度

其中

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

對于算法終止條件,我們考察算法第k次迭代步時目標函數的梯度相對初始梯度關系,以及樣本類別樣本規模,建立如下終止條件

其中為給定終止精度,表示指標集元素個數,n為訓練樣本個數.

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

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

2)根據類別k定義.

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

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

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

3.2 對偶坐標下降算法

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

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

其中與對偶變量相關

對偶坐標下降算法,每次僅更新一個變量,同時固定其他變量.由于目標函數變量中關于存在不可微項,這里對的變量分別討論.

根據軟閾值的方法可知,優化問題的解為

其中

在算法迭代中,需要判斷優化變量是否達到最優性條件,定義優化目標函數關于的投影梯度為

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

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

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

關于終止條件,我們可以采用文獻[17]的終止條件,即

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

其中

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

4 數值實驗

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

4.1 實驗數據準備與評價標準

針對大規模高維稀疏的順序回歸問題,目前還缺少相關的研究.這里我們收集并整理了部分文本順序回歸數據集,這些數據來自情感分析、電影評論、Amazon商品評論等多個領域,具體數據集如下:

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

2)Treebank3http://nlp.stanford.edu/sentiment/,來自斯坦福大學構建的情感數據庫Treebank,每條數據對應一個來自{very negative,negative,neutral,positive,very positive}的標簽.

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

4)LargeMovie5http://ai.stanford.edu/～amaas/data/sentiment/,是一個包含8種情感類別的電影評論數據.

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

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

關于評價標準,由于順序回歸問題與普通多分類問題不同,預測標準是預測標簽與真實標簽盡可能接近,因此,這里采用平均絕對誤差(Mean absolute error,MAE)和平均均方誤差(Mean square error,MSE)作為評價準則,即給定預測標簽和實際標簽,MAE和MSE定義如下

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

4.2 L2-NPSVOR與其他模型比較

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

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

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

3)RedSVM[7],對于p類順序回歸問題,其學習一個線性映射將樣本映射到一維實數軸上,在該數軸上尋找p?1個具有最大劃分間隔的閾值點,將直線分成p個連續的區間段進行預測.文獻[7]提出一種處理順序回歸的框架,將順序回歸問題轉化為一個二元分類問題,對樣本通過擴展將其轉化為二分類樣本,其中當,否則.

4)L1-NPSVOR[10],基于L1損失的NPSVOR,屬于有序分解模型,根據標簽有序信息,對每個類別均構造一個三劃分并學習一個超平面,從而構建了優化模型式(1),可直接將文獻[11]的DCD算法直接擴展求解其對偶問題.

表1 數據集特征描述Table 1 Data statistics

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

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

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

從表2的結果中,通過觀察可以得到以下幾點結論:

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

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

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

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

4.3 TRON與DCD算法比較

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

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

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

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

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

DCD-Mm:Hsieh等[11]在設計線性SVM的對偶坐標下降算法中,根據梯度投影的最大幅度值作為終止條件的判斷依據,并根據上下振幅值作為Shrinking閾值,將該策略應用到文本的DCD算法中,即Shrinking條件為,當時,

在訓練集上進行訓練,記錄目標函數值變化情況.由于L2-NPSVOR對于每個類別均需要求解一個子優化模型,圖2僅展示類別3對應的子優化模型(即k=3)絕對目標函數差訓練時間的變化.

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

圖2 TRON,TRON(WS),DCD-M and DCD-Mm在8個數據集上的比較(這里展示了類別3對應的優化問題).橫坐標是時間,縱坐標為L2-NPSVOR 原問題目標函數的的值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參數敏感性

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

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

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

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

5 結束語

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