Leveraging the margin more carefully

ABSTRACT

Boosting is a popular approach for building accurate classifiers. Despite the initial popular belief, boosting algorithms do exhibit overfitting and are sensitive to label noise. Part of the sensitivity of boosting algorithms to outliers and noise can be attributed to the unboundedness of the margin-based loss functions that they employ. In this paper we describe two leveraging algorithms that build on boosting techniques and employ a bounded loss function of the margin. The first algorithm interleaves the expectation maximization (EM) algorithm with boosting steps. The second algorithm decomposes a non-convex loss into a difference of two convex losses. We prove that both algorithms converge to a stationary point. We also analyze the generalization properties of the algorithms using the Rademacher complexity. We describe experiments with both synthetic data and natural data (OCR and text) that demonstrate the merits of our framework, in particular robustness to outliers.

REFERENCES

• 1: Peter L. Bartlett , Shahar Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.224-240, July 16-19, 2001
• 2: Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Machine Learning, v.48 n.1-3, p.253-285, 2002 [doi>10.1023/A:1013912006537]
• 3: O. Dekel, S. Shalev-Shwartz, and Y. Singer. Smooth epsilon-insensitive regression by loss symmetrization. COLT'03.
• 4: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. of the Royal Statistical Society, Ser. B, 39:1--38, 1977.
• 5: Thomas G. Dietterich, An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization, Machine Learning, v.40 n.2, p.139-157, Aug. 2000 [doi>10.1023/A:1007607513941]
• 6: N. Duffy and D. Helmbold. Potential boosters? NIPS'99.
• 7: Yoav Freund, Boosting a weak learning algorithm by majority, Information and Computation, v.121 n.2, p.256-285, Sept. 1995 [doi>10.1006/inco.1995.1136]
• 8: Yoav Freund, An adaptive version of the boost by majority algorithm, Proceedings of the twelfth annual conference on Computational learning theory, p.102-113, July 07-09, 1999, Santa Cruz, California, United States [doi>10.1145/307400.307419]
• 9: 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]
• 10: Klaus-U. Höffgen , Hans-U. Simon , Kevin S. van Horn, Robust trainability of single neurons, Journal of Computer and System Sciences, v.50 n.1, p.114-125, Feb. 1995 [doi>10.1006/jcss.1995.1011]
• 11: K. Lang. Newsweeder: Learning to filter netnews. ICML'95.
• 12: L. Mason, J. Baxter, P. Bartlett, and M. Frean. Functional gradient techniques for combining hypotheses. In Advances in Large Margin Classifiers. 1999.
• 13: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 14: G. Rätsch. Robust Boosting and Convex Optimization. Doctoral dissertation, University of Potsdam, 2001.
• 15: 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]
• 16: Rocco A. Servedio, Smooth Boosting and Learning with Malicious Noise, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.473-489, July 16-19, 2001
• 17: H. Tuy. 1994. D. C. optimization: Theory, Methods & Algorithms. Horst & Pardalos (Ed) Handbook of Global Opt.
• 18: S. Wang, R. Rosenfeld, Y. Zhao, and D. Schuurmans. The latent maximum entropy principle. In IEEE International Symposium on Information Theory, 2002.
• 19: X. Zhang X. Shen, G. C. Tseng and W. H. Wong. On psi-learning. i. J. of American Statistical Association, 2003.