NESVM: A fast gradient method for support vector machines

DSpace/Manakin Repository

Search OPUS


Advanced Search

Browse

My Account

Show simple item record

dc.contributor.author Zhou, T
dc.contributor.author Tao, D
dc.contributor.author Wu, X
dc.date.accessioned 2012-02-02T11:07:33Z
dc.date.issued 2010
dc.identifier.citation Proceedings - IEEE International Conference on Data Mining, ICDM, 2010, pp. 679 - 688
dc.identifier.isbn 9780769542560
dc.identifier.issn 1550-4786
dc.identifier.other E1 en_US
dc.identifier.uri http://hdl.handle.net/10453/16196
dc.description.abstract Support vector machines (SVMs) are invaluable tools for many practical applications in artificial intelligence, e.g., classification and event recognition. However, popular SVM solvers are not sufficiently efficient for applications with a great deal of samples as well as a large number of features. In this paper, thus, we present NESVM, a fast gradient SVM solver that can optimize various SVM models, e.g., classical SVM, linear programming SVM and least square SVM. Compared against SVM-Perf [1][2] (whose convergence rate in solving the dual SVM is upper bounded by O(1/√k) where k is the number of iterations) and Pegasos [3] (online SVM that converges at rate O(1/k) for the primal SVM), NESVM achieves the optimal convergence rate at O(1/k2) and a linear time complexity. In particular, NESVM smoothes the non-differentiable hinge loss and ℓ1-norm in the primal SVM. Then the optimal gradient method without any line search is adopted to solve the optimization. In each iteration round, the current gradient and historical gradients are combined to determine the descent direction, while the Lipschitz constant determines the step size. Only two matrix-vector multiplications are required in each iteration round. Therefore, NESVM is more efficient than existing SVM solvers. In addition, NESVM is available for both linear and nonlinear kernels. We also propose "homotopy NESVM" to accelerate NESVM by dynamically decreasing the smooth parameter and using the continuation method. Our experiments on census income categorization, indoor/outdoor scene classification event recognition and scene recognition suggest the efficiency and the effectiveness of NESVM. The MATLAB code of NESVM will be available on our website for further assessment. © 2010 IEEE.
dc.relation.isbasedon 10.1109/ICDM.2010.135
dc.title NESVM: A fast gradient method for support vector machines
dc.type Conference Proceeding
dc.parent Proceedings - IEEE International Conference on Data Mining, ICDM
dc.journal.number en_US
dc.publocation USA en_US
dc.identifier.startpage 679 en_US
dc.identifier.endpage 688 en_US
dc.cauo.name FEIT.Faculty of Engineering & Information Technology en_US
dc.conference Verified OK en_US
dc.for 080109 Pattern Recognition and Data Mining
dc.personcode 100507
dc.personcode 111502
dc.percentage 100 en_US
dc.classification.name Pattern Recognition and Data Mining en_US
dc.classification.type FOR-08 en_US
dc.edition en_US
dc.custom IEEE International Conference on Data Mining en_US
dc.date.activity 20101213 en_US
dc.location.activity Sydney, Australia en_US
dc.description.keywords Support vector machines, smooth, hinge loss, $\ell_1$ norm, Nesterov's method, continuation method en_US
dc.description.keywords ℓ1 norm
dc.description.keywords Continuation method
dc.description.keywords Hinge loss
dc.description.keywords Nesterov's method
dc.description.keywords Smooth
dc.description.keywords Support vector machines
dc.description.keywords ℓ1 norm
dc.description.keywords Continuation method
dc.description.keywords Hinge loss
dc.description.keywords Nesterov's method
dc.description.keywords Smooth
dc.description.keywords Support vector machines
pubs.embargo.period Not known
pubs.organisational-group /University of Technology Sydney
pubs.organisational-group /University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group /University of Technology Sydney/Strength - Quantum Computation and Intelligent Systems


Files in this item

This item appears in the following Collection(s)

Show simple item record