Structured Prediction with Projection Oracles
This work addresses the challenge of designing effective loss functions for structured prediction tasks in machine learning, offering a flexible approach that can be applied to various domains, though it is incremental in building on existing projection methods.
The authors tackled the problem of deriving loss functions for structured prediction by proposing a framework that uses projection oracles onto convex sets, automatically generating convex and smooth losses, and demonstrated improved accuracy in tasks like label ranking, ordinal regression, and multilabel classification.
We propose in this paper a general framework for deriving loss functions for structured prediction. In our framework, the user chooses a convex set including the output space and provides an oracle for projecting onto that set. Given that oracle, our framework automatically generates a corresponding convex and smooth loss function. As we show, adding a projection as output layer provably makes the loss smaller. We identify the marginal polytope, the output space's convex hull, as the best convex set on which to project. However, because the projection onto the marginal polytope can sometimes be expensive to compute, we allow to use any convex superset instead, with potentially cheaper-to-compute projection. Since efficient projection algorithms are available for numerous convex sets, this allows us to construct loss functions for a variety of tasks. On the theoretical side, when combined with calibrated decoding, we prove that our loss functions can be used as a consistent surrogate for a (potentially non-convex) target loss function of interest. We demonstrate our losses on label ranking, ordinal regression and multilabel classification, confirming the improved accuracy enabled by projections.