v-軟間隔羅杰斯特回歸分類機

黃成泉 王士同 蔣亦樟 董愛美③

?

v-軟間隔羅杰斯特回歸分類機

黃成泉*①②王士同①蔣亦樟①董愛美①③

①(江南大學(xué)數(shù)字媒體學(xué)院 無錫 214122)②(貴州民族大學(xué)工程實訓(xùn)中心 貴陽 550025)③(齊魯工業(yè)大學(xué)信息學(xué)院 濟南 250353)

坐標下降(Coordinate Descent, CD)方法是求解大規(guī)模數(shù)據(jù)分類問題的有效方法，具有簡單操作流程和快速收斂速率。為了提高羅杰斯特回歸分類器(Logistic Regression Classifier, LRC)的泛化性能，受-軟間隔支持向量機的啟發(fā)，該文提出一種-軟間隔羅杰斯特回歸分類機(-Soft Margin Logistic Regression Classifier,-SMLRC)，證明了-SMLRC對偶為一等式約束對偶坐標下降CDdual并由此提出了適合于大規(guī)模數(shù)據(jù)的-SMLRC-CDdual。所提出的-SMLRC-CDdual既能最大化類間間隔，又能有效提高LRC的泛化性能。大規(guī)模文本數(shù)據(jù)集實驗表明，-SMLRC-CDdual分類性能優(yōu)于或等同于相關(guān)方法。

羅杰斯特回歸；泛化；坐標下降；對偶坐標下降

1 引言

在模式分類問題中，非線性分類器在處理線性不可分問題時可以取得較高的精度，但在面對大規(guī)模數(shù)據(jù)應(yīng)用時，由于使用核方法和處理高階Hess矩陣等原因，導(dǎo)致非線性分類器的訓(xùn)練和測試過程效率非常低下，特別在處理大規(guī)模文本數(shù)據(jù)時，非線性分類器的精度優(yōu)勢并不明顯[1]。因此，如何高效地求解線性分類器得到了越來越多的關(guān)注。羅杰斯特回歸(Logistic Regression, LR)[2]被廣泛應(yīng)用于文本分類和自然語言處理(Natural Language Processing, NLP)[3]等領(lǐng)域，被認為是一種行之有效的模式分類方法。

大量優(yōu)化方法已經(jīng)用于訓(xùn)練羅杰斯特回歸原始問題，如迭代縮放(Iterative Scaling, IS)方法，坐標下降(Coordinate Descent, CD)方法[8]，擬牛頓(Quasi-Newton, QN)方法[9]，截斷牛頓(Truncated Newton)方法[10,11]。針對羅杰斯特回歸對偶問題，文獻[12]于2005年提出基于SMO[13]算法的核羅杰斯特回歸算法kLOGREG，文獻[14]于2011年提出了比其他羅杰斯特回歸模型算法有著較大速度優(yōu)勢的對偶坐標下降算法CDdual。在多變量最小化問題中，CD方法將一個多變量函數(shù)最優(yōu)化問題轉(zhuǎn)化為求解一系列坐標分量的子問題。使用CD方法求解問題時，僅對解向量的其中一個分量(坐標)在定義域內(nèi)尋優(yōu)，其它所有的分量固定為常數(shù)。CD方法比多變量最小化問題簡單，容易實現(xiàn)。CD方法分為外循環(huán)和內(nèi)循環(huán)兩層循環(huán)[15,16]，原始問題的CD (Primal CD, PCD)方法是CD方法中一種最常見形式。文獻[14]指出CD方法不僅可以快速求解LR原問題，而且可以用來快速求解LR的對偶問題，文獻[14]將求解LR對偶問題的快速方法稱為CDdual方法。為了加快優(yōu)化運算的收斂速度，CDdual方法在單變量子問題求解中使用了一種改進的牛頓迭代優(yōu)化算法。

