# SparseMAP: Differentiable Sparse Structured Inference

arXiv: https://arxiv.org/abs/1802.04223 · HTML: https://mlsanity.com/paper/1802.04223/

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2018.

## Built on by (most cited first, 30 of 62)

- [Implicit Behavioral Cloning](https://mlsanity.com/paper/2109.00137/) (2021)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [BayesDAG: Gradient-Based Posterior Inference for Causal Discovery](https://mlsanity.com/paper/2307.13917/) (2023)
- [Is Sparse Attention more Interpretable?](https://mlsanity.com/paper/2106.01087/) (2021)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [Mechanistic?](https://mlsanity.com/paper/2410.09087/) (2024)
- [CREST: A Joint Framework for Rationalization and Counterfactual Text Generation](https://mlsanity.com/paper/2305.17075/) (2023)
- [LION: Implicit Vision Prompt Tuning](https://mlsanity.com/paper/2303.09992/) (2023)
- [SPECTRA: Sparse Structured Text Rationalization](https://mlsanity.com/paper/2109.04552/) (2021)
- [Structured Reordering for Modeling Latent Alignments in Sequence Transduction](https://mlsanity.com/paper/2106.03257/) (2021)
- [Modeling Hierarchical Structures with Continuous Recursive Neural Networks](https://mlsanity.com/paper/2106.06038/) (2021)
- [Sparse and Structured Hopfield Networks](https://mlsanity.com/paper/2402.13725/) (2024)
- [Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Models](https://mlsanity.com/paper/2209.04862/) (2022)
- [Neuro-algorithmic Policies enable Fast Combinatorial Generalization](https://mlsanity.com/paper/2102.07456/) (2021)
- [Storchastic: A Framework for General Stochastic Automatic Differentiation](https://mlsanity.com/paper/2104.00428/) (2021)
- [Constraint-Free Structure Learning with Smooth Acyclic Orientations](https://mlsanity.com/paper/2309.08406/) (2023)
- [Differentiation Through Black-Box Quadratic Programming Solvers](https://mlsanity.com/paper/2410.06324/) (2024)
- [Learning Constraints and Descriptive Segmentation for Subevent Detection](https://mlsanity.com/paper/2109.06316/) (2021)
- [DAG Learning on the Permutahedron](https://mlsanity.com/paper/2301.11898/) (2023)
- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [Learning from Executions for Semantic Parsing](https://mlsanity.com/paper/2104.05819/) (2021)
- [Robust Multi-Object Tracking by Marginal Inference](https://mlsanity.com/paper/2208.03727/) (2022)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Constraining Linear-chain CRFs to Regular Languages](https://mlsanity.com/paper/2106.07306/) (2021)
- [Evidential Softmax for Sparse Multimodal Distributions in Deep Generative Models](https://mlsanity.com/paper/2110.14182/) (2021)

## Abstract (arXiv)

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.