The Structured Abstain Problem and the Lovász Hinge
This addresses a theoretical gap in machine learning for structured prediction tasks like image segmentation, providing corrected consistency results.
The paper resolves the open question of consistency for the Lovász hinge in structured binary classification, showing it is inconsistent unless the set function is modular, and introduces the structured abstain problem with consistent link functions for all submodular set functions.
The Lovász hinge is a convex surrogate recently proposed for structured binary classification, in which $k$ binary predictions are made simultaneously and the error is judged by a submodular set function. Despite its wide usage in image segmentation and related problems, its consistency has remained open. We resolve this open question, showing that the Lovász hinge is inconsistent for its desired target unless the set function is modular. Leveraging a recent embedding framework, we instead derive the target loss for which the Lovász hinge is consistent. This target, which we call the structured abstain problem, allows one to abstain on any subset of the $k$ predictions. We derive two link functions, each of which are consistent for all submodular set functions simultaneously.