Non-Convex Online Support Vector Machines

Abstract: In this paper, we propose a non-convex online Support Vector Machine (SVM) algorithm (LASVM-NC) based on the Ramp Loss, which has strong ability of suppressing the influence of outliers. Then, again in the online learning setting, we propose an outlier filtering mechanism (LASVM-I) based on approximating non-convex behavior in convex optimization. These two algorithms are built upon another novel SVM algorithm (LASVM-G) that is capable of generating accurate intermediate models in its iterative steps by leveraging the duality gap. We present experimental results that demonstrate the merit of our frameworks in achieving significant robustness to outliers in noisy data classification where mislabeled training instances are in abundance. Experimental evaluation shows that the proposed approaches yield more scalable online SVM algorithm with sparser models and less computational running time both in the training and recognition phases without sacrificing generalization performance. We also point out the relation between non-convex optimization and min-margin active learning.

Seyda Ertekin, Léon Bottou and C. Lee Giles: Non-Convex Online Support Vector Machines, IEEE Transactions on Pattern Recognition and Machine Intelligence, 33(2):368–381, February 2011.

Preprint: tpami-2010.djvu tpami-2010.pdf tpami-2010.ps.gz

@article{ertekin-bottou-giles-2011,
  author = {Ertekin, Seyda and Bottou, L\'{e}on and Giles, C. Lee},
  title = {Ignorance is Bliss: Non-Convex Online Support Vector Machines},
  journal = {IEEE Transactions on Pattern Recognition and Machine Intelligence},
  year = {2011},
  volume = {33},
  number = {2},
  pages = {368--381},
  month = {February},
  note = {to appear.},
  url = {http://leon.bottou.org/papers/ertekin-bottou-giles-2011},
}

Notes

See also Seyda Ertekin's Ph.D. Thesis.