Large scale semi-supervised linear SVMs

ABSTRACT

Large scale learning is often realistic only in a semi-supervised setting where a small set of labeled examples is available together with a large collection of unlabeled data. In many information retrieval and data mining applications, linear classifiers are strongly preferred because of their ease of implementation, interpretability and empirical performance. In this work, we present a family of semi-supervised linear support vector classifiers that are designed to handle partially-labeled sparse datasets with possibly very large number of examples and features. At their core, our algorithms employ recently developed modified finite Newton techniques. Our contributions in this paper are as follows: (a) We provide an implementation of Transductive SVM (TSVM) that is significantly more efficient and scalable than currently used dual techniques, for linear classification problems involving large, sparse datasets. (b) We propose a variant of TSVM that involves multiple switching of labels. Experimental results show that this variant provides an order of magnitude further improvement in training efficiency. (c) We present a new algorithm for semi-supervised learning based on a Deterministic Annealing (DA) approach. This algorithm alleviates the problem of local minimum in the TSVM optimization procedure while also being computationally attractive. We conduct an empirical study on several document classification tasks which confirms the value of our methods in large scale semi-supervised settings.

REFERENCES

• 1: Kristin P. Bennett , Ayhan Demiriz, Semi-supervised support vector machines, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.368-374, July 1999
• 2: Griff Bilbro , Reinhold Mann , Thomas K. Miller , Wesley E. Snyder , David E. Van den Bout , Mark White, Optimization by mean field annealing, Advances in neural information processing systems 1, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 3: O. Chapelle and A. Zien, Semi-Supervised Classification by Low Density Separation, AI & Statistics, Barbados, January 2005.
• 4: R. Collobert, F. Sinz, J. Weston, and L. Bottou, Large Scale Transductive SVMs, (submitted) 2006.
• 5: T. Joachims, Transductive Inference for Text Classification using Support Vector Machines, ICML 1998.
• 6: G. Fung and O. Mangasarian, Semi-Supervised Support Vector Machines for Unlabeled Data Classification, Optimization Methods and Software 15, 2001, 29--44.
• 7: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 8: S. Sathiya Keerthi , Dennis DeCoste, A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs, The Journal of Machine Learning Research, 6, p.341-361, 9/1/2005
• 9: C. Peterson and B. Soderberg, A new method for mapping optimization problems onto neural networks, International Journal of Neural Systems, 1(1):3--22, 1989.
• 10: Vikas Sindhwani , S. Sathiya Keerthi , Olivier Chapelle, Deterministic annealing for semi-supervised kernel machines, Proceedings of the 23rd international conference on Machine learning, p.841-848, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143950]
• 11: V. Sindhwani and S.S. Keerthi, Large Scale Semi-supervised Linear SVMs, Technical report, Yahoo research, 2006.
• 12: http://www.cs.uchicago.edu/~vikass/research.html
• 13: V. Vapnik, Statistical Learning Theory, John Wiley and Sons, New York, 1998.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Experimentation, Performance

Keywords:
global optimization, support vector machines, text categorization, unlabeled data