THE MAX-MIN APPROACH TO FEATURE-SELECTION - ITS FOUNDATIONS AND PRACTICAL POTENTIAL

A feature set search method known as the Max-Min method is investigate d. It relies only on the merit of individual features as well as pairs of features. This aspect is considered very important because the com putational advantage of such an algorithm exploiting only at most pair wise interactions of measurements would be very useful for solving fea ture selection problems of very high dimensionality. By means of a det ailed analysis of the heuristic reasoning behind the method its weakne sses are identified. The first weakness is due to the use of upper lim it on the error bound as a measure of effectiveness of a candidate fea ture. This strategy does not guarantee that selecting a candidate feat ure with the highest upper bound will yield the highest actual amount of additional information. The second weakness is that the method does not distinguish between a strong unconditional dependence and a poor performance of a feature which both manifest themselves by a near zero additional discriminatory information. Modifications aimed at overcom ing the latter by favouring features which exhibit unconditional depen dence and on the other hand suppressing features which exhibit strong unconditional dependence have been proposed and tested but only with a limited success. For this reason the Max-Min method is subjected to a detailed theoretical analysis. It is found that the key assumption un derlying the whole Max-Min algorithm is not justified and the algorith m itself is ill-founded, i.e. the actual increment of the criterion va lue (or decrease of the probability of error) can be bigger than the m inimum of pairwise error probability reductions assumed by the Max-Min method. A necessary condition for invalidity of the key assumption of the Max-Min algorithm is derived, and a counter-example proving the l ack of justification for the algorithm is presented.