A Dynamic Programming Approach to the Selection of Pattern Features

Abstract

A method is presented for selecting a subset of features from a specified set when economic considerations prevent utilization of the complete set. The formulation of the feature selection problem as a dynamic programming problem permits an optimal solution to feature selection problems which previously were uncomputable. Although optimality is defined in terms of a particular measure, the Fisher return function, other criteria may be substituted as appropriate to the problem at hand. This mathematical model permits the study of interactions among processing time, cost, and probability of correctly classifying patterns, thus illustrating the advantages of dynamic programming. The natural limitation of the model is that the only features which can be selected are those supplied by its designer. Conceptually, the dynamic programming approach can be extended to problems in which several constraints limit the selection of features, but the computational difficulties become dominant as the number of constraints grows beyond two or three.