潘巍 馬培軍 蘇小紅

摘要：在機(jī)器學(xué)習(xí)領(lǐng)域中，間隔扮演著重要的角色?？梢杂脕矶攘糠诸惖闹眯哦龋黄淅碚摲夯缫部捎糜谥笇?dǎo)分類算法的設(shè)計(jì)。近年來，該理論已廣泛應(yīng)用于特征選擇，分類器訓(xùn)練和集成學(xué)習(xí)。實(shí)際上，間隔思想表明如果在訓(xùn)練階段模型能夠產(chǎn)生大的間隔，那么分類任務(wù)將有好的置信度和高可靠性。文中介紹大間隔分類學(xué)習(xí)方法的研究現(xiàn)狀， 并給出了其存在的問題。

關(guān)鍵詞：間隔； 分類學(xué)習(xí)； 機(jī)器學(xué)習(xí)

中圖分類號(hào)：TP39141 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2013）06-0044-04

0引言

在機(jī)器學(xué)習(xí)領(lǐng)域中，間隔扮演著重要的角色，可以用來度量分類器的置信度而其理論泛化界也可用于指導(dǎo)分類算法的設(shè)計(jì)。該理論已經(jīng)廣泛應(yīng)用于特征選擇、分類器構(gòu)建、集成學(xué)習(xí)等領(lǐng)域。間隔的概念由Vapnik首次提出，并將其應(yīng)用于構(gòu)建支持向量機(jī)（Support Vector Machine）[1]。支持向量機(jī)利用最大分類間隔來實(shí)現(xiàn)線性分類任務(wù)。1999年，F(xiàn)riedman指出間隔分布是用來指導(dǎo)分類集成學(xué)習(xí)構(gòu)造穩(wěn)定模型的重要度量[2]。隨著間隔的泛化界的提出，從統(tǒng)計(jì)學(xué)習(xí)理論上解釋了最大分類間隔實(shí)際意義。實(shí)際上，間隔思想表明如果在訓(xùn)練階段模型能夠產(chǎn)生大的間隔，那么分類任務(wù)將有好的置信度和高可靠性。在過去的十幾年中，該理論在模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域引起了高度關(guān)注。

本文首先從特征選擇、SVM分類器的構(gòu)建和分類集成學(xué)習(xí)三個(gè)方法來闡述基于間隔方法的研究現(xiàn)狀。在此基礎(chǔ)上，給出了基于間隔分類學(xué)習(xí)中存在的問題并探討其未來發(fā)展方向。

1基于間隔的特征選擇方法的研究現(xiàn)狀

近年來在機(jī)器學(xué)習(xí)領(lǐng)域，間隔作為代表性的特征評(píng)估策略之一已成為研究熱點(diǎn)。間隔概念首次是由Vapnik 提出為了構(gòu)建SVM模型，這是用最大化類間的分類間隔來尋找最優(yōu)可分超平面。1999年，Shawe Taylor 和Cristianini在統(tǒng)計(jì)學(xué)習(xí)理論層面上證明了SVM中分類間隔是與其泛化誤差的上界是緊密相關(guān)的[3]。2002年，Crammer等人討論了Adaboost 算法中的分類泛化誤差，并指出其VC維與基分類器間的間隔分布相關(guān)，從而將間隔理論進(jìn)一步推廣到集成學(xué)習(xí)范疇[4]。2004年，Gilad Bachrach等人開發(fā)了兩種基于間隔特征選擇方法，并通過大間隔理論證明了這兩種方法的最近鄰無限樣本泛化界[5]。因此，從統(tǒng)計(jì)學(xué)習(xí)理論角度來看，分類間隔可認(rèn)為是一種用于衡量分類置信度的距離測(cè)度。近年來，大量基于間隔的特征選擇方法正在相繼不斷地提出。根據(jù)其構(gòu)造方式不同，間隔可分為兩類。一類稱之為樣本間隔（Sample Margin），用于度量樣本到分類邊界的距離；另一類假設(shè)間隔（Hypothesis Margin）則用來度量假設(shè)類別的距離。

