Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Recent developments in programmable, highly parallel Graphics Processing Units (GPUs) have enabled high performance implementations of machine learning algorithms. We describe a solver for Support Vector Machine training running on a GPU, using the Sequential Minimal Optimization algorithm and an adaptive first and second order working set selection heuristic, which achieves speedups of 9-35x over LIBSVM running on a traditional processor. We also present a GPU-based system for SVM classification which achieves speedups of 81-138x over LIBSVM (5-24x over our own CPU based SVM classifier).

REFERENCES

• 1: Asanović, K., Bodik, R., Catanzaro, B. C., Gebis, J. J., Husbands, P., Keutzer, K., Patterson, D. A., Plishker, W. L., Shalf, J., Williams, S. W., & Yelick, K. A. (2006). The Landscape of Parallel Computing Research: A View from Berkeley (Technical Report UCB/EECS-2006-183). EECS Department, University of California, Berkeley.
• 2: Asuncion, A., & Newman, D. (2007). UCI machine learning repository.
• 3: Léon Bottou , Olivier Chapelle , Dennis DeCoste , Jason Weston, Large-Scale Kernel Machines (Neural Information Processing), The MIT Press, 2007
• 4: Cao, L., Keerthi, S., Ong, C.-J., Zhang, J., Periyathamby, U., Fu, X. J., & Lee, H. (2006). Parallel sequential minimal optimization for the training of support vector machines. IEEE Transactions on Neural Networks, 17, 1039--1049.
• 5: Chu, C.-T., Kim, S. K., Lin, Y.-A., Yu, Y., Bradski, G., Ng, A. Y., & Olukotun, K. (2007). Map-reduce for machine learning on multicore. In B. Schöölkopf, J. Platt and T. Hoffman (Eds.), Advances in neural information processing systems 19, 281--288. Cambridge, MA: MIT Press.
• 6: Ronan Collobert , Samy Bengio , Yoshua Bengio, A parallel mixture of SVMs for very large scale problems, Neural Computation, v.14 n.5, p.1105-1114, May 2002 [doi>10.1162/089976602753633402]
• 7: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 8: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 9: Rong-En Fan , Pai-Hsuen Chen , Chih-Jen Lin, Working Set Selection Using Second Order Information for Training Support Vector Machines, The Journal of Machine Learning Research, 6, p.1889-1918, 12/1/2005
• 10: Ferreira, L. V., Kaskurewicz, E., & Bhaya, A. (2006). Parallel implementation of gradient-based neural networks for svm training. International Joint Conference on Neural Networks.
• 11: 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. Cambridge, MA: MIT Press.
• 12: J. J. Hull, A Database for Handwritten Text Recognition Research, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.550-554, May 1994 [doi>10.1109/34.291440]
• 13: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 14: S. S. Keerthi , S. K. Shevade , C. Bhattacharyya , K. R. K. Murthy, Improvements to Platt's SMO Algorithm for SVM Classifier Design, Neural Computation, v.13 n.3, p.637-649, March 2001 [doi>10.1162/089976601300014493]
• 15: LeCun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86, 2278--2324.
• 16: Nvidia (2007). Nvidia CUDA. http://nvidia.com/cuda.
• 17: Osuna, E., Freund, R., & Girosi, F. (1997). An improved training algorithm for support vector machines. Neural Networks for Signal Processing {1997} VII. Proceedings of the 1997 IEEE Workshop, 276--285.
• 18: 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
• 19: Henry A. Rowley , Shumeet Baluja , Takeo Kanade, Neural Network-Based Face Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.1, p.23-38, January 1998 [doi>10.1109/34.655647]
• 20: Gang Wu , Edward Chang , Yen Kuang Chen , Christoper Hughes, Incremental approximate matrix factorization for speeding up support vector machines, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150500]
• 21: Luca Zanni , Thomas Serafini , Gaetano Zanghirati, Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems, The Journal of Machine Learning Research, 7, p.1467-1492, 12/1/2006

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Theory