Maxi–Min Margin Machine: Learning Large Margin Classifiers Locally and Globally
- 7 February 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 19 (2), 260-272
- https://doi.org/10.1109/tnn.2007.905855
Abstract
In this paper, we propose a novel large margin classifier, called the maxi-min margin machine (M4). This model learns the decision boundary both locally and globally. In comparison, other large margin classifiers construct separating hyperplanes only either locally or globally. For example, a state-of-the-art large margin classifier, the support vector machine (SVM), considers data only locally, while another significant model, the minimax probability machine (MPM), focuses on building the decision hyperplane exclusively based on the global information. As a major contribution, we show that SVM yields the same solution as M4 when data satisfy certain conditions, and MPM can be regarded as a relaxation model of M4. Moreover, based on our proposed local and global view of data, another popular model, the linear discriminant analysis, can easily be interpreted and extended as well. We describe the M4 model definition, provide a geometrical interpretation, present theoretical justifications, and propose a practical sequential conic programming method to solve the optimization problem. We also show how to exploit Mercer kernels to extend M4 for nonlinear classifications. Furthermore, we perform a series of evaluations on both synthetic data sets and real-world benchmark data sets. Comparison with SVM and MPM demonstrates the advantages of our new model.Keywords
This publication has 11 references indexed in Scilit:
- Reduced Support Vector Machines: A Statistical TheoryIEEE Transactions on Neural Networks, 2007
- Training algorithms for fuzzy support vector machines with noisy dataPattern Recognition Letters, 2004
- Learning large margin classifiers locally and globallyPublished by Association for Computing Machinery (ACM) ,2004
- A support vector machine formulation to pca analysis and its kernel versionIEEE Transactions on Neural Networks, 2003
- Face recognition using LDA-based algorithmsIEEE Transactions on Neural Networks, 2003
- Fuzzy support vector machinesIEEE Transactions on Neural Networks, 2002
- Fractional-step dimensionality reductionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric conesOptimization Methods and Software, 1999
- Applications of second-order cone programmingLinear Algebra and its Applications, 1998
- Relationship of several variational methods for the approximate solution of ill-posed problemsMathematical Notes, 1970