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.

通过在组合项集上应用子模函数和高阶潜力，探索用于在结构化输出空间中找到多元解法子集的贪心算法，将贪心增广步骤降低到带有适当构造的高阶潜力的因子图推理中，以实现高效近似最大化。