最優間隔分布脊回歸

陳加略 姜 遠

(計算機軟件新技術國家重點實驗室(南京大學) 南京 210023) (軟件新技術與產業化協同創新中心 南京 210023) (chenjl@lamda.nju.edu.cn)

最優間隔分布脊回歸

陳加略 姜 遠

(計算機軟件新技術國家重點實驗室(南京大學) 南京 210023) (軟件新技術與產業化協同創新中心 南京 210023) (chenjl@lamda.nju.edu.cn)

脊回歸(ridge regression, RR)是經典的機器學習算法之一，廣泛應用于人臉識別、基因工程等諸多領域.其具有優化目標凸、存在閉合解、可解釋性強以及易于核化等優點，但是脊回歸的優化目標并沒有考慮樣本之間的結構關系.監督流形正則化學習是最具代表性的、最成功的脊回歸正則化方法之一，其通過最小化每類類內方差來考慮樣本之間的類內結構關系，可是單純地只考慮類內結構仍然不夠全面.以一種全新的視角重新審視最近提出的“最優間隔分布學習”原理，發現了最優間隔分布的目標可以同時優化類內間隔方差和類間間隔方差，從而同時優化了局部的類內結構和全局的類間結構.基于此提出了一種充分考慮數據結構化特征的脊回歸算法——最優間隔分布脊回歸(optimal margin distribution machine ridge regression, ODMRR)算法，該算法具有RR以及MRRR(manifold regularization ridge regression)的各種優勢.最后通過實驗驗證了該方法具有優越的性能.

脊回歸；流形正則化；最優間隔分布；間隔方差；全局結構

脊回歸(ridge regression, RR)[1]的優化目標致力于最小化模型輸出以及樣本標記之間的二次誤差，在人臉識別[2]、基因工程[3]、肝臟致癌預測[4]等諸多領域[5]有著廣泛的應用.脊回歸具有優化目標凸、存在閉式解、可解釋性強以及易于核化等優點.但其優化目標并沒有體現出數據的結構(structral)特征，這就意味著原始的脊回歸算法沒有考慮分類樣本之間存在的潛在相互關系.在分類模型的優化目標中加入正則化約束來假設數據之間的結構關系通常可以有效地提升性能.流形正則化(manifold regularization, MR)[6]是一種常見的做法，在諸多領域得到了廣泛應用，如多標記學習[7]、集成學習[8]、特征提取[9]、譜圖理論[10]、網頁圖像標記[11]等.MR是一種基于半監督[12]流形假設的適用于有標記和無標記樣本學習的正則化框架，它的優化目標是最小化每類樣本的類內方差，即要求分類器輸出類內緊湊.將MR加入到有監督RR后的優化目標也是凸的，并且存在閉合解，因此具備脊回歸算法所具有的各種優勢.

相比于最大化最小間隔[13]，最優間隔分布學習理論[14-15]的核心思想在于通過優化“間隔分布”來有效提升模型的泛化性能.由此提出的ODM[16],LDM[17]和cisLDM[18]算法都取得了很好的性能*此類方法以往被稱為“大間隔分布學習”方法[17-18],但由于“間隔分布”本身并沒有“大小”之別，因此“最優間隔分布”這個稱謂比“最大間隔分布”更合適[16]..在最優間隔分布學習理論中，優化間隔分布是通過最大化間隔均值并同時最小化間隔方差[13]來實現的.本文選擇了一種嶄新的視角，從優化數據結構特征的角度重新分析了最優間隔理論中優化間隔分布的目標，并發現最小化間隔方差這個目標可以拆解成最小化類內間隔方差和最大化類間間隔方差2項.針對分類模型進行分析，可以發現，MR中最小化類內方差的目標和最優間隔分布學習理論中最小化間隔方差的目標是相同的，都要求類內緊湊，即兩者都是在優化數據的局部類內結構.進一步對最優間隔學習理論中最大化間隔均值和最小化類間間隔方差這2項的目標進行分析，可以發現兩者共同作用的目的都是為了使分類器輸出類間松散.而類間松散可以看成是優化一種全局的結構關系.所以，MR的優化目標只優化了類內緊湊這一種局部分類特性，而最優間隔分布學習理論不僅考慮了類內緊湊，還進一步優化了類間松散這一種全局分類特性.換句話說，相比于MR，最優間隔分布學習理論考慮了更加全面的數據結構信息.

