Finding Potential Support Vectors in Separable Classification Problems
2013 (English)In: IEEE Transactions on Neural Networks and Learning Systems, ISSN 2162-237X, Vol. 24, no 11, 1799-1813 p.Article in journal (Refereed) Published
This paper considers the classification problem using support vector (SV) machines and investigates how to maximally reduce the size of the training set without losing information. Under separable data set assumptions, we derive the exact conditions stating which observations can be discarded without diminishing the overall information content. For this purpose, we introduce the concept of potential SVs, i.e., those data that can become SVs when future data become available. To complement this, we also characterize the set of discardable vectors (DVs), i.e., those data that, given the current data set, can never become SVs. Thus, these vectors are useless for future training purposes and can eventually be removed without loss of information. Then, we provide an efficient algorithm based on linear programming that returns the potential and DVs by constructing a simplex tableau. Finally, we compare it with alternative algorithms available in the literature on some synthetic data as well as on data sets from standard repositories.
Place, publisher, year, edition, pages
2013. Vol. 24, no 11, 1799-1813 p.
Data discardability conditions, discardable vectors, linear programming, potential support vectors, separable data sets, support vector machines
Computer Science Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-133962DOI: 10.1109/TNNLS.2013.2264731ISI: 000325981800008ScopusID: 2-s2.0-84886946220OAI: oai:DiVA.org:kth-133962DiVA: diva2:664448
FunderEU, FP7, Seventh Framework Programme, 257462 HYCON2VinnovaKnut and Alice Wallenberg Foundation
QC 201311152013-11-152013-11-142013-11-15Bibliographically approved