Heuristic Search Algorithm for Dimensionality Reduction Optimally Combining Feature Selection and Feature Extraction

Baokun He, Swair Shah, Crystal Maung, Gordon Arnold, Guihong Wan, Haim SchweitzerAAAI 2019 · DOI

Introduction

Dimensionality reduction is a cornerstone of machine learning, typically approached through either feature selection (choosing a subset of original features) or feature extraction (creating new, transformed features like PCA). While feature selection offers interpretability, feature extraction often yields higher accuracy. Practitioners frequently attempt to combine these by applying them sequentially—for instance, selecting features and then performing PCA.

However, research presented at AAAI-19 demonstrates that such sequential application is fundamentally sub-optimal. There exists a "hidden" optimal combination of selected and extracted features that independent steps cannot reach. This paper introduces the Hybrid Low Rank (HLR) representation, which optimally bridges this gap by framing dimensionality reduction as a combinatorial search problem.

The Hybrid Low Rank (HLR) Problem

The HLR problem aims to find a set of $r_1$ selected columns and $r_2$ extracted vectors from a matrix $X$ to minimize the overall reconstruction error. The core challenge is the massive combinatorial search space: for a dataset with $n$ features, there are $\binom{n}{r_1}$ possible subsets to evaluate.

To navigate this space, the authors treat the problem as a search over a subsets graph. In this graph, each node represents a specific subset of selected features, and edges represent the addition of a new feature.

The search space represented as a subset lattice graph.

Heuristic Search Strategy

The authors implement an A*-style "best-first" search using three variants of a heuristic function $f'(n)$:

  1. Optimal HLR ($f$): A lower-bound heuristic that guarantees finding the globally optimal solution.
  2. Greedy HLR ($u$): An upper-bound heuristic providing a fast, "best-guess" solution.
  3. Suboptimal HLR ($f + \epsilon u$): A weighted combination that allows users to trade off computation speed for accuracy, with a provable bound on the solution's distance from the optimum.

A key theoretical contribution is the "Sandwich" Property: the true optimal error is always bounded between the optimistic ($f$) and greedy ($u$) heuristics. This property allows the algorithm to effectively prune the search space, expanding only the most promising nodes.

Experimental Results and Efficiency

The HLR algorithm was evaluated on standard UCI datasets (e.g., vehicle, spectf) and high-dimensional text data (TechTC01).

Performance and Scalability

On the vehicle dataset, the heuristic search proved significantly more efficient than an exhaustive search. As shown in the performance plots, the time required for an exhaustive search grows exponentially with $r_1$, while the heuristic approach remains computationally tractable. Furthermore, the $f + u$ variant (greedy/suboptimal) provides massive speedups over the optimal $f$ heuristic while maintaining near-optimal accuracy.

Comparison of computation time between exhaustive search and heuristic variants.

On the high-dimensional TechTC01 dataset (over 29,000 features), where exhaustive search is impossible ($10^{288}$ combinations), the Greedy HLR provided solutions within 0.1% of the optimum. This demonstrates that the heuristics remain powerful even in extremely large search spaces.

Versatility and Interpretability

Unlike many existing methods limited to the Frobenius norm, this search framework is compatible with any unitarily invariant norm, including Spectral and Nuclear norms. This versatility, combined with the ability to explicitly balance $r_1$ interpretable features with $r_2$ extracted features, makes HLR a flexible tool for real-world data science.

Conclusion

By treating dimensionality reduction as a unified combinatorial problem, the HLR algorithm achieves superior reconstruction accuracy compared to traditional sequential methods. While computational complexity remains a challenge for non-unitarily invariant norms and memory-intensive fringe lists, the framework's provable optimality and error bounds mark a significant advancement in the field. Future work may extend these combinatorial techniques to other matrix factorization problems like Robust PCA.

Summary updated

BibTeX
@inproceedings{he2019heuristic,
  author = {Baokun He and Swair Shah and Crystal Maung and Gordon Arnold and Guihong Wan and Haim Schweitzer},
  title = {{Heuristic Search Algorithm for Dimensionality Reduction Optimally Combining Feature Selection and Feature Extraction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012280},
}
Figure