在本文中，我們借鑒了最優間隔分布學習理論思想，并提出了一種新的正則化方法即最優間隔分布正則化.流形正則化方法可看作為最優間隔正則化方法的特例.我們將其應用于脊回歸中得到了最優間隔分布脊回歸(optimal margin distribution machine ridge regression, ODMRR)算法，ODMRR算法的優化目標也是凸的，并且具有解析解，在多個真實數據集上取得很好效果.

1 研究背景

S={(x1,y1),(x2,y2),…,(xn,yn)}.

機器學習的目標就是通過訓練集S學習一個分類器，使其能夠預測未來從未見過的樣本標記.

假設f(x)=wTφ(x)+b是一個線性判別模型.其中w是線性分類面，b是截距，φ(x)是x在核k上的一個特征投影，并滿足k(xi,xj)=φ(xi)Tφ(xj).樣本(xi,yi)的間隔可以定義為

γi=yi(wTφ(xi)+b), ?i=1,2,…,n.

為了方便表示，可以將分類面w以及截據b拼接成一個增廣的向量：w′=[w;b]，將所有樣本的特征尾部拼上一個常數1形成增廣的特征φ(xi)′=[φ(xi);1].令X′=[φ(x1)′,φ(x2)′,…,φ(xn)′]，y=[y1,y2,…,yn]T.

對于線性判別分類器，其解w*通常存在表示形式：

φ(xi)=Xα，

(1)

其中，α=[α1,α2,…,αn]T是系數向量.可以將系數向量α和截距b拼成一個增廣的向量：α′=[α;b].

為了方便將算法推廣到核空間上，我們用K表示n×n的核矩陣，其第(i,j)個位置的元素為k(xi.xj)，可以發現K=XTX.在K的最后一行拼上K′=[K;11×n]，其中1m×n表示維度為m×n的全1矩陣.

1.1脊回歸和流形正則化

脊回歸(rigde regression, RR)的優化目標是找到一個分類面w和截距b，使得樣本輸出f(xi)和樣本標記yi之間的二次誤差之和盡量小.其優化目標可以形式化為

(2)

式(2)中的目標可以通過式(1)的表示定理轉化成等價的形式：

(3)

式(3)的優化目標是凸的，并且具有閉合的解析解，其解的形式為

α′=(λB+K′K′T)-1K′y，

流形假設數據采樣于高維歐式空間的一個低維流形，處于局部領域的示例具有相似的性質，即它們的標記也應該相似.對于分類問題,流形正則化的目標是減小2類樣本的類內方差.所以，監督型流形正則化的脊回歸(manifold regularization ridge regression, MRRR)的優化目標表示為

(4)

其中，λ1和λ2是正則化因子，C1和C2分別代表第1和第2類樣本.式(4)中最后2項就是流形正則化項，它們分別優化了第1,2類樣本的類內方差.可以發現，如果式(4)中的λ2=0,MRRR將會退化為RR算法，即RR是MRRR的特例.

式(4)中的目標也可以通過式(1)中的表示定理轉化成等價形式：

(5)

其中，In表示維度為n的單位陣，而:

n1和n2分別表示第1,2類樣本的數目.

式(5)的目標也是凸的，并且也具有閉合的解析解，其解的形式為

α′=(λ1B+K′(In+2λ2M)K′T)-1K′y.

1.2最優間隔分布學習理論

相比于最大化最小間隔，最優間隔分布學習理論揭示了優化間隔分布對于提升模型的泛化性能將更加顯著.最優間隔分布學習理論指出優化間隔分布具體表現為最大化間隔均值和最小化間隔方差.其中，間隔均值定義為

間隔方差定義為

根據間隔方差的定義可以發現，當yi=yj時，間隔方差的形式和流形正則化項的形式相同，即對于分類模型，類內方差即是類內的間隔方差.兩者的目的都是為了使分類器輸出類內緊湊.

