Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases

In plain words

Answering a question from a knowledge base, a large store of facts such as "this film was directed by that person", means turning the question into a formal query that the database can run. Most earlier systems were tested on questions that look like their training questions. The authors argue that real users ask things the training data never covered. So they want systems to be tested on three levels of new questions: the same kind as before, new combinations of parts the system has seen, and parts or whole topics it has never seen.

To make such tests possible, the authors built a large dataset of questions, each paired with its formal query, and split it so that each level has its own test set. They also built a model that reads the question together with the names of the candidate database items. A pre-trained language model (BERT) helps it understand what each item means. The model either writes the query token by token, or it scores a list of candidate queries built from the entities in the question.

The main finding is that the language model matters most on the harder levels. When the model uses simpler word vectors instead of BERT, it does almost as well on familiar questions but falls behind on new combinations and on unseen topics. All scores come from the authors' own runs.

TL;DR

The paper proposes a seq2seq semantic parser for knowledge base question answering. It encodes the question and the schema items with BERT, then either decodes an S-expression logical form over a vocabulary pruned to items within two hops of the linked entities (transduction), or scores enumerated two-hop candidates (ranking) §4.1, §4.2, §4.4. It also releases GrailQA, with 64,331 questions and test sets for all three generalization levels §3, §5.1. Results are author-reported: ranking with BERT gets 50.6 exact match and 58.0 F1 overall tab. 3. The code is Apache-2.0, but the dataset, the entity-linking data and the trained models must be downloaded separately (see Pitfalls).

Problem

Knowledge base question answering (KBQA) maps a natural-language question to a logical form that a knowledge base such as Freebase can execute §1, §2.1. Most datasets assume that test questions come from the training distribution (i.i.d.) §1. The authors argue that this is neither realistic nor efficient on large knowledge bases: the true user distribution is hard to capture, and sampling training questions at random is data-inefficient §1.

They define the three levels by the schema items in a query, meaning relations, classes and functions §2.2. i.i.d.: every item in the query appears in training, and the test questions follow the training distribution. Compositional: every item appears in training, but this combination does not. Zero-shot: at least one item never appears in training §2.2. Earlier semantic parsers built their lexicons from web mining, which can favour popular schema items §4.1.

Method

Logical form. Each question is mapped to an S-expression built from set functions: AND, JOIN, R (reverse), COUNT, ARGMAX and ARGMIN, plus the comparatives LT, LE, GT and GE §3.3, app. B. The authors' example, a theatre query with a capacity constraint and a producer join, is written as one nested S-expression §3.3.

Model. The model is a seq2seq network with an LSTM encoder and an LSTM decoder §4.1. The probability of a logical form factorises over its tokens eq. 1. The decoder state is updated by an LSTM cell from the previous token's embedding eq. 2. The output layer is the same matrix W that holds the item embeddings, so the softmax scores every item in the decoder vocabulary against the decoder state eq. 3, §4.1.

p(a \mid q) = \prod_{t=1}^{|a|} p(y_t \mid y_{<t}, q) eq. 1

\mathbf{h}_t = \mathrm{LSTM}(\mathbf{h}_{t-1}, \mathbf{g}_t) eq. 2

p(y_t \mid y_{<t}, q) = \big[\mathrm{Softmax}(\mathbf{W}\mathbf{h}_t)\big]_{y_t} eq. 3

BERT encoding of the question and the vocabulary. The decoder vocabulary V is split into chunks. Each chunk is concatenated with the question and passed through BERT on its own. The input is the question, a [SEP] token, then the chunk's items separated by ";" §4.2, fig. 3. The question's token states come from the first chunk §4.2. An item's embedding is the mean of BERT's last-layer outputs over the word pieces of its name §4.2. An entity is embedded from the surface form in the question, in the same way §4.2, remark "Vocabulary construction". Schema names are split on dots and underscores into words, so architecture.venue.capacity becomes three words §4.2, fig. 3.

Vocabulary pruning (VP). V holds the schema items reachable from at least one linked entity within two hops, plus the linked entities, the literals and the syntax constants §4.2, remark "Vocabulary construction". The vocabulary changes for each question. The paper says pruning applies at both training and inference time §4.2, remark.

Transduction mode. The decoder generates tokens from V with beam search until a stop token §4.4. Beam size is not stated in the paper.

Ranking mode. The candidates are all logical forms that use at most two relations and start from a linked entity. They can include a COUNT. The decoder scores each candidate and the best one is returned §4.4. Candidate generation reaches about 80% recall on GrailQA. Questions with superlatives or comparatives often have no topic entity, so they are not covered §4.4.

Entity linking. A BERT-based NER model trained on the training split finds mentions. Each mention is resolved to the most popular entity, by FACC1 counts, and the authors compare this with Aqqu §4.3. The comparison is in the Results section.

