A PAC bound for approximate support vector machines

Dongwei Cao, Daniel Boley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We study a class of algorithms that speed up the training process of support vector machines (SVMs) by returning an approximate SVM. We focus on algorithms that reduce the size of the optimization problem by extracting from the original training dataset a small number of representatives arid using these representatives to train an approximate SVM. The main contribution of this paper is a PAC-style generalization bound for the resulting approximate SVM, which provides a learning theoretic justification for using the approximate SVM in practice. The proved bound also generalizes and includes as a special case the generalization bound for the exact SVM, which denotes the SVM given by the original training dataset in this paper.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th SIAM International Conference on Data Mining
PublisherSociety for Industrial and Applied Mathematics Publications
Pages455-460
Number of pages6
ISBN (Print)9780898716306
DOIs
StatePublished - 2007
Event7th SIAM International Conference on Data Mining - Minneapolis, MN, United States
Duration: Apr 26 2007Apr 28 2007

Publication series

NameProceedings of the 7th SIAM International Conference on Data Mining

Other

Other7th SIAM International Conference on Data Mining
CountryUnited States
CityMinneapolis, MN
Period4/26/074/28/07

Keywords

  • Algorithmic stability
  • Approximate solutions
  • Generalization bounds
  • Support vector machines

Fingerprint Dive into the research topics of 'A PAC bound for approximate support vector machines'. Together they form a unique fingerprint.

Cite this