Pass-efficient unsupervised feature selection

Crystal Maung, Haim SchweitzerNeurIPS 2013

Introduction

In the era of "Big Data," selecting a representative subset of features (columns) from a massive matrix is a fundamental task known as the Column Subset Selection Problem. The gold standard for this has long been the Pivoted QR algorithm (QRP) due to its numerical stability and deterministic nature.

However, QRP has a major bottleneck: to select $k$ features, it traditionally requires $k$ full passes over the data. For modern datasets where $k$ might be in the hundreds or thousands and the data is too large to fit in RAM (requiring slow Disk I/O), this $O(k)$ pass complexity is prohibitively expensive. While randomized algorithms have been proposed to solve this in fewer passes, they introduce a probability of failure and can sometimes be less stable.

To address this, researchers have introduced IQRP (Improved Pivoted QR), a deterministic algorithm that selects the exact same features as the classic Businger-Golub algorithm but with orders of magnitude better efficiency.

The Bottleneck of Traditional QRP

The classic approach to feature selection involves iteratively finding the feature that best approximates the remaining data.

Standard multi-pass feature selection algorithm

As seen in the standard multi-pass framework, selecting $k$ features requires $k$ distinct passes over the entire dataset. When data resides out-of-core, the I/O overhead of reading the matrix repeatedly becomes the primary bottleneck. IQRP seeks to fix the "pass-efficiency" of this deterministic process without altering its output.

The IQRP Algorithm: Methods and Innovations

IQRP optimizes the classic QRP using two primary insights: batching and pruning. Crucially, the authors provide a proof by induction that IQRP is mathematically equivalent to QRP—it doesn't just approximate the results; it produces the exact same feature set.

1. Batching with a Buffer ($L$)

Instead of picking just one "best" feature per pass, IQRP maintains a small buffer (list $L$) of size $l$. In a single pass, it identifies multiple candidate features that are difficult to approximate. It then performs a "local" QRP on this small buffer to select multiple features at once.

Exploiting the buffer L in IQRP

This local exploitation guarantees that the algorithm selects the same features the global QRP would have picked, but it does so without needing to scan the entire dataset again for each feature.

2. Pruning via Monotonicity

The error of approximating a feature only decreases as more features are added to the selection. IQRP uses a min-heap to track a threshold ($T$). If a feature's current approximation error is already lower than the threshold of the "best" candidates found so far, the algorithm skips the expensive orthogonalization steps for that feature in the current pass. This allows the algorithm to ignore the vast majority of the data in later passes.

Key Results and Performance

The algorithm was evaluated on four diverse real-world datasets: Day1 (URL reputation), thrombin (KDD Cup 2001), Amazon (commerce reviews), and gisette (NIPS 2003). The results demonstrate significant improvements:

  • Massive Speedups: On the "Day1" dataset ($20,000 \times 3,231,957$), IQRP reduced the number of floating-point operations (flops) by a factor of over 100 compared to the standard QRP.
  • Pass Efficiency: While the original QRP requires $k$ passes (e.g., 500 passes to pick 500 features), IQRP often required fewer than 10 passes in absolute terms.
  • Data Skipping (IO-Passes): The authors distinguish between a "pass" (looking at metadata) and an "IO-pass" (reading the heavy matrix data). In terms of IO-passes, the reduction sometimes reached a factor of 1,000x. For most datasets, the effective number of IO-passes was reduced to nearly 1 or 2.
  • Memory Footprint: The algorithm remains lean, requiring only $O(km + n)$ memory, making it ideal for systems with limited RAM.

Limitations and Future Directions

While IQRP proves that deterministic algorithms can achieve "randomized-like" speeds, it does have limitations. Some randomized "Volume Sampling" algorithms can theoretically produce more accurate feature subsets in terms of reconstruction error, albeit at a higher risk of failure or computational cost. Additionally, IQRP requires a user-defined parameter $l$ (buffer size); while $l=k$ works well generally, the optimal balance between buffer size and pass reduction may vary by dataset.

Future work could explore how IQRP's pass-efficient logic integrates with distributed frameworks like Spark or MapReduce, where minimizing data movement and passes is even more critical.

Summary updated

BibTeX
@inproceedings{maung2013pass,
  author = {Crystal Maung and Haim Schweitzer},
  title = {{Pass-efficient unsupervised feature selection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
}
Figure