Exploiting separability in large-scale Support Vector Machine training

Kristian Woodsend(k.j.woodsendsms.ed.ac.uk)
Jacek Gondzio(J.Gondzioed.ac.uk)

Abstract: Support vector machine training can be represented as a large quadratic program. We present an efficient and numerically stable algorithm for this problem using interior point methods, which requires only O(n) operations per iteration. Through exploiting the separability of the Hessian, we provide a unified approach, from an optimization perspective, to 1-norm classification, 2-norm classification and epsilon-insensitive regression. Numerical experiments indicate that, in contrast to existing decomposition methods, the algorithm is largely unaffected by noisy data, for both linear and non-linear kernels, and they show our implementation outperforming all known implementations by a large margin. We discuss the effect of using multiple correctors, and monitoring the angle of the normal to the hyperplane to determine termination.

Keywords: Support Vector Machines, Interior Point Method, Separable QP, Low-rank Approximation, Cholesky Factorization

Category 1: Applications -- Science and Engineering (Data-Mining )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Technical Report MS-07-002 School of Mathematics, University of Edinburgh The Kings Buildings, Edinburgh, EH9 3JZ, UK August 7, 2007

Download: [PDF]

Entry Submitted: 08/08/2007
Entry Accepted: 08/08/2007
Entry Last Modified: 08/08/2007

Modify/Update this entry