PADIS

Pubblicazioni Aperte DIgitali Sapienza > Scienze statistiche > RICERCA OPERATIVA >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10805/2188

Title: DECOMPOSITION ALGORITHMS FOR SVM TRAINING BASED ON THE FRANK-WOLFE METHOD
Authors: MORELLI, GIANLUCA
Tutor: Liuzzi, Giampaolo
Keywords: Support Vector Machines
Frank-Wolfe method
optimization problem with one constraint
Issue Date: 18-Nov-2013
Abstract: This work deals with the Support Vector Machine (SVM) learning process which, as it is well-known, can be reduced to the solution of a quadratic problem in the so-called feature space. For very large datasets there are practical issues in the solution of this optimization problem. In particular it may be impossible to store in memory the Hessian of the quadratic form. Decomposition methods, such as the Sequential Minimal Optimization (SMO) method, overcome this limit by operating with small working sets of indices. While SMO methods use working sets of size two, we study SVM learning techniques with high-dimensional working sets. At every step of the training algorithm, we select a working set of cardinality possibly greater than two and we compute a descent direction, in the working set, by defining a Frank-Wolfe type linear sub-problem. We show that the latter sub-problem can be solved analytically and propose a fast procedure for this purpose, the calculation of the solution require only O(n log(n)) operations in the worst case. Two different SVM training algorithms are proposed along this line and an extensive numerical experimentation is carried out. Numerical results show that datasets such that the training algorithm does not take advantage of second order information, can be trained efficiently with first order information algorithms which use high-dimensional working set
URI: http://hdl.handle.net/10805/2188
Appears in PhD:RICERCA OPERATIVA

Files in This Item:

File Description SizeFormat
PhD_Gianluca_Morelli.pdfPhD Thesis of Gianluca Morelli799.1 kBAdobe PDF


This item is protected by original copyright

Recommend this item

Items in PADIS are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback Sviluppo e manutenzione a cura del CINECA