Structured Attention Networks

Yoon Kim; Carl Denton; Luong Hoang; Alexander M. Rush

Source-linked AI summary

Structured Attention Networks

Yoon Kim, Carl Denton, Luong Hoang, Alexander M. Rush

arXiv:1702.00887v3Feb 3, 2017cs.CLcs.LGcs.NE

TL;DR

The paper addresses how attention networks can model structural dependencies without abandoning end-to-end training. It embeds graphical-model distributions and differentiable inference into neural layers, and reports improvements over standard attention across synthetic and real tasks, alongside learned unsupervised structural representations.

Problem
Standard attention does not directly model structural dependencies, motivating richer structural distributions while retaining end-to-end training.
Method
The approach defines structured attention over graphical models, implementing linear-chain CRF and first-order dependency-parser layers with differentiable inference.
Results
Structured attention outperforms standard attention models across tree transduction, neural machine translation, question answering, and natural language inference, while learning interesting structural properties.
Takeaways & Limitations
Structured attention can provide soft selection over segments or latent subtrees and can learn latent labelers or parsers without annotated segmentations or parse trees.
Takeaways & Limitations
Backpropagating through inference is a practical complication, and structured attention was approximately 5× slower to train than simple attention in neural machine translation.

Abstract

from arXiv · show

Attention networks have proven to be an effective approach for embedding categorical inference within a deep neural network. However, for many tasks we may want to model richer structural dependencies without abandoning end-to-end training. In this work, we experiment with incorporating richer structural distributions, encoded using graphical models, within deep networks. We show that these structured attention networks are simple extensions of the basic attention procedure, and that they allow for extending attention beyond the standard soft-selection approach, such as attending to partial segmentations or to subtrees. We experiment with two different classes of structured attention networks: a linear-chain conditional random field and a graph-based parsing model, and describe how these models can be practically implemented as neural network layers. Experiments show that this approach is effective for incorporating structural biases, and structured attention networks outperform baseline attention models on a variety of synthetic and real tasks: tree transduction, neural machine translation, question answering, and natural language inference. We further find that models trained in this way learn interesting unsupervised hidden representations that generalize simple attention.

1 INTRODUCTION

Structured attention networks add explicit structural dependencies to attention layers while preserving differentiable training, extending attention toward segmentation and latent tree selection.

Standard attention does not directly model structural dependencies among source elements, instead relying on hidden network layers to learn them.
The paper develops internal structured layers that model these dependencies directly as a generalization of categorical soft-selection attention.
Structured attention views attention as inference in a graphical model over latent variables, with inference producing the context-vector expectation.
The approach builds on differentiable graphical-model inference to create structured internal attention layers and use their marginals as differentiable features.
The experiments use linear-chain CRFs and first-order graph-based dependency parsers, targeting synthetic reordering, translation, question answering, and natural language inference.
Structured-attention models outperform standard attention models and reveal learned internal structures without requiring segmented sentences or parse trees.

2 BACKGROUND: ATTENTION NETWORKS

Attention replaces fixed-vector compression with a variable-length memory and soft selection over source representations, formalized as an expectation over a latent categorical choice.

Standard networks create an information bottleneck by encoding an entire variable-length source sentence into a fixed-dimensional hidden representation.
Attention maintains hidden representations that scale with source size and performs an internal soft-selection over them.
Given inputs x, query q, and categorical latent variable z, the context c is the expectation of annotation f(x, z) under p(z | x, q).
The attention distribution and annotation function can be parameterized with neural networks, with the resulting context vector passed to a downstream network.
In neural machine translation, source RNN states form x, the decoder state forms q, and z selects the source position attended for translation.

3 STRUCTURED ATTENTION

Structured attention represents attention as inference over graphical models, allowing neural networks to softly select structured objects such as segments and dependency subtrees. Linear-chain CRFs and graph-based parsers provide differentiable attention layers that can be trained end-to-end.

