Proceedings

Ensembles of Partially Trained SVMs with Multiplicative Updates

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1089-1093.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

The training of support vector machines (SVM) involves a quadratic programming problem, which is often optimized by a complicated numerical solver. In this paper, we propose a much simpler approach based on multiplicative updates. This idea was first explored in [Cristianini et al., 1999], but its convergence is sensitive to a learning rate that has to be fixed manually. Moreover, the update rule only works for the hard-margin SVM, which is known to have poor performance on noisy data. In this paper, we show that the multiplicative update of SVM can be formulated as a Bregman projection problem, and the learning rate can then be adapted automatically. Moreover, because of the connection between boosting and Bregman distance, we show that this multiplicative update for SVM can be regarded as boosting the (weighted) Parzen window classifiers. Motivated by the success of boosting, we then consider the use of an adaptive ensemble of the partially trained SVMs. Extensive experiments show that the proposed multiplicative update rule with an adaptive learning rate leads to faster and more stable convergence. Moreover, the proposed ensemble has efficient training and comparable or even better accuracy than the best-tuned soft-margin SVM.

  1. [Collins and Schapire, 2002] M. Collins and R.E. Schapire. Lo- gistic regression, AdaBoost and Bregman distances. Machine Learning, 48(1/2/3), 2002.
  2. [Cristianini et al., 1999] N. Cristianini, C. Campbell, and J. Shawe- Taylor. Multiplicative updatings for support vector machines. In Proceeding of European Symposium on Artificial Neural Net- works, Bruges, Belgium, 1999.
  3. [Evgeniou et al., 2004] T. Evgeniou, M. Pontil, and A. Elisseeff. Leave one out error, stability, and generalization of voting com- binations of classifiers. Machine Learning, 55(1):71-97, April 2004.
  4. [Fedotov et al., 2001] A.A. Fedotov, P. Harremoes, and F. Topsoe. Vajda's tight lower bound and refinements of Pinsker's inequality. In Proceedings of the International Symposium on Information Theory, San Mateo, CA, 2001.
  5. [Fine and Scheinberg, 2001] S. Fine and K. Scheinberg. Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2:243-264, December 2001.
  6. [Hastie et al., 2005] T. Hastie, S. Rosset, R. Tibshirani, and J. Zhu. The entire regularization path for the support vector machine. In Lawrence K. Saul, Yair Weiss, and Léon Bottou, editors, Ad- vances in Neural Information Processing Systems 17, pages 561- 568. MIT Press, Cambridge, MA, 2005.
  7. [Kim et al., 2003] H.-C. Kim, S. Pang, H.-M. Je, D. Kim, and S. Bang. Constructing support vector machine ensemble. Pat- tern Recognition, 36(12):2757-2767, 2003.
  8. [Kivinen and Warmuth, 1997] J. Kivinen and M.K. Warmuth. Ad- ditive versus exponentiated gradient updates for linear prediction. Information and Computation, 132(1):1-64, 1997.
  9. [Kivinen and Warmuth, 1999] J. Kivinen and M. K. Warmuth. Boosting as entropy projection. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pages 134 -144, Santa Cruz, CA, USA, 1999.
  10. [Lin, 2001] C.-J. Lin. Linear convergence of a decomposition method for support vector machines. Technical report, National Taiwan University, 2001.
  11. [Platt, 1999] J.C. Platt. Fast training of support vector machines us- ing sequential minimal optimization. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods -Support Vector Learning, pages 185-208. MIT Press, Cambridge, MA, 1999.
  12. [Rätsch and Warmuth, 2005] G Rätsch and M Warmuth. Efficient margin maximization with boosting. Journal of Machine Learn- ing Research, 6:2131-2152, 2005.
  13. [Rätsch, 2001] G. Rätsch. Robust Boosting via Convex Optimiza- tion: Theory and Applications. PhD thesis, University of Pots- dam, October 2001.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards