Optimization Online


An Improved Algorithm for the Solution of the Entire Regulation Path of Support Vector Machine

C.J. Ong(mpeongcj***at***nus.edu.sg)
Shiyun Shao(g0600248***at***nus.edu.sg)
Jianbo Yang(g0600283***at***nus.edu.sg)

Abstract: This paper describes an improved algorithm for the numerical solution to the Support Vector Machine (SVM) classification problem for all values of the regularization parameter, C. The algorithm is motivated by the work of Hastie \emph{et. al.} and follows the main idea of tracking the optimality conditions of the SVM solution for descending value of C. It differs from Hastie's approach in that the tracked path is not assumed to be one-dimensional. Instead, a multi-dimensional feasible space for the optimality condition is used to solve the tracking problem. Such a treatment allows the algorithm to handle data set having duplicate points, nearly duplicate points and linearly dependent points, a common feature among many real-world data sets. Other contributions of this paper include a unifying formulation of the tracking process in the form of a linear program, an initialization routine that deals with duplicate data points, a routine that guards against accumulation of errors resulting from the use of incremental updates, a heuristics-based routine and update formula to speed up the algorithm. The algorithm is implemented under the Matlab environment and tested with several data sets including data set having up to several thousand data points.

Keywords: Support Vector Machine, numerical solutions of SVM, regulation

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

Citation: Technical Report C09-002, Department of Mechanical Engineering.

Download: [PDF]

Entry Submitted: 04/21/2009
Entry Accepted: 04/21/2009
Entry Last Modified: 04/21/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society