Prototype vector machine for large scale semi-supervised learning

ABSTRACT

Practical data mining rarely falls exactly into the supervised learning scenario. Rather, the growing amount of unlabeled data poses a big challenge to large-scale semi-supervised learning (SSL). We note that the computational intensiveness of graph-based SSL arises largely from the manifold or graph regularization, which in turn lead to large models that are difficult to handle. To alleviate this, we proposed the prototype vector machine (PVM), a highly scalable, graph-based algorithm for large-scale SSL. Our key innovation is the use of "prototypes vectors" for efficient approximation on both the graph-based regularizer and model representation. The choice of prototypes are grounded upon two important criteria: they not only perform effective low-rank approximation of the kernel matrix, but also span a model suffering the minimum information loss compared with the complete model. We demonstrate encouraging performance and appealing scaling properties of the PVM on a number of machine learning benchmark data sets.

REFERENCES

• 1: Bie, T. D., & Cristianini, N. (2004). Convex methods for transduction. Advances in Neural Information Processing Systems 16 (pp. 73--80).
• 2: Ronan Collobert , Fabian Sinz , Jason Weston , Léon Bottou, Large Scale Transductive SVMs, The Journal of Machine Learning Research, 7, p.1687-1712, 12/1/2006
• 3: Delalleau, O., Bengio, Y., & Roux, N. (2005). Efficient non-parametric function induction in semi-supervised learning. Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (pp. 96--103).
• 4: Fung, G., & Mangasarian, O. L. (2001). Semi-supervised support vector machines for unlabeled data classification. Optimization Methods and Software, 15, 29--44.
• 5: Goldberger, J., & Roweis, S. (2005). Hierarchical clustering of a mixture model. Advances in Neural Information Processing Systems 17 (pp. 505--512).
• 6: Gustavo, C., Marsheva, T., & Zhou, D. (2007). Semi-supervised graph-based hyperspectral image classification. IEEE Transactions on Geoscience and Remote Sensing, 45, 3044--3054.
• 7: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 8: Lawrence, N., & Jordan, M. (2003). Semi-supervised learning via gaussian processes. Advances in Neural Information Processing Systems 14 (pp. 753--760).
• 9: Mikhail Belkin , Partha Niyogi , Vikas Sindhwani, Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples, The Journal of Machine Learning Research, 7, p.2399-2434, 12/1/2006
• 10: Olivier Chapelle, B. S., & Zien, A. (2006). Semi-supervised learning. MIT.
• 11: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 12: Christopher K. I. Williams , Matthias Seeger, The Effect of the Input Density Distribution on Kernel-based Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.1159-1166, June 29-July 02, 2000
• 13: Williams, C., & Seeger, M. (2001). Using the Nyströöm method to speed up kernel machines. Advances in Neural Information Processing Systems 13 (pp. 682--688).
• 14: Xu, Z., Jin, R., Zhu, J., King, I., & Lyu, M. (2008). Efficient convex relaxation for transductive support vector machine. In Advances in neural information processing systems 20, 1641--1648.
• 15: Kai Zhang , Ivor W. Tsang , James T. Kwok, Improved Nyström low-rank approximation and error analysis, Proceedings of the 25th international conference on Machine learning, p.1232-1239, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390311]
• 16: Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schöölkopf, B. (2003). Learning with local and global consistency. Neural Information Processing Systems 16 (pp. 321--328).
• 17: Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using gaussian fields and harmonic functions. In ICML (pp. 912--919).
• 18: Xiaojin Zhu , John Lafferty, Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning, Proceedings of the 22nd international conference on Machine learning, p.1052-1059, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102484]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory