Differentiable Dynamic Programming for Structured Prediction and Attention

Arthur Mensch; Mathieu Blondel

Source-linked AI summary

Differentiable Dynamic Programming for Structured Prediction and Attention

Arthur Mensch, Mathieu Blondel

arXiv:1802.03676v2Feb 11, 2018stat.MLcs.LG

TL;DR

Dynamic programs are often non-differentiable, limiting their use as backpropagated neural-network layers. This paper smooths their max recursions with strongly convex regularizers, producing differentiable operators whose gradients represent relaxed solutions, and develops Viterbi and DTW instantiations for structured prediction and attention.

Problem
Dynamic-program solutions can be discontinuous and their optimal values non-differentiable, limiting their use in models trained by gradient descent.
Method
The paper replaces dynamic-program max operations with strongly-convex-regularized smoothed max operators and derives efficient differentiation through the resulting operators and gradients.
Results
The framework yields convex, differentiable, tractable dynamic-program operators with probabilistic gradient interpretations, including smoothed Viterbi and DTW instantiations.
Takeaways & Limitations
Different regularizers control the relaxed output distribution, with squared ℓ2 regularization providing sparse expected outputs and negentropy preserving associativity.
Takeaways & Limitations
For general strongly convex regularizers, solving the globally smoothed optimization problem can be intractable when the output space is exponential.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the non-differentiability of dynamic programs by smoothing their max operations, yielding differentiable operators and relaxed solutions for neural networks. It develops a unified framework, instantiates it for Viterbi and DTW, and applies both to structured prediction and neural machine translation attention.

1 Introduction: Optimization-based layers are motivated by the need to encode relevant input regularities or impose prior structure on neural-network outputs.The introduction places these layers within broader neural architectures composed of nested functions.
1 Introduction: Dynamic programs are difficult to use in gradient-trained models because their optimal solutions can be discontinuous and their values non-differentiable.Non-unique optima prevent differentiability, while hard solution mappings have null or undefined derivatives.
1 Introduction: Smoothing dynamic-program max operations with a strongly convex regularizer yields differentiable DP operators that can be trained end-to-end.The framework replaces (max, +) with (max_Ω, +) and supports backpropagation through both the operator and its gradient.
1 Introduction: The framework interprets gradients of smoothed DP operators as expected trajectories of random walks, providing continuous relaxations of discrete solutions.Negative entropy recovers CRF-based methods, whereas squared ℓ2 regularization produces sparse expected solutions.
1 Introduction: The paper derives smoothed Viterbi for sequence prediction and smoothed DTW for supervised time-series alignment, then evaluates them on structured prediction and neural machine translation attention.The DTW instantiation is illustrated in Figure 1.

2 Smoothed max operators

The paper smooths the max operator using strongly convex regularizers, obtaining smooth convex operators whose gradients provide relaxed solutions. Negentropy and squared ℓ2 regularization yield different computational and sparsity properties.

2 Smoothed max operators: A strongly convex regularizer defines a smoothed max operator that is differentiable everywhere with a Lipschitz-continuous gradient.The smoothed max is the convex conjugate of the regularizer restricted to the simplex.
2 Smoothed max operators: The smoothed max satisfies boundedness, distributivity of addition, and permutation-based commutativity under the stated regularizer conditions.These properties support its use within dynamic-programming recursions.
2 Smoothed max operators: Negentropy produces log-sum-exp and softmax, while squared ℓ2 regularization produces sparse gradients.Log-sum-exp additionally satisfies associativity, making negentropy natural for dynamic programming.

3 Differentiable DP layers

The section turns dynamic programs on DAGs into smooth, tractable layers by replacing max operations with strongly-convex-regularized alternatives. These layers provide differentiable value and relaxed solution operators whose gradients are expected paths and remain computable in O(|E|).

3.1 Dynamic programming on a DAG: Dynamic programming computes the highest-scoring path in a weighted DAG through an O(|E|) topologically ordered pass, rather than enumerating exponentially many paths.The recursion is optimal because the max operator satisfies distributivity and associativity requirements.
3.1 Dynamic programming on a DAG: The original linear-program value is nondifferentiable when optimal paths are nonunique, while its argmax path is discontinuous and unusable in gradient-descent models.This limits training to subgradient methods and prevents direct use of the discrete solution as a differentiable layer.
3.2 Smoothed max layers: Replacing max locally in the dynamic-programming recursion yields a smooth, tractable operator DP_Ω whose value approximates the original optimal-path problem.Unlike globally smoothed linear programs, the local recursion remains tractable by evaluating nodes in topological order.
3.2 Smoothed max layers: For separable regularizers, DP_Ω equals the globally smoothed value only for entropic regularization, whose vanishing scale recovers the original optimum.Entropic smoothing also inherits associativity, explaining its compatibility with recursive dynamic programming.
3.3 Relaxed argmax layers: The gradient ∇DP_Ω is an expected path in conv(Y), providing a continuous relaxation of the highest-scoring path while remaining computable by reverse-mode backpropagation in O(|E|).With squared ℓ2 regularization, the expected-path gradient is typically sparse; with negative entropy, it corresponds to a Gibbs distribution.
3.3 Relaxed argmax layers: The proposed DP_Ω layer is smooth, convex, tractable, and its gradient supplies a sound relaxation of the original path solution.Backpropagating through the layer requires applying its Hessian to an incoming matrix rather than explicitly forming the full Jacobian.

6 Structured and sparse attention

Structured attention extends segmentation attention to general regularizers and computes attention weights from smoothed dynamic-programming marginals. In French-to-English translation, ℓ2 regularization yields sparse, more interpretable maps while maintaining comparable translation performance.

