TL;DR
This paper introduces a novel Branch and Bound algorithm for optimal feature selection that significantly outperforms existing methods in terms of computational efficiency. By leveraging monotonic distance measures to prune the search space, it efficiently identifies feature subsets that minimize Bayesian classification error, even for high-dimensional datasets.
What Problem Does This Paper Address?
Selecting the optimal subset of features for classification is a critical but computationally challenging problem. When dealing with a large number of features ($n$) and a desired subset size ($k$), the number of possible subsets ($n \choose k$) grows exponentially, making exhaustive search infeasible. Existing greedy approaches often fail to find the globally optimal subset, leading to suboptimal classification performance. The paper addresses the need for an efficient and guaranteed optimal feature selection method that can handle high-dimensional data.
Methods
The core of the paper is a Branch and Bound (B&B) algorithm designed for feature selection. Unlike previous B&B approaches that might use the classification error itself for pruning, this algorithm uses a Bhattacharyya distance as a monotonic and additive measure. This distance is computationally cheaper to calculate than the Bayesian error and satisfies properties that allow for effective pruning of the search space.
Here's a breakdown of the key methodological aspects:
- Statistical Model: The paper assumes a statistical model of two independent multivariate normal distributions for classification.
- Bhattacharyya Distance: This distance measure is chosen for its closed-form calculation, additivity (for independent features), and monotonicity. It serves as a lower bound for the Bayesian classification error.
- Branch and Bound Search: The algorithm explores a "subset tree" where each node represents a feature subset.
- Bounding: At each node, a lower bound on the Bayesian error for any subset within that subtree is computed using the Bhattacharyya distance.
- Pruning: If this lower bound is worse than the best error found so far, the entire subtree is pruned, avoiding unnecessary computations.
- Error Estimation: For evaluating terminal nodes (subsets of size $k$), the paper uses a Monte Carlo method to estimate the Bayesian classification error when exact computation is intractable. This estimation process dynamically adjusts the number of samples ($N$) required to achieve a desired accuracy ($\epsilon$) with a certain probability ($1-\delta$).
Datasets
The paper evaluates its algorithm on:
- Synthetic Data: Datasets were generated with varying proportions of high and low-distanced features to study the algorithm's pruning efficiency.
- Gene Expression Data:
- AML/ALL leukemia dataset: (7129 genes, 72 samples)
- ER+/ER- breast cancer dataset: (3389 genes, 58 samples) For gene expression data, the algorithm was used heuristically by first selecting the top 300 genes based on Bhattacharyya distance before applying the B&B search.
Key Insights and Ideas
- Distance as a Pruning Tool: The most significant insight is the effective use of a monotonic distance measure (Bhattacharyya) as a proxy for pruning in a Branch and Bound framework. This is computationally much cheaper than estimating the actual classification error for every node.
- Optimality Guarantee: Unlike greedy methods, the B&B approach with proper bounding guarantees finding the globally optimal feature subset (under the stated assumptions).
- Efficiency for High Dimensions: The algorithm's pruning capabilities make it practical for high-dimensional datasets where exhaustive search or even less aggressive B&B methods would fail.
- Greedy Algorithms are Suboptimal: The paper provides a clear example demonstrating how greedy feature selection can lead to suboptimal results, motivating the need for optimal search strategies.
- Trade-off in Error Estimation: The Monte Carlo error estimation highlights a trade-off between accuracy ($\epsilon, \delta$) and computational cost (number of samples $N$).
Key Results
- Significant Pruning: The algorithm achieved very high pruning rates (up to 99.91% on tested datasets), meaning a vast majority of feature subsets were not evaluated.
- Competitive Classification Performance: The selected subsets achieved classification success rates comparable to or better than previously published results on gene expression datasets.
- Computational Speedup: The proposed algorithm was significantly faster than the Narendra & Fukunaga (1977) B&B algorithm, especially when the desired subset size ($k$) was much smaller than the total number of features ($n$). For instance, on synthetic data, it was considerably faster for $k=3$ and $n=50$.
- Robustness: The algorithm's performance was analyzed across different error estimation accuracy parameters ($\epsilon, \delta$), showing that even with less stringent accuracy, the selected subsets still performed well.
Limitations and Future Work
- Statistical Model Assumption: The algorithm's optimality guarantee relies on the assumption of independent multivariate normal distributions. While the paper notes that the algorithm can be used heuristically for more complex scenarios (like gene expression data), its theoretical guarantees might not hold.
- Exact Pe Computation: The paper acknowledges that exact computation of Bayesian error is often intractable, necessitating the use of Monte Carlo estimation. This introduces a probabilistic element to the error evaluation.
- Future Work: The paper suggests that the algorithm can be extended to handle more complex statistical models and potentially non-monotonic criteria. Further investigation into the trade-offs of error estimation accuracy and computational cost is also implied.
Summary updated