Part of Advances in Neural Information Processing Systems 15 (NIPS 2002)
Marina Sokolova, Mario Marchand, Nathalie Japkowicz, John Shawe-taylor
We introduce a new learning algorithm for decision lists to allow features that are constructed from the data and to allow a trade- oﬁ between accuracy and complexity. We bound its generalization error in terms of the number of errors and the size of the classiﬂer it ﬂnds on the training data. We also compare its performance on some natural data sets with the set covering machine and the support vector machine.