A MORE EFFICIENT BRANCH-AND-BOUND ALGORITHM FOR FEATURE-SELECTION

An algorithm is presented to be able to select the globally optimal su bset of d features from a larger D-feature set. This is a fundamental problem in statistical pattern recognition and combinatorial optimizat ion. Exhaustive enumeration is computationally unfeasible in most appl ications. This algorithm dynamically searches for the globally optimal solution on a minimum solution tree which is a subtree of the solutio n tree used in the traditional branch and bound algorithm. The new alg orithm is compared theoretically with the branch and bound algorithm. The analysis and the experimental results show that it is more efficie nt than the traditional algorithm.