支持向量機(Support Vector Machine,SVM)及其相關(guān)變體是目前實現(xiàn)模式分類的主流方法之一，其通過最大化類間間隔來增強分類機泛化能力。CD方法作為經(jīng)典的優(yōu)化方法，已經(jīng)被成功用于求解大規(guī)模線性支持向量機對偶[20]和羅杰斯特回歸對偶問題。受-軟間隔支持向量機(-Soft Margin Support Vector Machine,-SMSVM)[21]的啟示，本文為改善羅杰斯特回歸的泛化能力提出了-軟間隔羅杰斯特回歸分類機(-Soft Margin Logistic Regression Classifier,-SMLRC)，并使用坐標下降對所提方法對偶進行求解。此外，本文對因?qū)?shù)運算所造成的數(shù)值問題進行了正確處理并對所提方法收斂性進行了證明。大規(guī)模數(shù)據(jù)集上的實驗結(jié)果說明，本文所提方法較CDdual方法具有等效的收斂速度及泛化性能。

本文組織如下，在第2節(jié)對-軟間隔羅杰斯特回歸分類機-SMLRC進行描述。在第3節(jié)提出了求解-SMLRC的基于CDdual理論的快速算法-SMLRC-CDdual，并對該快速算法的收斂性和時間復(fù)雜度進行了分析。在第4節(jié)對文中所提算法進行了相關(guān)實驗和分析。第5節(jié)總結(jié)全文。

2-軟間隔羅杰斯特回歸分類機-SMLRC

2.1 問題描述

受-軟間隔支持向量機(-Soft Margin Support Vector Machine,-SMSVM)通過最大化類間間隔來達到強泛化能力的啟發(fā)，為了提高約束優(yōu)化問題式(1)的泛化能力，本文將參數(shù)和引入約束優(yōu)化問題式(1)而提出了-軟間隔羅杰斯特回歸分類機(-Soft Margin Logistic Regression Classifier,-SMLRC)。

2.2-SMLRC對偶

為導(dǎo)出-SMLRC原問題式(2)的對偶問題，引入Lagrange函數(shù)：

定理 1-SMLRC原問題式(2)的對偶為

定理2-SMLRC的對偶式(4)有唯一最優(yōu)解

定理2的證明類似于文獻[14]中定理1的證明，證明略。在3.2節(jié)，我們將討論如何選擇一個恰當?shù)某跏键c滿足和。

2.3-SMLRC對偶子問題

定理3-SMLRC的對偶對兩個Lagrange乘子變量和同時進行優(yōu)化的子問題為

定理4的證明見文獻[14]定理2證明。

3-SMLRC-CDdual

由CDdual理論和-SMLRC及其對偶可知，CDdual方法可用于-SMLRC對偶的求解。為此，本文提出了適合于大樣本的快速算法-SMLRC- CDdual。本文在該節(jié)對-SMLRC-CDdual算法和性質(zhì)進行介紹。

3.1 改進的牛頓迭代優(yōu)化法求解子問題

由定理3看出，-SMLRC對偶關(guān)于兩個Lagrange乘子變量和的優(yōu)化子問題與CDdual方法子問題具有相同的形式，因此改進的牛頓迭代優(yōu)化算法能用于求解子問題式(5)。與CDdual方法類似，為了消除因?qū)?shù)運算所造成的數(shù)值問題，我們將子問題式(5)變形為式(6)的子問題：

3.2-SMLRC-CDdual算法描述

文獻[14]指出LR對偶問題的解不是稀疏解，且其解向量中很多分量接近于0。同時由于-SMLRC對偶問題式(4)存在等式約束，因此不同于CDdual算法對初始點的初始化，在-SMLRC-CDdual算法中，我們將初始點初始化為

文獻[20]指出，在CD方法的內(nèi)循環(huán)中隨機改變坐標的原始序列可獲得更快的收斂速度。根據(jù)這一啟示，本文在-SMLRC-CDdual算法的每次內(nèi)循環(huán)運行前，先隨機改變坐標的序列：，其中是原始坐標序列的一種隨機映射，然后依次選擇相鄰兩個坐標求解單變量子問題式(5)。表1描述了-SMLRC對偶坐標下降方法。

