Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets

Adarsh Prasad, Stefanie Jegelka, Dhruv Batra

Research output: Contribution to journalConference articlepeer-review

42 Scopus citations

Abstract

To cope with the high level of ambiguity faced in domains such as Computer Vision or Natural Language processing, robust prediction methods often search for a diverse set of high-quality candidate solutions or proposals. In structured prediction problems, this becomes a daunting task, as the solution space (image labelings, sentence parses, etc.) is exponentially large. We study greedy algorithms for finding a diverse subset of solutions in structured-output spaces by drawing new connections between submodular functions over combinatorial item sets and High-Order Potentials (HOPs) studied for graphical models. Specifically, we show via examples that when marginal gains of submodular diversity functions allow structured representations, this enables efficient (sub-linear time) approximate maximization by reducing the greedy augmentation step to inference in a factor graph with appropriately constructed HOPs. We discuss benefits, tradeoffs, and show that our constructions lead to significantly better proposals.

Original languageEnglish
Pages (from-to)2645-2653
Number of pages9
JournalAdvances in Neural Information Processing Systems
Volume3
Issue numberJanuary
StatePublished - 2014
Externally publishedYes
Event28th Annual Conference on Neural Information Processing Systems 2014, NIPS 2014 - Montreal, Canada
Duration: 8 Dec 201413 Dec 2014

Fingerprint

Dive into the research topics of 'Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets'. Together they form a unique fingerprint.

Cite this