A continuation method for semi-supervised SVMs

ABSTRACT

Semi-Supervised Support Vector Machines (S³VMs) are an appealing method for using unlabeled data in classification: their objective function favors decision boundaries which do not cut clusters. However their main problem is that the optimization problem is non-convex and has many local minima, which often results in suboptimal performances. In this paper we propose to use a global optimization technique known as continuation to alleviate this problem. Compared to other algorithms minimizing the same objective function, our continuation method often leads to lower test errors.

REFERENCES

• 1: Astorino, A., & Fuduli, A. (2005). Nonsmooh optimization techniques for semi-supervised classification (Technical Report). U. Pisa, Dipartimento di Matematica. www.dm.unipi.it/mat_dia_med/PAPER_Astorino.pdf.
• 2: Kristin P. Bennett , Ayhan Demiriz, Semi-supervised support vector machines, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.368-374, July 1999
• 3: Chapelle, O. (2006). Training a support vector machine in the primal (Technical Report 147). Max Planck Institute. www.kyb.tuebingen.mpg.de/bs/people/chapelle/primal.
• 4: Chapelle, O., Weston, J., & Schöölkopf, B. (2002). Cluster kernels for semi-supervised learning. Advances in Neural Information Processing Systems 15.
• 5: Chapelle, O., & Zien, A. (2005). Semi-supervised classification by low density separation. Tenth International Workshop on Artificial Intelligence and Statistics.
• 6: Collobert, R., Sinz, F., Weston, J., & Bottou, L. (2006). Large scale transductive SVMs. Journal of Machine Learning Research. Submitted, www.kyb.tuebingen.mpg.de/bs/people/fabee/universvm.html.
• 7: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 8: Fung, G., & Mangasarian, O. (2001). Semi-supervised support vector machines for unlabeled data classification. Optimization Methods and Software, 29--44.
• 9: 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
• 10: Joachims, T. (2003). Transductive learning via spectral graph partitioning. International Conference on Machine Learning.
• 11: S. Sathiya Keerthi , Dennis DeCoste, A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs, The Journal of Machine Learning Research, 6, p.341-361, 9/1/2005
• 12: Kimeldorf, G., & Wahba, G. (1971). Some results on tchebycheffian spline functions. J. Math. Anal. Applic., 33, 82--95.
• 13: Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001). On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems.
• 14: Schölkopf, B., & Smola, A. (2002). Learning with kernels. Cambridge, MA: MIT Press.
• 15: Seeger, M. (2006). A taxonomy of semi-supervised learning methods. In O. Chapelle, B. Schölkopf and A. Zien (Eds.), Semi-supervised lerning. MIT Press.
• 16: Vikas Sindhwani , S. Sathiya Keerthi , Olivier Chapelle, Deterministic annealing for semi-supervised kernel machines, Proceedings of the 23rd international conference on Machine learning, p.841-848, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143950]
• 17: 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]
• 18: Vapnik, V., & Sterin, A. (1977). On structural risk minimization or overall risk in a problem of pattern recognition. Automation and Remote Control, 10, 1495--1503.
• 19: Vapnik, V. N. (1998). Statistical learning theory. New York: John Wiley & Sons, Inc.
• 20: Zhijun Wu, The Effective Energy Transformation Scheme as a Special Continuation Approach to Global Optimization with Application to Molecular Conformation, SIAM Journal on Optimization, v.6 n.3, p.748-768, 1996 [doi>10.1137/S1052623493254698]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Neural nets

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Theory