表1 v-SMLRC對偶坐標下降方法

3.3-SMLRC-CDdual算法收斂性分析

盡管CDdual算法的線性收斂性已經(jīng)在文獻[14]進行了證明，但由于-SMLRC-CDdual算法求解的是一種含有等式約束的LR對偶，是一種有別于CDdual算法的大樣本分類算法。因此，有必要對-SMLRC-CDdual算法的線性收斂性進行證明。

證明 由算法1中步驟(a)和步驟(d)可知，坐標對更新前和更新后的坐標對之和為常數(shù)。因此，式(4)中等式約束蘊涵于算法1中，即使用算法1求解問題式(4)與求解LR對偶問題式(11)等價。

由此，類似文獻[14]定理6的構(gòu)造證明即可得證。 證畢

3.4-SMLRC-CDdual算法復(fù)雜度分析

-SMLRC-CDdual算法由兩層循環(huán)構(gòu)成，算法最后收斂到最優(yōu)解，其外層循環(huán)為算法1中的for循環(huán)，內(nèi)層循環(huán)為算法1中for循環(huán)內(nèi)部的while循環(huán)。算法外層循環(huán)計算量較小，其主要計算量在內(nèi)層循環(huán)。設(shè)為每個樣本非零維數(shù)平均值。首先，在計算子問題系數(shù),時，內(nèi)積矩陣和的計算復(fù)雜度均為,的計算復(fù)雜度為，計算的復(fù)雜度為，但可提前運算并進行存儲。其次，在使用改進的牛頓迭代優(yōu)化算法求解牛頓方向時，對照文獻[14]中的分析其時間復(fù)雜度為。再次，使用改進的牛頓迭代優(yōu)化算法計算時，由于使用改進牛頓迭代優(yōu)化算法去除線性搜索迭代位置的昂貴時間開銷，同樣對照文獻[14]分析其時間復(fù)雜度為。最后，更新權(quán)向量的計算復(fù)雜度為。如果設(shè)定外層for循環(huán)的平均迭代次數(shù)為，則-SMLRC-CDdual算法的時間復(fù)雜度為，其中#Newton steps為改進牛頓迭代優(yōu)化法的平均迭代次數(shù)，與文獻[14]結(jié)果相似，該平均迭代次數(shù)在本文實驗中大多數(shù)情況下取值為1。

由上述關(guān)于-SMLRC-CDdual算法的時間復(fù)雜度分析可知，-SMLRC-CDdual算法的主要計算量為子問題系數(shù)的計算，但其時間復(fù)雜度和訓(xùn)練樣本規(guī)模呈線性關(guān)系，這說明該算法適合于大樣本高維數(shù)據(jù)問題的求解(見實驗部分)。

3.5 參數(shù)性質(zhì)

定理6證明方法與文獻[21]類似，證明略。定理6說明-SMLRC中參數(shù)具有和-SMSVM中參數(shù)同樣的性質(zhì)。

4 實驗研究

為了說明本文方法的有效性，本節(jié)將-SMLRC-CDdual方法分別在a9a, real-sim, news20, rcv1, ijcnn1和w8a 6個真實高維文檔數(shù)據(jù)集上進行測試，并與另外3種針對大樣本羅杰斯特回歸模型的CDdual[14], CDprimal[8]和TRON[11]方法進行比較，以顯示本文方法的泛化能力，所使用真實高維文檔數(shù)據(jù)集描述如表2所示，實驗中使用的高維文檔數(shù)據(jù)集均可從http://www.csie.ntu. edu. tw/~cjlin/libsvmtools/datasets/下載得到。本文所有實驗是在Intel Xeon W3565 3.20 GHz, 12 GB 內(nèi)

表2 實驗所用數(shù)據(jù)集描述

存，F(xiàn)edora 18 64位環(huán)境下完成。

