Abstract
Subset selection, i.e., to select a limited number of items optimizing some given objective function, is a fundamental problem with various applications such as unsupervised feature selection and sparse regression. By employing a multi-objective evolutionary algorithm (EA) with mutation only to optimize the given objective function and minimize the number of selected items simultaneously, the recently proposed POSS algorithm achieves state-of-the-art performance for subset selection. In this paper, we propose the PORSS algorithm by incorporating recombination, a characterizing feature of EAs, into POSS. We prove that PORSS can achieve the optimal polynomial-time approximation guarantee as POSS when the objective function is monotone, and can find an optimal solution efficiently in some cases whereas POSS cannot. Extensive experiments on unsupervised feature selection and sparse regression show the superiority of PORSS over POSS. Our analysis also theoretically discloses that recombination from diverse solutions can be more likely than mutation alone to generate various variations, thereby leading to better exploration; this may be of independent interest for understanding the influence of recombination.
Introduction
Subset selection is a fundamental challenge in machine learning and data science: given a set of $n$ items, the goal is to pick a subset of size $k$ that maximizes a specific objective function $f$. This problem appears in various domains, including unsupervised feature selection and sparse regression. Because subset selection is NP-hard, researchers typically rely on greedy algorithms or evolutionary strategies.
A recent successful approach, POSS (Pareto Optimization for Subset Selection), treats this as a bi-objective problem: maximizing the objective function while simultaneously minimizing the subset size. However, POSS relies solely on mutation (randomly flipping bits). This paper introduces PORSS (Pareto Optimization with Recombination for Subset Selection), which incorporates recombination—the "crossover" of two different solutions—to improve efficiency and effectiveness.
Methodology
PORSS maintains a "Pareto front" of non-dominated solutions, where no solution can improve one objective without degrading the other. The reproduction step in PORSS follows a four-step process:
- Selection: Two parent solutions are randomly selected from the current population.
- Recombination: Offspring are created by mixing parents using either one-point recombination or uniform recombination.
- Mutation: Standard bit-wise mutation is applied to the offspring.
- Update: New solutions are added to the population if they are non-dominated, and any existing solutions that become dominated are pruned.
Theoretically, PORSS maintains the optimal polynomial-time approximation guarantee $(1 - e^{-\gamma})$ for monotone objective functions, where $\gamma$ is the submodularity ratio. Furthermore, recombination acts as a "jump" operator, allowing the algorithm to combine building blocks from diverse solutions and escape local optima that mutation alone might struggle to overcome.
Experimental Evaluation
The authors evaluated PORSS across 20 real-world datasets for two major applications: unsupervised feature selection (e.g., sonar, mnist, SVHN) and sparse regression (e.g., scene, cifar10). These datasets range from 60 to over 18,000 features.
Key Results
In head-to-head comparisons, PORSS (specifically the uniform recombination version) consistently outperformed POSS and greedy algorithms. On unsupervised feature selection, PORSS achieved an average rank of 1.40, significantly better than POSS (3.05) and the greedy algorithm (3.95).
As shown in the figure above, the error ratio for PORSS decreases more rapidly and reaches lower final values compared to POSS as the running time (measured in $kn$ evaluations) increases.
Robustness to Subset Size
The advantage of PORSS is not limited to specific subset sizes. The algorithm demonstrates consistent superiority across different values of $k$, the subset size budget.
Conclusion
PORSS improves upon the state-of-the-art POSS algorithm by integrating recombination into the Pareto optimization framework. This addition provides a theoretical and empirical advantage, allowing for better exploration of the search space and faster convergence to optimal solutions. While the current theoretical bounds focus on monotone functions, the empirical success across diverse datasets suggests broad applicability for complex subset selection tasks.
Summary updated