研究中，可以將基于間隔的特征選擇方法大體分為三類。第一類是通過直接最大化間隔來進(jìn)行特征選擇，如Relief[6]、Simba[5]等等。第二類是通過最小化分類間隔損失來獲得搜索特征子集最佳的解決方案。2004年，Andrew等人提出了兩種基于Logistic 損失的特征選擇方法并應(yīng)用于SVM[7]，其間分別采用了L1 范數(shù)和L2范數(shù)正則化技術(shù)；實(shí)驗(yàn)結(jié)果顯示使用L1范數(shù)正則化方法相對(duì)而言是比較有效的。2008 年，Park等人提出了一種快速的特征選擇方法[8]，可利用Logistic損失來光滑近似Hinge損失并應(yīng)用于支持向量機(jī)。2009 年，Li等人提出了一種基于近鄰規(guī)則的特征選擇方法[9]。最后一類是利用間隔分類器的啟發(fā)式的特征選擇方法，其中最具代表性的當(dāng)屬SVM-RFE等算法。這三類方法中，第一和第二類方法是基于Filter模型的方法，而且均是獨(dú)立于分類器的評(píng)估特征方法并且執(zhí)行效率較高；但第三類方法的計(jì)算時(shí)間復(fù)雜性較高，從而限制其實(shí)用性。

2基于間隔的分類學(xué)習(xí)算法的研究現(xiàn)狀

至今為止，支持向量機(jī)（SVM）作為大間隔的分類學(xué)習(xí)模型在機(jī)器學(xué)習(xí)領(lǐng)域備受關(guān)注。SVM的思想是要找到一個(gè)線性可分超平面，并使用最大間隔來正確地區(qū)分二類訓(xùn)練數(shù)據(jù)，如此即可有效地減少對(duì)測(cè)試樣本分類錯(cuò)誤的風(fēng)險(xiǎn)。這種SVM可將其稱作硬間隔SVM 。但是在訓(xùn)練階段搜索最優(yōu)超平面時(shí)，由于可分邊界附近一些錯(cuò)分樣本的影響，原有硬間隔SVM 中最大間隔的原則將失效。為了解決上述問題，軟間隔SVM利用松散閾值來得到一個(gè)近似線性可分超平面，實(shí)現(xiàn)了最大化間隔并最小化松散閾值的和來最優(yōu)化學(xué)習(xí)模型的參數(shù)。對(duì)于線性不可分問題，核函數(shù)（Kernal Function） 已經(jīng)引入到SVM 模型構(gòu)建中并獲得巨大成功?；诤撕瘮?shù)映射的SVM 是將原有的數(shù)據(jù)映射到一個(gè)高維特征空間中，并在其上構(gòu)造最優(yōu)分類超平面。

