Beyond the point cloud: from transductive to semi-supervised learning

ABSTRACT

Due to its occurrence in engineering domains and implications for natural learning, the problem of utilizing unlabeled data is attracting increasing attention in machine learning. A large body of recent literature has focussed on the transductive setting where labels of unlabeled examples are estimated by learning a function defined only over the point cloud data. In a truly semi-supervised setting however, a learning machine has access to labeled and unlabeled examples and must make predictions on data points never encountered before. In this paper, we show how to turn transductive and standard supervised learning algorithms into semi-supervised learners. We construct a family of data-dependent norms on Reproducing Kernel Hilbert Spaces (RKHS). These norms allow us to warp the structure of the RKHS to reflect the underlying geometry of the data. We derive explicit formulas for the corresponding new kernels. Our approach demonstrates state of the art performance on a variety of classification tasks.

REFERENCES

• 1: Mikhail Belkin , Partha Niyogi, Problems of learning on manifolds, 2003
• 2: Belkin M., Niyogi P. & Sindhwani V. (2004) Manifold Regularization: A Geometric Framework for Learning for Examples. Technical Report TR-2004-06, Dept. of Computer Science, Univ. of Chicago
• 3: Belkin M., Matveeva I., & Niyogi P. (2004) Regression and Regularization on Large Graphs. COLT
• 4: Bousquet O., Chapelle O. & Hein, M. (2004) Measure Based Regularization. NIPS 16
• 5: Chapelle O., Weston J., & Schoelkopf B. (2003) Cluster Kernels for Semi-Supervised Learning. NIPS 15
• 6: Chapelle O. & Zien A. (2005) Semi-Supervised Classification by Low Density Separation. AI & Statistics
• 7: Delalleau O., Bengio Y. & Le Roux N. (2005) Efficient Non-Parametric Function Induction in Semi-Supervised Learning. AI & Statistics
• 8: 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
• 9: Joachims T. (2003) Transductive Learning via Spectral Graph Partitioning. ICML
• 10: Kegl B. & Wang L. (2005) Boosting on manifolds: adaptive regularization of base classifiers. NIPS 18
• 11: Lafon S. (2004) Diffusion maps and geometric harmonics. Ph.D. dissertation. Yale University
• 12: Kanal Paul Nigam , Tom M. Mitchell, Using unlabeled data to improve text classification, 2001
• 13: McCallum, A. K. (1996) Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering http://www.cs.cmu.edu/~mccallum/bow
• 14: Schoelkopf, B. & Smola A. J. (2002) Learning with Kernels. MIT Press, Cambridge, MA
• 15: Sindhwani, V. (2004) Kernel Machines for Semi-supervised Learning. Masters Thesis, University of Chicago
• 16: Smola, A. J., and Schoelkopf B. (1998) On a Kernel-Based Method for Pattern Recognition, Regression, Approximation, and Operator Inversion. Algorithmica, Vol. 22, No. 1/2, 211--231.
• 17: Si Wu , Shun-Ichi Amari, Conformal Transformation of Kernel Functions: A Data-Dependent Way to Improve Support Vector Machine Classifiers, Neural Processing Letters, v.15 n.1, p.59-67, February 2002 [doi>10.1023/A:1013848912046]
• 18: Vapnik, V. (1998) Statistical Learning Theory. Wiley-Interscience
• 19: Vert, J. P. and Yamanishi, Y. (2005), Supervised graph inference NIPS 18
• 20: Zhou, D., Bousquet, O., Lal, T. N., Weston J., & Schoelkopf, B. (2004) Learning with Local and Global Consistency. NIPS 16
• 21: Zhu, X., Ghahramani, Z., & Lafferty J. (2003) Semi-supervised Learning using Gaussian Fields and Harmonic Functions. ICML