Optimal reverse prediction: a unified perspective on supervised, unsupervised and semi-supervised learning

ABSTRACT

Training principles for unsupervised learning are often derived from motivations that appear to be independent of supervised learning. In this paper we present a simple unification of several supervised and unsupervised training principles through the concept of optimal reverse prediction: predict the inputs from the target labels, optimizing both over model parameters and any missing labels. In particular, we show how supervised least squares, principal components analysis, k-means clustering and normalized graph-cut can all be expressed as instances of the same training principle. Natural forms of semi-supervised regression and classification are then automatically derived, yielding semi-supervised learning algorithms for regression and classification that, surprisingly, are novel and refine the state of the art. These algorithms can all be combined with standard regularizers and made non-linear via kernels.

REFERENCES

• 1: Balcan, M.-F., & Blum, A. (2005). A PAC-style model for learning from labeled and unlabeled data. Conf. Comput. Learn. Theory (COLT) (pp. 111--126).
• 2: 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
• 3: Ben-David, S., Lu, T., & Páál, D. (2008). Does unlabeled data provably help? Conf. Comput. Learn. Theory (COLT) (pp. 33--44).
• 4: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 6: Chapelle, O., Vapnik, V., & Weston, J. (1999). Transductive inference for estimating values of functions. Adv. Neural Info. Proc. 12 (NIPS) (pp. 421--427).
• 7: Chen, H.-R., & Peng, J. (2008). 0-1 semidefinite programming for graph-cut clustering. In CRM Proceedings and Lecture Notes of the Amer. Math. Soc.
• 8: Corduneanu, A., & Jaakkola., T. (2006). Data dependent regularization. In O. Chapelle, B. Scholkööpf and A. Zien (Eds.), Semi-supervised learning, 163--182. MIT Press.
• 9: Cortes, C., & Mohri, M. (2006). On transductive regression. Adv. Neural Info. Proc. Sys. 19 (NIPS) (pp. 305--312).
• 10: De Bie, T., & Cristianini, N. (2003). Convex methods for transduction. Adv. Neural Info. Proc. Sys. 16 (NIPS) (pp. 73--80).
• 11: Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Kernel k-means: spectral clustering and normalized cuts, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014118]
• 12: Chris Ding , Xiaofeng He, K-means clustering via principal component analysis, Proceedings of the twenty-first international conference on Machine learning, p.29, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015408]
• 13: 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
• 14: Joachims, T. (2003). Transductive learning via spectral graph partitioning. Inter. Conf. Mach. Learn. (ICML) (pp. 290--297).
• 15: Jong, J.-C., & Kotz, S. (1999). On a relation between principal components and regression analysis. The American Statistician, 53, 349--351.
• 16: Katayama, T. (2005). Subspace methods for system identification. Springer.
• 17: Dan Klein , Christopher D. Manning, The unsupervised learning of natural language structure, Stanford University, Stanford, CA, 2005
• 18: Brian Kulis , Sugato Basu , Inderjit Dhillon , Raymond Mooney, Semi-supervised graph clustering: a kernel approach, Machine Learning, v.74 n.1, p.1-22, January 2009 [doi>10.1007/s10994-008-5084-4]
• 19: MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Berkeley Symp. on Math. Stats. and Prob (pp. 281--297).
• 20: Sebastian Mika , Bernhard Schölkopf , Alex Smola , Klaus-Robert Müller , Matthias Scholz , Gunnar Rätsch, Kernel PCA and de-noising in feature spaces, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.536-542, July 1999
• 21: Jiming Peng , Yu Wei, Approximating K-means-type Clustering via Semidefinite Programming, SIAM Journal on Optimization, v.18 n.1, p.186-205, February 2007 [doi>10.1137/050641983]
• 22: Schölkopf, B., & Smola, A. (2002). Learning with kernels. MIT Press.
• 23: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 24: Vikas Sindhwani , Partha Niyogi , Mikhail Belkin, Beyond the point cloud: from transductive to semi-supervised learning, Proceedings of the 22nd international conference on Machine learning, p.824-831, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102455]
• 25: Noah A. Smith , Jason Eisner, Contrastive estimation: training log-linear models on unlabeled data, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.354-362, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219884]
• 26: Xing, E., & Jordan, M. (2003). On semidefinite relaxation for normalized k-cut and connections to spectral clustering. TR CSD-03-1265, Berkeley.
• 27: Xu, L., Neufeld, J., Larson, B., & Schuurmans, D. (2004). Maximum margin clustering. Adv. Neural Info. Proc. Sys. 17 (NIPS) (pp. 1537--1544).
• 28: Zhou, D., & Schöölkopf, B. (2006). Discrete regularization. In O. Chapelle, B. Scholköpf and A. Zien (Eds.), Semi-supervised learning, 221--232. MIT Press.
• 29: Zhu, X. (2005). Semi-supervised learning literature survey. TR 1530, U. Wisconsin, CS Dept.

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.6 Optimization
          Subjects: Least squares methods
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  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