Oral
Differentiable Dynamic Programming for Structured Prediction and Attention
Arthur Mensch · Mathieu Blondel

Thu Jul 12th 11:20 -- 11:40 AM @ A5

Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, many DP algorithms are 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 structured prediction (audio-to-score alignment, NER) and on structured and sparse attention for translation.

Author Information

Arthur Mensch (Inria Parietal)
Mathieu Blondel (NTT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors