We propose a refined gradient ascent method including heuristic parameters for solving the dual problem of nonlinear SVM. Aiming to get better tuning to the particular training sequence, the proposed refinement consists of the use of heuristically established weights in correcting the search direction at each step of the learning algorithm that evolves in the feature space. We propose three variants for computing the correcting weights, their effectiveness being analyzed on experimental basis in the final part of the paper. The tests pointed out good convergence properties, and moreover, the proposed modified variants proved higher convergence rates as compared to Platt’s SMO algorithm. The experimental analysis aimed to derive conclusions on the recognition rate as well as on the generalization capacities. The learning phase of the SVM involved linearly separable samples randomly generated from Gaussian repartitions and the WINE and WDBC datasets. The generalization capacities in case of artificial data were evaluated by several tests performed on new linearly/nonlinearly separable data coming from the same classes. The tests pointed out high recognition rates (about 97%) on artificial datasets and even higher recognition rates in case of the WDBC dataset. 1. Introduction According to the theory of SVMs, while traditional techniques for pattern recognition are based on the attempt to optimize the performance in terms of the empirical risk, SVMs minimize the structural risk, that is, the probability of misclassifying yet-to-be-seen patterns for a fixed but unknown probability distribution of data [1–4]. The most distinguished and attractive features of this classification paradigm are the ability to condense the information contained by the training set and the use of families of decision surfaces of the relatively low Vapnik-Chervonenkis dimension. SVM approaches to classification lead to convex optimization problems, typically quadratic problems in a number of variables equal to the number of examples, and these optimization problems become challenging when the number of data points exceeds few thousands. For making SVM more practical, several algorithms have been developed such as Vapnik’s chunking and Osuna’s decompositions [1, 5]. They make the training of SVM possible by breaking the large QP problem into a series of smaller QP problems and optimizing only a subset of training data patterns at each step. Because the subset of training data patterns optimized at each step is called the working set, these approaches are referred to as the working
References
[1]
V. Vapnik, The Nature of Statistical Learning Theory, Springer, New York, NY, USA, 1995.
[2]
V. Vapnik, Statistical Learning Theory, John Wiley & Sons, New York, NY, USA, 1998.
[3]
S. Abe, “Support vector machines for pattern classification,” in Advances in Pattern Recognition, Springer, London, UK, 2010.
[4]
J. Shawe-Taylor and N. Cristianini, Support Vector Machines and Other Kernel-Based Learning Methods, Cambridge University Press, Cambridge, UK, 2000.
[5]
E. Osuna, R. Freund, and F. Girosi, “Improved training algorithm for support vector machines,” in Proceedings of the 7th IEEE Workshop on Neural Networks for Signal Processing (NNSP '97), pp. 276–285, September 1997.
[6]
L. I.-J. Chien, C.-C. Chang, and Y.-J. Lee, “Variant methods of reduced set selection for reduced support vector machines,” Journal of Information Science and Engineering, vol. 26, no. 1, pp. 183–196, 2010.
[7]
Y.-J. Lee and O. L. Mangasarian, “SSVM: a smooth support vector machine for classification,” Computational Optimization and Applications, vol. 20, no. 1, pp. 5–22, 2001.
[8]
L. J. Cao, S. S. Keerthi, C. J. Ong, P. Uvaraj, X. J. Fu, and H. P. Lee, “Developing parallel sequential minimal optimization for fast training support vector machine,” Neurocomputing, vol. 70, no. 1–3, pp. 93–104, 2006.
[9]
G. C. Cawley and N. L. C. Talbot, “Improved sparse least-squares support vector machines,” Neurocomputing, vol. 48, pp. 1025–1031, 2002.
[10]
C.-H. Li, H.-H. Ho, Y.-L. Liu, C.-T. Lin, B.-C. Kuo, and J.-S. Taur, “An automatic method for selecting the parameter of the normalized kernel function to support vector machines,” Journal of Information Science and Engineering, vol. 28, no. 1, pp. 1–15, 2012.
[11]
T. Joachims, “Making large-scale SVM learning practical,” in Advances in Kernel Methods—Support Vector Learning, pp. 41–56, 1998.
[12]
J. A. K. Suykens, J. de Brabanter, L. Lukas, and J. Vandewalle, “Weighted least squares support vector machines: robustness and sparce approximation,” Neurocomputing, vol. 48, pp. 85–105, 2002.
[13]
S. Rueping, “mySVM: another one of those support vector machines,” 2003, http://www-ai.cs.uni-dortmund.de/SOFTWARE/MYSVM.
[14]
E. Alpaydin, Introduction to Machine Learning, MIT Press, Cambridge, Mass, USA, 2004.
[15]
P. Laskov, “Feasible direction decomposition algorithms for training support vector machines,” Machine Learning, vol. 46, no. 1–3, pp. 315–349, 2002.
[16]
S. Shalev-Shwartz, Y. Singer, and N. Srebro, “Pegasos: primal estimated sub-GrAdient sOlver for SVM,” in Proceedings of the 24th International Conference on Machine Learning (ICML '07), pp. 807–814, June 2007.
[17]
V. Yugov and I. Kumazava, “Online boosting algorithm based on two-phase SVM training,” ISRN Signal Processing, vol. 12, 2012.
[18]
L. State, C. Cocianu, and M. Mircea, “Heuristic attempts to improve the generalization capacities in learning SVMs,” in Proceedings of the 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, pp. 108–116, 2012.
[19]
C.-L. Cocianu, L. State, and P. Vlamos, “A new method for learning the support vector machines,” in Proceedings of the 6th International Conference on Software and Database Technologies (ICSOFT '11), pp. 365–370, July 2011.
