THE MINIMUM FEATURE SET PROBLEM

One approach to improving the generalization power of a neural net is to try to minimize the number of nonzero weights used. We examine two issues relevant to this approach, for single-layer nets. First we boun d the VC dimension of the set of linear-threshold functions that have nonzero weights for at most s of n inputs. Second, we show that the pr oblem of minimizing the number of nonzero input weights used (without misclassifying training examples) is both NP-hard and difficult to app roximate.