×

Using an iterative linear solver in an interior-point method for generating support vector machines. (English) Zbl 1208.90184

Summary: This paper concerns the generation of support vector machine classifiers for solving the pattern recognition problem in machine learning. A method is proposed based on interior-point methods for convex quadratic programming. This interior-point method uses a linear preconditioned conjugate gradient method with a novel preconditioner to compute each iteration from the previous. An implementation is developed by adapting the object-oriented package OOQP to the problem structure. Numerical results are provided, and computational experience is discussed.

MSC:

90C51 Interior-point methods
90C20 Quadratic programming
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvira, M., Rifkin, R.: An empirical comparison of snow and svms for face detection. A.I. memo 2001-004, Center for Biological and Computational Learning, MIT, Cambridge, MA (2001)
[2] Anderson, E., Bai, Z., Bischof, C., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Ostrouchov, S., Sorensen, D.: LAPACK User’s Guide. SIAM, Philadelphia (1992) · Zbl 0843.65018
[3] Bach, F.R., Jordan, M.I.: Predictive low-rank decomposition for kernel methods. In: ICML ’05: Proceedings of the 22nd International Conference on Machine Learning, pp. 33–40. ACM Press, New York (2005)
[4] Blackford, L.S., Demmel, J., Dongarra, J., Duff, I., Hammarling, S., Henry, G., Heroux, M., Kaufman, L., Lumsdaine, A., Petitet, A., Pozo, R., Remington, K., Whaley, R.C.: An updated set of basic linear algebra subprograms (BLAS). ACM Trans. Math. Soft. 28, 135–151 (2002) · Zbl 1070.65520 · doi:10.1145/567806.567807
[5] Bottou, L.: LaSVM. http://leon.bottou.org/projects/lasvm/
[6] Burges, C.J.C.: A tutorial on support vector machines for pattern recognition. Data Min. Knowl. Discov. 2, 121–167 (1998) · Zbl 05470543 · doi:10.1023/A:1009715923555
[7] CBCL center for biological & computational learning. http://cbcl.mit.edu/projects/cbcl/
[8] Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines. Cambridge University Press, Cambridge (2000) · Zbl 0994.68074
[9] Dongarra, J.: Basic linear algebra subprograms technical forum standard. Int. J. High Perform. Appl. Supercomput. 16, 1–111 (2002), 115–199 · doi:10.1177/10943420020160010101
[10] Drineas, P., Mahoney, M.W.: On the Nyström method for approximating a gram matrix for improved kernel-based learning. J. Mach. Learn. Res. 6, 2153–2175 (2005) · Zbl 1222.68186
[11] Fan, R.-E., Chen, P.-H., Lin, C.-J.: Working set selection using second order information for training support vector machines. J. Mach. Learn. Res. 6, 1889–1918 (2005) · Zbl 1222.68198
[12] Ferris, M.C., Munson, T.S.: Interior point methods for massive support vector machines. SIAM J. Optim. 13, 783–804 (2003) · Zbl 1039.90092 · doi:10.1137/S1052623400374379
[13] Ferris, M.C., Munson, T.S.: Semismooth support vector machines. Math. Program. 101, 185–204 (2004) · Zbl 1076.90041
[14] Fine, S., Scheinberg, K.: Efficient SVM training using low-rank kernel representations. J. Mach. Learn. Res. 2, 243–264 (2001) · Zbl 1037.68112 · doi:10.1162/15324430260185619
[15] Fletcher, R.: Practical Methods of Optimization. Constrained Optimization, vol. 2. Wiley, New York (1981) · Zbl 0474.65043
[16] Gertz, E.M., Griffin, J.D.: Support vector machine classifiers for large data sets, Technical memo ANL/MCS-TM-289, Argonne National Lab, October 2005
[17] Gertz, E.M., Wright, S.J.: OOQP user guide. Technical Memorandum ANL/MCS-TM-252, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL (2001)
[18] Gertz, E.M., Wright, S.J.: Object oriented software for quadratic programming. ACM Trans. Math. Softw. (TOMS) 29, 49–94 (2003) · Zbl 1070.65501 · doi:10.1145/641876.641879
[19] Gill, P.E., Murray, W., Wright, M.H.: Practical Optimization. Academic, London (1981)
[20] Glasmachers, T., Igel, C.: Maximum-gain working set selection for SVMs. J. Mach. Learn. Res. 7, 1437–1466 (2006) · Zbl 1222.90040
[21] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[22] Hettich, C.B.S., Merz, C.: UCI repository of machine learning databases (1998). http://www.ics.uci.edu/\(\sim\)mlearn/MLRepository.html
[23] In Hyuk Jung, A.L.T., O’Leary, D.P.: A constraint reduced IPM for convex quadratic programming with application to SVM training. In: INFORMS Annual Meeting (2006)
[24] Joachims, T.: Making large-scale support vector machine learning practical. In: Schölkopf, B., Burges, C., Smola, A. (eds.) Advances in Kernel Methods–Support Vector Learning, pp. 169–184. MIT Press, Cambridge (1998)
[25] Keerthi, S., Shevade, S., Bhattacharyya, C., Murthy, K.: Improvements to Platt’s SMO algorithm for SVM classifier design. Neural Comput. 13, 637–649 (2001) · Zbl 1085.68629 · doi:10.1162/089976601300014493
[26] LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86, 2278–2324 (1998) · doi:10.1109/5.726791
[27] Louradour, J., Daoudi, K., Bach, F.: SVM speaker verification using an incomplete Cholesky decomposition sequence kernel. In: IEEE Odyssey 2006: The Speaker and Language Recognition Workshop, IEEE, June 2006
[28] Mangasarian, O.L., Musicant, D.R.: Lagrangian support vector machines. J. Mach. Learn. Res. 1, 161–177 (2001) · Zbl 0997.68108 · doi:10.1162/15324430152748218
[29] Osuna, E., Freund, R., Girosi, F.: Improved training algorithm for support vector machines. In: Proceedings of the IEEE Workshop on Neural Networks for Signal Processing, pp. 276–285. (1997)
[30] Platt, J.: Sequential minimal optimization. http://research.microsoft.com/en-us/projects/svm/default.aspx
[31] Platt, J.: Fast training of support vector machines using sequential minimal optimization. In: Schölkopf, B., Burges, C., Smola, A. (eds.) Advances in Kernel Methods–Support Vector Learning, pp. 41–65. MIT Press, Cambridge (1998)
[32] Platt, J.: Sequential minimal optimization: A fast algorithm for training support vector machine. Technical Report TR-98-14, Microsoft Research, (1998)
[33] Scheinberg, K.: An efficient implementation of an active set method for SVMs. J. Mach. Learn. Res. 7, 2237–2257 (2006) · Zbl 1222.90043
[34] Smola, A.J., Schölkopf, B.: Sparse greedy matrix approximation in machine learning. In: Proceedings of the 17th International Conference on Machine Learning, Stanford University, CA, pp. 911–918. (2000)
[35] Vapnik, V.N.: The Nature of Statistical Learning Theory. Springer, Heidelberg (1995) · Zbl 0833.62008
[36] Wright, S.J.: Primal–Dual Interior–Point Methods. SIAM Publications. SIAM, Philadelphia (1996) · Zbl 0863.65031
[37] Xiong Dong, J., Krzyzak, A., Suen, C.Y.: Fast SVM training algorithm with decomposition on very large data sets. IEEE Trans. Pattern Anal. Mach. Intell. 27, 603–618 (2005) · Zbl 05111105 · doi:10.1109/TPAMI.2005.77
[38] Yang, M.-H.: Resources for face detection. http://vision.ai.uiuc.edu/mhyang/face-detection-survey.html
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.