Concept boundary detection for speeding up SVMs

ABSTRACT

Support Vector Machines (SVMs) suffer from an O(n²) training cost, where n denotes the number of training instances. In this paper, we propose an algorithm to select boundary instances as training data to substantially reduce n. Our proposed algorithm is motivated by the result of (Burges, 1999) that, removing non-support vectors from the training set does not change SVM training results. Our algorithm eliminates instances that are likely to be non-support vectors. In the concept-independent preprocessing step of our algorithm, we prepare nearest-neighbor lists for training instances. In the concept-specific sampling step, we can then effectively select useful training data for each target concept. Empirical studies show our algorithm to be effective in reducing n, outperforming other competing downsampling algorithms without significantly compromising testing accuracy.

REFERENCES

• 1: Achlioptas, D., McSherry, F., & Schöölkopf, B. (2002). Sampling techniques for kernel methods. Advances in Neural Information Proc. Systems.
• 2: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 3: Christopher J. C. Burges, Geometry and invariance in kernel based methods, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 4: Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/cjlin/libsvm.
• 5: Shai Fine , Katya Scheinberg, Efficient svm training using low-rank kernel representations, The Journal of Machine Learning Research, 2, 3/1/2002
• 6: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 7: Graf, H. P., Cosatto, E., Bottou, L., Dourdanovic, I., & Vapnik, V. (2005). Parallel support vector machines: The cascade svm. In L. K. Saul, Y. Weiss and L. Bottou (Eds.), Advances in neural information processing systems 17, 521--528. MIT Press.
• 8: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 9: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 10: Lawrence, N. D., Seeger, M., & Herbrich, R. (2003). Fast sparse gaussian process methods: the informative vector machine. S. Becker, S. Thrun and K. Obermayer (eds) Advances in Neural Information Processing Systems. MIT Press.
• 11: LeCun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86, 2278--2324.
• 12: Liu, T., Moore, A. W., Gray, A., & Yang, K. (2005). An investigation of practical approximate nearest neighbor algorithms. In L. K. Saul, Y. Weiss and L. Bottou (Eds.), Advances in neural information processing systems 17, 825--832. Cambridge, MA: MIT Press.
• 13: Osuna, E., Freund, R., & Girosi, F. (1997). An improved training algorithm for support vector machines. IEEE Workshop on Neural Networks for Signal Processing.
• 14: Dmitry Pavlov , Darya Chudova , Padhraic Smyth, Towards scalable support vector machines using squashing, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.295-299, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347155]
• 15: Platt, J. (1998). Sequential minimal optimization: A fast algorithm for training support vector machines (Technical Report). Microsoft Research.
• 16: Alex J. Smola , Bernhard Schökopf, Sparse Greedy Matrix Approximation for Machine Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.911-918, June 29-July 02, 2000
• 17: Volker Tresp, Scaling Kernel-Based Systems to Large Data Sets, Data Mining and Knowledge Discovery, v.5 n.3, p.197-211, July 2001 [doi>10.1023/A:1011425201219]
• 18: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 19: Hwanjo Yu , Jiong Yang , Jiawei Han, Classifying large data sets using SVMs with hierarchical clusters, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956786]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Neural nets

General Terms:
Theory