The minimum feature subset selection problem

In applications of learning from examples to real-world tasks, feature subset selection is important to speed up training and to improve generalization performance. Ideally, an inductive algorithm should use subset of features as small as possible. In this paper however, the authors show that the problem of selecting the minimum subset of features is NP-hard. The paper then presents a greedy algorithm for feature subset selection. The result of running the greedy algorithm on hand-written numeral recognition problem is also given.