Abstract

We propose to construct a weighted majority vote on a set of basis functions by minimizing a risk bound (called the C-bound) that depends on the first two moments of the margin of the Q-convex combination realized on the data. This bound minimization algorithm turns out to be a quadratic program that can be efficiently solved. A first version of the algorithm is designed for the supervised inductive setting and turns out to be very competitive with AdaBoost, MDBoost and the SVM. The second version is designed for the transductive setting. It competes well against TSVM. We also propose a new PACBayes theorem that bounds the difference between the “true” value of the C-bound and its empirical estimate and that, unexpectedly, contains no KL-divergence.