Proximal support vector machine classifiers

ABSTRACT

Instead of a standard support vector machine (SVM) that classifies points by assigning them to one of two disjoint half-spaces, points are classified by assigning them to the closest of two parallel planes (in input or feature space) that are pushed apart as far as possible. This formulation, which can also be interpreted as regularized least squares and considered in the much more general context of regularized networks [8, 9], leads to an extremely fast and simple algorithm for generating a linear or nonlinear classifier that merely requires the solution of a single system of linear equations. In contrast, standard SVMs solve a quadratic or a linear program that require considerably longer computational time. Computational results on publicly available datasets indicate that the proposed proximal SVM classifier has comparable test set correctness to that of standard SVM classifiers, but with considerably faster computational time that can be an order of magnitude faster. The linear proximal SVM can easily handle large datasets as indicated by the classification of a 2 million point 10-attribute set in 20.8 seconds. All computational results are based on 6 lines of MATLAB code.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: K. P. Bennett and O. L. Mangasarian. Robust linear programming discrimination of two linearly inseparable sets. Optimization Methods and Software, 1:23-34, 1992.
• 3: P. S. Bradley and O. L. Mangasarian. Massive data discrimination via linear support vector machines. Optimization Methods and Software, 13:1-10, 2000. ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98- 03.ps.
• 4: US Census Bureau. Adult dataset. Publicly available from: www.sgi.com/Technology/mlc/db/.
• 5: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 6: Vladimir S. Cherkassky , Filip Mulier, Learning from Data: Concepts, Theory, and Methods, John Wiley & Sons, Inc., New York, NY, 1998
• 7: CPLEX Optimization Inc., Incline Village, Nevada. Using the CPLEX(TM) Linear Optimizer and CPLEX(TM) Mixed Integer Optimizer (Version 2.0), 1992.
• 8: T. Evgeniou, M. Pontil, and T. Poggio. Regularization networks and support vector machines. Advances in Computational Mathematics, 13:1-50, 2000.
• 9: T. Evgeniou, M. Pontil, and T. Poggio. Regularization networks and support vector machines. In A. Smola, P. Bartlett, B. Sch51kopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 171-203, Cambridge, MA, 2000. MIT Press.
• 10: M. C. Ferris and T. S. Munson. Interior point methods for massive support vector machines. Technical Report 00-05, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, May 2000. ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00-05.ps.
• 11: Glenn Fung , Olvi L. Mangasarian, Data selection for support vector machine classifiers, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.64-70, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347105]
• 12: G. Fung, O. L. Mangasarian, and A. Smola. Minimal kernel classifiers. Technical Report 00-08, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, November 2000. ftp: //ftp.cs, wisc.edu /pub/dmi/tech-reports/ O0-O8.ps.
• 13: D. Gale. The Theory of Linear Economic Models. McGraw-Hill Book Company, New York, 1960.
• 14: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 15: J. Gracke, M. Griebel, and M. Thess. Data mining with sparse grids. Technical report, Institut f/ir Angrwandte Mathematik, Universita~t Bonn, Bonn, Germany, 2000. http://wissrech.iam.unibonn.de/research/projects/garcke/sparsemining.html.
• 16: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 17: Y.-J. Lee and O. L. Mangasarian. RSVM: Reduced support vector machines. Technical Report 00-07, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, July 2000. Proceedings of the First SIAM International Conference on Data Mining, Chicago, April 5-7, 2001, CD-ROM. ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00-07.ps.
• 18: Yuh-Jye Lee , O. L. Mangasarian, SSVM: A Smooth Support Vector Machine for Classification, Computational Optimization and Applications, v.20 n.1, p.5-22, October 2001 [doi>10.1023/A:1011215321374]
• 19: O. L. Mangasarian. Nonlinear Programming. SIAM, Philadelphia, PA, 1994.
• 20: O. L. Mangasarian. Generalized support vector machines. In A. Smola, P. Bartlett, B. SchSlkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 135:146, Cambridge, MA, 2000. MIT Press. ftp://ftp.cs.wisc.edu/math-prog/techreports/98-14.ps.
• 21: O. L. Mangasarian and R. R. Meyer. Nonlinear perturbation of linear programs. SIAM Journal on Control and Optimization, 17(6):745-752, November 1979.
• 22: O. L. Mangasarian and D. R. Musicant. Successive overrelaxation for support vector machines. IEEE Transactions on Neural Networks, 10:1032-1037, 1999. ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98- 18.ps.
• 23: O. L. Mangasarian and D. R. Musicant. Active support vector machine classification. Technical Report 00-04, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, April 2000. Machine Learning, to appear. ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/OO-O4.ps.
• 24: O. L. Mangasarian , David R. Musicant, Lagrangian support vector machines, The Journal of Machine Learning Research, 1, p.161-177, 9/1/2001
• 25: O. L. Mangasarian , T.-H. Shiau, Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems, SIAM Journal on Control and Optimization, v.25 n.3, p.583-595, May 1, 1987 [doi>10.1137/0325033]
• 26: MATLAB. User's Guide. The MathWorks, Inc., Natick, MA 01760, 1994-2001. http://www.mathworks.com.
• 27: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 28: P. M. Murphy and D. W. Aha. UCI repository of machine learning databases, 1992. www.ics.uci.edu/~mlearn/MLRepository.html.
• 29: D. R. Musicant. NDC: normally distributed clustered datasets, 1998. www.cs.wisc.edu/~-.musicant/data/ndc/.
• 30: S. Odewahn, E. Stockwell, R. Pennington, R. Humphreys, and W. Zumach. Automated star/galaxy discrimination with neural networks. Astronomical Journal, 103(1):318-331, 1992.
• 31: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 32: Alexander J. Smola , Peter J. Bartlett, Advances in Large Margin Classifiers, MIT Press, Cambridge, MA, 2000
• 33: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 34: A. N. Tikhonov and V. Y. Arsenin. Solutions of Ill-Posed Problems. John Wiley ~: Sons, New York, 1977.
• 35: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 36: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 37: Alexis Wieland. Twin spiral dataset, http://wwwcgi.cs.cmu.edu/afs/cs.cmu.edu/project/airepository/ai/areas/neural/bench/cmu/0.html.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Theory

Keywords:
data classification, linear equations, support vector machines