An Inexact Implementation of Smoothing Homotopy Method for Semi-Supervised Support Vector Machines

ABSTRACT

Semi-supervised Support Vector Machines is an appealing method for using unlabeled data in classification. Smoothing homotopy method is one of feasible method for solving semi-supervised support vector machines. In this paper, an inexact implementation of the smoothing homotopy method is considered. The numerical implementation is based on a truncated smoothing technique. By the new technique, many “non-active” data can be filtered during the computation of every iteration so that the computation cost is reduced greatly. Besides this, the global convergence can make better local minima and then result in lower test errors. Final numerical results verify the efficiency of the method.

Semi-supervised Support Vector Machines is an appealing method for using unlabeled data in classification. Smoothing homotopy method is one of feasible method for solving semi-supervised support vector machines. In this paper, an inexact implementation of the smoothing homotopy method is considered. The numerical implementation is based on a truncated smoothing technique. By the new technique, many “non-active” data can be filtered during the computation of every iteration so that the computation cost is reduced greatly. Besides this, the global convergence can make better local minima and then result in lower test errors. Final numerical results verify the efficiency of the method.

Cite this paper

H. Xiong and F. Shi, "An Inexact Implementation of Smoothing Homotopy Method for Semi-Supervised Support Vector Machines,"*Journal of Data Analysis and Information Processing*, Vol. 1 No. 1, 2013, pp. 1-7. doi: 10.4236/jdaip.2013.11001.

H. Xiong and F. Shi, "An Inexact Implementation of Smoothing Homotopy Method for Semi-Supervised Support Vector Machines,"

References

[1] A. Astorino and A. Fuduli, “Nonsmooth Optimization Techniques for Semi-Supervised Classification,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 29, No. 12, 2007, pp. 2135-2142. doi:10.1109/TPAMI.2007.1102

[2] C. J. C. Burges, “A Tutorial on Support Vector Machines for Pattern Recognition, “Data Mining and Knowledge Discovery, Vol. 2, No. 2, 1998, pp. 121-167. doi:10.1023/A:1009715923555

[3] E. L. Allgower and K. Georg, “Numerical Continuation Methods: An Introduction,” Springer-Vergal, Berlin, 1990. doi:10.1007/978-3-642-61257-2

[4] E. Polak, J. O. Royset and R. S. Womersley, “Algorithms with Adaptive Smoothing for Finite Minimax Problems,” Journal of Optimization Theory and Application, Vol. 119, No. 3, 2003, pp. 459-484. doi:10.1023/B:JOTA.0000006685.60019.3e

[5] G. Fung and O. Mangasarian, “Semi-Supervised Support Vector Machines for Unlabeled Data Classification,” Optimization Methods and Software, Vol. 15, No. 1, 2001, pp. 29-44. doi:10.1080/10556780108805809

[6] G. X., Liu, “Aggregate Homotopy Methods for Solving Sequential Max-Min Problems, Complementarity Problems and Variational Inequalities,” PhD Thesis, Jilin University, Jilin, 2003.

[7] K. Bennett and A. Demiriz, “Semi-Supervised Support Vector Machines,” In: M. S. Kearns, S. A. Solla and D. A. Cohn, Eds, Advances in Neural Information Processing Systems, MIT Press, Vol. 10, 1998, pp. 368-374.

[8] L. T. Watson, S. C. Billups and A. P. Morgan, “Algorithm 652 Hompack: A Suite of Codes for Globally Convergent Homotopy Algorithms,” ACM Transactions on Mathematical Software, Vol. 13, No. 3, 1987, pp. 281-310. doi:10.1145/29380.214343

[9] M. M. Mkela and P. Neittaanmki, “Nonsmooth Optimizatin: Analysis and Algorithms with Application to Optimal Control,” Utopia Press, Singapore, 1992.

[10] P. M. Murphy and D. W. Aha, “UCI Repository of Machine Learning Databases. http://www.ics.uci.edu/ mlearn/MLRepository.html.

[11] O. Chapelle, V. Sindhwani and S. S. Keerthi, “Optimization Techniques for Semi-Supervised Support Vector Machines,” Journal of Machine Learning Research, Vol. 9, 2008, pp. 203-233.

[12] O. Chapelle, M. Chi and A. Zien, “A Continuation Method for Semi-Supervised SVMs,” ACM International Conference Proceeding Series, Proceedings of the 23rd international conference on Machine learning, Vol. 148, 2006, pp. 185-192.

[13] O. Chapelle and A. Zien, “Semi-Supervised Classification by Low Density Separation,” Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, Vol. 1, 2005, pp. 57-64.

[14] O. Chapelle, V. Sindwani and S. Keerthi, “Branch and Bound for Semi-Supervised Support Vector Machines,” Advances in Neural Information Processing Systems 19, Proceedings of the 2006 Conference, MIT Press, Cambridge, 2007, pp. 217-224.

[15] O. L. Mangasarian and D. R. Musicant, “Lagrangian Support Vector Machines,” Journal of Machine Learning Research, Vol. 1, 2001, pp. 161-177.

[16] S. Birbil, S. C. Fang and J. Han, “Entropic Regularization Approach for Mathematical Programs with Equilibrium Constraints,” Technical Report, Industrial Engineering and Operations Research, Carolina, 2002.

[17] T. D. Bie, N. Cristianini, “Semi-Supervised Learning Using Semi-Definite Programming,” In: O. Chapelle, B. Scholkopf and A. Zien, Eds., Semi-Supervised Learning, MIT Press, Cambridge, 2006.

