Differentiable Greedy Networks

Abstract

Optimal selection of a subset of items from a given set is a hard problem that requires combinatorial optimization. In this paper, we propose a subset selection algorithm that is trainable with gradient-based methods yet achieves near-optimal performance via submodular optimization. We focus on the task of identifying a relevant set of sentences for claim verification in the context of the FEVER task. Conventional methods for this task look at sentences on their individual merit and thus do not optimize the informativeness of sentences as a set. We show that our proposed method which builds on the idea of unfolding a greedy algorithm into a computational graph allows both interpretability and gradient-based training. The proposed differentiable greedy network (DGN) outperforms discrete optimization algorithms as well as other baseline methods in terms of precision and recall.

arXiv commentWork in progress and under review

References in corpus (9)

• Adam: A Method for Stochastic Optimization
• Categorical Reparameterization with Gumbel-Softmax
• Enriching Word Vectors with Subword Information
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures
• Maximal Sparsity with Deep Networks?
• Differentiable Dynamic Programming for Structured Prediction and Attention
• Interpretable Recurrent Neural Networks Using Sequential Sparse Recovery
• End-to-end Learning of LDA by Mirror-Descent Back Propagation over a Deep Architecture

Cited by in corpus (1)

• Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications