劉建偉，付 捷，羅雄麟

中國石油大學(xué)（北京）自動(dòng)化研究所，北京 102249

距離和損失函數(shù)約束正則化的AdaBoost算法

劉建偉，付 捷，羅雄麟

中國石油大學(xué)（北京）自動(dòng)化研究所，北京 102249

1 引言

其中ut，i=，樣本分類準(zhǔn)則為：

at權(quán)值反映該弱分類器的訓(xùn)練誤差率。在訓(xùn)練開始之前，初始化樣本的初始權(quán)值w1，i=1/m，假如有t輪實(shí)驗(yàn)，即t個(gè)弱分類器，在每輪訓(xùn)練結(jié)束后，就會(huì)產(chǎn)生這個(gè)弱分類器ft(xi)的訓(xùn)練誤差，同時(shí)得到ft(xi)的信任權(quán)at(0≤at＜1)，at反映了ft(xi)的訓(xùn)練準(zhǔn)確度，而且at必須保證·ut=0，如果的訓(xùn)練誤差小，那么at就較大；反之就較小。同時(shí)根據(jù)訓(xùn)練結(jié)果更新樣本權(quán)重。

AdaBoost算法偽代碼如下所示：

J.Kivinen和M.K.Warmuth在文獻(xiàn)[8]中提出了一種基于正則化的在線學(xué)習(xí)模式，他們認(rèn)為預(yù)測(cè)算法的設(shè)計(jì)必須考慮兩點(diǎn)：一方面，算法應(yīng)該從實(shí)驗(yàn)中學(xué)習(xí)到信息，如果重新觀察同樣的樣本和真實(shí)值，那么新權(quán)重w的損失L(y，wΤ·x)應(yīng)該比舊權(quán)重的損失函數(shù)L(y，sΤ·x)小。定義改善預(yù)測(cè)正確性的特性為正確性。另一方面，算法至少應(yīng)該保持在先前實(shí)驗(yàn)中學(xué)習(xí)的信息。因?yàn)橄惹八械膶W(xué)習(xí)信息應(yīng)該體現(xiàn)在權(quán)向量s中，新的權(quán)向量w應(yīng)該接近舊的權(quán)向量s，以距離函數(shù)d(w，s)來測(cè)試新舊權(quán)向量的近似度，同時(shí)稱新舊向量的近似度為保守性。算法為了同時(shí)權(quán)衡正確性和保守性，算法的學(xué)習(xí)目標(biāo)可表示為最小化以下函數(shù)：

其中d(w，s)為距離函數(shù)，代表著新舊權(quán)重的近似度；L(y，wΤ·x)為損失函數(shù)，代表著算法的準(zhǔn)確性，在正確性和保守性上，系數(shù)λ＞0發(fā)揮著至關(guān)重要的作用。如果λ接近0，最小化U(w)接近最小化d(w，s)，因此算法的權(quán)向量會(huì)更新很小；當(dāng)λ接近無窮大時(shí)，最小化U(w)近似于距離d(w，s)，其中約束條件為L(y，wΤ·x)=0，如果考慮到樣本和輸出受到噪聲等因素的干擾，可選擇一個(gè)小的系數(shù)值λ。

J.Kivinen和M.K.Warmuth在文獻(xiàn)[12]提出可以用式（1）更新AdaBoost算法弱分類器的權(quán)值。但未對(duì)相應(yīng)的算法進(jìn)行研究。

標(biāo)準(zhǔn)的AdaBoost算法中的模型值修正時(shí)，要始終滿足一個(gè)條件·ut=0，建立以下約束方程：

因此，如果把式（2）中的約束條件換為損失函數(shù)約束，則得到本文討論的基于距離和損失函數(shù)正則化的AdaBoost算法。

本文對(duì)基于距離和損失函數(shù)正則化的AdaBoost算法作了研究，使用相關(guān)熵距離函數(shù)：

2 基于距離函數(shù)和損失函數(shù)正則化的AdaBoost算法

將根據(jù)以上算法進(jìn)行雙目標(biāo)優(yōu)化：選擇距離函數(shù)和損失函數(shù)，以便求出新的AdaBoost的權(quán)值更新模式。

定理1假如距離函數(shù)為：

U對(duì)wi求導(dǎo)得：

表1 三種數(shù)據(jù)集上的預(yù)測(cè)誤差平均值 （%）

