大間隔分類學習研究現(xiàn)狀

潘巍 馬培軍 蘇小紅

摘要：在機器學習領域中，間隔扮演著重要的角色?？梢杂脕矶攘糠诸惖闹眯哦?；其理論泛化界也可用于指導分類算法的設計。近年來，該理論已廣泛應用于特征選擇，分類器訓練和集成學習。實際上，間隔思想表明如果在訓練階段模型能夠產(chǎn)生大的間隔，那么分類任務將有好的置信度和高可靠性。文中介紹大間隔分類學習方法的研究現(xiàn)狀， 并給出了其存在的問題。

關鍵詞：間隔； 分類學習； 機器學習

中圖分類號：TP39141 文獻標識碼：A文章編號：2095-2163（2013）06-0044-04

0引言

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

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

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

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

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

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

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

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

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

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

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

4大間隔分類學習存在的問題

目前，大間隔分類學習存在的主要問題有：

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

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

5結(jié)束語

在機器學習領域中，間隔扮演著重要的角色，這是對分類置信度的一種刻畫，可用于估計分類學習算法的泛化誤差界和指導分類算法的設計。近年來，該理論已廣泛應用于特征選擇，分類器訓練和集成學習。本文論述大間隔分類學習方法的研究現(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.