當yi≠yj時，間隔方差的形式為

φ(xi)′+w′Tφ(xj)′)2，

經過分析可以發現，這一項實際上代表了類間間隔方差.最小化間隔方差和最大化間隔均值兩者共同作用的目標是為了使分類器輸出類間分散.

所以最優間隔分布學習理論既考慮了使分類器輸出類內緊湊這一局部分類特性，還考慮了使分類器輸出類間分散這一全局分類特性.

2 最優間隔分布脊回歸

最優間隔分布(ODM)的主要思想就是利用最優間隔分布學習理論中同時考慮分類器輸出類內緊湊、類間松散這2個分類特性的優勢.將最大化間隔均值和最小化間隔方差作為正則化項加入到分類模型的優化目標中.

脊回歸的二次誤差項表示為等價的矩陣形式：

可以發現，最小化-2yTX′Tw′的目標就是最大化間隔均值，即脊回歸的優化目標中本身就包含了最大化間隔均值.所以，對于脊回歸問題，最優間隔分布只需要考慮最小化間隔方差一項正則化項就可以了.于是，我們將ODM運用于脊回歸問題，并得到了ODMRR的優化目標：

w′TX′(In+2λ2(D°diag(yyT)-

S°yyT))X′Tw′+λ1w′TAw′，

(6)

定理1. 優化目標(6)中的最優解w*存在式(1)的表示形式.

證明.w*可以分解成有φ(xi)伸張以及和φ(xi)正交2個部分，形式為

φ(xi)+v=Xα+v，

其中，XTv=0.可以發現：

X′Tw′=XTw+b=XT(Xα+v)+b=XTXα+b，

所以，在優化目標式(6)中，只有w′TAw′與v相關，其他項都與v獨立，可以證明：

w′TAw′=wTw=(Xα+v)T(Xα+v)=
αTXTXα+vTv≥αTXTXα

且不等式當且僅當v=0時才成立.

所以，設置v=0不會影響到優化目標式(6)的最優值，即w*可以表示成式(1)的表示形式.

證畢.

于是，通過定理1，可以將優化目標式(6)轉換為等價的形式：

(7)

式(7)的優化目標是凸的，也具有閉合和解析解，其解的形式為

α′=(λ1B+K′(In+2λ2(D°diag(yyT)-
S°yyT))K′T)-1K′Ty.

為了能夠控制類內間隔方差和和類間間隔方差的權重，也可以把優化目標等價表示為

(8)

其中，λ1，λ2，λ3全是正則化因子，式(8)中第2項是第1類的類內間隔分布，第3項是第2類的類內間隔分布，最后一項是2類樣本的類間間隔分布,我們將式(8)的優化目標記為ODMRR-3h.可以發現，如果λ3=0，式(8)的優化目標就會退化為式(4)流形正則化方法的優化目標，如果λ2=0和λ3=0，式(8)的優化目標將會退化為式(2)的脊回歸的優化目標.所以脊回歸算法以及流形正則化的脊回歸算法都可以看作最優間隔正則脊回歸算法的特例.

根據定理1的證明，式(8)也存在等價的表示形式：

(9)

其中，

式(9)的優化目標為凸，其解也為解析解，其形式為

α′=(λ1B+K′(In+P+Q)K′T)-1K′y.

4 實驗測試

本節將先介紹實驗的設置，然后給出實驗的結果，并對結果進行簡單地分析.

4.1實驗設置

實驗共選擇了14個數據集，其中digit1和g241n是半監督數據集.austra，isolet，vehicle和wdbc都是UCI數據集.Letter是多標記數據集，從中選出8對相對比較難分類的字符組成了8組2分類數據集，分別記為DvsP，EvsF，IvsJ，IvsL，MvsN，UvsY，VvsY，DvsO.表1中列出了所有數據集的樣本和特征維度.并且所有數據集都通過隨機采樣以1∶1的比例平分成訓練數據和測試數據.

