Abstract
Structured prediction requires searching over a combinatorial number ofstructures. To tackle it, we introduce SparseMAP, a new method for sparsestructured inference, together with corresponding loss functions. SparseMAPinference is able to automatically select only a few global structures: it issituated between MAP inference, which picks a single structure, and marginalinference, which assigns probability mass to all structures, includingimplausible ones. Importantly, SparseMAP can be computed using only calls to aMAP oracle, hence it is applicable even to problems where marginal inference isintractable, such as linear assignment. Moreover, thanks to the solutionsparsity, gradient backpropagation is efficient regardless of the structure.SparseMAP thus enables us to augment deep neural networks with generic andsparse structured hidden layers. Experiments in dependency parsing and naturallanguage inference reveal competitive accuracy, improved interpretability, andthe ability to capture natural language ambiguities, which is attractive forpipeline systems.