Binary separation and training support vector machines
- 10 May 2010
- journal article
- research article
- Published by Cambridge University Press (CUP) in Acta Numerica
- Vol. 19, 121-158
Abstract
We introduce basic ideas of binary separation by a linear hyperplane, which is a technique exploited in thesupport vector machine(SVM) concept. This is a decision-making tool for pattern recognition and related problems. We describe a fundamentalstandard problem(SP) and show how this is used in most existing research to develop a dual-based algorithm for its solution. This algorithm is shown to be deficient in certain aspects, and we develop a new primal-based SQP-like algorithm, which has some interesting features. Most practical SVM problems are not adequately handled by a linear hyperplane. We describe thenonlinear SVMtechnique, which enables a nonlinear separating surface to be computed, and we propose a new primal algorithm based on the use of low-rank Cholesky factors.It may be, however, that exact separation is not desirable due to the presence of uncertain or mislabelled data. Dealing with this situation is the main challenge in developing suitable algorithms. Existing dual-based algorithms use the idea ofL1penalties, which has merit. We suggest how penalties can be incorporated into a primal-based algorithm. Another aspect of practical SVM problems is often the huge size of the data set, which poses severe challenges both for software package development and for control of ill-conditioning. We illustrate some of these issues with numerical experiments on a range of problems.Keywords
This publication has 44 references indexed in Scilit:
- Training a Support Vector Machine in the PrimalNeural Computation, 2007
- A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programmingMathematical Programming, 2004
- Best Choices for Regularization Parameters in Learning Theory: On the Bias—Variance ProblemMathematische Annalen, 2002
- Asymptotic convergence of an SMO algorithm without any assumptionsIEEE Transactions on Neural Networks, 2002
- On the mathematical foundations of learningBulletin of the American Mathematical Society, 2001
- Improvements to Platt's SMO Algorithm for SVM Classifier DesignNeural Computation, 2001
- 10.1162/15324430152748218Applied Physics Letters, 2000
- 10.1162/15324430260185619Applied Physics Letters, 2000
- 10.1162/15324430152733142Applied Physics Letters, 2000
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998