
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Implementation Issues of SecondOrder Cone Programming Approaches for Support Vector Machine Learning Problems
Rameswar DEBNATH Masakazu MURAMATSU Haruhisa TAKAHASHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E92A
No.4
pp.12091222 Publication Date: 2009/04/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E92.A.1209 Print ISSN: 09168508 Type of Manuscript: PAPER Category: Neural Networks and Bioengineering Keyword: support vector machine, kernel matrix, secondorder cone programming, HKM search direction, AHO search direction,
Full Text: PDF>>
Summary:
The core of the support vector machine (SVM) problem is a quadratic programming problem with a linear constraint and bounded variables. This problem can be transformed into the second order cone programming (SOCP) problems. An interiorpointmethod (IPM) can be designed for the SOCP problems in terms of storage requirements as well as computational complexity if the kernel matrix has lowrank. If the kernel matrix is not a lowrank matrix, it can be approximated by a lowrank positive semidefinite matrix, which in turn will be fed into the optimizer. In this paper we present two SOCP formulations for each SVM classification and regression problem. There are several search direction methods for implementing SOCPs. Our main goal is to find a better search direction for implementing the SOCP formulations of the SVM problems. Two popular search direction methods: HKM and AHO are tested analytically for the SVM problems, and efficiently implemented. The computational costs of each iteration of the HKM and AHO search direction methods are shown to be the same for the SVM problems. Thus, the training time depends on the number of IPM iterations. Our experimental results show that the HKM method converges faster than the AHO method. We also compare our results with the method proposed in Fine and Scheinberg (2001) that also exploits the lowrank of the kernel matrix, the stateoftheart SVM optimization softwares SVMTorch and SVM^{light}. The proposed methods are also compared with Joachims 'Linear SVM' method on linear kernel.

