Home

Conic SMO

Ilia Vovsha

Title:
Conic SMO
Author(s):
Vovsha, Ilia
Date:
Type:
Technical reports
Department:
Center for Computational Learning Systems
Permanent URL:
Series:
CCLS Technical Report
Part Number:
CCLS-11-03
Publisher:
Center for Computational Learning Systems, Columbia University
Publisher Location:
New York
Abstract:
We derive an SMO-like algorithm for the optimization problem arising from the Second Order Cone Programming formulation of support vector machines (SVMs) for classification. Due to the square root term in the objective of the form, we cannot easily compute the location of the extrema using Newton’s formula. Instead we modify the analytic solution proposed for SMO (Platt, 1999), to account for the particular objective function and partial derivatives. We then establish some theoretical properties of the algorithm based on the results of (Bordes et al., 2005), and develop practical working set selection similar to (Fan et al., 2005). In addition, we propose an efficient implementation, and compare the convergence rate of Conic-SMO and SMO on synthetic data.
Subject(s):
Computer science
Item views:
164
Metadata:
View

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services.