# Encode the question and the vocabulary  [§4.2]
# Input:  question (text); vocab (list of schema items, entities, literals)
# Output: question states (N, d); one embedding per vocab item (d)
def encode_question_and_vocab(question, vocab, chunk_size):
    # Split the decoder vocabulary into fixed-size chunks  [§4.2]
    chunks = split_into_chunks(vocab, chunk_size)
    question_states = None
    item_embeddings = []
    for chunk_index, chunk in enumerate(chunks):
        # One BERT pass per chunk: question, [SEP], items joined by ";"  [§4.2]
        bert_input = question + " [SEP] " + " ; ".join(chunk)
        states = bert(bert_input)
        if chunk_index == 0:
            # Question states come from the first chunk only  [§4.2]
            question_states = question_part(states)
        # Mean of the word-piece outputs for each item  [§4.2]
        item_embeddings.extend(mean_over_pieces(states, chunk))
    return question_states, item_embeddings

# One decoding step over the pruned vocabulary  [§4.1, eq. 1-3]
# Input:  previous token id; decoder state; item_embeddings (|V|, d)
# Output: log-probabilities over V; updated decoder state
def decode_step(previous_token, state, item_embeddings):
    # Input embedding of the previous token, from the shared matrix  [§4.1]
    token_input = item_embeddings[previous_token]
    # Recurrent update of the decoder state  [§4.1, eq. 2]
    state = lstm_cell(token_input, state)
    # Score every vocabulary item against the state  [§4.1, eq. 3]
    logits = item_embeddings @ state          # (|V|,)
    return log_softmax(logits), state

# Ranking mode: pick the best enumerated candidate  [§4.4]
# Input:  question; candidates (token lists from 1- and 2-hop search)
# Output: the highest-scoring candidate
def rank_candidates(question, candidates):
    best = None
    best_score = -inf
    for candidate in candidates:
        # Per-token log-probabilities of the candidate under the decoder  [§4.4]
        token_log_probs = score_tokens(question, candidate)
        # Length-normalised score; the paper body does not specify it
        # The code averages per-token log-probabilities
        # [code: bert_constrained_seq2seq.py#L547-L549]
        score = mean(token_log_probs)
        if score > best_score:
            best = candidate
            best_score = score
    return best

Hyperparameters

Values for the BERT model. The paper body names no chunk size, beam size, decoding-length limit or training epochs. The code values are given for reference, and the code is in the Paper vs code section.

Results

Author-reported. The GrailQA split has 44,337 training, 6,763 validation and 13,231 test questions §5.1. The validation and test sets are 50% zero-shot (held-out domains: five for validation, ten for test), 25% compositional and 25% i.i.d. §5.1. Exact match (EM) compares logical forms by graph isomorphism of the graph queries. F1 compares the answer sets, using a local SPARQL endpoint §5.1. The QGG baseline reports F1 only §5.2.

Overall results, GrailQA test tab. 3

The authors describe BERT as the main factor for compositional and zero-shot results. Transduction F1 falls by 17.5 points on compositional questions and by 26.2 points on zero-shot questions when GloVe replaces BERT §5.3. Ranking falls by 21.9 points on zero-shot §5.3, tab. 3. Without BERT, ranking scores higher on i.i.d. EM (62.2 against 59.9) tab. 3.

Pretraining on GrailQA, tested on WebQSP (no in-domain training for zero-shot) §5.5

Entity linking on GrailQA §4.3, uncaptioned table

GraphQuestions. The ranking model reaches 25.0 F1 there, which the authors say beats SPARQA by 3.5 points §4.4.

Error analysis. Of 100 sampled errors from the ranking model, 34% are coverage limits, 33% entity linking, 26% relation misclassification and 7% other, such as typing and function errors §5.4.

Fine-grained results. Performance drops as queries get more relations. The ranking model beats transduction on three-relation questions §5.3, fig. 4. Transduction does better on superlatives and comparatives, where ranking has no topic entity to start from §5.3, fig. 4.

Robustness. Bounds over paraphrase groups and template groups are tighter for BERT models than for GloVe models §5.3, fig. 5.

Paper vs code

The code is at commit bc15df916ca4101f773722151c90ba3f9eff9df5. Paths are relative to the repository root. The repository is the dki-lab GitHub repository, which the paper links in its first-page footnote, and the README names the paper.

