Structured Prediction with Abstention via the Lovász Hinge
This work solves a theoretical gap in structured prediction for tasks like image segmentation, offering a framework for selective abstention to improve interpretability, though it is incremental in building on prior embedding methods.
The paper addresses the inconsistency of the Lovász hinge loss in binary structured classification and identifies that it is consistent only for modular set functions, leading to a new structured abstain problem that allows abstention on subsets of predictions. It provides consistent link functions for polymatroids and demonstrates experimental potential for interpretability, with extensions to multiclass settings.
The Lovász hinge is a convex loss function proposed for binary structured classification, in which k related binary predictions jointly evaluated by a submodular function. Despite its prevalence in image segmentation and related tasks, the consistency of the Lovász hinge has remained open. We show that the Lovász hinge is inconsistent with its desired target unless the set function used for evaluation is modular. Leveraging the embedding framework of Finocchiaro et al. (2024), we find the target loss for which the Lovász hinge is consistent. This target, which we call the structured abstain problem, is a variant of selective classification for structured prediction that allows one to abstain on any subset of the k binary predictions. We derive a family of link functions, each of which is simultaneously consistent for all polymatroids, a subset of submodular set functions. We then give sufficient conditions on the polymatroid for the structured abstain problem to be tightly embedded by the Lovász hinge, meaning no target prediction is redundant. We experimentally demonstrate the potential of the structured abstain problem for interpretability in structured classification tasks. Finally, for the multiclass setting, we show that one can combine the binary encoding construction of Ramaswamy et al. (2018) with our link construction to achieve an efficient consistent surrogate for a natural multiclass generalization of the structured abstain problem.