1. The Lovász Hinge: A Novel Convex Surrogate for Submodular Losses
- Author
-
Jiaqian Yu, Matthew B. Blaschko, Centre de vision numérique (CVN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec, Organ Modeling through Extraction, Representation and Understanding of Medical Image Content (GALEN), Ecole Centrale Paris-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), CentraleSupélec, Departement Elektrotechniek - ESAT [leuven], Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Ecole Centrale Paris
- Subjects
Computation ,Hinge ,02 engineering and technology ,Oracle ,Submodular set function ,Combinatorics ,[STAT.ML]Statistics [stat]/Machine Learning [stat.ML] ,Statistics - Machine Learning ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,sub-modularity ,Mathematics ,computer.programming_language ,business.industry ,Applied Mathematics ,convex surrogate ,Regular polygon ,Pascal (programming language) ,loss function ,Computer Science - Learning ,Computational Theory and Mathematics ,Jaccard index score ,020201 artificial intelligence & image processing ,Computer Vision and Pattern Recognition ,Artificial intelligence ,business ,Lovász extension ,computer ,Software - Abstract
Learning with non-modular losses is an important problem when sets of predictions are made simultaneously. The main tools for constructing convex surrogate loss functions for set prediction are margin rescaling and slack rescaling. In this work, we show that these strategies lead to tight convex surrogates iff the underlying loss function is increasing in the number of incorrect predictions. However, gradient or cutting-plane computation for these functions is NP-hard for non-supermodular loss functions. We propose instead a novel surrogate loss function for submodular losses, the Lovasz hinge, which leads to $\mathcal {O}(p\; \log p)$ O ( p log p ) complexity with $\mathcal {O}(p)$ O ( p ) oracle accesses to the loss function to compute a gradient or cutting-plane. We prove that the Lovasz hinge is convex and yields an extension. As a result, we have developed the first tractable convex surrogates in the literature for submodular losses. We demonstrate the utility of this novel convex surrogate through several set prediction tasks, including on the PASCAL VOC and Microsoft COCO datasets.
- Published
- 2020