Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929638693928960 |
|---|---|
| author | Bomze, Immanuel D'Onofrio, Federico Palagi, Laura Peng, Bo |
| author_facet | Bomze, Immanuel D'Onofrio, Federico Palagi, Laura Peng, Bo |
| contents | In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to an interpretable classification model. The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a problem solvable in polynomial time. To handle the hard problem, we first introduce two mixed-integer formulations for which novel semidefinite relaxations are proposed. Exploiting the sparsity pattern of the relaxations, we decompose the problems and obtain equivalent relaxations in a much smaller cone, making the conic approaches scalable. To make the best usage of the decomposed relaxations, we propose heuristics using the information of its optimal solution. Moreover, an exact procedure is proposed by solving a sequence of mixed-integer decomposed semidefinite optimization problems. Numerical results on classical benchmarking datasets are reported, showing the efficiency and effectiveness of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10099 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach Bomze, Immanuel D'Onofrio, Federico Palagi, Laura Peng, Bo Optimization and Control Machine Learning 90C22, 90C11 I.5.1; I.2.0 In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to an interpretable classification model. The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a problem solvable in polynomial time. To handle the hard problem, we first introduce two mixed-integer formulations for which novel semidefinite relaxations are proposed. Exploiting the sparsity pattern of the relaxations, we decompose the problems and obtain equivalent relaxations in a much smaller cone, making the conic approaches scalable. To make the best usage of the decomposed relaxations, we propose heuristics using the information of its optimal solution. Moreover, an exact procedure is proposed by solving a sequence of mixed-integer decomposed semidefinite optimization problems. Numerical results on classical benchmarking datasets are reported, showing the efficiency and effectiveness of our approach. |
| title | Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach |
| topic | Optimization and Control Machine Learning 90C22, 90C11 I.5.1; I.2.0 |
| url | https://arxiv.org/abs/2404.10099 |