Training Support Vector Machines Using Frank-Wolfe Optimization Methods
| Autor: | Maria Grazia Gasparo, Ricardo Ñanculef, Emanuele Frandi, Stefano Lodi, Claudio Sartori |
|---|---|
| Přispěvatelé: | E. FRANDI, R. ÑANCULEF, M. G. GASPARO, S. LODI, C. SARTORI |
| Rok vydání: | 2012 |
| Předmět: |
FOS: Computer and information sciences
Computational complexity theory Computer science Feature vector Computer Vision and Pattern Recognition (cs.CV) MINIMAL ENCLOSING BALLS Computer Science - Computer Vision and Pattern Recognition Machine Learning (stat.ML) KERNEL METHODS Machine Learning (cs.LG) Statistics - Machine Learning Artificial Intelligence FOS: Mathematics Quadratic programming Ball (mathematics) Mathematics - Optimization and Control business.industry LARGE SCALE PROBLEMS Support vector machine SUPPORT VECTOR MACHINES CORE VECTOR MACHINES Computer Science - Learning FRANK-WOLFE OPTIMIZATION Kernel method Binary classification Optimization and Control (math.OC) Kernel (statistics) Computer Vision and Pattern Recognition Artificial intelligence business Algorithm Software |
| DOI: | 10.48550/arxiv.1212.0695 |
| Popis: | Training a support vector machine (SVM) requires the solution of a quadratic programming problem (QP) whose computational complexity becomes prohibitively expensive for large scale datasets. Traditional optimization methods cannot be directly applied in these cases, mainly due to memory restrictions. By adopting a slightly different objective function and under mild conditions on the kernel used within the model, efficient algorithms to train SVMs have been devised under the name of core vector machines (CVMs). This framework exploits the equivalence of the resulting learning problem with the task of building a minimal enclosing ball (MEB) problem in a feature space, where data is implicitly embedded by a kernel function. In this paper, we improve on the CVM approach by proposing two novel methods to build SVMs based on the Frank–Wolfe algorithm, recently revisited as a fast method to approximate the solution of a MEB problem. In contrast to CVMs, our algorithms do not require to compute the solutions of a sequence of increasingly complex QPs and are defined by using only analytic optimization steps. Experiments on a large collection of datasets show that our methods scale better than CVMs in most cases, sometimes at the price of a slightly lower accuracy. As CVMs, the proposed methods can be easily extended to machine learning problems other than binary classification. However, effective classifiers are also obtained using kernels which do not satisfy the condition required by CVMs, and thus our methods can be used for a wider set of problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|