On the Generalization of the C-Bound to Structured Output Ensemble Methods

Abstract

This paper generalizes an important result from the PAC-Bayesian literature for binary classification to the case of ensemble methods for structured outputs. We prove a generic version of the , an upper bound over the risk of models expressed as a weighted majority vote that is based on the first and second statistical moments of the vote's margin. This bound may advantageously (i) be applied on more complex outputs such as multiclass labels and multilabel, and (ii) allow to consider margin relaxations. These results open the way to develop new ensemble methods for structured output prediction with PAC-Bayesian guarantees.

Tasks

Reproductions