Attention-over-Attention Neural Networks for Reading Comprehension

In plain words

A cloze question is a sentence with one word blanked out, and the reader has to pick the missing word from a passage. This paper's model reads the passage and the question, and for each word of the question it works out which passage words matter. Those per-word maps are then combined by a second attention step that asks which question words matter most. The result is a single map over the passage, and the word it points to most strongly is the answer.

The point of the second step is that the model learns how much to trust each question word instead of relying on a fixed rule such as "add them up" or "take the average". The authors also add an optional check: the top candidate answers are put back into the blank and scored with simple language models, which helps on the children's-book dataset. The model is meant to be simple, with no extra weights beyond the base reader.

TL;DR

Cloze reading comprehension with a GRU reader. Attention over the passage is computed for each question word, and a second attention over those maps, weighted by a document-to-question attention, gives the final pointer over passage positions. Predictions are over the vocabulary by summing mass over repeated words §3 eq. 11. An optional 5-best re-ranking with three n-gram-style LM features gives further gains on CBTest §4 tab. 2. Results are author-reported. No official code was found.

Problem

Cloze-style reading comprehension asks a model to fill a blank in a query using a document; the answer is usually a single word that occurs in the document §2. Earlier readers either combined per-word attention maps with fixed merge functions, such as sum or average, or set several non-trainable hyperparameters §1 §3. The paper argues that the query side needs more attention than it receives in those designs §3.

Two public datasets are used: CNN / Daily Mail news, where the query is a summary sentence with one entity masked, and the Children's Book Test (CBTest), where the query is the 21st sentence of a passage of 20 sentences and the answer is a named entity (NE) or common noun (CN) §2.2 tab. 1. The authors note that verb and preposition questions depend less on the passage, so most work, including this paper, focuses on NE and CN §2.2.

Method

Overview. The model has four stages: a shared embedding and bi-directional GRU encoder for document and query, a pair-wise matching matrix, two softmaxes over that matrix, and a final sum over positions that carry the same word §3 fig. 1. The authors state that this adds only a few computation steps to the AS Reader and no weights §3.

Step 1. Contextual embedding §3 eq. 1-4. Words are mapped to vectors with one embedding matrix W_e that is shared by document and query. Each side is then encoded by a bi-directional GRU; a word's representation is the concatenation of its forward and backward states. The paper calls d the one-way GRU dimension, so each contextual vector has 2d entries.

e(x) = W_e \cdot x, \quad x \in \mathcal{D}, \mathcal{Q} eq. 1

\overrightarrow{h_s(x)} = \overrightarrow{GRU}(e(x)) eq. 2

\overleftarrow{h_s(x)} = \overleftarrow{GRU}(e(x)) eq. 3

h_s(x) = [\overrightarrow{h_s(x)}; \overleftarrow{h_s(x)}] eq. 4

Step 2. Pair-wise matching §3 eq. 5. Each document position i and query position j get a score from the dot product of their contextual vectors. Stacked, these form a matrix with one row per document word and one column per query word.

M(i,j) = h_{doc}(i)^{T} \cdot h_{query}(j) eq. 5

Step 3. Query-to-document attention §3 eq. 6-7. For each query word t, apply a softmax down the column M(:,t) over document positions. This gives a distribution over the passage for that query word. The full set of these columns is alpha.

\alpha(t) = softmax(M(1,t),...,M(|\mathcal D|,t)) eq. 6

\alpha = [\alpha(1), \alpha(2), ..., \alpha(|\mathcal Q|)] eq. 7

Step 4. Document-to-query attention and attention-over-attention §3 eq. 8-10. For each document word t, apply a softmax across the row M(t,:) over query positions, giving beta(t). Then average the beta(t) over document positions to get one query-level weight vector beta. The paper does not apply a second softmax after averaging, because an average of distributions still sums to one §3. The final passage attention is the dot product s = alpha^T beta, a weighted sum of the per-query-word maps in alpha, where the weights are the learned importance of each query word.

\beta(t) = softmax(M(t,1),...,M(t,|\mathcal Q|)) eq. 8

\beta = \frac{1}{n}\sum\limits_{t=1}^{|\mathcal D|}\beta(t) eq. 9

s = \alpha^{T} \beta eq. 10

Step 5. Prediction over the vocabulary §3 eq. 11. The output is not over passage positions. For each word w in the vocabulary, sum s_i over the positions where w occurs in the document. The authors say that predicting over the vocabulary rather than positions changes performance significantly, but they give no ablation §3.

P(w|\mathcal D, \mathcal Q) = \sum_{i \in I(w,\mathcal D)} s_i, \quad w \in V eq. 11

Step 6. Training objective §3 eq. 12. Maximise the log-likelihood of the correct answer.

\mathcal{L} = \sum_{i} \log(p(x)), \quad x \in \mathcal{A} eq. 12

N-best re-ranking §4. After decoding, keep the 5-best answers from the network §5.1. Refill each candidate into the blank to form a full sentence, score it with three features, and pick the candidate with the lowest weighted cost.

• Global n-gram LM: trained on the document parts of the training data §4.
• Local n-gram LM: trained per test sample on that sample's document only; not trained on the whole test set §4.
• Word-class LM: trained like the global LM, but on class IDs from 1000 word classes produced by mkcls §4.
• Feature weights are tuned with K-best MIRA on the validation set §4.

Pseudocode for the forward pass of the reader, covering steps 1 to 5:

