PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentiable Reasoning over a Virtual Knowledge Base

Bhuwan Dhingra, Manzil Zaheer, Vidhisha Balachandran, Graham Neubig, Ruslan Salakhutdinov, William W. Cohen

arXiv:2002.10640v1cs.CLcs.LG

TL;DR

Complex multi-hop questions are difficult to answer efficiently from incomplete knowledge bases or from scattered corpus passages. DrKIT treats indexed text as a virtual knowledge base and differentiably follows relation paths; it improves MetaQA 3-hop accuracy by 9 points and reports faster throughput than baseline approaches.

  • Problem

    Knowledge bases are often incomplete, while multi-hop answers may require aggregating evidence across documents, which is expensive for query-dependent QA systems.

    Source: §1 · p. 1

  • Method

    DrKIT uses a differentiable module to follow soft relation paths over a query-independently encoded corpus, retrieving relevant spans and aggregating their entity mentions.

    Source: §1 · p. 2

  • Results

    DrKIT improves MetaQA 3-hop accuracy by 9 points and increases Queries/sec by 10-100x over baseline approaches.

    Source: §5 · p. 11

  • Takeaways & Limitations

    DrKIT answers multi-hop questions directly from a large entity-linked text corpus using sparse operations and inner product search.

    Source: §5 · p. 11

    On HotpotQA, the top 10 retrieved passages lack both correct passages for 33% of questions, and the answer-containing passage is missing for around 20% of those cases.

    Source: §3.3 · p. 10

Abstract

from arXiv · show

We consider the task of answering complex multi-hop questions using a corpus as a virtual knowledge base (KB). In particular, we describe a neural module, DrKIT, that traverses textual data like a KB, softly following paths of relations between mentions of entities in the corpus. At each step the module uses a combination of sparse-matrix TFIDF indices and a maximum inner product search (MIPS) on a special index of contextual representations of the mentions. This module is differentiable, so the full system can be trained end-to-end using gradient based methods, starting from natural language inputs. We also describe a pretraining scheme for the contextual representation encoder by generating hard negative examples using existing knowledge bases. We show that DrKIT improves accuracy by 9 points on 3-hop questions in the MetaQA dataset, cutting the gap between text-based and KB-based state-of-the-art by 70%. On HotpotQA, DrKIT leads to a 10% improvement over a BERT-based re-ranking approach to retrieving the relevant passages required to answer a question. DrKIT is also very efficient, processing 10-100x more queries per second than existing multi-hop systems.

1 INTRODUCTION

DrKIT treats a query-independent text corpus as a virtual knowledge base, addressing the incompleteness and extraction costs of explicit KBs and the difficulty of answering multi-hop questions across documents. It follows relation paths with a differentiable module over indexed text.

1 INTRODUCTION

  • Explicit KBs support efficient entity-relation reasoning, but are often incomplete, while populating them through relation extraction is error-prone, expensive, and slow.Source: §1 · p. 1
  • Treating a corpus as a virtual KB can preserve facts missed by relation extraction, but query-dependent QA is costly and single-passage retrieval struggles when multi-hop evidence is scattered across documents.Source: §1 · p. 1
  • Phrase-indexed QA uses question-independent contextual span representations and fast MIPS retrieval, but its local-context index is limited to answers derivable from one passage.Source: §1 · pp. 1–2
  • DrKIT approximates relation-following over an indexed corpus: a weighted entity set and dense relation vector retrieve top-K spans, whose entity mentions are aggregated into the next weighted entity set.For multi-hop queries, that output can be fed into the module again.Source: §1 · p. 2
  • 9 points on MetaQA 3-hop questions and a 70% reduction in the text-to-KB performance gap; DrKIT also improves on a BERT-based HotpotQA reranker while running 10x faster.The framework provides up to 15x faster inference than existing multi-hop and open-domain QA systems; on MetaQA, it improves by 5 points on 2-hop questions and reduces the gap by 30%.Source: §1 · p. 2

2 DIFFERENTIABLE REASONING OVER A KB OF INDEXED TEXT

DrKIT treats a text corpus as a virtual KB by expanding entities to co-occurring mentions, scoring relevant mentions, and aggregating them into candidate entities for iterative hops. The section formalizes this as differentiable textual follow and describes efficient indexing and mention-encoder pretraining.

2.1 DIFFERENTIABLE MULTI-HOP REASONING

  • Each hop expands entities to co-occurring mentions, scores their relevance to the question and current entity, and aggregates linked mentions into weighted entity candidates for recursive traversal.This differentiable textual follow operation keeps the number of nonzero entity weights bounded by the top-K mentions.Source: §2.1 · pp. 3–4

