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 virtual KB, softly following paths of relations between mentions of entities in the corpus. At each step the operation uses a combination of sparse-matrix TFIDF indices and maximum inner product search (MIPS) on a special index of contextual representations. This module is differentiable, so the full system can be trained completely end-to-end using gradient based methods, starting from natural language inputs. We also describe a pretraining scheme for the index mention 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%. DrKIT is also very efficient, processing upto 10x more queries per second than existing state-of-the-art QA systems. Large knowledge bases (KBs), such as FreeBase and Wikidata, organize information around entities, which makes it easy to reason over their contents. For example, given a query like "When was Grateful Dead's lead singer born?", one can identify the entity Grateful Dead and the path of relations LeadSinger, BirthDate to efficiently extract the answer-provided that this information is present in the KB. Unfortunately, large KBs are often incomplete (Min et al., 2013) . While relation extraction methods can be used to populate KBs, this process is inherently error-prone, and errors in extraction can propagate to downstream tasks. Advances in open-domain QA (Moldovan et al., 2002; Yang et al., 2019) suggest an alternativeinstead of performing relation extraction, one could treat a large corpus as a virtual KB by answering queries with spans from the corpus. This ensures facts are not lost in the relation extraction process, but also poses challenges. One challenge is that it is relatively expensive to answer questions using QA models which encode each document in a query-dependent fashion (Chen et al., 2017; Devlin et al., 2019) -even with modern hardware (Strubell et al., 2019; Schwartz et al., 2019) . The cost of QA is especially problematic for certain complex questions, such as the example question above. If the passages stating that "Jerry Garcia was the lead singer of Grateful Dead" and "Jerry Garcia was born in 1942" are far apart in the corpus, it is difficult for systems that retrieve and read a single passage to find an answer-even though in this example, it might be easy to answer the question after the relations were explicitly extracted into a KB. More generally, complex questions involving sets of entities or paths of relations may require aggregating information from entity mentions in multiple documents, which is expensive. One step towards efficient QA is the recent work of Seo et al. (2018; on phrase-indexed question answering (PIQA), in which spans in the text corpus are associated with question-independent contextual representations and then indexed for fast retrieval. Natural language questions are then answered by converting them into vectors that are used to perform inner product search (MIPS) against the index. This ensures efficiency during inference. However, this approach cannot be directly used to answer complex queries, since by construction, the information stored in the index is about the local context around a span-it can only be used for questions where the answer can be derived by reading a single passage. This paper addresses this limitation of phrase-indexed question answering. We introduce an efficient, end-to-end differentiable framework for doing complex QA over a large text corpus that has been encoded in a query-independent manner. Specifically, we consider "multi-hop" complex queries which can be answered by repeatedly executing a "soft" version of the operation below, defined over a set of entities X and a relation R: Y = X.follow(R) = {x : ∃x ∈ X s.t. R(x, x ) holds} In past work soft, differentiable versions of this operation were used to answer multi-hop questions against an explicit KB (Cohen et al., 2019) . Here we propose a more powerful neural module which approximates this operation against an indexed corpus. In our module, the input X is a sparse vector representing a weighted set of entities, and the relation R is a dense feature vector, e.g. a vector derived from a neural network over a natural language query. The output Y is another sparse vector representing the weighted set of entities, aggregated over entity mentions in the top-k spans retrieved from the index. The spans in turn are retrieved using a MIPS query constructed from X and R, and we discuss pretraining schemes for the index in §2.3. For multi-hop queries, the output entities Y can be recursively passed as input to the next iteration of the same module. The weights of the entities in Y are differentiable w.r.t the MIPS queries, which allows end-to-end learning without any intermediate supervision. We discuss an implementation based on sparse matrix-vector products, whose runtime and memory depend only on the number of spans K retrieved from the index. This is crucial for scaling up to large corpora, and leads to upto 15x faster inference than existing state-of-the-art multi-hop and open-domain QA systems. The system we introduce is called DrKIT (for Differentiable Reasoning over a Knowledge base of Indexed Text). We test DrKIT on the MetaQA benchmark for complex question answering, and show that it improves on prior text-based systems by 5 points on 2-hop and 9 points on 3-hop questions, reducing the gap between text-based ad KB-based systems by 30% and 70%, respectively. We also test DrKIT on a new dataset of multi-hop slot-filling over Wikipedia articles, and show that it outperforms DrQA (Chen et al., 2017) and PIQA (Seo et al., 2019) adapted to this task. We present DrKIT, a differentiable module that is capable of answering multi-hop questions directly using a large entity-linked text corpus. DrKIT is designed to imitate traversal in KB over the text corpus, providing ability to follow relations in the "virtual" KB over text. We achieve state-of-theart results on MetaQA dataset for answering natural language questions, with a 9 point increase in the 3-hop case. We also developed an efficient implementation using sparse operations and inner product search, which led to a 10x increase in QPS over baseline approaches. We use p = 400 dimensional embeddings for the mentions and queries, and 200-dimensional embeddings each for the start and end positions. This results in an index of size 750MB. When computing A E→M , the entity to mention co-occurrence matrix, we only retain mentions in the top 50 paragraphs matched with an entity, to ensure sparsity. Further we initialize the first 4 layers of the question encoder with the Transformer network from pre-training. For the first hop, we assign Z 0 as a 1-hot vector for the least frequent entity detected in the question using an exact match. The number of nearest neighbors K and the softmax temperature λ were tuned on the dev set of each task, and we found K = 10000 and λ = 4 to work best. We pretrain the index on a combination of the MetaQA corpus, using the KB provided with MetaQA for distance data, and the Wikidata corpus. Table 3 .
Differentiable multi-hop access to a textual knowledge base of indexed contextual representations
{"src": "scitldr-AIC_train", "paper_id": "SJxstlHFPH"}