Change search
ReferencesLink to record
Permanent link

Direct link
Finding Potential Support Vectors in Separable Classification Problems
KTH, School of Electrical Engineering (EES), Automatic Control.
Show others and affiliations
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
Abstract [en]

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.
Keyword [en]
Data discardability conditions, discardable vectors, linear programming, potential support vectors, separable data sets, support vector machines
National Category
Computer Science Electrical Engineering, Electronic Engineering, Information Engineering
URN: urn:nbn:se:kth:diva-133962DOI: 10.1109/TNNLS.2013.2264731ISI: 000325981800008ScopusID: 2-s2.0-84886946220OAI: diva2:664448
EU, FP7, Seventh Framework Programme, 257462 HYCON2VinnovaKnut and Alice Wallenberg Foundation

QC 20131115

Available from: 2013-11-15 Created: 2013-11-14 Last updated: 2013-11-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Varagnolo, Damiano
By organisation
Automatic Control
Computer ScienceElectrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 23 hits
ReferencesLink to record
Permanent link

Direct link