On the Generalization of the C-Bound to Structured Output Ensemble Methods
This work enables the development of new ensemble methods with PAC-Bayesian guarantees for structured output prediction, addressing a limitation in existing theory.
The paper generalizes the C-Bound from binary classification to ensemble methods for structured outputs, proving a generic version that applies to complex outputs like multiclass and multilabel predictions and allows margin relaxations.
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 \Cbound, 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.