Timezone: »

 
Poster
Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets
Adarsh Prasad · Stefanie Jegelka · Dhruv Batra

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

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.

[ PDF] 

Author Information

Adarsh Prasad (UT Austin)
Stefanie Jegelka (MIT)
Dhruv Batra (FAIR (Meta) / Georgia Tech)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors