SparseMAP: Differentiable Sparse Structured Inference

Abstract

Structured prediction requires searching over a combinatorial number of structures. To tackle it, we introduce SparseMAP: a new method for sparse structured inference, and its natural loss function. SparseMAP automatically selects only a few global structures: it is situated between MAP inference, which picks a single structure, and marginal inference, which assigns probability mass to all structures, including implausible ones. Importantly, SparseMAP can be computed using only calls to a MAP oracle, making it applicable to problems with intractable marginal inference, e.g., linear assignment. Sparsity makes gradient backpropagation efficient regardless of the structure, enabling us to augment deep neural networks with generic and sparse structured hidden layers. Experiments in dependency parsing and natural language inference reveal competitive accuracy, improved interpretability, and the ability to capture natural language ambiguities, which is attractive for pipeline systems.

arXiv commentPublished in ICML 2018. 14 pages, including appendix

References in corpus (6)

• From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification
• DyNet: The Dynamic Neural Network Toolkit
• Learning Graphical Model Parameters with Approximate Marginal Inference
• A Regularized Framework for Sparse and Structured Neural Attention
• Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
• End-to-End Learning for Structured Prediction Energy Networks

Cited by in corpus (23)

• Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers
• Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data
• Efficient and Modular Implicit Differentiation
• Gradient Estimation with Stochastic Softmax Tricks
• Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties
• Sinkformers: Transformers with Doubly Stochastic Attention
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• The Limited Multi-Label Projection Layer
• Fast Differentiable Sorting and Ranking
• Flow-based Spatio-Temporal Structured Prediction of Motion Dynamics
• Efficient Marginalization of Discrete and Structured Latent Variables via Sparsity
• Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
• Understanding Multi-Head Attention in Abstractive Summarization
• LP-SparseMAP: Differentiable Relaxed Optimization for Sparse Structured Prediction
• Augmenting Neural Networks with First-order Logic
• Learning Randomly Perturbed Structured Predictors for Direct Loss Minimization
• Understanding Deep Architectures with Reasoning Layer
• Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels
• Sparse Communication via Mixed Distributions
• Proximal Mapping for Deep Regularization
• Constraining Linear-chain CRFs to Regular Languages
• Feature Clustering for Support Identification in Extreme Regions
• Using holistic event information in the trigger