Part of Advances in Neural Information Processing Systems 17 (NIPS 2004)
Mario Marchand, Mohak Shah
We propose a “soft greedy” learning algorithm for building small conjunctions of simple threshold functions, called rays, deﬁned on single real-valued attributes. We also propose a PAC-Bayes risk bound which is minimized for classiﬁers achieving a non-trivial tradeoﬀ between sparsity (the number of rays used) and the mag- nitude of the separating margin of each ray. Finally, we test the soft greedy algorithm on four DNA micro-array data sets.