Sample Compress & Kernel Methods

A PAC-Bayes Sample Compression Approach to Kernel Methods

Pascal Germain, Alexandre Lacoste, François Laviolette, Mario Marchand, and Sara Shanian. In ICML 2011.

Abstract: We propose a PAC-Bayes sample compression approach to kernel methods that can accommodate any bounded similarity function and show that the support vector machine (SVM) classifier is a particular case of a more general class of data-dependent classifiers known as majority votes of sample-compressed classifiers. We provide novel risk bounds for these majority votes and learning algorithms that minimize these bounds.