Structured attention layers: Structured attention models transitions between input elements with a linear-chain model and derives attention weights from normalized marginal probabilities.The generalization replaces the CRF-specific construction with marginals induced by an arbitrary regularizer.
Experiments: Figure 4 shows that both regularizations produce the same translation in the example, but ℓ2 attention is sparser and more interpretable.
Generalizing structured attention: Gradients through the structured attention operator can be computed with a more general and simpler method that is more robust to underflow than forward-backward backpropagation.
Experiments: ℓ2-regularized attention maps are sparse and more interpretable, while standard softmax, entropy, and ℓ2 results remain within 0.8 BLEU on newstest2014.For French-to-English translation, standard softmax obtains 27.96 BLEU, while entropy and ℓ2 regularization obtain 27.96 and 27.19.

7 Conclusion

The paper frames strongly convex smoothing as a way to make dynamic programs convex, differentiable, and tractable while retaining structured interpretations. It connects gradients to probabilistic outputs and identifies regularization choices with distinct approximation and sparsity properties.

Conclusion: The framework turns a broad class of dynamic programs into convex, differentiable, and tractable operators by smoothing their max recursions.
Conclusion: Gradients of smoothed dynamic programs can be interpreted as expected trajectories, providing continuous and probabilistic relaxations of hard structured solutions.
Conclusion: Negentropy uniquely preserves associativity of the smoothed max operator, whereas squared ℓ2 regularization provides sparser expected outputs.
Conclusion: The framework supports inference in graphical models and backpropagation through relaxed maximum-likelihood objectives using first- and second-order derivatives.

A.3 Proof of Proposition 2 (properties of DPΩ(θ))

The proof establishes structural properties of the smoothed dynamic-programming operator, including convexity, approximation bounds, and the special role of negative entropy. It also contrasts tractable recursive DP smoothing with generally intractable global relaxed optimization.

Properties of DPΩ(θ): DPΩ is convex, while its value is bounded relative to the original dynamic-programming and linear-programming objectives by regularizer-dependent constants.
Properties of DPΩ(θ): Negative entropy is exactly the regularizer for which the smoothed local DP equals the globally relaxed objective, because its smoothed max is associative.
Properties of DPΩ(θ): The globally relaxed objective and its gradient are generally intractable when the set of structures has exponential size, despite the gradient lying in the convex hull of feasible paths.

A.5 Proof of Proposition 3 (computation of ∇DPΩ(θ))

The proof derives reverse-mode recursions for gradients of smoothed dynamic programs and identifies those gradients with expectations under an associated random walk. The resulting algorithms retain dynamic-programming complexity for sequence and alignment operators.

Proof of gradient computation: Gradient entries are computed by a two-step recursion in reverse topological order, initialized from the terminal node.
Proof of gradient computation: The gradient ∇DPΩ(θ) equals the expected trajectory of a random walk whose transition probabilities are the local smoothed-max gradients.
Regularizer-specific computation: Squared ℓ2 smoothing uses simplex projection and tends to produce sparse gradients, supporting sparse attention mechanisms.
Smoothed Viterbi: For the smoothed Viterbi computation, values, gradients, directional derivatives, and Hessian-vector products all use O(TS^2) time.
Smoothed DTW: The smoothed DTW operator generalizes soft-DTW to arbitrary strongly convex regularizers and adds computation of Hessian-vector products.

C Experimental details and further results

The supplementary experiments visualize how entropy and ℓ2 regularization produce different test predictions. ℓ2 regularization yields sparse outputs that make ambiguities easier to inspect.

Figure 6 compares test predictions produced with entropy and ℓ2 regularization.
ℓ2 regularization produces sparse predictions that make ambiguous outputs easier to identify.The accompanying examples show that sparse outputs can expose a finite set of plausible predictions.
Entropy regularization yields dense probability vectors, unlike the sparse outputs produced by ℓ2 regularization.

C.1 Named entity recognition (section §5.2)

The experiments examine regularized NER predictions and visualize their interpretability, while additional alignment results compare the proposed model with a baseline. ℓ2 regularization produces sparse tag probabilities that support explicit ambiguity inspection.

Named entity recognition: The convex surrogate loss and log likelihood are strongly prone to overfitting, requiring small batches and vanilla SGD with a large step size.Accelerated stochastic optimizers had lower generalization performance than SGD for all losses.
Further visualization: The end-to-end trained model qualitatively produces better score-onset alignment maps than the baseline on Bach10 test data.
Named entity recognition: ℓ2 regularization produces sparse tag probabilities that expose a finite set of candidate tag sequences for ambiguous entities.For “Union Bank of Switzerland,” the model proposes two tag sequences, whereas negentropy assigns nonzero probability to every sequence.

C.3 Structured and sparse attention (section §6)

The structured attention experiments evaluate model speed, translation quality, and attention sparsity. The results indicate that adding structure and sparsity does not hinder general translation performance, while ℓ2 regularization yields sparse attention patterns.

With too small a temperature parameter γ, the smoothed Viterbi operator reduces to unregularized MAP estimation and has zero derivatives.
Negentropy-regularized attention runs at approximately 7500 tokens/s, compared with 15000 tokens/s for softmax attention.
The ℓ2-regularized attention model runs at approximately 5000 tokens/s, or one-third the speed of softmax attention.The implementation discussion notes that lower-level kernel rewrites could improve this speed.
ℓ2 regularization uncovers sparse attention patterns in translation examples.Figure 8 illustrates these sparsity patterns on Newstest2014 test samples.