Structured attention: Structured attention models attention as a CRF over multiple discrete latent variables, with graph edges encoding their independence structure.Clique potentials are produced by a neural model over x and q, and inference computes the attention expectation used as the context vector.
Subsequence selection: Segmentation attention uses binary latent variables and a linear-chain CRF to model contiguous subsequence selection while allowing multiple or no inputs to be selected.Forward-backward computes all marginals in linear time, implicitly summing over exponentially many binary sequences through dynamic programming.
Subsequence selection: A linear-chain CRF generalizes standard softmax attention by replacing vector normalization with differentiable forward-backward inference over pairwise potentials.Gradients can be computed through the marginals with respect to the potentials, enabling end-to-end training.
Syntactic tree selection: Syntactic attention applies graph-based dependency parsing to softly select parent words under one-head and projectivity constraints.Edge marginals can be computed in O(n^3) time with the inside-outside algorithm, producing a context vector for each word.
End-to-end training: Structured attention layers place graphical-model inference inside deep networks, enabling the whole model to train end-to-end without segmented or parsed supervision.The main implementation complication is backpropagating gradients through the inference algorithm; numerical stability requires signed log-space operations for the backward pass.

4 EXPERIMENTS

Across four tasks, structured attention layers incorporate segmentation or syntactic structure into end-to-end neural models. They improve over simpler attention baselines and learn useful latent structural representations, though gains vary by task.

Experimental scope: The experiments test structured attention on tree transduction, machine translation, question answering, and natural language inference.The models use syntactic attention for tree tasks and NLI, segmentation attention for translation, and an n-state CRF for multi-step QA.
4.1 TREE TRANSDUCTION: Structured attention significantly outperforms simple attention on the tree-transduction task and learns boundaries such as matching parentheses.The structured model is hypothesized to partially reconstruct the arithmetic tree, while Figure 3 shows attention weights from closing parentheses generally placed on opening parentheses.
4.2 NEURAL MACHINE TRANSLATION: Structured attention outperforms simple and sigmoid attention on both character-to-word and word-to-word translation tasks, although word-to-word gains are modest and unlikely to be statistically significant.Sigmoid attention performs better than simple attention for character-to-word translation, while the reverse holds for word-to-word translation.
4.2 NEURAL MACHINE TRANSLATION: On character-to-word translation, sigmoid and structured attention spread weights across contiguous character subsequences, supporting an implicit segmentation model.The structured model also learns additional parameters to smooth this attention pattern.
4.3 QUESTION ANSWERING: In question answering, Binary CRF attention recovers supporting fact sequences better than MemN2N, with improvements of up to two-fold on tasks 2, 11, 13, and 17.Higher supporting-fact sequence accuracy does not necessarily imply higher answer accuracy; all three models achieve 100% answer accuracy on task 15 despite differing fact accuracies.
4.4 NATURAL LANGUAGE INFERENCE: For natural language inference, structured attention outperforms simple attention and hard-parent baselines, while pretrained syntactic attention performs worse than training from scratch.The learned syntactic layer develops an almost plausible dependency structure without explicit parse-tree supervision, but makes errors such as assigning the determiner The to the wrong head.

5 CONCLUSION

Structured attention networks generalize simple attention with graphical models and improve performance across tasks, while adding computational cost. The framework also points toward differentiable embedded algorithms and latent structural representations.

Structured attention networks incorporate graphical models to generalize simple attention and support backpropagation through structured inference.The work implements linear-chain CRF and first-order dependency-parser attention layers.
Experiments show improvements over standard models across tree transduction, neural machine translation, question answering, and natural language inference.
5× slower training occurred for structured attention than simple attention in neural machine translation, despite identical O(n) asymptotic runtime.
Differentiable inference can extend beyond tractable exact inference to approximate inference and differentiable optimization algorithms.

A MODEL DETAILS

The syntactic attention layer models latent dependency-tree structure with neural scores and differentiable inside-outside inference. Parent probabilities are converted into soft-parent representations for downstream attention.

A bidirectional LSTM produces hidden states for each input word before syntactic attention scores dependency arcs.
An MLP assigns a score to each directed dependency arc xi → xj, where xi is the parent of xj.
Inside-outside inference converts arc scores into parent probabilities p(zij = 1 | x), which produce each word’s soft-parent representation.

A.2 TREE TRANSDUCTION

The tree-transduction model combines source and decoder representations through attention and predicts target symbols with an LSTM. Structured and simple variants use different source representations and fixed training settings.

The decoder LSTM combines hidden states with source representations through a bilinear attention map to obtain context vectors.
The model predicts the next target symbol with softmax(Vĥj + b) after combining the context vector with the decoder state.
Structured and simple models use distinct j-th source representations, with structured representations determined by θij from the parsing LSTM.
All experiments use l = 50, 50-dimensional parsing LSTMs, and shared symbol embeddings between encoder and parsing LSTMs.
Training uses 13 epochs, learning rate 1.0 with decay after epoch 9 or stalled validation performance, and beam size 5 decoding.