證明由U=d+λL( )w·ut得：

3 實(shí)驗(yàn)結(jié)果

基于距離和損失函數(shù)的不同，下文稱定理1中提出的算法為AdaBoostRE（AdaBoost Relative Entropy）算法；稱定理2中提出的算法為AdaBoostIE（AdaBoost Itakura-Saito Entropy）；稱定理3中提出的算法為AdaBoostEE（AdaBoost Exponent Entropy）。為了綜合比較AdaBoost測(cè)試算法在真實(shí)數(shù)據(jù)中的訓(xùn)練和預(yù)測(cè)效果，使用UCI數(shù)據(jù)庫中的Ionosphere數(shù)據(jù)集、Breast_cancer數(shù)據(jù)集和Australian數(shù)據(jù)集對(duì)上述的四種新的AdaBoost算法進(jìn)行了實(shí)驗(yàn)研究[16]。同時(shí)與三種Real AdaBoost，Gentle AdaBoost和Modest AdaBoost算法進(jìn)行比較分析。這里，Ionosphere數(shù)據(jù)集中每個(gè)樣本為34維數(shù)據(jù)，訓(xùn)練樣本數(shù)為176，測(cè)試樣本有175個(gè)。Breast_ cancer數(shù)據(jù)集為10維數(shù)據(jù)，訓(xùn)練樣本數(shù)為342，測(cè)試樣本數(shù)為341個(gè)。Australian數(shù)據(jù)為14維數(shù)據(jù)，訓(xùn)練樣本數(shù)為345，測(cè)試樣本為345。三種數(shù)據(jù)集上的預(yù)測(cè)誤差平均值如表1所示。

從表1可以看出，所有算法在Ionosphere數(shù)據(jù)集上的預(yù)測(cè)誤差率在10%以上，Breast_cancer數(shù)據(jù)集上的預(yù)測(cè)誤差率為3%～9%之間，Australian數(shù)據(jù)集上的預(yù)測(cè)誤差率為14%～19%之間。三種數(shù)據(jù)集上，AdaBoostRE預(yù)測(cè)誤差率最低，AdaBoostIE和AdaBoostEE算法比AdaBoost，Modest Ada-Boost和Gentle AdaBoost算法預(yù)測(cè)誤差率高。

4 結(jié)論

本文基于J.Kivinen和M.K.Warmuth在文獻(xiàn)[12]中提出的弱分類器對(duì)基于距離和損失函數(shù)正則化的AdaBoost權(quán)值更新模式作了研究，使用相關(guān)熵距離函數(shù)，Itakura-Saito距離函數(shù)，指數(shù)一次近似距離和相關(guān)熵?fù)p失函數(shù)結(jié)合，實(shí)現(xiàn)了三種AdaBoost弱分類權(quán)更新算法。在實(shí)驗(yàn)部分，利用UCI標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)提出的三種算法與三種主要的AdaBoost算法：Real AdaBoost[9]，Gentle AdaBoost[10]和Modest AdaBoost[12]算法作了比較研究。本文提出的AdaBoost算法采用了新的樣本權(quán)值更新方法和弱分類器訓(xùn)練方法，可以達(dá)到很好的預(yù)測(cè)效果。其中AdaBoostRE算法的預(yù)測(cè)效果要優(yōu)于傳統(tǒng)的Real AdaBoost，Gentle AdaBoost和Modest AdaBoost算法，達(dá)到很好的預(yù)測(cè)準(zhǔn)確性。

[1]Xi Y Τ，Xiang Z J，Ramadge P J，et al.Speed and sparsity of regularized boosting[C]//Proceedings of the Τwelfth International Conference on Artificial Intelligence and Statistics，2009.

[2]Rudin C，Schapire R E.Margin-based ranking and an equivalence between AdaBoost and RankBoost[J].Journal of Machine Learning Research，2009，10：2193-2232.

[3]Buhlmann P，Hothorn Τ.Boosting algorithms：regularization，prediction and model fitting[J].Statistical Science，2007，22（4）：477-505.

[4]Rudin C，Schapire R E，Daubechies I.Boosting based on a smooth margin[C]//COLΤ，2004：502-517.

[5]Rudin C，Daubechies I，Schapire R E.Τhe dynamics of Ada-Boost：cyclic behavior and convergence of margins[J].Journal of Machine Learning Research，2004，5：1557-1595.

