SparseMAP: Differentiable Sparse Structured Inference

By Vlad Niculae, André F. T. Martins, Mathieu Blondel, Claire Cardie. 2018

133 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Implicit Behavioral Cloning (2021, background): “Many other works have investigated using the notion of implicit functions in 225 learning, including works that investigate implicit layers [39, 40, 41, 42].”
Deep Equilibrium Models (2019, background): “There has been a growing interest in implicit layers in recent years [37, 3, 37, 50], but the precise formulation of the DEQ is quite different, and our current models represent the largest-scale practical application of implicit layers in deep learning of which we are aware.”
Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization (2018, background): “Our work is also related to recent research in structured prediction (Belanger, Yang, and McCallum 2017; Tu and Gimpel 2018; Niculae et al. 2018; Djolonga and Krause 2017). which aims to make a prediction lying in a discrete set.”
Learning Classifiers with Fenchel-Young Losses: Generalized Entropies, Margins, and Algorithms (2018, background): “This paper studies and extends Fenchel-Young (F-Y) losses, recently proposed for structured prediction (Niculae et al., 2018).”
Fast Differentiable Sorting and Ranking (2020, background): “Introducing quadratic regularization Q ( µ ) := µ 2 is considered by Martins & Astudillo (2016) over the unit simplex and by Niculae et al. (2018) over marginal polytopes.”
Sparse Sequence-to-Sequence Models (2019, methodology): “Niculae et al. (2018) use sparsity to predict interpretable sets of structures.”
Understanding Multi-Head Attention in Abstractive Summarization (2019, methodology): “Sparsity has been used to improve the interpretability of single-head attention architectures (Malaviya et al., 2018; Deng et al., 2018; Niculae et al., 2018).”
Gradient Estimation with Stochastic Softmax Tricks (2020, background): “[62] Vlad Niculae, André FT Martins, Mathieu Blondel, and Claire Cardie.”
Learning Binary Trees via Sparse Relaxation (2020, background): “This situation arises in as diverse scenarios as hyperparameter optimization (Pedregosa, 2016), meta-learning (Rajeswaran et al., 2019), or structured prediction (Stoyanov et al., 2011; Domke, 2013; Niculae et al., 2018).”
Latent Alignment and Variational Attention (2018, background): “Recent work has combined neural attention with traditional alignment [18, 72] and induced structure/sparsity [48, 33, 44, 85, 54, 55, 49], which can be combined with the variational approaches outlined in this paper.”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “, 2019), sparse inference (Niculae et al., 2018), or submodular maximization (Tschiatschek et al.”
Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data (2019, background): “…softmax and its sparsity-enforcing alternative sparsemax (Martins & Astudillo, 2016), which has already received signiﬁcant attention in a wide range of applications: probabilistic inference, topic modeling, neural attention (Niculae & Blondel, 2017; Niculae et al., 2018; Lin et al., 2019).”
Efficient and Modular Implicit Differentiation (2021, methodology): “We now show that the KKT conditions, manually differentiated in several works [19, 35, 6, 53, 52], fit our framework.”