Multi-class cost-sensitive boosting with p-norm loss functions

ABSTRACT

We propose a family of novel cost-sensitive boosting methods for multi-class classification by applying the theory of gradient boosting to p-norm based cost functionals. We establish theoretical guarantees including proof of convergence and convergence rates for the proposed methods. Our theoretical treatment provides interpretations for some of the existing algorithms in terms of the proposed family, including a generalization of the costing algorithm, DSE and GBSE-t, and the Average Cost method. We also experimentally evaluate the performance of our new algorithms against existing methods of cost sensitive boosting, including AdaCost, CSB2, and AdaBoost.M2 with cost-sensitive weight initialization. We show that our proposed scheme generally achieves superior results in terms of cost minimization and, with the use of higher order p-norm loss in certain cases, consistently outperforms the comparison methods, thus establishing its empirical advantage.

REFERENCES

• 1: Naoki Abe , Bianca Zadrozny , John Langford, An iterative method for multi-class cost-sensitive learning, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014056]
• 2: C. L. Blake and C. J. Merz. UCI repository of machine learning databases. Department of Information and Computer Sciences, University of California, Irvine, 1998. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 3: 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]
• 4: Charles Elkan, Magical thinking in data mining: lessons from CoIL challenge 2000, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.426-431, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502576]
• 5: 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
• 6: 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]
• 7: Ulrich Knoll , Gholamreza Nakhaeizadeh , Birgit Tausend, Cost-sensitive pruning of decision trees, Proceedings of the European conference on machine learning on Machine Learning, p.383-386, May 1994, Catania, Italy
• 8: Dragos Dorin Margineantu , Thomas G. Dietterich, Methods for cost-sensitive learning, Oregon State University, Corvallis, OR, 2002
• 9: L. Mason, J. Baxter, P. Barlett, and M. Frean. Boosting algorithms as gradient descent. In Advances in Neural Information Processing systems 12, pages 512--158, 2000.
• 10: L. Mason, J. Baxter, P. Bartlett, and M. Frean. Boosting algorithms as gradient descent in function space. Technical report, RSISE, Australian National University, 1999. http://wwwsyseng.anu.edu.au/~jon/papers/doom2.ps.gz.
• 11: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 12: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 13: 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
• 14: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 15: Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502540]
• 16: Bianca Zadrozny , John Langford , Naoki Abe, Cost-Sensitive Learning by Cost-Proportionate Example Weighting, Proceedings of the Third IEEE International Conference on Data Mining, p.435, November 19-22, 2003
• 17: T. Zhang. Sequential greedy approximation for certain convex optimization problems. volume IT-49, pages 682--691, 2003.
• 18: Z. H. Zhou and X. Y. Liu. On multi-class cost sensitive learning. In Proceedings of the 21st National Conference on Artificial Intelligence, pages 567--572, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
boosting, cost-sensitive learning, multi-class classification