Subset Selection by Pareto Optimization with Recombination

Chao Qian, Chao Bian, Chao FengAAAI 2020 · OpenReview

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:

  1. Selection: Two parent solutions are randomly selected from the current population.
  2. Recombination: Offspring are created by mixing parents using either one-point recombination or uniform recombination.
  3. Mutation: Standard bit-wise mutation is applied to the offspring.
  4. 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).

Performance comparison on 10 unsupervised feature selection datasets showing error ratio vs. running time.

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.

Performance comparison with varying subset size $k$ for unsupervised feature selection and sparse regression.

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

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.
BibTeX
@inproceedings{qian2020subset,
  author = {Chao Qian and Chao Bian and Chao Feng},
  title = {{Subset Selection by Pareto Optimization with Recombination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=HfPOsGcxHK4},
}
Figure