實驗1共選擇了6組對比算法：RR，MRRR，ODMRR，ODMRR_3h，ODMRR_S1，ODMRR_S1_3h.其中，在ODMRR算法中，帶有_S1后綴代表相似性矩陣S采用全1矩陣，沒有_S1后綴的相似性矩陣S則采用高斯距離矩陣.帶有_3h的后綴表示優化目標采用式(9)的表示形式，否則采用式(6)的表示形式.

Table 1 Dataset and the Dimension of Its Instances and Features

4.2實驗結果

表2中的實驗結果是在每個數據集上進行10次實驗所得到平均精度和方差.其中，深色背景都是我們算法的實驗結果.我們使用加粗字體來標明每個數據集中測試精度最高的一組算法的結果.

在每輪實驗中，所有參數全部都是采用固定其余所有參數，然后通過10次交叉驗證的方法選出的最優值.在交叉驗證的過程中，選擇80%的訓練數據用于訓練模型，用剩下的20%的數據來驗證模型參數.10次交叉驗證又包含先粗調后細調的過程，粗調的參數取值為[10-5,10-4,…,105]，細調的參數取值為[2-4,2-3,…,24].而ODMRR和ODMRR_3h算法中使用到的高斯距離矩陣中的σ參數則采用σ=1的默認值設置.

Table 2 Experiment Result表2 實驗結果

由于3個脊回歸的算法都需要計算一次矩陣的求逆計算，所以這3個算法的速度都不是特別快.在這3個算法中，RR包含一個參數，MRRR包含2個參數，而ODMRR算法包含3個參數.為了減少調參的時間，我們采用固定其余參數，只調整一個參數的方法.從表2的實驗結果中可以發現，即便在如此簡單的調參方法下，ODMRR算法在14個數據集中有10個達到最優結果，其中2個和最優結果打平.并且可以很明顯地發現對于給類內間隔分布和類間間隔分布分配不同參數的ODMRR_3h方法相比使用相同參數的ODMRR方法取得了更多的最優結果.所以這也一定程度上說明，類內結構關系和類間結構關系在對于分類器的貢獻在部分數據集上可能是不同的.

5 結束語

脊回歸算法及其流形正則化算法是機器學習領域的經典方法.這2種算法都沒有充分考慮數據全局的結構化關系.我們以一種全新的視角分析了最優間隔分布學習理論對于優化間隔分布的優化目標、提出了了一種充分考慮類內結構關系和類間結構關系的正則化脊回歸算法——最優間隔分布脊回歸算法(ODMRR).由于脊回歸算法和流形正則化的脊回歸算法都是ODMRR算法的特例，所以ODMRR算法保有了脊回歸和流形正則化的脊回歸算法中所共有的優化目標為凸函數、有解析解、易于核化等優勢.考慮到類內結構關系和類間結構關系對于模型的貢獻不同，我們也提出了ODMRR算法的一種簡單變形ODMRR_3算法方便用戶調節兩者之間的權重.最后，我們在真實數據集上進行了實驗且在大部分數據集上取得了最優的結果.

[1] Hoerl A E, Kennard R W. Ridge regression: Biased estimation for nonorthogonal problems[J].Technometrics, 1970, 12(1): 55-67

[2] Xue Hui, Zhu Yulian, Chen Songcan. Local ridge regression for face recognition[J].Neurocomputing, 2009, 72(4): 1342-1346

[3] Cule E, Vineis P, De Iorio M. Significance testing in ridge regression for genetic data[J]. BMC Bioinformatics, 2011, 12(1): 372-378

[4] Liu Shujie, Kawamoto T, Morita O, et al. Discriminating between adaptive and carcinogenic liver hypertrophy in rat studies using logistic ridge regression analysis of toxicogenomic data: The mode of action and predictive models[J]. Toxicology and Applied Pharmacology, 2017, 318(9): 79-87

[5] Marquardt D W, Snee R D. Ridge regression in practice[J].The American Statistician, 1975, 29(1): 3-20

[6] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples[J]. Journal of Machine Learning Research, 2006, 7(11): 2399-2434