隨著支持向量機(jī)研究的深入，對(duì)于訓(xùn)練抗噪聲的SVM學(xué)習(xí)模型展開了廣泛的討論。1999年，LS-SVM獲得提出[10]，可利用平方Hinge損失來替換軟間隔SVM 中的Hinge損失來訓(xùn)練SVM。但在統(tǒng)計(jì)學(xué)習(xí)理論中，Hinge損失要比平方Hinge損失具有更好的魯棒性和稀疏性。針對(duì)LS-SVM 中的魯棒性較差的問題WLS-SVM[11] 也相繼提出，利用了Hempel魯棒估計(jì)獲得平方損失的權(quán)值。2002年，Song等人利用樣本到類別質(zhì)心的平方距離來替代LS-SVM 中的平方損失，從而構(gòu)建了一種魯棒的SVM，并將其應(yīng)用到彈孔圖像分類[12]。2006 年，Xu等人將孤立點(diǎn)檢測(cè)與大間隔理論相結(jié)合構(gòu)造出一種斜坡?lián)p失來訓(xùn)練SVM，可以表達(dá)一個(gè)凸松弛損失訓(xùn)練問題并通過半定規(guī)劃來求解[13]。2007年，Wu等人構(gòu)造了一種截?cái)嗟腍inge 損失，通過對(duì)遠(yuǎn)離該類的異常樣本用不敏感損失值來懲罰，從而使其獲得較好魯棒性和較少的支持向量[14]。2008年，Wang等人利用Huber損失來光滑文獻(xiàn)[13]中斜坡?lián)p失，然后在原始空間中訓(xùn)練支持向量機(jī)，但其中需調(diào)優(yōu)的參數(shù)過多，從而限制了其實(shí)用性[15]。2010年，Ma等人將中位數(shù)回歸引入到Hinge損失中并得到了一種魯棒的支持向量機(jī)[16]，對(duì)于兩類分類問題總的損失懲罰由兩個(gè)屬于不同類的中位數(shù)損失的和來衡量。此外，許多研究者將模糊粗糙集理論引入到SVM 學(xué)習(xí)模型中來改善其魯棒性，從而構(gòu)建出許多模糊SVM模型（FSVM）[17-18]。這些研究的主要思想是通過計(jì)算樣本附屬于類別的隸屬度來確定軟間隔SVM中的Hinge 損失對(duì)該樣本的松散系數(shù)， 由于隸屬度較低的樣本多為異常和噪聲點(diǎn)，因此該模型可以有效改善噪聲對(duì)SVM 模型的不良影響。FSVM一個(gè)致命的缺陷在于不能夠給出一個(gè)通用化的原則來確定樣本的隸屬度值即SVM 損失項(xiàng)中樣本的松散系數(shù)，而都是通過經(jīng)驗(yàn)來選取模糊函數(shù)來計(jì)算隸屬度。

3分類集成學(xué)習(xí)方法的研究現(xiàn)狀

