×

An iterative algorithm learning the maximal margin classifier. (English) Zbl 1045.68115

Summary: A simple learning algorithm for maximal margin classifiers (also support vector machines with quadratic cost function) is proposed. We build our iterative algorithm on top of the Schlesinger-Kozinec algorithm (S-K-algorithm) from 1981 which finds a maximal margin hyperplane with a given precision for separable data. We suggest a generalization of the S-K-algorithm (i) to the non-linear case using kernel functions and (ii) for non-separable data. The requirement in memory storage is linear to the data. This property allows the proposed algorithm to be used for large training problems.
The resulting algorithm is simple to implement and as the experiments showed competitive to the state-of-the-art algorithms. The implementation of the algorithm in Matlab is available. We tested the algorithm on the problem aiming at recognition poor quality numerals.

MSC:

68T10 Pattern recognition, speech recognition
68T05 Learning and adaptive systems in artificial intelligence

Software:

SVMlight; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Vapnik, V. N.; Chervonenkis, A. Ya., The Theory of Pattern Recognition (1974), Nauka: Nauka Moscow · Zbl 0284.68070
[2] Vapnik, V. N., The Nature of Statistical Learning Theory (1995), Springer: Springer Berlin · Zbl 0934.62009
[3] Schlesinger, M. I.; Kalmykov, V. G.; Suchorukov, A. A., Sravnitelnyj analiz algoritmov sinteza linejnogo reshajushchego pravila dlja proverki slozhnych gipotez, Automatika, 1, 3-9 (1981), (in Russian)
[4] Kozinec, B. N., Rekurentnyj algoritm razdelenia vypuklych obolochek dvuch mnozhestv, (Vapnik, V. N., Algoritmy Obuchenia Raspoznavania (Learning algorithms in pattern recognition) (1973), Sovetskoje radio: Sovetskoje radio Moskva), 43-50, (in Russian)
[5] Schlesinger, M. I.; Hlaváč, V., Ten Lectures on Statistical and Structural Pattern Recognition (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1087.62505
[6] Aizerman, M. A.; Braverman, E. M.; Rozoner, L. I., Theoretical foundations of the potential function method in pattern recognition learning, Autom. Remote Control, 25, 821-837 (1964) · Zbl 0151.24701
[7] Platt, J. C., Fast training of support vectors machines using sequential minimal optimization, (Scholkopf, B.; Burges, C. J.C.; Smola, A. J., Advances in Kernel Methods (1998), MIT Press: MIT Press Cambridge, MA, USA)
[8] T. Joachims, Advances in Kernel methods—support vector learning, in: B. Schlkopf, C. Burges, A. Smola (Eds.), Chapter Making Large-Scale Support Vector Machine Learning Practical, MIT Press, Cambridge, MA, 1999, pp. 169-184. Code downloadable from http://svmlight.joachims.org/; T. Joachims, Advances in Kernel methods—support vector learning, in: B. Schlkopf, C. Burges, A. Smola (Eds.), Chapter Making Large-Scale Support Vector Machine Learning Practical, MIT Press, Cambridge, MA, 1999, pp. 169-184. Code downloadable from http://svmlight.joachims.org/
[9] Yi Li, P.M. Long, The relaxed online maximum margin algorithm, in: S.A. Solla, T.K. Leen, K.R. Muller (Eds.), Advances in Neural Information Processing Systems, Vol. 12, MIT Press, Cambridge, MA, USA, 2000, pp. 498-504.; Yi Li, P.M. Long, The relaxed online maximum margin algorithm, in: S.A. Solla, T.K. Leen, K.R. Muller (Eds.), Advances in Neural Information Processing Systems, Vol. 12, MIT Press, Cambridge, MA, USA, 2000, pp. 498-504.
[10] Keerthi, S. S.; Shevade, S. K.; Bhattacharyya, C.; Murthy, K. R.K., A fast iterative nearest point algorithm for support vector machine classifier design, IEEE Trans. Neural Networks, 11, 1, 124-136 (2000)
[11] T.T. Friess, R. Harrison, Support vector neural networks: the Kernel Adatron with bias and soft-margin, Technical Report 725, University of Sheffield, UK, 1998.; T.T. Friess, R. Harrison, Support vector neural networks: the Kernel Adatron with bias and soft-margin, Technical Report 725, University of Sheffield, UK, 1998.
[12] Kowalczyk, A., Advances in large margin classifiers, (Smola, A. J.; Bartlett, P. J.; Schõlkopf, B.; Schuurmans, D., Chapter, Maximal Margin Perceptron (1999), MIT Press: MIT Press Cambridge, MA)
[13] A. Novikoff, On convergence proofs for perceptrons, in: Proceeding of the Symposium on the Mathematical Theory of Automata, Polytechnic Institute of Brooklyn Vol. 12, 1963, pp. 615-622.; A. Novikoff, On convergence proofs for perceptrons, in: Proceeding of the Symposium on the Mathematical Theory of Automata, Polytechnic Institute of Brooklyn Vol. 12, 1963, pp. 615-622. · Zbl 0116.34103
[14] Gilbert, E. G., Minimizing the quadratic form on a convex set, SIAM J. Control, 4, 61-79 (1966) · Zbl 0196.51204
[15] Mitchell, B. F.; Demyanov, V. F.; Malozemov, V. N., Finding the point of a polyhedron closest to the origin, SIAM J. Control, 12, 19-26 (1974) · Zbl 0277.52007
[16] Ripley, B. D., Neural networks and related methods for classification, J. R. Statist. Soc. Ser. B, 56, 409-456 (1994), (with discussion) · Zbl 0815.62037
[17] UCI-benchmark repository of artificial and real data sets, University of California Irvine, http://www.ics.uci.edu/ mlearn; UCI-benchmark repository of artificial and real data sets, University of California Irvine, http://www.ics.uci.edu/ mlearn
[18] Kresel, U., Advances in Kernel methods-support vector learning, (Schõlkopf, B.; Burges, C.; Smola, A., Chapter Pairwise classification and support vector machines (1999), MIT Press: MIT Press Cambridge, MA), 255-268
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.