nips nips2003 nips2003-48 nips2003-48-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tijl D. Bie, Nello Cristianini
Abstract: The 2-class transduction problem, as formulated by Vapnik [1], involves finding a separating hyperplane for a labelled data set that is also maximally distant from a given set of unlabelled test points. In this form, the problem has exponential computational complexity in the size of the working set. So far it has been attacked by means of integer programming techniques [2] that do not scale to reasonable problem sizes, or by local search procedures [3]. In this paper we present a relaxation of this task based on semidefinite programming (SDP), resulting in a convex optimization problem that has polynomial complexity in the size of the data set. The results are very encouraging for mid sized data sets, however the cost is still too high for large scale problems, due to the high dimensional search space. To this end, we restrict the feasible region by introducing an approximation based on solving an eigenproblem. With this approximation, the computational cost of the algorithm is such that problems with more than 1000 points can be treated. 1
[1] V. N. Vapnik. Statistical Learning Theory. Springer, 1998.
[2] K. Bennett and A. Demiriz. Semi-supervised support vector machines. In M. S. Kearns, S. A. Solla, and D. A. Cohn, editors, Advances in Neural Information Processing Systems 11, Cambridge, MA, 1999. MIT Press.
[3] T. Joachims. Transductive inference for text classification using support vector machines. In Proc. of the International Conference on Machine Learning (ICML), 1999.
[4] N. Cristianini, J. Kandola, A. Elisseeff, and J. Shawe-Taylor. On optimizing kernel alignment. Submitted for publication, 2003.
[5] S. D. Kamvar, D. Klein, and C. D. Manning. Spectral learning. In Proc. of the International Joint Conference on Artificial Intelligence (IJCAI), 2003.
[6] O. Chapelle, J. Weston, and B. Sch¨lkopf. Cluster kernels for semi-supervised o learning. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, Cambridge, MA, 2003. MIT Press.
[7] C. Helmberg. Semidefinite Programming for Combinatorial Optimization. Habilitationsschrift, TU Berlin, January 2000. ZIB-Report ZR-00-34, KonradZuse-Zentrum Berlin, 2000.
[8] 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 (JMLR), 5:27–72, 2004.
[9] T. Poggio, S. Mukherjee, R. Rifkin, A. Rakhlin, and A. Verri. b. In Proceedings of the Conference on Uncertainty in Geometric Computations, 2001.
[10] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1985.
[11] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.