為了對比4種算法在訓(xùn)練過程中的收斂速度，我們在算法求解過程中將權(quán)向量的“函數(shù)值相對誤差”RDFV(Relative Difference of the Function Value)[23]作為衡量算法收斂速度的一重要指標，該值表示為

分類準確率Acc是衡量算法泛化性能的一重要指標，其百分制定義為，其中，為正確測試樣本數(shù)，為測試樣本總數(shù)。

為了客觀公正的對4種算法的泛化性能進行比較，我們將所有實驗數(shù)據(jù)集歸一化為[0,1], 4種算法外循環(huán)最大迭代次數(shù)Iter設(shè)定為200，改進牛頓迭代優(yōu)化算法求解子問題中牛頓迭代最大次數(shù)設(shè)定為100，比例系數(shù)設(shè)定為0.1。CDdual算法閾值和分別設(shè)定為和, CDdual, CDprimal和TRON 3種算法懲罰參數(shù)使用5-重交叉驗證方法選取。由式(4)約束可知，其中為樣本總數(shù)，因此-SMLRC-CDdual算法中參數(shù)對(,)在集合{1, 3, 5, 10, 100, 1000}×{1000, 5000,

10000, 50000, 100000}中選取。4種算法在表2所示數(shù)據(jù)集上運行收斂時所得準確率結(jié)果和訓(xùn)練時間如表3所示，圖1顯示了不同算法在表2所示數(shù)據(jù)集上各運行一次收斂時的訓(xùn)練時間與RDFV之間關(guān)系，圖2顯示了不同算法在表2所示數(shù)據(jù)集上各運行一次收斂時的訓(xùn)練時間與分類精度Acc之間關(guān)系，圖3顯示了3個基于CD的方法(-SMLRC- CDdual, CDdual和CDprimal)在表2所示數(shù)據(jù)集上運行每次外循環(huán)結(jié)束時所得準確率結(jié)果。需要注意的是在表3、圖1和圖2中的訓(xùn)練時間以秒(s)計。

從表3、圖1、圖2和圖3所示實驗結(jié)果可以看出，本文所提出之-SMLRC-CDdual算法是一種能有效提高LR泛化能力的適合于大樣本的快速算法，但較CDdual, CDprimal和TRON 3方法具有較慢的收斂速度。

5 結(jié)束語

受-軟間隔支持向量機的啟發(fā)，通過向羅杰斯特回歸模型LR引入?yún)?shù)和，本文提出一種-軟間隔羅杰斯特回歸分類機-SMLRC。另外，通過對偶規(guī)劃理論證明了-SMLRC對偶為一等式約束CDdual，從而提出了適合于大規(guī)模數(shù)據(jù)的-SMLRC-

圖1 4種算法在6數(shù)據(jù)集下運行的RDFV與訓(xùn)練時間

圖2 4種算法在6數(shù)據(jù)集下運行的準確率與訓(xùn)練時間

圖3 3種算法200次外循環(huán)準確率結(jié)果

CDdual算法。大規(guī)模文本數(shù)據(jù)集實驗均表明，-SMLRC-CDdual具有相較于其他相關(guān)方法明顯或相當?shù)哪Ｊ椒诸愋阅軆?yōu)勢。如何更有效地選取參數(shù)和的優(yōu)化取值使- SMLRC-CDdual既保有高泛化性能又能獲得更快的收斂速度，有待進一步深入研究和探討。

表3 4種算法收斂訓(xùn)練時間和準確率結(jié)果

[1] BOTTOU L and BOUSQUET O. The tradeoffs of large scale learning[C]. Proceedings of Advances in Neural Information Processing Systems, Cambridge, 2008: 151-154.

[2] LIN C Y, TSAI C H, LEE C P,. Large-scale logistic regression and linear support vector machines using Spark[C]. Proceedings of 2014 IEEE International Conference on Big Data, Washington DC, 2014: 519-528. doi: 10.1109/BigData. 2014.7004269.

[3] AGERRI R, ARTOLA X, BELOKI Z,. Big data for natural language processing: A streaming approach[J]., 2015, 79: 36-42. doi: 10.1016/ j.knosys.2014.11.007.