[18] X. J. Zhu, “Semi-Supervised Learning Literature Survey,” Technical Report 1530, Computer Science, University of Wisconsin-Madison, 2005.

[19] X. S. Li and S. C. Fang, “On the Entropic Regularization Method for Solving Min-Max Problems with Applications,” Mathematical Methods and Operations Research, Vol. 46, No. 1, 1997, pp. 119-130. doi:10.1007/BF01199466

[20] Y. Xiao, H. J. Xiong and B. Yu, “Truncated Aggregate Homotopy Method for Nonconvex Nonlinear Programming,” Optimization Methods and Software, 2012, pp. 1- 18.

[21] H. J. Xiong and B. Yu, “Aggregate Homotopy Method for Semi-Supervised SVMs,” 2011 International Conference on Electric Information and Control Engineering, pp. 1147-1150.

[1] A. Astorino and A. Fuduli, “Nonsmooth Optimization Techniques for Semi-Supervised Classification,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 29, No. 12, 2007, pp. 2135-2142. doi:10.1109/TPAMI.2007.1102

[2] C. J. C. Burges, “A Tutorial on Support Vector Machines for Pattern Recognition, “Data Mining and Knowledge Discovery, Vol. 2, No. 2, 1998, pp. 121-167. doi:10.1023/A:1009715923555

[3] E. L. Allgower and K. Georg, “Numerical Continuation Methods: An Introduction,” Springer-Vergal, Berlin, 1990. doi:10.1007/978-3-642-61257-2

[4] E. Polak, J. O. Royset and R. S. Womersley, “Algorithms with Adaptive Smoothing for Finite Minimax Problems,” Journal of Optimization Theory and Application, Vol. 119, No. 3, 2003, pp. 459-484. doi:10.1023/B:JOTA.0000006685.60019.3e

[5] G. Fung and O. Mangasarian, “Semi-Supervised Support Vector Machines for Unlabeled Data Classification,” Optimization Methods and Software, Vol. 15, No. 1, 2001, pp. 29-44. doi:10.1080/10556780108805809

[6] G. X., Liu, “Aggregate Homotopy Methods for Solving Sequential Max-Min Problems, Complementarity Problems and Variational Inequalities,” PhD Thesis, Jilin University, Jilin, 2003.

[7] K. Bennett and A. Demiriz, “Semi-Supervised Support Vector Machines,” In: M. S. Kearns, S. A. Solla and D. A. Cohn, Eds, Advances in Neural Information Processing Systems, MIT Press, Vol. 10, 1998, pp. 368-374.

[8] L. T. Watson, S. C. Billups and A. P. Morgan, “Algorithm 652 Hompack: A Suite of Codes for Globally Convergent Homotopy Algorithms,” ACM Transactions on Mathematical Software, Vol. 13, No. 3, 1987, pp. 281-310. doi:10.1145/29380.214343

[9] M. M. Mkela and P. Neittaanmki, “Nonsmooth Optimizatin: Analysis and Algorithms with Application to Optimal Control,” Utopia Press, Singapore, 1992.

[10] P. M. Murphy and D. W. Aha, “UCI Repository of Machine Learning Databases. http://www.ics.uci.edu/ mlearn/MLRepository.html.

[11] O. Chapelle, V. Sindhwani and S. S. Keerthi, “Optimization Techniques for Semi-Supervised Support Vector Machines,” Journal of Machine Learning Research, Vol. 9, 2008, pp. 203-233.

[12] O. Chapelle, M. Chi and A. Zien, “A Continuation Method for Semi-Supervised SVMs,” ACM International Conference Proceeding Series, Proceedings of the 23rd international conference on Machine learning, Vol. 148, 2006, pp. 185-192.

[13] O. Chapelle and A. Zien, “Semi-Supervised Classification by Low Density Separation,” Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, Vol. 1, 2005, pp. 57-64.

[14] O. Chapelle, V. Sindwani and S. Keerthi, “Branch and Bound for Semi-Supervised Support Vector Machines,” Advances in Neural Information Processing Systems 19, Proceedings of the 2006 Conference, MIT Press, Cambridge, 2007, pp. 217-224.

[15] O. L. Mangasarian and D. R. Musicant, “Lagrangian Support Vector Machines,” Journal of Machine Learning Research, Vol. 1, 2001, pp. 161-177.

[16] S. Birbil, S. C. Fang and J. Han, “Entropic Regularization Approach for Mathematical Programs with Equilibrium Constraints,” Technical Report, Industrial Engineering and Operations Research, Carolina, 2002.

[17] T. D. Bie, N. Cristianini, “Semi-Supervised Learning Using Semi-Definite Programming,” In: O. Chapelle, B. Scholkopf and A. Zien, Eds., Semi-Supervised Learning, MIT Press, Cambridge, 2006.

[18] X. J. Zhu, “Semi-Supervised Learning Literature Survey,” Technical Report 1530, Computer Science, University of Wisconsin-Madison, 2005.

[19] X. S. Li and S. C. Fang, “On the Entropic Regularization Method for Solving Min-Max Problems with Applications,” Mathematical Methods and Operations Research, Vol. 46, No. 1, 1997, pp. 119-130. doi:10.1007/BF01199466

[20] Y. Xiao, H. J. Xiong and B. Yu, “Truncated Aggregate Homotopy Method for Nonconvex Nonlinear Programming,” Optimization Methods and Software, 2012, pp. 1- 18.

[21] H. J. Xiong and B. Yu, “Aggregate Homotopy Method for Semi-Supervised SVMs,” 2011 International Conference on Electric Information and Control Engineering, pp. 1147-1150.