[6]Collins M，Schapire R E，Singer Y.Logistic regression，Ada-Boost and Bregman distances[J].Machine Learning，2002，48：253-285.

[7]Schapire R E.Τhe convergence rate of AdaBoost[C]//Τhe 23rd Conference on Learning Τheory，2010.

[8]Kivinen J，Warmuth M K.Exponentiated gradient versus gradient descent for linear predictors[J].Information and Computation，1997，132（2）：1-63.

[9]Freund Y.Boosting a weak learning algorithm by majority[J]. Information and Computation，1995，121（2）：256-285.

[10]R?tsch G，Onoda Τ，Müller K R.Soft margins for AdaBoost[J]. Machine Learning，2001，42（3）：287-320.

[11]Freund Y，Schapire R E.Game theory，on-line prediction and boosting[C]//Proceedings of the Ninth Annual Conference on Computational Learning Τheory，1996：325-332.

[12]Kivinen J，Warmuth M K.Boosting as entropy projection[C]// Computational Learning Τheory，New York，1999.

[13]VezhnevetsA，VezhnevetsV.ModestAdaBoost—teaching AdaBoost to generalize better[C]//Graphicon，2005.

[14]Schapire R E，Singer Y.Improved boosting algorithms using confidence-rated predictions[J].Machine Learning，1999，37（3）：297-336.

[15]Friedman J，Hastie Τ，Τibshirani R.Additive logistic regression：a statistical view of boosting[J].Τhe Annals of Statistics，2000，38（2）：337-374.

[16]Τhe Center for Machine Learning and Intelligent Systems. UC irvine machine learning repository[EB/OL].（2007-10-07）. http：//archive.ics.uci.edu/ml/datasets.html.

LIU Jianwei,FU Jie,LUO Xionglin

Institute of Automation,China University of Petroleum,Beijing 102249,China

According to weight update model via distance and lost function regularization,proposed by J.Kivinen and M.K.Warmuth, using relative entropy,Itakura-Saito,first order exponential approximation distance function,combined with relative entropy lost function,this paper devises three sorts of weight update method of weak classifier of AdaBoost.Using the UCI real datasets, the three algorithms AdaBoostRE,AdaBoostIE,AdaBoostEE are compared with three leading assembly classifier：Real AdaBoost, Gentle AdaBoost and Modest AdaBoost.Experimental results show promising performance of the proposed method.

distance function;loss function;regularization;AdaBoost algorithm

基于距離函數(shù)和損失函數(shù)正則化的權(quán)值更新模式，使用相關(guān)熵距離函數(shù)，Itakura-Saito距離函數(shù)，指數(shù)一次近似距離和相關(guān)熵?fù)p失函數(shù)結(jié)合，實(shí)現(xiàn)了三種AdaBoost弱分類器權(quán)值更新算法。使用UCI數(shù)據(jù)庫數(shù)據(jù)對(duì)提出的三種算法AdaBoostRE，AdaBoostIE，AdaBoostEE與Real AdaBoost，Gentle AdaBoost和Modest AdaBoost算法作了比較，可以看到提出的AdaBoostRE算法預(yù)測(cè)效果最好，優(yōu)于Real AdaBoost，Gentle AdaBoost和Modest AdaBoost算法。

距離函數(shù)；損失函數(shù)；正則化；AdaBoost算法

A

ΤP181

10.3778/j.issn.1002-8331.1111-0360

LIU Jianwei,FU Jie,LUO Xionglin.AdaBoost algorithm based on distance and loss function constraint regularization. Computer Engineering and Applications,2013,49（15）：133-135.

國家自然科學(xué)基金（No.21006127，No.20976193）；中國石油大學(xué)（北京）基礎(chǔ)學(xué)科研究基金項(xiàng)目資助。

劉建偉（1966—），男，博士，副研究員，主要研究方向：智能信息處理，復(fù)雜系統(tǒng)分析，預(yù)測(cè)與控制，算法分析與設(shè)計(jì)；付捷（1987—），女，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)；羅雄麟（1963—），男，博士，教授，主要研究方向：智能控制。E-mail：liujw@cup.edu.cn

2011-11-21

2012-02-17

1002-8331（2013）15-0133-03

CNKI出版日期：2012-05-09 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120509.0845.006.html