A.3 NEURAL MACHINE TRANSLATION

The neural machine translation implementation compares simple, Bernoulli, and structured attention within an LSTM encoder-decoder. Structured attention derives context from CRF marginals computed by forward-backward inference.

The baseline encoder is an LSTM over the source sentence, while the decoder is another LSTM producing target-step hidden states.
Simple categorical attention uses a bilinear map to combine hidden states with input representations and form each context vector.
Bernoulli attention replaces categorical normalization with sigmoid weights for a linear combination.
Structured attention parameterizes unary and pairwise CRF potentials, then uses forward-backward inference to obtain normalized marginals and context vectors.
The encoder and decoder LSTMs have 2 layers and 500 hidden units, with dropout probability 0.3 and beam size 5 decoding.

A.4 QUESTION ANSWERING

The question-answering models compare a MemN2N-style baseline with unary and binary CRF attention layers. These structured models compute context vectors from learned marginals over latent fact selections.

Baseline architecture: The baseline represents a sequence of facts and a query with embeddings in a multi-hop MemN2N architecture.The full model uses K hops, tied embedding matrices, and a distribution over the answer vocabulary.
Structured attention: Unary and binary CRF variants use the same fact and query representations as the baseline while parameterizing structured attention potentials.The binary model additionally uses pairwise potentials between adjacent latent selections.
Structured attention: The binary CRF discourages selecting the same fact again by setting adjacent self-transition potentials to −∞.Its forward-backward marginals are then used to compute the context vector.
Context computation: When the annotation function factors over latent components, the context vector can be computed from the corresponding marginal distributions.This replaces summation over complete latent assignments with marginal evaluation for the factored components.
Training setup: Training uses stochastic gradient descent with a decaying learning rate, a 25-sentence memory capacity, 20-dimensional embeddings, and gradient renormalization above 40.The setup also includes position encoding, temporal encoding, and linear start.

A.5 NATURAL LANGUAGE INFERENCE

The natural-language-inference models build on sentence representations from pretrained GloVe embeddings and compare simple attention with structured parsing attention. The structured variant augments each word representation with a soft parent representation derived from a shared parsing layer.

Baseline setup: The baseline follows Parikh et al. by representing premise and hypothesis words with transformed, normalized 300-dimensional pretrained GloVe embeddings.The pretrained embeddings remain fixed while the linear transformation is trained.
Inter-sentence attention: Each input representation is augmented with a convex combination of the other sentence’s representations, with weights computed by dot products followed by softmax.This performs inter-sentence attention between the premise and hypothesis.
Prediction: The resulting representations are processed by MLPs, summed, combined through a final MLP, and passed to a softmax distribution over labels.The label distribution is expressed as p(l | x1, . . . , xn, y1, . . . , ym) = softmax(Vh([¯x; ¯y]) + b).
Structured parsing attention: In the structured model, a bidirectional parsing LSTM produces scores θij, and each word representation is concatenated with its soft-parent representation.The parsing layer is shared between the two sentences.
Training setup: The MLPs use two layers with 300 ReLU units and dropout probability 0.2, while training uses Adagrad for 100 epochs with gradient normalization at 5.The pretrained scenario additionally uses Adam for pretraining.

B FORWARD/BACKWARD THROUGH THE INSIDE-OUTSIDE ALGORITHM

The parsing attention layer computes word-parent marginals with an inside-outside implementation of Eisner’s algorithm, then backpropagates through that dynamic program to the input potentials. Both forward and backward procedures run in O(n3) time.

Forward inference: Parsing marginals are obtained with inside-outside Eisner dynamic programming over log inside and outside tables.The tables have size n×n×2×2, encoding span boundaries, root side, and completeness.
Forward inference: The algorithm returns the marginal distribution of each word’s parent in O(n3) time.The marginal is formed from matching inside and outside quantities and normalized by the sentence-level partition value.
Backward differentiation: Backpropagation receives the loss gradient with respect to the marginals and computes gradients with respect to the input potentials.The backward pass uses signed log-space arithmetic because intermediate derivatives can be negative.
Backward differentiation: The backward pass through the inside-outside algorithm also takes O(n3) time.It propagates derivatives through the outside and inside recurrences to the potential gradients.
Forward inference: Inside and outside computations initialize log-space tables and combine span structures with potentials using dynamic-programming recurrences.The implementation uses log-space operations, with ⊕ as logadd and ⊗ as addition for numerical precision.