nips nips2007 nips2007-76 nips2007-76-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Zenglin Xu, Rong Jin, Jianke Zhu, Irwin King, Michael Lyu
Abstract: We consider the problem of Support Vector Machine transduction, which involves a combinatorial problem with exponential computational complexity in the number of unlabeled examples. Although several studies are devoted to Transductive SVM, they suffer either from the high computation complexity or from the solutions of local optimum. To address this problem, we propose solving Transductive SVM via a convex relaxation, which converts the NP-hard problem to a semi-definite programming. Compared with the other SDP relaxation for Transductive SVM, the proposed algorithm is computationally more efficient with the number of free parameters reduced from O(n2 ) to O(n) where n is the number of examples. Empirical study with several benchmark data sets shows the promising performance of the proposed algorithm in comparison with other state-of-the-art implementations of Transductive SVM. 1
[1] T. D. Bie and N. Cristianini. Convex methods for transduction. In S. Thrun, L. Saul, and B. Sch¨ lkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, o Cambridge, MA, 2004.
[2] O. Chapelle, M. Chi, and A. Zien. A continuation method for semi-supervised SVMs. In ICML ’06: Proceedings of the 23rd international conference on Machine learning, pages 185–192, New York, NY, USA, 2006. ACM Press.
[3] O. Chapelle, B. Sch¨ lkopf, and A. Zien. Semi-Supervised Learning. MIT Press, Cambridge, o MA, 2006.
[4] O. Chapelle, V. Sindhwani, and S. Keerthi. Branch and bound for semi-supervised support vector machines. In B. Sch¨ lkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Inforo mation Processing Systems 19. MIT Press, Cambridge, MA, 2007.
[5] O. Chapelle and A. Zien. Semi-supervised classification by low density separation. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, pages 57–64, 2005.
[6] R. Collobert, F. Sinz, J. Weston, and L. Bottou. Large scale transductive SVMs. Journal of Machine Learning Reseaerch, 7:1687–1712, 2006.
[7] J.-B. Hiriart-Urruty and C. Lemarechal. Convex analysis and minimization algorithms II: advanced theory and bundle methods. (2nd part edition). Springer-Verlag, New York, 1993.
[8] T. Joachims. Transductive inference for text classification using support vector machines. In ICML ’99: Proceedings of the Sixteenth International Conference on Machine Learning, pages 200–209, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
[9] G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5:27– 72, 2004.
[10] Y. Nesterov and A. Nemirovsky. Interior point polynomial methods in convex programming: Theory and applications. Studies in Applied Mathematics. Philadelphia, 1994.
[11] V. Sindhwani, S. S. Keerthi, and O. Chapelle. Deterministic annealing for semi-supervised kernel machines. In ICML ’06: Proceedings of the 23rd international conference on Machine learning, pages 841–848, New York, NY, USA, 2006. ACM Press.
[12] J. F. Sturm. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11:625–653, 1999.
[13] H. Valizadegan and R. Jin. Generalized maximum margin clustering and unsupervised kernel learning. In B. Sch¨ lkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information o Processing Systems 19. MIT Press, Cambridge, MA, 2007.
[14] L. Xu and D. Schuurmans. Unsupervised and semi-supervised multi-class support vector machines. In AAAI, pages 904–910, 2005.
[15] X. Zhu. Semi-supervised learning literature survey. Technical report, Computer Sciences, University of Wisconsin-Madison, 2005.
[16] X. Zhu, Z. Ghahramani, and J. D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of Twentith International Conference on Machine Learning (ICML-2003), pages 912–919, 2003.