[4] DARROCH J N and RATCLIFF D. Generalized iterative scaling for log-linear models[J]., 1972, 43(5): 1470-1480. doi: 10.1214/aoms/ 1177692379.

[5] DELLA P S, DELLA P V, and LAFFERTY J. Inducing features of random fields[J]., 1997, 19(4): 380-393. doi: 10.1109/34.588021.

[6] GOODMAN J. Sequential conditional generalized iterative scaling[C]. Proceedings of the 40th annual meeting of the association of computational linguistics, Philadelphia, 2002: 9-16. doi: 10.3115/1073083.1073086.

[7] JIN R, YAN R, ZHANG J,. A faster iterative scaling algorithm for conditional exponential model[C]. Proceedings of the 20th International Conference on Machine Learning, New York, 2003: 282-289.

[8] HUANG F L, HSIEN C J, CHANG K W,. Iterative scaling and coordinate descent methods for maximum entropy[J]., 2010, 11(2): 815-848.

[9] MINKA T P. A comparison of numerical optimizers for logistic regression[OL]. http://research.microsoft.com/en-us/ um/people/minka/papers/logreg/minka-logreg.pdf. 2007.

[10] KOMAREK P and MOORE A W. Making logistic regression a core data mining tool: a practical investigation of accuracy, speed, and simplicity[R]. Technical report TR-05-27, Robotics Institute of Carnegie Mellon University, Pittsburgh, 2005.

[11] LIN C J, WENG R C, and KEERTHI S S. Trust region Newton method for large-scale logistic regression[J]., 2008, 9(4): 627-650.

[12] KEERTHI S S, DUAN K B, SHEVADE S K,. A fast dual algorithm for kernel logistic regression[J]., 2005, 61(1-3): 151-165. doi: 10.1007/s10994- 005-0768-5.

[13] PLATT J C. Fast training of support vector machines using sequential minimal optimization[C]. Proceedings of Advances in Kernel Methods: Support Vector Learning, Cambridge, 1999: 185-208.

[14] YU H F, HUANG F L, and LIN C J. Dual coordinate descent methods for logistic regression and maximum entropy models[J]., 2011, 85(1/2): 41-75. doi: 10.1007/s10994-010-5221-8.

[15] 顧鑫, 王士同, 許敏. 基于多源的跨領(lǐng)域數(shù)據(jù)分類快速新算法[J]. 自動化學(xué)報, 2014, 40(3): 531-547. doi: 10.3724/SP.J. 1004.2014.00531.

GU X, WANG S T, and XU M. A new cross-multidomain classification algorithm and its fast version for large datasets[J]., 2014, 40(3): 531-547. doi: 10.3724/SP.J.1004.2014.00531.

[16] 顧鑫, 王士同. 大樣本多源域與小目標域的跨領(lǐng)域快速分類學(xué)習(xí)[J]. 計算機研究與發(fā)展, 2014, 51(3): 519-535. doi: 10.7544/issn1000-1239.2014.20120652.

GU X and WANG S T. Fast cross-domain classification method for large multisources/small target domains[J]., 2014, 51(3): 519-535. doi: 10.7544/issn1000-1239.2014.20120652.

[17] 張學(xué)峰, 陳渤, 王鵬輝, 等. 一種基于Dirichelt過程隱變量支撐向量機模型的目標識別方法[J]. 電子與信息學(xué)報, 2015, 37(1): 29-36. doi: 10.11999/JEIT140129.

ZHANG X F, CHEN B, WANG P H,. A target recognition method based on dirichlet process latent variable support vector machine model[J].&, 2015, 37(1): 29-36. doi: 10.11999/ JEIT140129.

[18] 及歆榮, 侯翠琴, 侯義斌. 無線傳感器網(wǎng)絡(luò)下線性支持向量機分布式協(xié)同訓(xùn)練方法研究[J]. 電子與信息學(xué)報, 2015, 37(3): 708-714. doi: 10.11999/JEIT140408.

