Label propagation through linear neighborhoods

ABSTRACT

A novel semi-supervised learning approach is proposed based on a linear neighborhood model, which assumes that each data point can be linearly reconstructed from its neighborhood. Our algorithm, named Linear Neighborhood Propagation (LNP), can propagate the labels from the labeled points to the whole dataset using these linear neighborhoods with sufficient smoothness. We also derive an easy way to extend LNP to out-of-sample data. Promising experimental results are presented for synthetic data, digit and text classification tasks.

REFERENCES

• 1: Belkin, M., & Niyogi, P. (2002) Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. Advances in Neural Information Processing Systems 14.
• 2: Belkin, M., Matveeva, I., & Niyogi, P. (2004) Regularization and Semi-supervised Learning on Large Graphs. In Proceedings of the 17th Conference on Learning Theory.
• 3: Belkin, M., Niyogi, P., & Sindhwani, V. (2005) On Manifold Regularization. In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics.
• 4: Chapelle, O., Weston, J., & Schöölkopf, B. (2003). Cluster Kernels for Semi-Supervised Learning. In Advances in Neural Information Processing Systems 15.
• 5: Fan R. K. Chung. (1997). Spectral Graph Theory. Regional Conference Series in Mathematics, no. 92.
• 6: Delalleu, O., Bengio, Y., & Le Roux, N. (2005). Non-Parametric Function Induction in Semi-Supervised Learning. In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics.
• 7: Golub, G. H., Van Loan. C. F.(1989). Matrix Computation. 2nd ed. Baltimore.
• 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: Roweis, S. T., & Saul, L. K. (2000). Noninear Dimensionality Reduction by Locally Linear Embedding. Science: vol. 290, 2323--2326.
• 10: Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press, Cambridge, MA.
• 11: Szummer, M., & Jaakkola, T. (2002). Partially Labeled Classification with Markov Random Walks. Advances in Neural Information Processing Systems 14.
• 12: Tenenbaum, J. B., Silva, V., & Langford, J. C. (2000). A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science: vol. 290, 2319--2323.
• 13: Zhou, D., Bousquet, O., Lal, T. N. Weston, J., & Schöölkopf, B. (2004a). Learning with Local and Global Consistency. Advances in Neural Information Processing Systems 16.
• 14: Zhou, D. & Schöölkopf, B. (2004b). Learning from Labeled and Unlabeled Data Using Random Walks. Pattern Recognition, Proceedings of the 26th DAGM Symposium.
• 15: Zhu, X., Ghahramani, Z., & Lafferty, J.(2003). Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions. In Proceedings of the 20th International Conference on Machine Learning.
• 16: Zhu, X. (2005). Semi-Supervied Learning Literature Survey. Computer Sciences Technical Report 1530, University of Wisconsin-Madison.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Algorithms