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 -