›› 2010, Vol. 25 ›› Issue (4): 709-727.doi: 10.1007/s11390-010-1055-x

Special Issue: Artificial Intelligence and Pattern Recognition

• Special Section on Advances in Machine Learning and Applications • Previous Articles     Next Articles

Learning with Uncertain Kernel Matrix Set

Lei Jia(贾 磊), Shi-Zhong Liao*(廖士中), Member, CCF, and Li-Zhong Ding(丁立中)   

  1. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China
  • Received:2009-05-15 Revised:2010-02-09 Online:2010-07-09 Published:2010-07-09
  • About author:
    Lei Jia received his B.E. and M.B. degrees in computer science from Tianjin University of China in 2004 and 2007 respectively. Currently he is a Ph.D. candidate at School of Computer Science and Technology, Tianjin University. His research interests include machine learning, model selection and kernel methods.
    Shi-Zhong Liao is a professor and Ph.D. supervisor at School of Computer Science and Technology, Tianjin University. He is a member of CCF. He received the Ph.D. degree in computer science from Tsinghua University in 1997. His research interests include artificial intelligence and theoretical computer science.
    Li-Zhong Ding received his B.E. degree in computer science from Tianjin University of China in 2009. Currently he is a Ph.D. candidate at School of Computer Science and Technology, Tianjin University. His research interests include computational learning theory, model selection and kernel methods.
  • Supported by:

    This work is supported in part by the National Natural Science Foundation of China under Grant No. 60678049 and Natural Science Foundation of Tianjin under Grant No. 07JCYBJC14600.

PDF

1746

We study support vector machines (SVM) for which the kernel matrix is not specified exactly and it is only known to belong to a given uncertainty set. We consider uncertainties that arise from two sources: (i) data measurement uncertainty, which stems from the statistical errors of input samples; (ii) kernel combination uncertainty, which stems from the weight of individual kernel that needs to be optimized in multiple kernel learning (MKL) problem. Much work has been studied, such as uncertainty sets that allow the corresponding SVMs to be reformulated as semi-definite programs (SDPs), which is very computationally expensive however. Our focus in this paper is to identify uncertainty sets that allow the corresponding SVMs to be reformulated as second-order cone programs (SOCPs), since both the worst case complexity and practical computational effort required to solve SOCPs is at least an order of magnitude less than that needed to solve SDPs of comparable size. In the main part of the paper we propose four uncertainty sets that meet this criterion. Experimental results are presented to confirm the validity of these SOCP reformulations.


[1] Shawe-Taylor J, Cristianini N. Kernel Methods for Pattern Analysis. Cambridge: Cambridge University Press, UK, 2005.

[2] Sh\"olkopf B, Smola A J. Learning with Kernels. Cambridge, Massachusetts: The MIT Press, USA, 2002.

[3] Burges C J C. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1998, 2(2): 121-167.

[4] Cristianini N, Shawe-Taylor J. An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge: Cambridge University Press, UK, 2000.

[5] Zhang L, Zhang B. Relationship between support vector set and kernel functions in SVM. Journal of Computer Science and Technology, 2002, 17(5): 549-555.

[6] Lanckriet G, Cristianini N, Baltlett P, El Ghaoui L, Jordan M I. Learning the kernel matrix with semi-definite programming. Journal of Machine Learning Research, Dec. 2004, 5: 27-72.

[7] Rakotomamonjy A, Bach F, Canu S, Grandvalet Y. More efficiency in multiple kernel learning. In Proc. the 24th International Conference on Machine Learning, Corvalis, USA, June 20-24, 2007, pp.775-782.

[8] Bach F, Lanckriet G R G, Jordan M I. Multiple kernel learning, conic duality, and the SMO algorithm. In Proc. the 21st International Conference on Machine Learning, Banff, Canada, July 4-8, 2004, pp.41-48.

[9] Sonnenburg S, R\"aetsch G, Sch\"aefer C, Sch\"olkopf B. Large scale multiple kernel learning. Journal of Machine Learning Research, Dec. 2006, 7: 1531-1565.

