Differentiable Dynamic Programming for Structured Prediction and Attention

Abstract

Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, DP algorithms are usually non-differentiable, which hampers their use as a layer in neural networks trained by backpropagation. To address this issue, we propose to smooth the max operator in the dynamic programming recursion, using a strongly convex regularizer. This allows to relax both the optimal value and solution of the original combinatorial problem, and turns a broad class of DP algorithms into differentiable operators. Theoretically, we provide a new probabilistic perspective on backpropagating through these DP operators, and relate them to inference in graphical models. We derive two particular instantiations of our framework, a smoothed Viterbi algorithm for sequence prediction and a smoothed DTW algorithm for time-series alignment. We showcase these instantiations on two structured prediction tasks and on structured and sparse attention for neural machine translation.

References in corpus (2)

• From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification
• Why Delannoy numbers?

Cited by in corpus (17)

• End to end learning and optimization on graphs
• Differentiable Divergences Between Time Series
• Cycle-skipping mitigation using misfit measurements based on differentiable dynamic time warping
• RePose: Learning Deep Kinematic Priors for Fast Human Pose Estimation
• Learning Classifiers with Fenchel-Young Losses: Generalized Entropies, Margins, and Algorithms
• Meta-Learning for Domain Generalization in Semantic Parsing
• Differentiable Greedy Networks
• Understanding Deep Architectures with Reasoning Layer
• Learning Discriminative Prototypes with Dynamic Time Warping
• Differentiable Spline Approximations
• Convex Regularization in Monte-Carlo Tree Search
• A Surrogate Objective Framework for Prediction+Optimization with Soft Constraints
• Sparse Continuous Distributions and Fenchel-Young Losses
• A PAC-Bayesian Perspective on Structured Prediction with Implicit Loss Embeddings
• Differentiable Robust LQR Layers
• Dynamic programming by polymorphic semiring algebraic shortcut fusion
• Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs