Fast branch & bound algorithms for optimal feature selection

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• Optimal feature subset selection is critical for model performance and interpretability.
• Traditional Branch & Bound algorithms for feature selection can be computationally intensive due to exponential search spaces.

Purpose of the Study:

• To introduce a novel search principle for optimal feature subset selection using the Branch & Bound method.
• To improve the computational efficiency and speed of Branch & Bound algorithms for feature selection.

Main Methods:

• Development of a simple mechanism for predicting criterion values to avoid slow evaluations.
• Proposal of two implementations of the prediction mechanism for nonrecursive and recursive criterion forms.
• Investigation of factors influencing Branch & Bound algorithm performance, including feature diversity, stability, and criterion function dependence.

Main Results:

• The proposed algorithms consistently find the optimum several times faster than existing Branch & Bound methods.
• Algorithm speed is shown to depend significantly on feature diversity, feature stability, and criterion function dependence on subset size.
• Identification of scenarios leading to dramatically accelerated searches, including linear time completion.

Conclusions:

• The novel prediction mechanism substantially enhances the efficiency of Branch & Bound for optimal feature subset selection.
• Understanding feature and criterion properties is crucial for optimizing Branch & Bound search performance.
• The findings offer practical improvements for feature selection in machine learning and data mining applications.