Building support vector machines with reduced classifier complexity. (English) Zbl 1222.68230

Keerthi, S. Sathiya; Chapelle, Olivier; Decoste, Dennis

J. Mach. Learn. Res. 7, 1493-1515 (2006).

Summary: Support vector machines (SVMs), though accurate, are not preferred in applications requiring great classification speed, due to the number of support vectors being large. To overcome this problem we devise a primal method with the following properties: (1) it decouples the idea of basis functions from the concept of support vectors; (2) it greedily finds a set of kernel basis functions of a specified maximum size \((d_{\text{max}})\) to approximate the SVM primal cost function well; (3) it is efficient and roughly scales as \(O(nd_{\text{max}}^{2})\) where \(n\) is the number of training examples; and, (4) the number of basis functions it requires to achieve an accuracy close to the SVM accuracy is usually far less than the number of SVM support vectors.

MSC:

68T05	Learning and adaptive systems in artificial intelligence
62H30	Classification and discrimination; cluster analysis (statistical aspects)

Keywords:

SVMs; classification; sparse design

Software:

SVMlight