The minimum feature set problem

✍ Scribed by Kevin S. Van Horn; Tony R. Martinez

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 334 KB
• Volume: 7
• Category: Article
• ISSN: 0893-6080
• DOI: 10.1016/0893-6080(94)90082-5

✦ Synopsis

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 bound the VC dimension of the set of linear-threshold fimctions that have nonzero weights figr at most s of n inputs. Second, we show that the problem of minimizing the number of nonzero input weights used ( without misclassifving training examples) is both NP-hard and difficult to approximate.