• Training uses gold entities. The paper says all models use the same entity linker §5.2. The training reader defaults to perfect entity linking, which takes the entities from the gold graph query bert_seq2seq_reader.py. The training config does not turn this off train_bert.jsonnet.
• Training vocabulary. The paper applies two-hop pruning in training and inference §4.2, remark. The training config uses mix2, which keeps only items in the gold query's domains and also within two hops of the entities, then adds the gold tokens train_bert.jsonnet bert_seq2seq_reader.py bert_seq2seq_reader.py. The reader's comment says this mode is only for ideal experiments bert_seq2seq_reader.py. Validation uses 2_step train_bert.jsonnet bert_seq2seq_reader.py.
• Ranking candidates from several entities. The paper says candidates start from each identified entity §4.4. When linking is not gold, the code builds the two-hop candidates only from the first linked entity, and repeats that list for each entity bert_seq2seq_reader.py. Duplicates can result.
• Attention. The paper body describes the decoder without attention §4.1, eq. 2. The code uses dot-product attention over the encoder states train_bert.jsonnet bert_constrained_seq2seq.py.
• Item embeddings across chunks. The paper's worked example takes the item embedding from the first chunk §4.2. The figure caption does not name a chunk fig. 3. The code takes each item's embedding from the chunk that contains it bert_constrained_seq2seq.py. The paper is ambiguous here, so the code's choice is the one that runs.
• Ranking score. The paper body does not say how candidates are scored §4.4. The code uses the mean per-token log-probability, which is the default avg mode bert_constrained_seq2seq.py bert_constrained_seq2seq.py bert_constrained_seq2seq.py. The sum is used only for the top-k metric bert_constrained_seq2seq.py.
• Patience for GloVe. The paper says patience is 3 for all models app. D.2. The GloVe training config uses 45 epochs and patience 5 train_glove.jsonnet.
• Beam size and length. The paper gives neither beam size nor decoding length. The code uses a beam of 10 by default bert_constrained_seq2seq.py and a decoding limit of 200 in training and 100 in the test configs train_bert.jsonnet bert_vp.jsonnet.
• Consistent items. Hidden size 768 app. D.1, Adam with learning rates 1e-3 and 2e-5 app. D.1, batch 1 with gradient accumulation 16 app. D.1, and the output layer as a matrix product with the item embeddings eq. 3 bert_constrained_seq2seq.py all match.

Pitfalls

• Unstated values. The paper body gives no chunk size, beam size, decoding limit, maximum epochs, learning-rate schedule, warm-up, dropout, weight decay, random seed or hardware. The code's values are listed above; they are not in the paper.
• Gold information in training. Training uses gold entities and gold domains bert_seq2seq_reader.py bert_seq2seq_reader.py, and the vocabulary always contains the gold tokens bert_seq2seq_reader.py. Inference uses linked entities. The paper does not say this, so a reimplementation that follows the paper text will train on a different vocabulary from the released code.
• Test-time reader may differ. The test configs' dataset_reader also uses mix2 with training: true bert_vp.jsonnet bert_ranking.jsonnet. The README runs predict with --use-dataset-reader. I did not run it, so I cannot say whether that reader builds gold-informed vocabularies at test time. Check before reporting test numbers.
• No linked entity. At inference, if no entity is linked, the vocabulary is the full schema list plus entities and literals bert_seq2seq_reader.py. That is a large decoder vocabulary, and the paper does not describe it.
• Cost. Each question needs one BERT pass per chunk, so a vocabulary of N items needs about N/45 passes bert_seq2seq_reader.py. Two-hop pruning and candidate generation need SPARQL calls. The README reports online times of 60.9 s for transduction, 4.8 s with pruning, 115.5 s for ranking, and 1.9 s to 80.9 s for the BERT variants, on one RTX 2080 Ti at batch size 1 with caches off README.md. The paper's own runtime analysis is commented out in the LaTeX source.
• Recall ceiling. Ranking cannot return a query that is not in its candidate set. The authors measure roughly 80% recall §4.4 and attribute 34% of errors to this §5.4.
• Entity linking is a separate system. The test reader loads linked entities from a shipped file bert_seq2seq_reader.py, and the linker source is in a separate folder . I did not audit the linker. Entity linking alone accounts for 33% of sampled errors §5.4.
• Artifacts are missing from the repository. cache/ and saved_models/ contain only READMEs. The GrailQA training and test files are not in data/, which holds GraphQuestions files only . Running the code needs a Freebase Virtuoso endpoint README.md. The dataset's own license was not checked for this card. Only the paper and the Apache-2.0 code were used.
• Masking and numerics. Masked logits are set to -1e32 bert_constrained_seq2seq.py. A candidate whose log-probability sum is exactly zero is also replaced by -1e32 bert_constrained_seq2seq.py. Both are safe in float32. Check them before any half-precision port.
• Single runs. Each row is one reported run with no variance. The README sets PYTHONHASHSEED=23 for every command README.md. Hash seeding can change results.
• Units in the text. The text describes some differences as "%". The values in the table are F1 points, for example 36.0 to 18.5 on compositional questions tab. 3.
• Figure numbers. Figure and table numbers were derived from the order of the LaTeX source, not checked against the published PDF. The teaser figure may or may not be numbered, which shifts the other figure numbers by one.

Lineage

• Builds on: the LSTM encoder-decoder (seq2seq) for semantic parsing §4.1; BERT for contextual embeddings §4.2; the GraphQuestions logical-form generation method of Su et al. 2016 for candidate forms §3.1.
• Compared against: QGG (Lan & Jiang 2020) §5.2; SPARQA on GraphQuestions §4.4; Aqqu for entity linking §4.3.
• Superseded by: not known from content already in this wiki.