[10] Rakotomamonjy A, Bach F, Canu S, Grandvalet Y. SimpleMKL. Journal of Machine Learning Research, Nov. 2008, 9: 2491-2521.

[11] Chapelle O, Rakotomamonjy A. Second order optimization of kernel parameters. In Proc. the NIPS Workshop on Kernel Learning: Automatic Selection of Optimal Kernels, Vancouver, Canada, Dec. 8-13, 2008.

[12] Bousquet O, Herrmann D J L. On the complexity of learning the kernel matrix. In Proc. Advances in Neural Information Processing Systems 14, Vanconver, Canada, Dec. 9-14, 2002, pp.367-373.

[13] Yeh C J, Su W P, Lee S J. Improving efficiency of multi-kernel learning for support vector machines. In Proc. 2008 International Conference on Machine Learning and Cybernetic, Qunming, China, July 12-15, 2008, pp.3985-3990.

[14] Varma M, Babu B R. More generality in efficient multiple kernel learning. In Proc. the 26th International Conference on Machine Learning, Montreal, Canada, June 14-18, 2009, Article No.134.

[15] Alizadeh F, Goldfarb D. Second-order cone programming. Mathematical Programming Series B, 2003, 95(1): 3-51.

[16] Lobo M S, Vandenberghe L, Boyd S, Lebret H. Applications of second-order cone programming. Linear Algebra and Applications, 1998, 284(1-3): 193-228.

[17] Mittelmann H D. An independent benchmarking of SDP and SOCP solvers. Math. Programm. Ser. B, 2003, 95(2): 407-430.

[18] Sturm J F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 1999, (11/12): 625-653.

[19] Sturm J F. Similarity and other spectral relations for symmetric cones. Technical report, Department of Quantative Economics, Maastricht University, The Netherlands, 1999.

[20] Goldfarb D, Iyengar G. Robust convex quadratically constrained programs. Mathematical Programming Series B, 2003, 97(3): 495-515.

[21] Nesterov Y, Nemirovskii A. Interior-Point Polynomial Algorithms in Convex Programming. Philadelphia, PA: SIAM, 1994.

[22] Tsang I W H, Kwok J T Y. Efficient hyperkernel learning using second-order cone programming. IEEE Transactions on Neural Networks, 2006, 17(1): 48-58.

[23] Ben-Tal A, Nemirovski A. Robust convex optimization. Mathematics of Operations Research, 1998, 23(4): 769-805.

[24] Lanckriet G, Ghaoui L, Bhattacharyya C, Jordan M I. A robust minimax approach to classification. Journal of Machine Learning Research, Dec. 2002, 3: 555-582.

[25] Strohmann T R, Belitski A, Grudic G Z, DeCoste D. Sparse greedy minimax probability machine classification. In Proc. Advances in Neural Information Processing Systems 15, Vancouver and Whistler, Canada, Dec. 8-13, 2003.

[26] Marshall A, Olkin I. Multivariate chebyshev inequalities. Ann. Math. Stat., 1960, 31(4): 1001-1014.

[27] Popescu I, Bertsimas D. Optimal inequalities in probability theory: A convex optimization approach. Technical Report TM62, Insead, 2000.

[28] Cheng S O, Smola A J, Williamson R C. Learning the kernel with hyperkernels. Journal of Machine Learning Research, Jul. 2005, 6: 1043-1071.

[29] Toh K C, Todd M J, Tutuncu R H. SDPT3 --- A Matlab software package for semidefinite programming. Optimization Methods and Software, 1999, 11: 545-581.

[30] Newman D J, Hettich S, Blake C L, Merz C J. UCI Repository of machine learning databases. Department of Information and Computer Sciences, University of California, Irvine, 1998.

[31] King R D. Statlog databases. Department of Statistics and Modelling Science, University of Strathclyde, Glasgow, U.K., 1992.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved