Mixed-integer quadratic optimization and iterative clustering techniques for semi-supervised support vector machines

• Jan Pablo Burgard ^[1] ; Maria Eduarda Pinheiro ^[1] ; Martin Schmidt ^[1]
  1. [1] University of Trier

     University of Trier

     Kreisfreie Stadt Trier, Alemania

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 32, Nº. Extra 3, 2024 (Ejemplar dedicado a: Mathematical Optimization and Machine Learning), págs. 391-428
• Idioma: inglés
• DOI: 10.1007/s11750-024-00668-w
• Enlaces
  • Texto completo
• Resumen

  • Among the most famous algorithms for solving classification problems are support vector machines (SVMs), which find a separating hyperplane for a set of labeled data points. In some applications, however, labels are only available for a subset of points. Furthermore, this subset can be non-representative, e.g., due to self-selection in a survey. Semi-supervised SVMs tackle the setting of labeled and unlabeled data and can often improve the reliability of the results. Moreover, additional information about the size of the classes can be available from undisclosed sources. We propose a mixedinteger quadratic optimization (MIQP) model that covers the setting of labeled and unlabeled data points as well as the overall number of points in each class. Since the MIQP’s solution time rapidly grows as the number of variables increases, we introduce an iterative clustering approach to reduce the model’s size. Moreover, we present an update rule for the required big-M values, prove the correctness of the iterative clustering method as well as derive tailored dimension-reduction and warm-starting techniques. Our numerical results show that our approach leads to a similar accuracy and precision than the MIQP formulation but at much lower computational cost. Thus, we can solve larger problems. With respect to the original SVM formulation, we observe that our approach has even better accuracy and precision for biased samples.

• Referencias bibliográficas
  • Almasi ON, Rouhani M (2016) Fast and de-noise support vector machine training method based on fuzzy clustering method for large real world...
  • Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of Euclidean sum-of-squares clustering. Mach Learn 75(2):245–248. https://doi.org/10.1007/s10994-009-5103-0
  • Belkin M, Niyogi P, Sindhwani V (2006) Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. J...
  • Bennett KP, Demiriz A (1998) Semi-supervised support vector machines. In: Proceedings of the 11th international conference on neural information...
  • Birzhandi P, Youn HY (2019) CBCH (clustering-based convex hull) for reducing training time of support vector machine. J Supercomput 75(8):5261–5279. ...
  • Birzhandi P, Kim KT, Youn HY (2022) Reduction of training data for support vector machine: a survey. Soft Comput 26(8):3729–3742. https://doi.org/10.1007/s00500-022-06787-5
  • Boser BE, Guyon IM, Vapnik VN (1992) A training algorithm for optimal margin classifiers. In: Proceedings of the fifth annual workshop on...
  • Burgard JP, Krause J, Schmaus S (2021) Estimation of regional transition probabilities for spatial dynamic microsimulations from survey data...
  • Cervantes J, Li X, Yu W (2006) Support vector machine classification based on fuzzy clustering for large data sets, vol 4293. Springer, Berlin,...
  • Chapelle O, Zien A (2005) Semi-supervised classification by low density separation. In: Cowell RG, Ghahramani Z (eds) Proceedings of the tenth...
  • Chapelle O, Chi M, Zien A (2006) A continuation method for semi-supervised SVMs. In: Proceedings of the 23rd international conference on machine...
  • Cortes C, Vapnik V (1995) Support vector networks. Mach Learn 20:273–297. https://doi.org/10.1007/BF00994018
  • Dasgupta S (2007) The hardness of k-means clustering. https://cseweb.ucsd.edu/~dasgupta/papers/kmeans.pdf
  • de Almeida MB, de Pádua Braga A, Braga JP (2000) SVM-KM: speeding SVMs learning with a priori cluster selection and k-means. Proceedings of...
  • Dunning I, Huchette J, Lubin M (2017) JuMP: a modeling language for mathematical optimization. SIAM Rev 59(2):295–320. https://doi.org/10.1137/15M1020575
  • Hyndman RJ, Fan Y (1996) Sample quantiles in statistical packages. Am Stat 50(4):361–365. https://doi.org/10.2307/2684934
  • Joachims T (2002) Training transductive support vector machines. In: Learning to classify text using support vector machines. Springer, New...
  • Kontonatsios G, Brockmeier AJ, Przybyła P, McNaught J, Mu T, Goulermas JY, Ananiadou S (2017) A semi-supervised approach using label propagation...
  • Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129–137. https://doi.org/10.1109/TIT.1982.1056489
  • MacQueen J (1967) Classification and analysis of multivariate observations. In: Proceedings of the fifth Berkeley symposium on mathematical...
  • Mahajan M, Nimbhorkar P, Varadarajan K (2012) The planar k-means problem is NP-hard. Theor Comput Sci 442:13–21. https://doi.org/10.1016/j.tcs.2010.05.034
  • Melacci S, Belkin M (2009) Laplacian support vector machines trained in the primal. J Mach Learn Res. arXiv:0909.5422
  • Olson RS, La Cava W, Orzechowski P, Urbanowicz RJ, Moore JH (2017) PMLB: a large benchmark suite for machine learning evaluation and comparison....
  • Skinner CJ, D’Arrigo J (2011) Inverse probability weighting for clustered nonresponse. Biometrika 98(4):953–966. https://doi.org/10.1093/biomet/asr058
  • Yao Y, Liu Y, Yu Y, Xu H, Lv W, Li Z, Chen X (2013) K-SVM: an effective SVM algorithm based on K-means clustering. J Comput. https://doi.org/10.4304/jcp.8.10.2632-2639
  • Yu X, Yang J, Zhan J-P (2012) A transductive support vector machine algorithm based on spectral clustering. AASRI Proc 1:384–388. https://doi.org/10.1016/j.aasri.2012.06.059