JI X R, HOU C Q, and HOU Y B. Research on the distributed training method for linear SVM in WSN[J].&, 2015, 37(3): 708-714. doi: 10.11999/JEIT140408.

[19] 高發(fā)榮, 王佳佳, 席旭剛, 等. 基于粒子群優(yōu)化-支持向量機方法的下肢肌電信號步態(tài)識別[J]. 電子與信息學(xué)報, 2015, 37(5): 1154-1159. doi: 10.11999/JEIT141083.

GAO F R, WANG J J, XI X G,. Gait recognition for lower extremity electromyographic signals based on PSO- SVM method[J].&, 2015, 37(5): 1154-1159. doi: 10.11999/ JEIT141083.

[20] HSIEH C J, CHANG K W, LIN C J,. A dual coordinate descent method for large-scale linear SVM[C]. Proceedings of the 25th International Conference on Machine Learning, New York, 2008: 408-415. doi: 10.1145/1390156.1390208.

[21] CHEN P H, LIN C J, and SCH?LKOPF B. A tutorial on-support vector machines[J]., 2005, 21(2): 111-136. doi: 10.1002/ asmb.537.

[22] PENG X J, CHEN D J, and KONG L Y. A clipping dual coordinate descent algorithm for solving support vector machines[J]., 2014, 71: 266-278. doi: 10.1016/j.knosys.2014.08.005.

[23] TSAI C H, LIN C Y, and LIN C J. Incremental and decremental training for linear classification[C]. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2014: 343-352. doi: 10.1145/2623330.2623661.

黃成泉： 男，1976年生，教授，博士生，研究方向為模式識別、數(shù)據(jù)挖掘和機器學(xué)習(xí)等.

王士同： 男，1964年生，教授，博士生導(dǎo)師，研究方向為模式識別、人工智能、數(shù)據(jù)挖掘和模糊系統(tǒng)等.

蔣亦樟： 男，1988年生，博士生，研究方向為模式識別、智能計算及其應(yīng)用等.

董愛美： 女，1978年生，講師，博士生，研究方向為模式識別、人工智能和機器學(xué)習(xí)等.

Foundation Items: The National Natural Science Foundation of China (61272210, 61202311), The Natural Science Foundation of Jiangsu Province (BK2012552), The Science and Technology Foundation of Guizhou Province ([2013]2136)

-Soft Margin Logistic Regression Classifier

HUANG Chengquan①②WANG Shitong①JIANG Yizhang①DONG Aimei①③

①(School of Digital Media, Jiangnan University, Wuxi 214122, China)②(Engineering Training Center, Guizhou Minzu Univeristy, Guiyang 550025, China)③(School of Information, Qilu University of Technology, Jinan 250353, China)

Coordinate Descent (CD) is a promising method for large scale pattern classification issues with straightforward operation and fast convergence speed. In this paper, inspired by-soft margin Support Vector Machine (-SVM) for pattern classification, a new-Soft Margin Logistic Regression Classifier (-SMLRC) is proposed for pattern classification to enhance the generalization performance of Logistic Regression Classifier (LRC). The dual of-SMLRC can be regarded as CDdual problem with equality constraint and then a new large scale pattern classification method called-SMLRC-CDdual is proposed. The proposed-SMLRC-CDdual can maximize the inner-class margin and effectively enhance the generalization performance of LRC. Empirical results conducted with large scale document datasets demonstrate that the proposed method is effective and comparable to other related methods.

Logistic regression; Generalization; Coordinate Descent (CD); Dual Coordinate Descent (CDdual)

TP391.4

A

1009-5896(2016)04-0985-08

10.11999/JEIT150769

2015-06-29；改回日期：2015-12-08；網(wǎng)絡(luò)出版：2016-01-22

黃成泉 hcq863@163.com

國家自然科學(xué)基金(61272210, 61202311)，江蘇省自然科學(xué)基金(BK2012552)，貴州省科學(xué)技術(shù)基金(黔科合J字[2013]2136號)