Asymmetric boosting

ABSTRACT

A cost-sensitive extension of boosting, denoted as asymmetric boosting, is presented. Unlike previous proposals, the new algorithm is derived from sound decision-theoretic principles, which exploit the statistical interpretation of boosting to determine a principled extension of the boosting loss. Similarly to AdaBoost, the cost-sensitive extension minimizes this loss by gradient descent on the functional space of convex combinations of weak learners, and produces large margin detectors. It is shown that asymmetric boosting is fully compatible with AdaBoost, in the sense that it becomes the latter when errors are weighted equally. Experimental evidence is provided to demonstrate the claims of cost-sensitivity and large margin. The algorithm is also applied to the computer vision problem of face detection, where it is shown to outperform a number of previous heuristic proposals for cost-sensitive boosting (AdaCost, CSB0, CSB1, CSB2, asymmetric-AdaBoost, AdaC1, AdaC2 and AdaC3).

REFERENCES

• 1: Chawla, N. V., Lazarevie, A., Hall, L. O., & Bowyer, K. (2003). Smoteboost: Improving prediction of the minority class in boosting. In Proceedings of Principles of Knowledge Discovery in Databases.
• 2: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 3: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 4: Wei Fan , Salvatore J. Stolfo , Junxin Zhang , Philip K. Chan, AdaCost: Misclassification Cost-Sensitive Boosting, Proceedings of the Sixteenth International Conference on Machine Learning, p.97-105, June 27-30, 1999
• 5: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 6: Freund, Y., & Schapire, R. (2004). A discussion of "Process consistency for AdaBoost" by Wenxin Jiang, "On the Bayes-risk consistency of regularized boosting methods" by Gabor Lugosi and Nicolas Vayatis, "Statistical behavior and consistency of classification methods based on convex risk minimization" by Tong Zhang. Annals of Statistics.
• 7: Friedman, J., Hastie, T., & Tibshirani, R. (2000). Additive logistic regression: A statistical view of boosting. Journal of Annals of Statistics.
• 8: Hongyu Guo , Herna L. Viktor, Learning from imbalanced data sets with boosting and data generation: the DataBoost-IM approach, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007736]
• 9: Hastie, Tibshirani, & Friedman (2001). The elements of statistical learning. New York: Springer-Verlag Inc.
• 10: Mason, L., Baxter, J., Bartlett, P., & Frean, M. (2000). Boosting Algorithms as Gradient Descent. NIPS.
• 11: Park, S.-B., Hwang, S., & Zhang, B.-T. (2003). Mining the risk types of human papillomavirus (hpv) by adacost. International Conference on Database and expert Systems Applications.
• 12: Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics.
• 13: Sun, Y., Wong, A. K. C., & Wang, Y. (2005). Parameter inference of cost-sensitive boosting algorithms. Machine Learning and Data Mining in Pattern Recognition, 4th International Conference.
• 14: Kai Ming Ting, A Comparative Study of Cost-Sensitive Boosting Algorithms, Proceedings of the Seventeenth International Conference on Machine Learning, p.983-990, June 29-July 02, 2000
• 15: Stijn Viaene , Richard A. Derrig , Guido Dedene, Cost-sensitive learning and decision making for massachusetts pip claim fraud data, International Journal of Intelligent Systems, v.19 n.12, p.1197-1215, December 2004 [doi>10.1002/int.v19:12]
• 16: Viola, P., & Jones, M. (2001). Robust real-time object detection. Proc. 2nd Intl Workshop on Statistical and Computational Theories of Vision Modeling, Learning, Computing and Sampling. Vancouver, Canada.
• 17: Viola, P., & Jones, M. (2002). Fast and robust classification using asymmetric adaboost and a detector cascade. NIPS.
• 18: Zadrozny, B., Langford, J., & Abe, N. (2003). A simple method for cost-sensitive learning. Technical Report RC22666, IBM.