Skip to main content
SpringerLink
Log in

Conic Relaxations for Semi-supervised Support Vector Machines

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

Semi-supervised support vector machines arise in machine learning as a model of mixed integer programming problem for classification. In this paper, we propose two convex conic relaxations for the original mixed integer programming problem. The first one is a new semi-definite relaxation, and its possibly maximal ratio of the optimal value is estimated approximately. The second one is a doubly nonnegative relaxation, which is relaxed from a well-known conic programming problem called completely positive programming problem that is equivalent to the original problem. Furthermore, we prove that the doubly nonnegative relaxation is tighter than the semi-definite relaxation. Finally, the numerical results show that two proposed relaxations not only generate proper classifiers but also outperform some existing methods in classification accuracy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20(3), 273–297 (1995)

    MATH  Google Scholar 

  2. Joachims, T.: Transductive inference for text classification using support vector machines. In: Proceedings of 16th International Conference on Machine Learning, pp. 200–209 (1999)

  3. Osuna, E., Freund, R., Girosi, F.: Training support vector machines: an application to face detection. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 130–136 (1997)

  4. Tay, F.E., Cao, L.: Application of support vector machines in financial time series forecasting. Omega 29(4), 309–317 (2001)

    Article  Google Scholar 

  5. Chapelle, O., Schölkopf, B., Zien, A.: Semi-supervised Learning. MIT Press, Cambridge (2006)

    Book  Google Scholar 

  6. Chapelle, O., Sindhwani, V., Keerthi, S.S.: Optimization techniques for semi-supervised support vector machines. J. Mach. Learn. Res. 9, 203–233 (2008)

    MATH  Google Scholar 

  7. Giannessi, F., Tardella, F.: Connections between nonlinear programming and discrete optimization. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 1, pp. 149–188. Kluwer, Boston (1998)

    Chapter  Google Scholar 

  8. Bennett, K., Demiriz, A.: Semi-supervised support vector machines. In: Kearns, M.J., Solla, S.A., Cohn, D.A. (eds.) Advances in Neural Information Processing Systems 11, pp. 368–374. MIT Press, Cambridge (1999)

    Google Scholar 

  9. Bai, Y., Chen, Y., Niu, B.: SDP relaxation for semi-supervised support vector machine. Pac. J. Optim. 8(1), 3–14 (2012)

    MathSciNet  MATH  Google Scholar 

  10. Bai, Y., Niu, B., Chen, Y.: New SDP models for protein homology detection with semi-supervised SVM. Optimization 62(4), 561–572 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  11. De Bie, T., Cristianini, N.: Convex methods for transduction. In: Thrun, S., Saul, L.K., Schölkopf, B. (eds.) Advances in Neural Information Processing Systems, vol. 16, pp. 73–80. MIT Press, Cambridge (2004)

    Google Scholar 

  12. Li, Y.F., Tsang, I.W., Kwok, J.T., Zhou, Z.H.: Tighter and convex maximum margin clustering. In: Proceedings of 12th International Conference on Artificial Intelligence and Statistics, pp. 344–351 (2009)

  13. Valizadegan, H., Jin, R.: Generalized maximum margin clustering and unsupervised kernel learning. In: Schölkopf, B., Platt, J., Hofmann, T. (eds.) Advances in Neural Information Processing Systems, vol. 19, pp. 1417–1424. MIT Press, Cambridge (2006)

    Google Scholar 

  14. Xu, Z., Jin, R., Zhu, J., King, I., Lyu, M.: Efficient convex relaxation for transductive support vector machine. In: Platt, J.C., Koller, D., Singer, Y., Roweis, S. (eds.) Advances in Neural Information Processing Systems, vol. 20, pp. 1641–1648. MIT Press, Cambridge (2008)

    Google Scholar 

  15. Sindhwani, V., Keerthi, S.S., Chapelle, O.: Deterministic annealing for semi-supervised kernel machines. In: Proceedings of 23rd International Conference on Machine Learning, pp. 841–848 (2006)

  16. Collobert, R., Sinz, F., Weston, J., Bottou, L.: Large scale transductive SVMs. J. Mach. Learn. Res. 7, 1687–1712 (2006)

    MathSciNet  MATH  Google Scholar 

  17. Chapelle, O., Zien, A.: Semi-supervised classification by low density separation. In: Proceedings of 10th International Workshop on Artificial Intelligence and Statistics., pp. 57–64 (2005)

  18. Gieseke, F., Airola, A., Pahikkala, T., Kramer, O.: Fast and simple gradient-based optimization for semi-supervised support vector machines. Neurocomputing 123, 23–32 (2014)

    Article  Google Scholar 

  19. Zhao, B., Wang, F., Zhang, C.: CutS3VM: a fast semi-supervised SVM algorithm. In: Proceedings of 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 830–838 (2008)

  20. Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming, version 2.1 (2015). http://www.stanford.edu/~boyd/cvx

  21. Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Prog. Comput. 2(3–4), 203–230 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  22. Luo, Z.Q., Sidiropoulos, N.D., Tseng, P., Zhang, S.: Approximation bounds for quadratic optimization with homogeneous quadratic constraints. SIAM J. Optim. 18(1), 1–28 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  23. Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479–495 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  24. Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117–129 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  25. Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Prog. Comput. 2(1), 1–19 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  26. Ge, D., Ye, Y.: On doubly positive semidefinite programming relaxations (2010). http://www.optimizationonline.org/DBHTML/2010/08/2709.html

  27. Yoshise, A., Matsukawa, Y.: On optimization over the doubly nonnegative cone. In: 2010 IEEE Multi-conference on Systems and Control, pp. 13–19 (2010)

  28. Deng, N., Tian, Y., Zhang, C.: Support Vector Machines: Optimiaztion Based Theory, Algorithms, and Extensions. CRC Press, Boca Raton (2012)

    Google Scholar 

  29. Xu, L., Neufeld, J., Larson, B., Schuurmans, D.: Maximum margin clustering. In: Saul, L.K., Weiss, Y., Bottou, L. (eds.) Advances in Neural Information Processing Systems, vol. 17, pp. 1537–1544. MIT Press, Cambridge (2004)

    Google Scholar 

  30. Horn, R.A.: The Hadamard product. Proc. Symp. Appl. Math 40, 87–169 (1990)

    Article  MathSciNet  Google Scholar 

  31. Jarre, F.: Burer’s key assumption for semidefinite and doubly nonnegative relaxations. Optim. Lett. 6(3), 593–599 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  32. Fang, S.C., Xing, W.: Linear Conic Optimization. Science Press, Beijing (2013). (in Chinese)

    Google Scholar 

  33. Bai, Y.Q., Shen, Y.J., Shen, K.J.: Consensus proximal support vector machine for classification problems with sparse solutions. J. Oper. Res. Soc. China 2(1), 57–74 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  34. Astorino, A., Fuduli, A.: Support vector machine polyhedral separability in semisupervised learning. J. Optim. Theory Appl. 164(3), 1039–1050 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We thank two anonymous reviewers for their valuable comments. This research was supported by a grant from National Natural Science Foundation of China (No.11371242).

Author information

Authors and Affiliations

  1. Department of Mathematics, Shanghai University, Shanghai, China

    Yanqin Bai & Xin Yan

Authors
  1. Yanqin Bai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xin Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yanqin Bai.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bai, Y., Yan, X. Conic Relaxations for Semi-supervised Support Vector Machines. J Optim Theory Appl 169, 299–313 (2016). https://doi.org/10.1007/s10957-015-0843-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-015-0843-4

Keywords

Mathematics Subject Classification

Search

Navigation