集成學(xué)習(xí)的思想是訓(xùn)練多個(gè)弱學(xué)習(xí)器，并將其相應(yīng)結(jié)合后來進(jìn)行決策或預(yù)測(cè)，從而改善單個(gè)學(xué)習(xí)模型的預(yù)測(cè)能力。集成學(xué)習(xí)的實(shí)質(zhì)是對(duì)多個(gè)學(xué)習(xí)器的結(jié)合方式進(jìn)行研究。近年來大量有關(guān)文獻(xiàn)被發(fā)表，這些文獻(xiàn)詳細(xì)地討論了集成方法的理論依據(jù)以及實(shí)現(xiàn)過程。在過去的幾十年中，涌現(xiàn)了大量的集成學(xué)習(xí)算法。Boosting[19]是被最廣泛使用的一種提高分類學(xué)習(xí)準(zhǔn)確度的集成方法，可視作一個(gè)模型平均方法。Boost-ing產(chǎn)生一系列的樣本子集來訓(xùn)練基分類，每次訓(xùn)練樣本子集中由基分類器錯(cuò)分的樣本將給其分配更高的權(quán)值，從而提高在下一次基分類器訓(xùn)練生成的訓(xùn)練樣本子集中抽取該錯(cuò)分樣本的概率。如此迭代下去產(chǎn)生多個(gè)基分類器，最終的分類結(jié)果將由多個(gè)基分類器加權(quán)融合而獲得。1992年，Wolpert 介紹了一種最小化泛化錯(cuò)誤率的集成方法，被稱作疊加法[20]。其思想是將基學(xué)習(xí)器分布在多個(gè)層次上，每一層中學(xué)習(xí)器的輸出作為下一層的輸入，利用多層的學(xué)習(xí)器來完成學(xué)習(xí)任務(wù)。1996年，Breiman 提出了Bagging（Bootstrap Aggregation） 集成方法[21]。Bagging最初是為決策樹模型而設(shè)計(jì)的，但也可以使用在任何類型的分類或回歸模型中。該方法通過Bootstrap采樣從訓(xùn)練集中產(chǎn)生出多個(gè)訓(xùn)練子集，然后利用這些子集來分別訓(xùn)練一個(gè)基分類或回歸模型。對(duì)于回歸問題，Bagging的輸出是多個(gè)回歸模型預(yù)測(cè)值的平均；而對(duì)于分類問題則用投票法來決定樣本的類別。1998年，Ho等人用隨機(jī)子空間方法構(gòu)建決策森林[22]；在數(shù)據(jù)集中存在大量的特征時(shí)，該方法效果良好。Logitboost[23]是由Friedman等人提出一種Boosting算法，通過在分類器的迭代中使用Logistic 回歸模型來確定樣本的權(quán)值，而獲得了良好的效果。原因在于Logistic 回歸模型描述的是一個(gè)或多個(gè)因素之間的概率關(guān)系，對(duì)于Boosting算法而言迭代中樣本的權(quán)值可以表示為一個(gè)概率形式。1999 年，Schapire介紹了一種Boosting算法叫做AdaBoost[24]，通過分析其泛化界解釋Boosting算法的潛在理論。同年，F(xiàn)riedman 將梯度思想[25]引入到Boosting學(xué)習(xí)中，在每個(gè)迭代中使用潛在損失函數(shù)的梯度為樣本分配權(quán)值，由此設(shè)計(jì)出了一系列基于梯度的Boosting算法。之后，為了解決Adaboost 算法對(duì)噪聲數(shù)據(jù)較敏感問題，F(xiàn)reund 等人提出了一種魯棒的Boosting算法叫做Brownboost[26]，該法利用無限水平近似技術(shù)來構(gòu)造出一個(gè)魯棒的損失函數(shù)，然后用其來計(jì)算在每次迭代過程中樣本的權(quán)重。2003年，Kim等人分別用Bagging和Boosting來構(gòu)建SVM分類集成系統(tǒng)[27]，實(shí)驗(yàn)結(jié)果顯示集成后的分類系統(tǒng)比傳統(tǒng)的SVM 分類方法具有更好的分類性能。2005年，Rosset等人提出了一種利用樣本的權(quán)衰減函數(shù)來改善基于梯度的Boosting方法的魯棒性，這個(gè)權(quán)衰減函數(shù)融入了Huber估計(jì)的思想[28]。2008 年，Zhang等人提出了一個(gè)局部Boosting算法[29]，這是一種基于重采樣的AdaBoost方法，實(shí)驗(yàn)結(jié)果顯示該算法比AdaBoost算法具有更好的穩(wěn)健性。

對(duì)于集成學(xué)習(xí)結(jié)合方式的有效性，許多學(xué)者進(jìn)行了討論。1999年，Opitz等人比較了Bagging和兩個(gè)Boosting算法[30]（AdaBoost，Arching），比較后發(fā)現(xiàn)在一個(gè)低噪聲環(huán)境下，Boosting分類性能優(yōu)于Bagging，但Bagging 的魯棒性更強(qiáng)。2000年，Jain等人以一組分類器的結(jié)果如何結(jié)合改進(jìn)總體分類精度為目標(biāo)來討論分類器組合方式問題[31]。研究者將這一問題針對(duì)不同的特征集，不同的訓(xùn)練樣本集，不同的分類方法進(jìn)行分析。實(shí)驗(yàn)結(jié)果顯示對(duì)于相同的特征集，結(jié)合不同的分類器沒有任何優(yōu)勢(shì)，但在不同特征集下構(gòu)建出的分類系統(tǒng)卻效果明顯。同年，Kuncheva等人采用遺傳算法設(shè)計(jì)了兩個(gè)分類器融合系統(tǒng)[32]，設(shè)計(jì)發(fā)現(xiàn)對(duì)于可能有重疊的特征子集，分類集成系統(tǒng)顯現(xiàn)出良好的性能，但對(duì)于不相交的特征子集分類準(zhǔn)確率卻難以得到真正改善。2002年，Skurichina討論了分類集成決策的穩(wěn)定性問題[33]，結(jié)果顯示Bagging可以有效改善分類的穩(wěn)定性。2007年，Anne等研究了基分類器的選擇和融合方法對(duì)分類集成系統(tǒng)的影響問題[34]，并得到一個(gè)重要的實(shí)驗(yàn)結(jié)論：選擇各異的基分類器對(duì)提升分類集成系統(tǒng)的性能是有幫助的。