2.2 EFFICIENT IMPLEMENTATION

  • The implementation combines sparse TFIDF entity-to-mention expansion with top-K inner-product search and coreference aggregation, with query complexity almost independent of entity and mention counts.Ragged sparse-matrix representations support vector-driven products; MIPS retrieves top-scoring mentions without enumerating them all.Source: §2.1 · p. 4, §2.2 · p. 5

2.3 PRETRAINING THE INDEX

  • The mention encoder is pretrained separately, its corpus-wide embeddings are indexed once and held fixed during downstream QA training, and KB-derived slot-filling data supplies supervision.The pretraining pairs passages mentioning both entities in a KB fact with a query formed from the subject and a natural-language relation description.Source: §2.3 · pp. 5–6
  • Pretraining uses shared-entity, shared-relation, and random hard negatives; the multi-hop slot-filling setup collected 950K pairs over 550K articles.The experiments use WikiData facts and Wikipedia passages, with subject-article passages restricted to reduce noise.Source: §2.3 · p. 6

3 EXPERIMENTS

Across MetaQA, WikiData slot-filling, and HotpotQA retrieval, DrKIT is evaluated for multi-hop accuracy and inference efficiency. The reported results include gains over prior or cascaded systems, while downstream HotpotQA reading-comprehension gains over entity-centric retrieval are small.

3.1 METAQA: MULTI-HOP QUESTION ANSWERING WITH TEXT

  • DrKIT outperforms prior text-only state-of-the-art by a large margin on MetaQA 2-hop and 3-hop questions, despite lacking PullNet's intermediate KB-derived path supervision.Adding that supervision gives DrKIT a small lift on 1- and 2-hop questions but does not help on 3-hop questions.Source: §3.1 · p. 7
  • On MetaQA, DrKIT's runtime gains over PullNet range from 5x to 15x as the number of retrieved nearest neighbors varies.Figure 3 compares Hits@1 and queries per second on MetaQA and WikiData, and also shows the effect of K during MIPS.Source: §3.1 · p. 7, Figure 3 · p. 7
  • MetaQA ablations show that removing TFIDF hurts 2-hop and 3-hop performance, while un-pretrained BERT representations are 23 points worse on 3-hop questions.Taking a sum instead of a maximum over mentions and removing the softmax temperature also hurt; pretraining with only 50% of KB edges retained still outperforms PullNet and the KB-only state of the art.Source: §3.1 · p. 7

3.2 WIKIDATA: MULTI-HOP SLOT-FILLING

  • On WikiData slot-filling, end-to-end DrKIT improves over cascaded architectures and DrKIT trained on the same data improves over retrained PIQA.The best performance uses KB-pretrained mention representations; fixed BERT representations lag behind.Source: §3.2 · p. 8
  • On the slot-filling analysis, entity linking raises DrKIT accuracy from 50% to 66%, and it reaches 55% on relations observed fewer than five times in training.The slot-filling-trained representations encode entity co-occurrence better than vanilla BERT, while the two are comparable at fine-grained entity-type detection.Source: §3.2 · p. 8

3.3 HOTPOTQA: MULTI-HOP INFORMATION RETRIEVAL

  • HotpotQA tests retrieval from 5.23M entity passages, then uses retrieved passages for answer extraction; the system runs two hops because each question's hop count is unknown.The retrieval task identifies the two passage-title entities needed for answering, and the system mixes distributions from zero, one, and two hops.Source: §3.3 · p. 9
  • DrKIT improves HotpotQA retrieval accuracy across the reported cutoffs, with larger gains at @2 and @5 and over 10x more queries per second than the entity-centric IR baseline.The speed comparison uses batch size 1; DrKIT can run with batch sizes up to 40, unlike that baseline.Source: §3.3 · pp. 9–10, Table 2 · p. 9
  • DrKIT+BERT reaches 42.88 joint F1 on HotpotQA and is up to 100x faster than models that outperform it.The system feeds DrKIT's top 5 retrieved passages to a BERT-based answer-span extraction model.Source: §3.3 · p. 10

4 RELATED WORK

Prior work addresses multi-step reasoning over symbolic knowledge bases and text corpora, but the approaches described differ in how relations are represented and whether retrieval can be trained end-to-end.

4 RELATED WORK

  • Knowledge graph embeddings represent discrete symbols continuously and can generalize to unseen facts, while text corpora contain more complete information.DrKIT instead focuses on relations implicit in text-derived mention representations.Source: §4 · p. 10
  • Talmor and Berant (2018) parse compositional queries into computation trees and run black-box QA separately on the leaves, preventing end-to-end training.Source: §4 · p. 10
  • Graph-based and entity-path approaches use relevant evidence documents; dynamic retrieval methods process evidence query-dependently and are slower than preprocessed indexed representations.The text also attributes slower inference to methods that interleave multi-step retrieval with reading comprehension.Source: §4 · p. 11

