Linear Programming Support Vector Machines for Pattern Classification and Regression Estimation: and The SR Algorithm: Improving Speed and Tightness of VC Bounds in SV Algorithms
Thilo-Thomas Friel, Robert F. Harrison · White Rose Research Online (University of Leeds, The University of Sheffield, University of York) · 1998
Three novel algorithms are presented; the linear programming (LP) machine for pattern classification, the LP machine for regression estimation and the set-reduction (SR) algorithm. The LP machine is a learning machine which achieves solutions as good as the SV machine by only maximising a linear cost-function (SV machine are based on quadratic programming). The set-reduction algorithm improves the speed and accuracy of LP machines, SV machines and other related algorithms. An LP machines's decisions are optimal in the sense that it implements Vapnick's (Vapnick and Chervonekis in 1979, Vapnick 1995) structural risk minimisation (SRM) principle. The LP machine has a number of attractive and interesting properties like a high generalisation ability, fast learning based on linear optimisation, capacity control, and a self organisation property. The SR algorithm is an efficient method to improve speed in a LP machine, SV machine and related algorithms, VC bounds are known to be loose bounds. The SR algorithm allows to construct optimal support vector machines by determining the necessary and sufficient number of support patterns. The algorithm does also give tighter VC bounds (for bounds of which are a function of the number of support patterns)