4大間隔分類學(xué)習(xí)存在的問題

目前，大間隔分類學(xué)習(xí)存在的主要問題有：

（1）噪聲是普遍存在的，基于間隔的特征選擇方法對(duì)噪聲比較敏感，未來對(duì)基于間隔的特征選擇方法的抗噪性研究是一個(gè)很好的研究方向。

（2）對(duì)于現(xiàn)有魯棒的SVM分類學(xué)習(xí)方法而言，這些方法已經(jīng)有效地解決了分類模型對(duì)噪聲的影響，但其訓(xùn)練模型的時(shí)間復(fù)雜性較高，由此而限制了其實(shí)用性。這些問題，將有待于進(jìn)一步研究。

5結(jié)束語

在機(jī)器學(xué)習(xí)領(lǐng)域中，間隔扮演著重要的角色，這是對(duì)分類置信度的一種刻畫，可用于估計(jì)分類學(xué)習(xí)算法的泛化誤差界和指導(dǎo)分類算法的設(shè)計(jì)。近年來，該理論已廣泛應(yīng)用于特征選擇，分類器訓(xùn)練和集成學(xué)習(xí)。本文論述大間隔分類學(xué)習(xí)方法的研究現(xiàn)狀，并給出了其存在的問題，為未來的研究有一定的指導(dǎo)意義。

參考文獻(xiàn)：

[1]CORTES C， VAPNIK V. Support-vector networks[J]. Machine learning， 1995， 20（3）：273–297.

[2]SCHAPIRE R E， FREUND Y， BARTLETT P， et al. Boosting the margin： a new explanation for the effectiveness of voting methods[J]. Annals of Statistics， 1998， 26：1651–1686.

[3]BARTLETT P， SHAWE-TAYLOR J. Generalization performance of support vector machines and other pattern classifiers[J]. Advances in Kernel Methods—Support Vector Learning， 1999：43–54.

[4]CRAMMER K， GILAD R B， NAVOT A， et al. Margin Analysis of the Lvq Algorithm[C]//Proceeding 17th Conference on Neural Information Processing Systems， 2002：462–469.

[5]GILAD-BACHRACH R， NAVOT A， TISHBY N. Margin based feature selection-theory and algorithms[C]//Proceedings of the 21st International Conference on Machine Learning， 2004：40–48.

[6]KONONENKO I， RUAN D， FREUND Y. Estimating attributes analysis and extensions of RELIEF[C]//Proceedings of European Conference Machine Learning， 1994：171–182.

[7]ANDREW Y N. Feature selection L1 vs. L2 regularization， and rotational invariance[C]//Proceedings of the 21st International Conference on Machine Learning， 2004：171–182.

[8]PARK S Y， LIU Y. Robust penalized Logistic regression with truncated loss functions[J]. Canadian Journal of Statistics， 2011， 39（2）：300–323

[9]LI Y， LU B L. Feature selection based on loss-margin of nearest neighbor classification[J]. Pattern Recognition， 2009， 42：1914–1921.

[10]SUYKENS J， VANDEWALLE J. Least squares support vector machine classifiers[J]. Neural Processing Letters， 1999， 9（3）：293–300.

[11]SUYKENS J， BRABANTER J， LUKAS L， et al. Weighted least squares support vector machines： robustness and sparse approximation[J]. Neurocomputing， 2002，8：85–105.