5 CONCLUSION

DrKIT traverses an entity-linked text corpus as a virtual knowledge base to answer multi-hop questions. The paper reports gains on MetaQA and faster inference than baseline approaches.

5 CONCLUSION

  • 9 points higher in the 3-hop case on MetaQA, where DrKIT achieves state-of-the-art results for natural-language question answering.Source: §5 · p. 11
  • DrKIT answers multi-hop questions directly from a large entity-linked text corpus by imitating knowledge-base traversal over textual relations.Source: §5 · p. 11
  • 10–100x more queries per second than baseline approaches with an implementation using sparse operations and inner-product search.Source: §5 · p. 11

A METAQA: IMPLEMENTATION DETAILS

The MetaQA implementation uses contextual embeddings and a sparse entity-to-mention matrix, with tuned retrieval settings and pretraining on MetaQA and WikiData.

A METAQA: IMPLEMENTATION DETAILS

  • 400-dimensional mention and query embeddings, 200-dimensional start and end position embeddings, and a 750MB index define the representation setup.Source: A METAQA: IMPLEMENTATION DETAILS · p. 14
  • The entity-to-mention matrix retains mentions from only the top 50 paragraphs matched with each entity to keep it sparse.The first four question-encoder layers are initialized from a pretrained Transformer.Source: A METAQA: IMPLEMENTATION DETAILS · p. 14
  • The first hop starts from the least frequent exactly matched question entity; dev tuning selected K = 10000 and λ = 4, and index pretraining combines MetaQA and WikiData.Source: A METAQA: IMPLEMENTATION DETAILS · p. 14

B WIKIDATA DATASET STATISTICS

Table 4 presents details of the collected WikiData dataset.

B WIKIDATA DATASET STATISTICS

C INDEX ANALYSIS

DrKIT is evaluated on open slot filling and probing experiments that examine what its learned representations capture. Entity-mention indexing outperforms phrase-based alternatives, while the probes distinguish entity-type information from entity co-occurrence information.

C INDEX ANALYSIS

  • The open slot-filling task uses 109K passages collected from Wikipedia articles for 8K subject entities in the dev and test sets.The task draws on 1M slot-filling queries and requires answers to be extracted from the corpus rather than selected from candidate passages.Source: C INDEX ANALYSIS · p. 14
  • DrKIT on entity mentions consistently outperforms other phrase-based models on Levy et al. (2017) slot filling, including relations split by training frequency.DrKIT-entities also has high Hits@1 on rare relations, indicating generalization to less frequent data.Source: C INDEX ANALYSIS · pp. 14–15, Figure 4 · p. 15
  • The probing experiments freeze BERT’s mention encoders and train only query encoders, using a learned weighted average of BERT layers.The first probe tests shared-entity negatives; the second tests shared-relation negatives.Source: C INDEX ANALYSIS · p. 15
  • BERT performs well on shared-entity negatives but drops on shared-relation negatives, while DrKIT performs well on both probes.The authors suggest slot-filling fine-tuning primarily adds entity co-occurrence information to contextual representations, alongside entity-type information.Source: C INDEX ANALYSIS · p. 15

D HOTPOTQA ANSWER EXTRACTION

For HotpotQA, the answer extractor processes passages retrieved by DrKIT using a modified BERT model. It predicts answer type, answer spans, and supporting facts with a combined training loss.

D HOTPOTQA ANSWER EXTRACTION

  • The BERT extractor predicts span, yes, or no answers with a three-way classifier, extracting start and end positions only for span predictions.It receives concatenated top passages identified by DrKIT.Source: D HOTPOTQA ANSWER EXTRACTION · p. 15
  • Supporting facts are predicted with a binary classifier applied to each sentence’s [unused0] representation, using probability above 0.5 at inference.Each sentence in the concatenated passages is prepended with [unused0].Source: D HOTPOTQA ANSWER EXTRACTION · p. 15
  • Training averages the answer-type loss, the sum of supporting-fact losses, and the start- and end-position losses for span answers.The combined objective is given as an average of these loss components.Source: D HOTPOTQA ANSWER EXTRACTION · p. 15
  • A heuristic for this task is to detect an entity of the correct type in the sentence, since every sentence contains the subject entity.The passage presents this as a reasonable heuristic, not as the extractor’s stated prediction procedure.Source: D HOTPOTQA ANSWER EXTRACTION · p. 15
  • The extractor is trained on five passages per question: two gold passages and three TFIDF negatives from HotpotQA’s distractor setting.Gold passages are placed first for 60% of examples and all passages are shuffled for the remainder; the combined passage limit is 512 tokens.Source: D HOTPOTQA ANSWER EXTRACTION · p. 16
Loading 2002.10640v1…