Novel GPU Boruta algorithms for feature selection from high-dimensional data

Technical Summary: Novel GPU Boruta Algorithms for Feature Selection from High-Dimensional Data

Problem Statement
Feature selection is a critical step in developing robust Artificial Intelligence for Science (AI4S) models, particularly in fields like bioinformatics and materials discovery where data exhibits high dimensionality and complex inter-feature correlations. While wrapper methods like the Boruta algorithm are effective at identifying relevant features by considering feature interactions, they suffer from high computational complexity. The original Boruta algorithm, which relies on Random Forests, has a time complexity proportional to the product of attributes and objects, making it inefficient for large-scale datasets when run on CPU-based platforms. This inefficiency limits the applicability of rigorous feature selection in modern high-dimensional scientific data analysis.

Methodology
To address the computational bottleneck, the authors propose two GPU-accelerated variants of the Boruta algorithm, leveraging the cuML library for Random Forest implementation on NVIDIA GPUs. Both variants retain the core logic of the original Boruta algorithm—comparing the importance of original features against randomized "shadow features"—but differ in how feature importance is quantified:

1. Boruta-TreeImp: This variant quantifies feature importance based on impurity reduction (Gini impurity or similar metrics) accumulated across all trees in the Random Forest. The algorithm accelerates the construction of the Random Forest on the GPU and calculates importance by traversing the tree structures to sum gain values.
2. Boruta-Permut: This variant quantifies feature importance based on permutation. It measures the change in model prediction error (Mean Squared Error for regression; KL divergence for classification probabilities) when feature values are randomly shuffled. This method is implemented entirely on the GPU to maximize parallelism during the prediction and loss calculation phases.

The authors provide a computational complexity analysis, noting that while both methods are dominated by the Random Forest training time $O(M \cdot m \cdot n \cdot \log n)$, the GPU parallelization significantly reduces wall-clock time. They observe that Boruta-TreeImp is generally more efficient for large feature sets ($m$), whereas Boruta-Permut may be preferable for smaller feature sets, though it incurs higher costs due to the need for $m$ separate predictions per iteration.

Key Contributions

• GPU Implementation: The successful adaptation of the Boruta wrapper method to GPU architectures using cuML, creating two distinct implementations (TreeImp and Permut).
• Cost-Effectiveness Analysis: A rigorous comparison of computational costs using cloud server rental prices, demonstrating that GPU execution is significantly cheaper than multi-core CPU execution for these tasks.
• Algorithmic Comparison: A detailed evaluation of the trade-offs between impurity-based and permutation-based importance metrics within the accelerated Boruta framework.

Experimental Results
The authors evaluated the proposed algorithms on a self-constructed synthetic dataset and four public datasets (CT, NEWS, ENERGY, MADELON), comparing them against the original CPU-based Boruta (scikit-learn) and the BorutaShap algorithm.

• Synthetic Data: On a dataset with 10 known relevant features and 40 noise features, both Boruta and Boruta-Permut correctly identified all 10 features. Boruta-TreeImp correctly identified 9, failing to select one feature (feature-18) which entered the objective function as a cube root. The authors attribute this to the known limitation of impurity-based importance, which can overestimate the importance of random features, leading to conservative selection in this specific context.
• Bias and Multicollinearity: Experiments showed that sample bias (scarce samples for a relevant feature) caused all algorithms to fail in selecting that feature. In the presence of multicollinearity, Boruta-Permut selected fewer redundant linearly correlated features compared to the original Boruta.
• Public Datasets: Across the CT, NEWS, ENERGY, and MADELON datasets, the GPU-accelerated versions maintained feature selection effectiveness comparable to the original Boruta (as measured by model performance metrics like MSE, MAE, $R^2$, and Accuracy).
• Efficiency Gains: The most significant finding was the reduction in time and cost. For example, on the NEWS dataset, the original Boruta took ~22 minutes (costing ~$1.77), while Boruta-TreeImp took ~7.5 minutes (costing ~$0.015). On the MADELON dataset, Boruta-TreeImp completed in under 5 minutes at a cost of ~$0.01, compared to ~10 minutes and ~$0.80 for the original.

Significance and Claims
The paper claims that performing Boruta feature selection on GPUs offers an effective and cost-efficient solution for large-scale data analysis. The authors emphasize that their methods "greatly improve computational efficiency while preserving feature selection accuracy comparable to the original Boruta algorithm."

The study modestly concludes that while the GPU acceleration solves the scalability issue, the choice between the two variants depends on the data characteristics. Specifically, they note that the impurity-based version (Boruta-TreeImp) can sometimes overestimate the importance of shadow features or miss features with complex, non-linear contributions (like the cube root example), suggesting that the permutation-based version (Boruta-Permut) may be more robust in certain scenarios despite higher computational overhead. The work positions these algorithms as a practical step toward enabling rigorous feature engineering for AI4S models handling massive datasets.