Stability of transductive regression algorithms

ABSTRACT

This paper uses the notion of algorithmic stability to derive novel generalization bounds for several families of transductive regression algorithms, both by using convexity and closed-form solutions. Our analysis helps compare the stability of these algorithms. It suggests that several existing algorithms might not be stable but prescribes a technique to make them stable. It also reports the results of experiments with local transductive regression demonstrating the benefit of our stability bounds for model selection, in particular for determining the radius of the local neighborhood used by the algorithm.

REFERENCES

• 1: Belkin, M., Matveeva, I., & Niyogi, P. (2004a). Regularization and semi-supervised learning on large graphs. COLT (pp. 624--638).
• 2: Belkin, M., Niyogi, P., & Sindhwani, V. (2004b). Manifold regularization (Technical Report TR-2004-06). University of Chicago.
• 3: Olivier Bousquet , André Elisseeff, Stability and generalization, The Journal of Machine Learning Research, 2, p.499-526, 3/1/2002 [doi>10.1162/153244302760200704]
• 4: Chapelle, O., Vapnik, V., & Weston, J. (1999). Transductive Inference for Estimating Values of Functions. NIPS 12 (pp. 421--427).
• 5: Cortes, C., & Mohri, M. (2007). On Transductive Regression. NIPS 19 (pp. 305--312).
• 6: El-Yaniv, R., & Pechyony, D. (2006). Stable transductive learning. COLT (pp. 35--49).
• 7: McDiarmid, C. (1989). On the method of bounded differences. Surveys in Combinatorics (pp. 148--188). Cambridge University Press, Cambridge.
• 8: Dale Schuurmans , Finnegan Southey, Metric-Based Methods for Adaptive Model Selection and Regularization, Machine Learning, v.48 n.1-3, p.51-84, 2002 [doi>10.1023/A:1013947519741]
• 9: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 10: Vapnik, V. N. (1998). Statistical learning theory. New York: Wiley-Interscience.
• 11: Wu, M., & Schöölkopf, B. (2007). Transductive classification via local learning regularization. AISTATS (pp. 628--635).
• 12: Zhou, D., Bousquet, O., Lal, T., Weston, J., & Schöölkopf, B. (2004). Learning with local and global consistency. NIPS 16 (pp. 595--602).
• 13: Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using gaussian fields and harmonic functions. ICML (pp. 912--919).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Stability (and instability)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  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