A PAC-Bayes approach to the Set Covering Machine

François Laviolette, Mario Marchand, Mohak Shah

Advances in Neural Information Processing Systems 18 (NIPS 2005)

We design a new learning algorithm for the Set Covering Ma- chine from a PAC-Bayes perspective and propose a PAC-Bayes risk bound which is minimized for classifiers achieving a non trivial margin-sparsity trade-off.