Support Vector Machine via Sequential Subspace Optimization

Guy Narkiss (guynsiglab.technion.ac.il)
Michael Zibulevsky (mzibee.technion.ac.il)

Abstract: We present an optimization engine for large scale pattern recognition using Support Vector Machine (SVM). Our treatment is based on conversion of soft-margin SVM constrained optimization problem to an unconstrained form, and solving it using newly developed Sequential Subspace Optimization (SESOP) method. SESOP is a general tool for large-scale smooth unconstrained optimization. At each iteration the method minimizes the objective function over a subspace spanned by the current gradient and by directions of few previous steps and gradients. Following an approach of A. Nemirovski, we also include into the search subspace the direction from the starting point to the current point, and a weighted sum of all previous gradients: this provides the worst case optimality of the method. The subspace optimization can be performed extremely fast in the cases when the objective function is a combination of expensive linear mappings with computationally cheap non-linear functions, like in the unconstrained SVM problem. Presented numerical results demonstrate high e±ciency of the method.

Keywords: Large-scale optimization, pattern recognition, Support Vector Machine, conjugate gradients, subspace optimization

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

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Tech. Report CCIT No 557, EE Dept., Technion, Haifa, Israel, September 2005

Download: [PDF]

Entry Submitted: 09/25/2005
Entry Accepted: 09/25/2005
Entry Last Modified: 09/25/2005

Modify/Update this entry