SparseMAP: Differentiable Sparse Structured Inference

  • 2018-06-20 16:09:16
  • Vlad Niculae, AndrĂ© F. T. Martins, Mathieu Blondel, Claire Cardie
  • 1

Abstract

Structured prediction requires searching over a combinatorial number ofstructures. To tackle it, we introduce SparseMAP: a new method for sparsestructured inference, and its natural loss function. SparseMAP automaticallyselects only a few global structures: it is situated between MAP inference,which picks a single structure, and marginal inference, which assignsprobability mass to all structures, including implausible ones. Importantly,SparseMAP can be computed using only calls to a MAP oracle, making itapplicable to problems with intractable marginal inference, e.g., linearassignment. Sparsity makes gradient backpropagation efficient regardless of thestructure, enabling us to augment deep neural networks with generic and sparsestructured 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.

 

Quick Read (beta)

loading the full paper ...