Support vector machines (SVMs) are well-studied supervised learning models for binary classification. Large amounts of samples can be cheaply and easily obtained in many applications. What is often a costly and error-prone process is to label these data points manually. Semi-supervised support vector machines (S3VMs) extend the well-known SVM classifiers to the semi-supervised approach, aiming to maximize the margin between samples in the presence of unlabeled data. By leveraging both labeled and unlabeled data, S3VMs attempt to achieve better accuracy and robustness than traditional SVMs. Unfortunately, the resulting optimization problem is non-convex and hence difficult to solve exactly. This paper presents a new branch-and-cut approach for S3VMs using semidefinite programming (SDP) relaxations. We apply optimality-based bound tightening to bound the feasible set. Box constraints allow us to include valid inequalities, strengthening the lower bound. The resulting SDP relaxation provides bounds that are significantly stronger than the ones available in the literature. For the upper bound, instead, we define a local search heuristic exploiting the solution of the SDP relaxation. Computational results highlight the algorithm’s efficiency, showing its capability to solve instances with ten times more data points than the ones solved in the literature.

Optimization meets machine learning: an exact algorithm for semi-supervised support vector machines / Piccialli, Veronica; Schwiddessen, Jan; Sudoso, Antonio M.. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - (2024). [10.1007/s10107-024-02175-z]

Optimization meets machine learning: an exact algorithm for semi-supervised support vector machines

Piccialli, Veronica
;
Sudoso, Antonio M.
2024

Abstract

Support vector machines (SVMs) are well-studied supervised learning models for binary classification. Large amounts of samples can be cheaply and easily obtained in many applications. What is often a costly and error-prone process is to label these data points manually. Semi-supervised support vector machines (S3VMs) extend the well-known SVM classifiers to the semi-supervised approach, aiming to maximize the margin between samples in the presence of unlabeled data. By leveraging both labeled and unlabeled data, S3VMs attempt to achieve better accuracy and robustness than traditional SVMs. Unfortunately, the resulting optimization problem is non-convex and hence difficult to solve exactly. This paper presents a new branch-and-cut approach for S3VMs using semidefinite programming (SDP) relaxations. We apply optimality-based bound tightening to bound the feasible set. Box constraints allow us to include valid inequalities, strengthening the lower bound. The resulting SDP relaxation provides bounds that are significantly stronger than the ones available in the literature. For the upper bound, instead, we define a local search heuristic exploiting the solution of the SDP relaxation. Computational results highlight the algorithm’s efficiency, showing its capability to solve instances with ten times more data points than the ones solved in the literature.
2024
Branch-and-cut; Global optimization; Semidefinite programming; SVM
01 Pubblicazione su rivista::01a Articolo in rivista
Optimization meets machine learning: an exact algorithm for semi-supervised support vector machines / Piccialli, Veronica; Schwiddessen, Jan; Sudoso, Antonio M.. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - (2024). [10.1007/s10107-024-02175-z]
File allegati a questo prodotto
File Dimensione Formato  
Piccialli_Optimization-meets-machine_2024.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 612.75 kB
Formato Adobe PDF
612.75 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1731511
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact