FoCM 2014 conference
Workshop B3 - Continuous Optimization
No date set
Nearest Neighbors Methods for Support Vector Machines
Sergio Camelo Gómez
Universidad de los Andes, Colombia - sa.camelo38@uniandes.edu.co
A key issue in the practical applicability of the Support Vector Machine methodology is the identification of the support vectors in very large data sets. In this article we propose methods based on sampling and nearest neighbours that allow for an efficient implementation of an approximate solution to the classification problem. The main idea will be that under some conditions, the support vectors of the SVM problem are, with high probability, k-neighbours of the support vectors of a random subsample from the original data. This means that if a random subsample is expanded repeatedly with the k-neighbours of its support vectors, updating the support vectors at each iteration, an approximate solution of the complete data set can be obtained at low cost. We prove some theoretical results that motivate the methodology and evaluate the performance of the proposed method with different examples.
Joint work with María González-Lima (Universidad Simón Bolivar, Venezuela) and Adolfo Quiroz (Universidad de los Andes, Colombia).