Learning large margin classifiers locally and globally

ABSTRACT

A new large margin classifier, named Maxi-Min Margin Machine (M⁴) is proposed in this paper. This new classifier is constructed based on both a "local: and a "global" view of data, while the most popular large margin classifier, Support Vector Machine (SVM) and the recently-proposed important model, Minimax Probability Machine (MPM) consider data only either locally or globally. This new model is theoretically important in the sense that SVM and MPM can both be considered as its special case. Furthermore, the optimization of M⁴ can be cast as a sequential conic programming problem, which can be solved efficiently. We describe the M⁴ model definition, provide a clear geometrical interpretation, present theoretical justifications, propose efficient solving methods, and perform a series of evaluations on both synthetic data sets and real world benchmark data sets. Its comparison with SVM and MPM also demonstrates the advantages of our new model.

REFERENCES

• 1: Bertsekas, D. P. (1999). Nonlinear programming. Belmont, Massashusetts: Athena Scientific. 2nd edition.
• 2: Breiman, L. (1998). Arcing classifiers. Annals of Statistics, 26(3), 801--849.
• 3: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 4: Gert R.G. Lanckriet , Laurent El Ghaoui , Chiranjib Bhattacharyya , Michael I. Jordan, A robust minimax approach to classification, The Journal of Machine Learning Research, 3, p.555-582, 3/1/2003
• 5: Lobo, M., Vandenberghe, L., Boyd, S., & Lebret, H. (1998). Applications of second order cone programming. Linear Algebra and its Applications, 284, 193--228.
• 6: Pruessner, A. (2003). Conic programming in GAMS. In Optimization software - the state of the art. http://www.gamsworld.org/cone/links.htm: INFORMS Atlanta.
• 7: Alexander J. Smola , Peter J. Bartlett, Advances in Large Margin Classifiers, MIT Press, Cambridge, MA, 2000
• 8: Sturm, J. (1999). Using Sedumi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization Methods and Software, 11, 625--653.
• 9: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995