Structured Prediction with Projection Oracles

Abstract

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.

In proceedings of NeurIPS 2019 (v2: minor modifications in Appendix A)

Cited by in corpus (9)

• Efficient and Modular Implicit Differentiation
• Gradient Estimation with Stochastic Softmax Tricks
• The Limited Multi-Label Projection Layer
• Fast Differentiable Sorting and Ranking
• Calibrated Surrogate Losses for Adversarially Robust Classification
• Learning with Fenchel-Young Losses
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings
• Sparse Continuous Distributions and Fenchel-Young Losses
• Surrogate Regret Bounds for Polyhedral Losses