[7] Luo Yong, Tao Dacheng, Xu Chang, et al. Multiview vector-valued manifold regularization for multilabel image classification[J]. IEEE Trans on Neural Networks and Learning Systems, 2013, 24(5): 709-722

[8] Geng Bo, Tao Dacheng, Xu Chao, et al. Ensemble manifold regularization[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2012, 34(6): 1227-1233

[9] Xu Zenglin, King I, Lyu M R T, et al. Discriminative semi-supervised feature selection via manifold regularization[J]. IEEE Trans on Neural Networks, 2010, 21(7): 1033-1047

[10] Luo Siwei, Zhao Lianwei. Manifold learning algorithms based on spectral graph theory[J].Journal of Computer Research and Development, 2006, 43(7): 1173-1179 (in Chinese)(羅四維, 趙連偉. 基于譜圖理論的流形學習算法[J]. 計算機研究與發展, 2006, 43(7): 1173-1179)

[11] Liu W, Liu H, Tao D, et al. Manifold regularized kernel logistic regression for Web image annotation[J]. Neurocomputing, 2016, 172(C): 3-8

[12] Zhu Xiaojin. Semi-supervised learning literature survey[J].Computer Science, University of Wiscousin-Madison, 2006, 2(3): 4-64

[13] Vapnik V. The Nature of Statistical Learning Theory[M]. Berlin: Springer, 1995

[14] Zhou Zhihua. Large margin distribution learning[C] //Proc of the Workshop on Artificial Neural Networks in Pattern Recognition. Berlin: Springer, 2014: 1-11

[15] Gao Wei, Zhou Zhihua. On the doubt about margin explanation of boosting[J].Artificial Intelligence, 2013, 203(5): 1-18

[16] Zhang Teng, Zhou Zhihua. Multi-class optimal distribution machine[C] //Proc of the 34th Int Conf on Machine Learning. 2017 [2017-04-01]. http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icml17mcODM.pdf

[17] Zhang Teng, Zhou Zhihua. Large margin distribution machine[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 313-322

[18] Zhou Yuhang, Zhou Zhihua. Large margin distribution learning with cost interval and unlabeled data[J]. IEEE Trans on Knowledge and Data Engineering, 2016, 28(7): 1749-1763

OptimalMarginDistributionRidgeRegression

Chen Jialüe and Jiang Yuan

(NationalKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210023) (CollaborativeInnovationCenterofNovelSoftwareTechnologyandIndustrialization,Nanjing210023)

Ridge regression (RR) has been one of the most classical machine learning algorithms in many real applications such as face detection, cell prediction, etc. The ridge regression has many advantages such as convex optimization objection, closed-form solution, strong interpretability, easy to kernelization and so on. But the optimization objection of ridge regression doesn’t consider the structural relationship between instances. Supervised manifold regularized (MR) method has been one of the most representative and successful ridge regression regularized methods, which considers the instance structural relationship inter each class by minimizing each class’s variance. But considering the structural relationship interclasses alone is not a very comprehensive idea. Based on the recent principle of optimal margin distribution machine (ODM) learning with a novel view, we find the optimization object of ODM can include the local structural relationship and the global structural relationship by optimizing the margin variance interclasses and the margin variance intraclasses. In this thesis, we propose a ridge regression algorithm called optimal margin distribution machine ridge regression (ODMRR) which fully considers the structural character of the instance. Besides, this algorithm can still contain all the advantages of ridge regression and manifold regularized ridge regression. Finally, the experiments validate the effectiveness of our algorithm.

ridge regression (RR); manifold regularization; optimal margin distribution machine (ODM); margin variance; global structure

n, born in 1976.

her PhD degree in computer science from Nanjing University in 2004. Currently professor and PhD supervisor at the Department of Computer Science & Technology, Nanjing University. Her main research interests include machine learning and data mining.

Chen Jialüe, born in 1991. PhD. His main research interests include machine learning and data mining.

2017-05-23；

：2017-06-25

國家自然科學基金項目(61673201) This work was supported by the National Natural Science Foundation of China (61673201).

姜遠(jiangy@lamda.nju.edu.cn)

TP181