Slack and Margin Rescaling as Convex Extensions of Supermodular Functions
Slack and margin rescaling are variants of the structured output SVM, which is frequently applied to problems in computer vision such as image segmentation, object localization, and learning parts based object models. They define convex surrogates to task specific loss functions, which, when specialized to non-additive loss functions for multi-label problems, yield extensions to increasing set functions. We demonstrate in this paper that we may use these concepts to define polynomial time convex extensions of arbitrary supermodular functions, providing an analysis framework for the tightness of these surrogates. This analysis framework shows that, while neither margin nor slack rescaling dominate the other, known bounds on supermodular functions can be used to derive extensions that dominate both of these, indicating possible directions for defining novel structured output prediction surrogates. In addition to the analysis of structured prediction loss functions, these results imply an approach to supermodular minimization in which margin rescaling is combined with non-polynomial time convex extensions to compute a sequence of LP relaxations reminiscent of a cutting plane method. This approach is applied to the problem of selecting representative exemplars from a set of images, validating our theoretical contributions.
Code (1)
Tasks
Image SegmentationObject LocalizationSemantic SegmentationStructured PredictionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
The Lovász Hinge: A Novel Convex Surrogate for Submodular Losses
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…
A Convex Surrogate Operator for General Non-Modular Loss Functions
Empirical risk minimization frequently employs convex surrogates to underlying discrete loss functions in order to achieve computational tractability during optimization. However, classical convex surrogates can only tig…
Fast and Scalable Structural SVM with Slack Rescaling
We present an efficient method for training slack-rescaled structural SVM. Although finding the most violating label in a margin-rescaled formulation is often easy since the target function decomposes with respect to the…
Remarks on equality of two distributions under some partial orders
In this note we establish some appropriate conditions for stochastic equality of two random variables/vectors which are ordered with respect to convex ordering or with respect to supermodular ordering. Multivariate exten…
Vocal Bursts Valence PredictionSupermodularity and valid inequalities for quadratic optimization with indicators
We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in g…
valid