Online Boosting Algorithms Based on Exponential and 0-1 Loss
-
摘要: 推导了使用指数损失函数和0-1损失函数的Boosting 算法的严格在线形式,证明这两种在线Boosting算法最大化样本间隔期望、最小化样本间隔方差.通过增量估计样本间隔的期望和方差,Boosting算法可应用于在线学习问题而不损失分类准确性. UCI数据集上的实验表明,指数损失在线Boosting算法的分类准确性与批量自适应 Boosting (AdaBoost)算法接近,远优于传统的在线Boosting;0-1损失在线Boosting算法分别最小化正负样本误差,适用于不平衡数据问题,并且在噪声数据上分类性能更为稳定.Abstract: In this paper, strict derivation for the online form of Boosting algorithms using exponential loss and 0-1 loss is presented, which proves that the two online Boosting algorithms can maximize the average margin and minimize the margin variance. By estimating the margin mean and variance incrementally, Boosting algorithms can be applied to online learning problems without losing classification accuracy. Experiments on UCI machine learning datasets show that the online Boosting using exponential loss is as accurate as batch AdaBoost, and significantly outperforms the traditional online Boosting, and that the online Boosting using 0-1 loss can minimize classification errors of positive samples and negative samples at the same time, thus applies to imbalance data. Moreover, Boosting using 0-1 loss is more robust on noisy data.
-
Key words:
- AdaBoost /
- online learning /
- feature selection /
- imbalance data
-
[1] Freund Y, Schapire R E, Abe N. A short introduction to Boosting. Journal-Japanese Society for Artificial Intelligence, 1999, 14(5): 771-780 [2] Freund Y, Schapire R E. A desicion-theoretic generalization of on-line learning and an application to Boosting. Journal of Computer and System Sciences, 1997, 55(1): 119-139 [3] Cao Ying, Miao Qi-Guang, Liu Jia-Chen, Gao Lin. Advance and prospects of Adaboost algorithm. Acta Automatica Sinica, 2013, 39(6): 745-758(曹莹, 苗启广, 刘家辰, 高琳. Adaboost算法研究进展与展望. 自动化学报, 2013, 39(6): 745-758) [4] Viola P, Jones M J. Robust real-time face detection. International Journal of Computer Vision, 2004, 57(2): 137-154 [5] Zhang C, Zhang Z Y. A Survey of Recent Advances in Face Detection, Technical Report MSR-TR-2010-66, Microsoft Research, Redmond, WA, 2010 [6] Wu J X, Rehg J M, Mullin M D. Learning a rare event detection cascade by direct feature selection. [Online], available: http: //papers.nips.cc/paper/2353-learning-a-rare-event-detection-cascade-by-direct-feature-selection.pdf, October 25, 2012 [7] Bartlett P, Freund Y, Lee W S, Schapire R E. Boosting the margin: a new explanation for the effectiveness of voting methods. The Annals of Statistics, 1998, 26(5): 1651-1686 [8] Grabner H, Grabner M, Bischof H. Real-time tracking via on-line Boosting. In: Proceedings of the 2006 British Machine Vision Conference. Edinburgh, British, 2006, 1: 4756 [9] Kuo C H, Nevatia R. How does person identity recognition help multi-person tracking? In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2011. 1217-1224 [10] Yang B, Nevatia R. Multi-target tracking by online learning of non-linear motion patterns and robust appearance models. In: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2012. 1918-1925 [11] Grabner H, Bischof H. On-line Boosting and vision. In: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, NY: IEEE, 2006, 1: 260-267 [12] Liu X M, Yu T. Gradient feature selection for online Boosting. In: Proceedings of the 11th IEEE International Conference on Computer Vision (ICCV). Rio de Janeiro: IEEE, 2007. 1-8 [13] Oza N C. Online Ensemble Learning [Ph.D. dissertation], The University of California, Berkeley, 2001 [14] Grabner H, Leistner C, Bischof H. Semi-supervised on-line Boosting for robust tracking. Computer Vision-ECCV 2008. Berlin Heidelberg: Springer, 2008: 234-247 [15] Babenko B, Yang M H, Belongie S. Robust object tracking with online multiple instance learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1619-1632 [16] Shen C H, Li H X. On the dual formulation of Boosting algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(12): 2216-2231 [17] Friedman J H. Greedy function approximation: a gradient Boosting machine. Annals of Statistics, 2001, 29(5): 11891232 [18] Vapnik V. The Nature of Statistical Learning Theory. New York: Springer, 2000 [19] Wu J, Brubaker S C, Mullin M D, Rehg J M. Fast asymmetric learning for cascade face detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(3): 369-382 [20] Ge Jun-Feng, Luo Yu-Pin. A comprehensive study for asymmetric Adaboost and its application in object detection. Acta Automatica Sinica, 2009, 35(11): 1403-1409 (葛俊锋, 罗予频. 非对称AdaBoost算法及其在目标检测中的应用. 自动化学报, 2009, 35(11): 1403-1409) [21] He H B, Garcia E A. Learning from imbalanced data. Transactions on Knowledge and Data Engineering, 2009, 21(9): 1263-1284 [22] Li Qiu-Jie, Mao Yao-Bin, Wang Zhi-Quan. Research on Boosting-based imbalanced data classification. Computer Science, 2011, 38(12): 224-228 (李秋洁, 茅耀斌, 王执铨. 基于Boosting的不平衡数据分类算法研究. 计算机科学, 2011, 38(12): 224-228) [23] Li Qiu-Jie, Mao Yao-Bin. AUC optimization Boosting based on data rebalance. Acta Automatica Sinica, 2013, 39(9): 1467-1475 (李秋洁, 茅耀斌. 基于数据重平衡的AUC 优化Boosting算法. 自动化学报, 2013, 39(9): 1467-1475) [24] Sun Y M, Kamel M S, Wong A K C, Wang Y. Cost-sensitive Boosting for classification of imbalanced data. Pattern Recognition, 2007, 40(12): 3358-3378
点击查看大图
计量
- 文章访问数: 2492
- HTML全文浏览量: 128
- PDF下载量: 1384
- 被引次数: 0