Structured prediction requires manipulating a large number of combinatorial structures, e.g., dependency trees or alignments, either as latent or output variables. Recently, the SparseMAP method has been proposed as a differentiable, sparse alternative to maximum a posteriori (MAP) and marginal inference. SparseMAP returns a combination of a small number of structures, a desirable property in some downstream applications. However, SparseMAP requires a tractable MAP inference oracle. This excludes, e.g., loopy graphical models or factor graphs with logic constraints, which generally require approximate inference. In this paper, we introduce LP-SparseMAP, an extension of SparseMAP that addresses this limitation via a local polytope relaxation. LP-SparseMAP uses the flexible and powerful domain specific language of factor graphs for defining and backpropagating through arbitrary hidden structure, supporting coarse decompositions, hard logic constraints, and higher-order correlations. We derive the forward and backward algorithms needed for using LP-SparseMAP as a hidden or output layer. Experiments in three structured prediction tasks show benefits compared to SparseMAP and Structured SVM.
翻译:结构化预测需要操纵大量的组合结构,例如依赖树或组合,作为潜在或产出变量。最近,提出了SparseMAP方法,作为最大后缘(MAP)和边际推断的一种不同、稀疏的替代物。SparseMAP 返回了少数结构的组合,这是某些下游应用中可取的属性。然而,SparseMAP需要一种可移动的MAP推理或触角。这不包括逻辑限制的循环图形模型或要素图,通常需要大致推理。在本文件中,我们采用了LP-SparseMAP,这是SparseMAP的延伸,通过本地的多极放松来应对这一限制。LP-SparseMAP使用灵活和强大的特定域语言,通过任意的隐藏结构来定义和反向调整要素图,支持粗化的分解、硬逻辑限制和更高级的对应关系。我们从三个结构化的MAPA中得出使用LP-SparseMAP所需的前向和落后算法,将Sp-VseMAP作为隐藏或输出层。