[12]SONG Q， HU W， XIE W. Robust support vector machine with Bullet Hole image classification[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C：Applications and Reviews， 2002， 32（4）：440–448.

[13]XU L， CRAMMER K， SCHUURMANS D. Robust support vector machine training via convex outlier ablation[C]//Proceedings of the 21st American Association for Artificial Intelligence， 2006：413–420.

[14]WU Y， LIU Y F. Robust truncated hinge loss support vector machines[J]. IEEE Transaction Pattern Analysis and Machine Intelligence， 2007， 102（479）：974–983.

[15]WANG L， JIAA H D， LI J. Training Robust support vector machine with smooth ramp loss in the primal space[J]. Neurocomputing， 2008， 71（479）：3020–3025.

[16]MA Y F， HUANG X L， WANG S N. Robust support vector machine using least median loss penalty [C]//Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory， 2011：18–26.

[17]JIANG X F， ZHANG Y， CHENG L J. Fuzzy SVM with a new fuzzy membership function[J]. Neural Computing & Applications， 2006， 15（3-4）： 268–276.

[18]WU K， YAP K H. Fuzzy SVM for content-based image retrieval： A pseudolabel Support Vector Machine framework[J]. Computational Intelligence Magazine， 2006， 1（2）：10–16.

[19]GALAR M， FERNANDEZ A， BARRENECHEA E， et al. A review on ensembles for the class imbalance problem： bagging， boosting and hybrid-based approaches[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C： Applications and Reviews， 2012， 42（4）：463–484.

[20]WOLPERT H D. Stacked generalization[J]. Neural Networks， 1992， 5（2）：241–259.

[21]BERIMEN L. Bagging predictors[J]. Machine Learning， 1996， 24（2）：123–140.

[22]HO T K. The random subspace method for constructing decision forests[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1998，20（8）：832–844.

[23]KOTSIANTIS S B. Logitboost of simple Bayesian classifier[J]. Informatica， 2005，29（1）：53–59.

[24]FREUND Y. Experiments with a New Boosting Algorithm[C]//Proceedings of the 13th International Conference Machine Learning， 1996：148–156.

[25]FRIEDMAN J. Greedy function approximation： a gradient Boosting machine[J]. Annals of Statistics， 2001， 29（5）：53–59.

[26]An adaptive version of the Boost by majority algorithm[C]//Proceedings of the 19th International Conf-erence on Machine Learning， 2001：293–318.

[27]KIM H C， PANG S N， JE H M， et al. Constructing support vector machine ensemble[J]. Pattern Recognition， 2003， 36（12）：2757–2767.

[28]ROSSET S. Robust Boosting and its relation to bagging[C]//12th ACM SIGKDD Conference on Know-ledge Discovery and Data Mining， 2005：131–138.

[29]ZHANG C X， ZHANG J . A local boosting algorithm for solving classification problems[J]. Computational Statistics and Data Analysis， 2008， 52（4）：1928–1941.

[30]OPITZ D W， RICHARD M. Popular ensemble methods： An empirical study[J]. Journal of Artificial Intell-igence Research， 1999， 11（4）：169–198.

[31]JAIN A K， ROBERT P W. Statistical pattern recognition： a review.[J].IEEE Transactions on Pattern An-alysis and Machine Intelligence，2005：131–138.

[32]KUNCHEVA L I， JAIN J. Classifier ensembles with a random linear Oracle[J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（4）：500–508.

[33]SKURICHINA M， ROBERT P W. Bagging， boosting and the random subspace method for linear classifiers[J]. Pattern Analysis and Applications， 2002， 5（2）：121–135.

[34]ANNE M P， CAUNTO A. Investigating the Influence of the choice of the ensemble members in accuracy and diversity of selection-based and fusion-based methods for ensembles[J]. Pattern Recognition Letters， 2007， 28（4）：472–486.