Development of Support Vector Machines in Graphics Processing Units for Pattern Recognition
Authors
Abstract
Machine learning aims to develop algorithms which extract relevant (and meaningful) information from existing data. Or even more exciting would be extraction of the fundamental laws that not only govern all learning processes but as the universe itself. Naturally, this appears to be a complicated task as the more advanced the algorithms are, the heavier requirements are needed from currently available hardware.Thus, current single-threaded algorithms are often unable to scale with the demanding processing power needed. Among the supervised learning algorithms, SVM are the most widely used algorithm due to their generalization properties and regularization capability. SVM are binary large margin classifiers which have found successful applications in many scientific fields such as engineering, bio-informatics, information management, finance, business among many others.
The SVM aims to find the optimal decision hyperplane which is equivalent to reach both the smallest generalization and empirical errors. By making use of the Kernel trick, the SVM shows powerful classification and regression performance in complex non-linear problems. Thus, functions which obey Mercer's theorem transform the input vectors into a highly-dimensional space and by learning a linear model in this feature space.
An important and crucial point in the SVM formulation is that it can provide a good generalization independent of the training set's distribution by using the principle of structural risk minimization.
However, they usually require significant memory and computational burden for calculating the large Gram matrix. To circumvent this limitation fast learning methods have been proposed. Nevertheless most implementations still do no take advantage of either the multi-core architecture of today CPU nor the more powerful GPU.
In this work we focus on a GPU SVM classifier, developed from a previous studied Multi-Threaded parallel CPU standalone SVM version (MT-SVM) which builds up from the scratch an implementation of the Sequential Minimal Optimization (SMO) algorithm.
Although previous approaches have been developed, our implementation includes a new kernel function, the Universal Kernel Function (UKF) which leads to a broad spectrum of the generalization capabilities of the learning machine. Experiments performed on UCI datasets benchmarks yield performance competitive results as compared to state-of-the-art LIBSVM tools while delivering better speedups on large datasets.
Finally, we used our GPU implementation to study a real case problem which consists of offline signature recognition. This is a difficult problem arising in many practical applications. The results achieved for the task of detecting forged signatures are promising although more research is needed because original and faked signatures can be extremely similar. We obtained excellent results on the identification of an individual's signature despite the fact that a generic classifier configuration is complicated to achieve. Future objectives will aim to improve the multi-class learning architecture used in the process of signature identification.