nips nips2007 nips2007-190 nips2007-190-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ronny Luss, Alexandre D'aspremont
Abstract: In this paper, we propose a method for support vector machine classification using indefinite kernels. Instead of directly minimizing or stabilizing a nonconvex loss function, our method simultaneously finds the support vectors and a proxy kernel matrix used in computing the loss. This can be interpreted as a robust classification problem where the indefinite kernel matrix is treated as a noisy observation of the true positive semidefinite kernel. Our formulation keeps the problem convex and relatively large problems can be solved efficiently using the analytic center cutting plane method. We compare the performance of our technique with other methods on several data sets.
[1] C. S. Ong, X. Mary, S. Canu, and A. J. Smola. Learning with non-positive kernels. Proceedings of the 21st International Conference on Machine Learning, 2004.
[2] A. Zamolotskikh and P. Cunningham. An assessment of alternative strategies for constructing emd-based kernel functions for use in an svm for image classification. Technical Report UCD-CSI-2007-3, 2004.
[3] H. Saigo, J. P. Vert, N. Ueda, and T. Akutsu. Protein homology detection using string alignment kernels. Bioinformatics, 20(11):1682–1689, 2004.
[4] G. R. G. Lanckriet, N. Cristianini, M. I. Jordan, and W. S. Noble. Kernel-based integration of genomic data using semidefinite programming. 2003. citeseer.ist.psu.edu/648978.html.
[5] G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. El Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5:27–72, 2004.
[6] C. S. Ong, A. J. Smola, and R. C. Williamson. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 6:1043–1071, 2005.
[7] F. R. Bach, G. R. G. Lanckriet, and M. I. Jordan. Multiple kernel learning, conic duality, and the smo algorithm. Proceedings of the 21st International Conference on Machine Learning, 2004.
[8] S. Sonnenberg, G. R¨ tsch, C. Sch¨ fer, and B. Sch¨ lkopf. Large scale multiple kernel learning. Journal of a a o Machine Learning Research, 7:1531–1565, 2006.
[9] Marco Cuturi. Permanents, transport polytopes and positive definite kernels on histograms. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, 2007.
[10] B. Haasdonk. Feature space interpretation of svms with indefinite kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(4), 2005.
[11] K. P. Bennet and E. J. Bredensteiner. Duality and geometry in svm classifiers. Proceedings of the 17th International conference on Machine Learning, pages 57–64, 2000.
[12] G. Wu, E. Y. Chang, and Z. Zhang. An analysis of transformation on non-positive semidefinite similarity matrix for kernel machines. Proceedings of the 22nd International Conference on Machine Learning, 2005.
[13] H.-T. Lin and C.-J. Lin. A study on sigmoid kernel for svm and the training of non-psd kernels by smo-type methods. 2003.
[14] A. Wo´ nica, A. Kalousis, and M. Hilario. Distances and (indefinite) kernels for set of objects. Proceedings z of the 6th International Conference on Data Mining, pages 1151–1156, 2006.
[15] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[16] C. Gigola and S. Gomez. A regularization method for solving the finite convex min-max problem. SIAM Journal on Numerical Analysis, 27(6):1621–1634, 1990.
[17] M. Overton. Large-scale optimization of eigenvalues. SIAM Journal on Optimization, 2(1):88–120, 1992.
[18] D. Bertsekas. Nonlinear Programming, 2nd Edition. Athena Scientific, 1999.
[19] J.-L. Goffin and J.-P. Vial. Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Optimization Methods and Software, 17(5):805–867, 2002.
[20] J. J. Hull. A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5), 1994.
[21] A. Asuncion and D.J. Newman. UCI Machine sity of California, Irvine, School of Information http://www.ics.uci.edu/∼mlearn/MLRepository.html. 8 Learning Repository. Univerand Computer Sciences, 2007.