TY - GEN

T1 - A PAC bound for approximate support vector machines

AU - Cao, Dongwei

AU - Boley, Daniel

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - Algorithmic stability

KW - Approximate solutions

KW - Generalization bounds

KW - Support vector machines

UR - http://www.scopus.com/inward/record.url?scp=70449115429&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449115429&partnerID=8YFLogxK

U2 - 10.1137/1.9781611972771.44

DO - 10.1137/1.9781611972771.44

M3 - Conference contribution

AN - SCOPUS:70449115429

SN - 9780898716306

T3 - Proceedings of the 7th SIAM International Conference on Data Mining

SP - 455

EP - 460

BT - Proceedings of the 7th SIAM International Conference on Data Mining

PB - Society for Industrial and Applied Mathematics Publications

T2 - 7th SIAM International Conference on Data Mining

Y2 - 26 April 2007 through 28 April 2007

ER -