# AoA Reader forward pass  [§3] [eq. 1-11]
# Input:  doc (|D|,) word ids; query (|Q|,) word ids
# Output: probs over vocabulary V  (|V|,)

def aoa_reader(doc, query):
    # Shared embedding, then one bi-GRU per side  [§3] [eq. 1-4]
    doc_states = bi_gru(embed(doc))              # (|D|, 2d)
    query_states = bi_gru(embed(query))          # (|Q|, 2d)

    # Pair-wise matching by dot product  [§3] [eq. 5]
    matching = doc_states @ query_states.T       # (|D|, |Q|)

    # Query-to-document: softmax over document positions  [§3] [eq. 6-7]
    doc_attention = softmax(matching, axis=0)    # (|D|, |Q|)

    # Document-to-query: softmax over query positions  [§3] [eq. 8]
    query_attention = softmax(matching, axis=1)  # (|D|, |Q|)

    # Average over document positions; no second softmax  [§3] [eq. 9]
    query_importance = mean(query_attention, axis=0)  # (|Q|,)

    # Attention over attention  [§3] [eq. 10]
    passage_attention = doc_attention @ query_importance  # (|D|,)

    # Sum mass of repeated words into the vocabulary  [§3] [eq. 11]
    probs = scatter_add(vocab_size, doc, passage_attention)  # (|V|,)
    return probs

Hyperparameters

Dataset statistics tab. 1:

Vocabulary sizes tab. 1: CNN 118,497; CBT NE 53,063; CBT CN 53,185.

Results

Author-reported. Setup: CNN news and CBTest NE / CN §5.2, the training splits and sizes in tab. 1, and the baselines listed in tab. 2. Accuracy is in percent. Entries marked "-" are not reported. Single-model rows come first, then ensembles.

Re-ranking ablation on 5-best CBTest NE / CN, each row includes the rows above it tab. 4:

Feature weights in the re-ranking step tab. 5, and the ratio eta from eq. 13 (the global plus word-class weight over the local weight):

\eta = \frac{LM_{global} + LM_{wc}}{LM_{local}} eq. 13

Other reported numbers: on CNN, the single model is 4.9 points above CAS Reader on validation and 4.4 on test, using tab. 2 values (the text gives 4.1 and 3.7; see Pitfalls) §5.2. The authors report a length analysis on CBTest NE, where the gain over AS Reader is larger when the passage is longer than 700 tokens §6 fig. 2. On the frequency-rank analysis, the most frequent candidate is the answer in 1071 of 2500 CBTest NE test samples §6 fig. 3.

Paper vs code

No official code. The paper gives no code link and no project page. A GitHub search for "attention-over-attention" found only third-party reimplementations, which are not published by the authors. The first author's GitHub profile lists a repository on cloze-style reading comprehension evaluation, which has no AoA model file. The user-scoped repository search returned HTTP 403, so the profile listing was read instead.

Pitfalls

• Averaging normaliser is undefined. eq. 9 divides by n without defining it. The sum runs over document positions, so the implied choice is the number of document positions. A mean over document positions is the reading that keeps beta normalised §3.
• Two RNNs, shared or not. The embedding matrix is shared §3, but the paper says "two bi-directional RNNs ... individually". Whether the two GRUs share weights is not stated; separate GRUs match the wording.
• Hidden size meaning. tab. 3 lists "Hidden # units". The paper defines d as the one-way GRU size §3, so the encoder output is 2d wide. Check this when comparing dimensions.
• Text and table disagree. The text says the single model beats CAS Reader by 4.1 and 3.7 points on CNN validation and test §5.2. The table values give 4.9 and 4.4 (73.1 vs 68.2 and 74.4 vs 70.0) tab. 2. Use the table.
• Index in the loss. eq. 12 sums over i without defining it, and x ranges over the answer set A; the answer is usually a single word §2.1. Summing over a candidate's several positions is implied by eq. 11 §3.
• Vocabulary handling. Words that are not in the vocabulary cannot be predicted eq. 11. How the vocabulary is built and how OOV tokens are handled is not stated tab. 1 §5.1.
• Re-ranking sign convention. Features are combined into a "cost" and the lowest is chosen §4. Whether the LM features are log probabilities, and their signs, is not stated.
• Local LM leakage risk. The local LM is trained on each test sample's document only §4. The paper says training it on the whole test set would not be legal; an implementation must keep it per sample.
• Re-ranking only on CBTest. tab. 2 reports re-ranking results only for CBTest NE and CN, not CNN.
• Ensemble averaging. The ensemble uses four seeds §5.1, but how the members are combined is not stated.
• Missing training details. Epochs, stopping rule, dropout placement, document truncation, padding and masking, and the learning-rate schedule are not stated §5.1.
• No variance reported. The tables give single numbers with no spread across seeds or runs tab. 2 tab. 4.

Lineage

• Builds on: the AS Reader (Kadlec et al.), which the paper extends by adding a second attention step and keeping its sum-over-positions output §3. The CAS Reader (Cui et al.) is the other direct predecessor; it uses fixed merge functions such as sum and average, which this paper replaces §3 §7.
• Compared against: Deep LSTM Reader, Attentive Reader, MemNN, AS Reader, CAS Reader, Stanford AR, GA Reader, Iterative Attention, EpiReader, and their ensembles tab. 2.
• Superseded by: not recorded in this wiki yet.