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

劉建偉，付 捷，羅雄麟

中國石油大學（北京）自動化研究所，北京 102249

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

劉建偉，付 捷，羅雄麟

中國石油大學（北京）自動化研究所，北京 102249

1 引言

其中ut，i=，樣本分類準則為：

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

AdaBoost算法偽代碼如下所示：

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

其中d(w，s)為距離函數，代表著新舊權重的近似度；L(y，wΤ·x)為損失函數，代表著算法的準確性，在正確性和保守性上，系數λ＞0發揮著至關重要的作用。如果λ接近0，最小化U(w)接近最小化d(w，s)，因此算法的權向量會更新很?。划敠私咏鼰o窮大時，最小化U(w)近似于距離d(w，s)，其中約束條件為L(y，wΤ·x)=0，如果考慮到樣本和輸出受到噪聲等因素的干擾，可選擇一個小的系數值λ。

J.Kivinen和M.K.Warmuth在文獻[12]提出可以用式（1）更新AdaBoost算法弱分類器的權值。但未對相應的算法進行研究。

標準的AdaBoost算法中的模型值修正時，要始終滿足一個條件·ut=0，建立以下約束方程：

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

本文對基于距離和損失函數正則化的AdaBoost算法作了研究，使用相關熵距離函數：

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

將根據以上算法進行雙目標優化：選擇距離函數和損失函數，以便求出新的AdaBoost的權值更新模式。

定理1假如距離函數為：

U對wi求導得：

表1 三種數據集上的預測誤差平均值 （%）

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

3 實驗結果

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

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

4 結論

本文基于J.Kivinen和M.K.Warmuth在文獻[12]中提出的弱分類器對基于距離和損失函數正則化的AdaBoost權值更新模式作了研究，使用相關熵距離函數，Itakura-Saito距離函數，指數一次近似距離和相關熵損失函數結合，實現了三種AdaBoost弱分類權更新算法。在實驗部分，利用UCI標準數據集對提出的三種算法與三種主要的AdaBoost算法：Real AdaBoost[9]，Gentle AdaBoost[10]和Modest AdaBoost[12]算法作了比較研究。本文提出的AdaBoost算法采用了新的樣本權值更新方法和弱分類器訓練方法，可以達到很好的預測效果。其中AdaBoostRE算法的預測效果要優于傳統的Real AdaBoost，Gentle AdaBoost和Modest AdaBoost算法，達到很好的預測準確性。

[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

基于距離函數和損失函數正則化的權值更新模式，使用相關熵距離函數，Itakura-Saito距離函數，指數一次近似距離和相關熵損失函數結合，實現了三種AdaBoost弱分類器權值更新算法。使用UCI數據庫數據對提出的三種算法AdaBoostRE，AdaBoostIE，AdaBoostEE與Real AdaBoost，Gentle AdaBoost和Modest AdaBoost算法作了比較，可以看到提出的AdaBoostRE算法預測效果最好，優于Real AdaBoost，Gentle AdaBoost和Modest AdaBoost算法。

距離函數；損失函數；正則化；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.

國家自然科學基金（No.21006127，No.20976193）；中國石油大學（北京）基礎學科研究基金項目資助。

劉建偉（1966—），男，博士，副研究員，主要研究方向：智能信息處理，復雜系統分析，預測與控制，算法分析與設計；付捷（1987—），女，碩士研究生，主要研究方向：機器學習；羅雄麟（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