Feature selection is of great importance in Machine Learning, where it can be used to reduce the dimensionality of classification, ranking and prediction problems. The removal of redundant and noisy features can improve both the accuracy and scalability of the trained models. However, feature selection is a computationally expensive task with a solution space that grows combinatorically. In this work, we consider in particular a quadratic feature selection problem that can be tackled with the Quantum Approximate Optimization Algorithm (QAOA), already employed in combinatorial optimization. First we represent the feature selection problem with the QUBO formulation, which is then mapped to an Ising spin Hamiltonian. Then we apply QAOA with the goal of finding the ground state of this Hamiltonian, which corresponds to the optimal selection of features. In our experiments, we consider seven different real–world datasets with dimensionality up to 21 and run QAOA on both a quantum simulator and, for small datasets, the 7–qubit IBM (ibm–perth) quantum computer. We use the set of selected features to train a classification model and evaluate its accuracy. Our analysis shows that it is possible to tackle the feature selection problem with QAOA and that currently available quantum devices can be used effectively. Future studies could test a wider range of classification models as well as improve the effectiveness of QAOA by exploring better performing optimizers for its classical step.
Feature selection is of great importance in Machine Learning, where it can be used to reduce the dimensionality of classification, ranking and prediction problems. The removal of redundant and noisy features can improve both the accuracy and scalability of the trained models. However, feature selection is a computationally expensive task with a solution space that grows combinatorically. In this work, we consider in particular a quadratic feature selection problem that can be tackled with the Quantum Approximate Optimization Algorithm (QAOA), already employed in combinatorial optimization. First we represent the feature selection problem with the QUBO formulation, which is then mapped to an Ising spin Hamiltonian. Then we apply QAOA with the goal of finding the ground state of this Hamiltonian, which corresponds to the optimal selection of features. In our experiments, we consider seven different real–world datasets with dimensionality up to 21 and run QAOA on both a quantum simulator and, for small datasets, the 7–qubit IBM (ibm–perth) quantum computer. We use the set of selected features to train a classification model and evaluate its accuracy. Our analysis shows that it is possible to tackle the feature selection problem with QAOA and that currently available quantum devices can be used effectively. Future studies could test a wider range of classification models as well as improve the effectiveness of QAOA by exploring better performing optimizers for its classical step.
As the volume of data for classification tasks in machine learning grows, feature selection plays an increasingly crucial role in enhancing the efficiency and effectiveness of these tasks. Existing classical feature selection algorithms often encounter challenges, such as high computational complexity and vulnerability to local optima. Quantum algorithms have been proposed to overcome these limitations. Here, our work proposes a new approach that combines the Quantum Approximate Optimization Algorithm (QAOA) with the classical feature selection algorithm Maximum Relevance-Minimum Redundancy (MRMR). First, we transform the feature selection problem into the Quadratic Unconstrained Binary Optimization (QUBO) problem. Then, we map the QUBO formulation to Hamiltonian with the Ising model. Finally, we employ QAOA with a shallow circuit to search this Hamiltonian's ground state, which matches the specific solution for feature selection. We conducted numerical experiments on eight real-world datasets for classification tasks from diverse domains, including finance, medicine, and natural hazards. Experiment results suggest that QAOA-selected feature subsets size are typically less than half the complete set while achieving comparable or better classification accuracy than classical MRMR, demonstrating its preference for smaller, more efficient feature subsets.
Feature selection is a common step in many ranking, classification, or prediction tasks and serves many purposes. By removing redundant or noisy features, the accuracy of ranking or classification can be improved and the computational cost of the subsequent learning steps can be reduced. However, feature selection can be itself a computationally expensive process. While for decades confined to theoretical algorithmic papers, quantum computing is now becoming a viable tool to tackle realistic problems, in particular special-purpose solvers based on the Quantum Annealing paradigm. This paper aims to explore the feasibility of using currently available quantum computing architectures to solve some quadratic feature selection algorithms for both ranking and classification.
One of the biggest obstacles to creating precise machine learning models is choosing representative and pertinent characteristics from big, unbalanced datasets. While too many features raise the risk of overfitting and computational expense, class imbalance frequently results in decreased accuracy and bias. The Simulated Annealing technique is used in this study to tackle a Quadratic Unconstrained Binary Optimization (QUBO) problem that is formulated as a quantum-assisted feature selection method to handle these problems. The technique seeks to reduce inter-feature redundancy and the number of selected features. There are 102,487 samples in the majority class and 11,239 in the minority class, totaling 28 characteristics in the experimental dataset. Nine ideal features were found during the feature selection method (12, 14, 15, 22, 23, 24, 25, 27, and 28). Ten-fold cross-validation was used to assess a Random Forest Classifier that was trained using an 80:20 split. With precision, recall, f1-score, and accuracy all hitting 1.00, the suggested QUBO+SMOTE method demonstrated exceptional performance. Comparatively, QUBO without SMOTE performed worse with accuracy 0.95 and minority-class f1-score of only 0.71, whereas a traditional Recursive Feature Elimination (RFE) approach obtained accuracy 0.97 with minority-class f1-score of 0.94. These findings indicate that QUBO can reduce dimensionality and address class imbalance which requires its integration with SMOTE. This study demonstrates how quantum computing can enhance the effectiveness and efficiency of machine learning, especially for large-scale imbalanced datasets
Feature selection is an essential step for reducing complexity of high dimensional data, usually in preparation for developing machine learning models such as computational biomarkers. However, there are limitations associated with feature selection such as for metabolomic data where there are hundreds or even thousands of features per study participant, while the available number of participants in a clinical trials is limited. Classical methods such as exhaustive search require evaluation of all possible feature combinations, making them costly in terms of computation and runtime, or even infeasible, as feature dimensionality increases. In this study, we propose a novel Quadratic Unconstrained Binary Optimization (QUBO) coefficient formulation and pose metabolomic feature selection as a QUBO problem that selects a specified number of features by balancing their relevance against redundancy among the selected variables. To evaluate our proposed QUBO objective function, we conducted a series of experiments using Bias-Field Digitized Counterdiabatic Quantum Optimization (BF-DCQO) and Quantum Approximate Optimization Algorithm (QAOA) on a quantum gate based computer. We also compared the method to several classical methods on three metabolomic datasets associated with Autism Spectrum Disorder (ASD) on a classical computer. Our method reduces runtime compared with exhaustive search and Iterative Tabu Search (ITS) and achieves competitive performance across classifiers compared to classical filter, wrapper, and embedded methods. These results do not claim quantum advantage; rather, they establish hardware feasibility and demonstrate the current capabilities of Noisy Intermediate-Scale Quantum (NISQ) devices.
Abstract The Quantum approximate optimization algorithm (QAOA) constitutes one of the often mentioned candidates expected to yield a quantum boost in the era of near-term quantum computing. In practice, quantum optimization will have to compete with cheaper classical heuristic methods, which have the advantage of decades of empirical domain-specific enhancements. Consequently, to achieve optimal performance we will face the issue of algorithm selection, well-studied in practical computing. Here we introduce this problem to the quantum optimization domain. Specifically, we study the problem of detecting those problem instances of where QAOA is most likely to yield an advantage over a conventional algorithm. As our case study, we compare QAOA against the well-understood approximation algorithm of Goemans and Williamson on the Max-Cut problem. As exactly predicting the performance of algorithms can be intractable, we utilize machine learning (ML) to identify when to resort to the quantum algorithm. We achieve cross-validated accuracy well over 96%, which would yield a substantial practical advantage. In the process, we highlight a number of features of instances rendering them better suited for QAOA. While we work with simulated idealised algorithms, the flexibility of ML methods we employed provides confidence that our methods will be equally applicable to broader classes of classical heuristics, and to QAOA running on real-world noisy devices.
Abstract In machine learning, fewer features reduce model complexity. Carefully assessing the influence of each input feature on the model quality is therefore a crucial preprocessing step. We propose a novel feature selection algorithm based on a quadratic unconstrained binary optimization (QUBO) problem, which allows to select a specified number of features based on their importance and redundancy. In contrast to iterative or greedy methods, our direct approach yields higher-quality solutions. QUBO problems are particularly interesting because they can be solved on quantum hardware. To evaluate our proposed algorithm, we conduct a series of numerical experiments using a classical computer, a quantum gate computer, and a quantum annealer. Our evaluation compares our method to a range of standard methods on various benchmark data sets. We observe competitive performance.