Differentiable Reasoning over a Virtual Knowledge Base
Authors: Bhuwan Dhingra
Manzil Zaheer
Vidhisha Balachandran
Graham Neubig
Ruslan Salakhutdinov
William W. Cohen
Venue:  (2020)
Keywords: Question Answering
Multi-Hop QA
Deep Learning
Knowledge Bases
Information Extraction
Data Structures for QA

Abstract: 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 up to 10-100x more queries per second than existing multi-hop systems.

Published as a conference paper at ICLR 2020
DIFFERENTIABLE REASONING OVER A VIRTUAL KNOWLEDGE BASE
Bhuwan Dhingra'; Manzil Zaheer", Vidhisha Balachandran',
Graham Neubig', Ruslan Salakhutdinov', William W. Cohen
School of Computer Science, Carnegie Mellon University
2 Google Research
#bdhingra, vbalacha, gneubig, rsalakhu) cmu edu [manzilzaheer, wcohen]@google.coo
ABSTRACT
We consider the task of answering complex multi-hop questions using corpus as a virtual knowledge base (KB). In particular, we describe a neural module, DrKIT, that traverses textual data like KB, softly following paths of relations between mentions of entities the corpus. each step the module uses com- bination of sparse-matrix TFIDF indices and 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 gra- dient based methods. starting from natural language inputs. We also deseribe 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 question. DrKIT is also very efficient, processing 10-100x more queries per second than existing multi-hop systems!
INTRODUCTION
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 the 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, KBs are often incomplete (Min et al.) 2013). While relation extraction methods can be used to populate KBs, this process is inherently error-prone, expensive and slow.
Advances in open-domain QA (Moldovan et al. 2002 Yang al. 2019) suggest an alternative- instead 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 relatively expensive to answer questions using QA models which encode each document in a query-dependen fashion (Chen et al. 2017 Devlin al. 2019) evven 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 the Grateful Dead" and "Jerry Garcia was born in 1942" are far apart in the corpus, it is difficult for systems that retrieve and read single passage to find an answer-eved though in this example, might be easy to answer the question after the relations were explicitly extracted into a KB. More generally, complex questions involving sets of entities paths of relations may require aggregating information from multiple documents, which is expensive.
One step towards efficient QA is the recent work Seo et al. (2018 2019) phrase-indexed ques- tion answering (PIQA), in which spans in the text corpus are associated with question-independen independent
Part of this work was done during an internship at Google.
Code available ahttp:/ : /wwww cs. cmu http.///ooiiiigrrpee.././......

---

Published as a conference paper at ICLR 2020
contextual representations and then indexed for fast retrieval. Natural language questions are then answered by converting them into vectors that are used to perform maximum inner product search (MIPS) against the index. This can be done efficiently using approximate algorithms (Shrivastava Li, 2014). 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)) {a' 3x X s.t. R(z,2') 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 indexed corpus (a virtual KB). 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 neural network over a natural language query. X and R are used to construct a MIPS query used for retrieving the top- K spans from the index. The output Y is another vector representing the weighted set of entities, aggregated over entity mentions in the top-K spans. We discuss pretraining schemes for the index in 2..
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 mparse-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, providing up to 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 and KB- KB-based systems by 30% and 70%, respectively. We also test DrKIT on new dataset of multi-hop slot-filling over Wikipedia articles, and show that outperforms DrQA (Chen et al. (017) and PIQA (Seo et al. 2019) adapted to this task. Finally, we apply DrKIT to multi-hop information retrieval on the HotpotQA dataset (Yang et al., 2018), and show that it significantly improves over a BERT-based reranking approach, while being 10x faster.
DIFFERENTIABLE REASONING OVER A KB OF INDEXED TEXT
We want to answer a question q using a text corpus as if it were a KB. We start with the set of entities in the question g, and would ideally want to follow relevant outgoing relation edges in the KB to arrive at the answer. To simulate this behaviour on text, we first expand z to set of co- occurring mentions m (say using TFIDF). Not all of these co-occurring mentions are relevant for the question q, so we train neural network which filters the mentions based on a relevance score of q to m. Then we can aggregate the resulting set of mentions m to the entities they refer to, ending up with an ordered set 2' of entities which are answer candidates, very similar to traversing the KB. Furthermore, if the question requires more than one hop to answer, we can repeat the above procedure starting with z/. This is depicted pictorially in Figure |
We begin by first formalizing this idea in a prohabilistic framework in 2.1 In 2.2 we describe how the expansion of entities mentions and the filtering of mentions can be performed efficiently, using sparse-matris products and MIPS algorithms (Johnson et al. 2017). Lastly we discuss a pretraining scheme for constructing the mention representations in 22.
We denote the given corpus as D {d1, d2....). where each de (dk. Idd...... ... ) is a sequence of tokens. We start by running an entity linker over the corpus to identify mentions of a fixed set of entities E. Each mention m is tuple (em, km im im) denoting that the text span dim ..... dmm in document km mentions the entity cm E E, and the collection of all mentions in the corpus is denoted as M. Note that typically [M| > 18).
Notation:
2

---

Published as a conference paper at ICLR 2020
Question: When was the Grateful Dead and Bob Dylan album released?
2nd
Zo Entities
Expand entilies mentions
BOW Emb
Query Enc
Dense query vector
Sparse matrix set product
Top-k inner product search
fMM
A E-M
Pretrained mention representations
Mentions
First hop answers
Z1
Contex
Linked KB Facts
LMI
Bob Dybon is American singer- songwriter.
Bib Dylan, countayy ?
Dylan the Dead
Bob Dylnn, profedd Lon,
American beauty
G dratehul Deac formed in 1965 in Alto,
Grazaful bounded))
Aggregate
Located)
The times they...
to entrties
mantions
BM +M-+E
Bob Grateful Dead
performer.
performes
multi-hop questions by iteratively mapping an input of entities X (The Grateful Dead, Dylan) an output set entities (Dylan the Dead, American beauty, ...) which are related any input entity by some relation (alhum by).
Figure 1: DrKIT
2.1 DIFFERENTIABLE MULTI-HOP REASONING
We assume weakly supervised setting where during training only know the final answer entities & for T-hop question. We denote the latent sequence of entities which answer each of the intermediate hops as 20, 21...., E &, where 2g is mentioned in the question, and 27 a. We can recursively write the probability of an intermediate answer as:
Pr(2a/0) = Σ Pr(2+1u, 1-) Pr(zz-14))
(1)
2t-1E8
Here Pr(zo (q) is the output of entity linking system over the question, and Pr(zelg, zt-1) cor- responds to a single-hop model which answers the 1-th hop, given the entity from the previous hop 2r-1, by following the appropriate relation. Eq. [ models reasoning over chain of latent entities, but when answering questions over a text corpus, we must reason over entity mentions, rather than entities themselves. Hence Pr(zelg, 2t-1) needs to be aggregated over all mentions of 2s, which yields
Pr(#1gg) = Σ Σ Pr(z./m) Pr(m|g, zt- Pr((z-119)
(2)
MEM 2E-
The interesting term to model in the above equation Pr(m| q, 2t-1), which represents the relevance of mention given the question and entity 21-1. Following the analogy of a KB, we first expand the entity 2t-1 to co-occuring mentions m and use learned scoring function find the relevance of these mentions. Formally, let ((m) denote a TFIDF vector for the document containing m, G(2,11) be the TFIDF vector of the surface form of the entity from the previous hop, and (m,, 2,9) be learnt scoring function (different for each hop). Thus, we model Pr(m/g 1t-1) as
Pr(m/g, 21-1) 1(G(2-11 F(m)
X sm 21-1.
expansion co-occurring mentions
relevance filtering
Another equivalent way look our model in Eq. 3] is that the second term retrieves mentions of the correct type requested by the question in the t-th hop, and the first term filters these based on co-occurrence with 2,-1. When dealing with a large of mentions m, we will typically retain only the top-K relevant mentions. We will show that this joint modelling of co-occurrence and relevance important for good performance, as was also observed by Seo et (2019)
The other term left in Eq. i Pr(z/m), which if mention m refers to the entity = else 0, based the entity linking system. In general, compute Eq. the mention scoring of Eq. needs to

---

Published as a conference paper at ICLR 2020
be evaluated for all latent entity and mention pairs, which is prohibitively expensive. However, by restricting 8, to be an inner product we can implement this efficiently (22.2)
To highlight the differentiability of the proposed overall scheme, we can represent the computation in Eq. 2 as matrix operations. We pre-compute the TFIDF term for all entities and mentions into sparse matrix, which we denote as Ag-M (e, m] 1 (G(e)= F(m) > c). Then entity expansion to co-occuring mentions can be done using a sparse-matri by sparse-vector multiplication between Ag-M and 2z-1- For the relevance scores, let T (x((s(mm ())1,)) denote the top- K relevant men- tions encoded as a sparse vector in IR R Finally, the aggregation of mentions to entities can be formulated as multiplication with another sparse-matrix - E. which encodes coreference, i.e. mentions corresponding to the same entity. Putting all these together, using @ to denote element- wise product, and defining Ze [Pr(z+ = eilg):-.. ....; Pr(z e(g]l)),, can observe that for large K (i.c., as K + M). Eq. becomes equivalent to:
Z, = softmax ([zī-AA-M C Tx(s:(m, 2-11 BM-E).
(4)
Note that every operation in above equation is differentiable and between sparse matrices and vec- tors: we will discuss efficient implementations in 222 Further, the number of non-zero entries in Zi bounded by K, since we filtered (the dlement-wise product in Eq. 4 to top- K relevant mentions among TFIDF based expansion and since each mention can only point to single entity in BM-EE- This important, as it prevents the number of entries in Z₂ from exploding across hops (which might happen if, for instance, we added the relevance and TFIDF scores instead).
We can view Z,-1, Ze as weighted multisets of entities, and sy (m, q) as implicitly selecting men- tions which correspond to a relation R. Then Eq. 4 becomes a differentiable implementation of Zr Z (Rt), i.e mimicking the graph traversal in a traditional KB. We thus call Eq. 4 teltua operation.
Training and Inference. The model is trained end-to-end by optimizing the cross-entropy loss between Zr, the weighted set of entities after T' hops, and the ground truth answer set A. We use a temperature coefficient when computing the softmax in Eq, 4 since the inner product scores of the top-K retrieved mentions typically high values, which would otherwise result in very peaked distributions of Zz We also found that taking a maximum over the mention set of an entity Ms, in Eq. 2 works better than taking sum. This corresponds to optimizing only over the most confident mention of each entity, which works for corpora like Wikipedia that do not have much redundancy. A similar observation was made by Min et al. (2019) in weakly supervised settings.
2.2 EFFICIENT IMPLEMENTATION
Sparse TFIDF Mention Encoding. To compute the sparse-matrix Ag-M for entity- mention ex- pansion in Eq 4 the TFIDF vectors F(m) and G(z-1) are constructed over unigrams and bigrams, hashed to a vocabulary of 16M buckets. While F computes the vector from the whole passage around m. G only uses the surface form of 2t-1. This corresponds retrieving all mentions a document using 2--1 as the query. We limit the number of retrieved mentions per entity to maxi- mum of μt, which leads to a E| x |M sparse-matrix.
Efficient Entity-Mention expansion. The expansion from a set of entities to mentions occurring around them can be computed using the sparse-matrix by sparse-vector product z Ag--MM A simple lower bound for multiply- ing a sparse [g] x [M| matrix, with maximum j non- zeros in each row, by a sparse |8] x 1 vector with K non-zeros ((Kp)) Note that this lower bound is in- dependent of the size of matrix Ag-M, or in other words independent of the number of entities or mentions. To at- tain the lower bound, the multiplication algorithm must be vector driven, because any matrix-driven algorithms need to at least iterate over all the rows. Instead we slice the relevant rows from AE-M.. To enable this our solution is to represent the sparse-matrix Ag-M as two row-wise lists of variable-sized lists of the indices and
10
sparse x sparse dense
10a
10'
10'
10"
10'
10"
100
20
10'
[E] Mum entilie
Figure 2: Runtime on single K80 GPU when using ragged representations for im- plementing matrix vector product, vs the default sparse-matrix times dense vector product available in TensorFlow. |g| > 10a leads to OOM for the latter.
4

---

Published as a conference paper at ICLR 2020
values of the non-zero elements, respectively. This results in "ragged" representation of the ma- trix (ei.Ras 2018) which can be easily sliced corresponding to the non-zero entries in the vector in O[log [&]) time. We are now left with K sparse-vectors with at most μ non-zero ele- ments in each. We can add these sparse-vectors weighted by corresponding values from the vector zi_, in O(K K max { K, (a)) time. Moreover, such an implementation is feasible with deep learning frameworks such as TensorFlow. We tested the scalability of our approach by varying the number of entities for a fixed density of mentions j (from Wikipedia). Figure 2 compares our approach to the default sparse-matris times dense-vector product available in TensorFlow.
Efficient top-K mention relevance filtering: To make computation of Eq. feasible, we need an efficient way to get top-K relevant mentions related to an entity in žt-1 1 for given question q. without enumerating all possibilities. A key insight is that by restricting the scoring function si (m,, 2t-1, 9) to an inner product, we can easily approximate a parallel version of this computation, across all mentions m. To do this, let f(m) be a dense encoding of m, and gr (i (11) be a dense encoding of the question for the t-th hop, both in Rº (the details of the dense encoding is provided in next paragraph), then the scoring function st (m, 22119) q) becomes
(5) f(m2): with which can be computed in parallel by multiplying a matrix f(M) = [m
(m,, 2,-1. 9) exp [f(m) 90(9, 2-1))
ge(g, 2-11). Although this matrix will be very large for realistic corpus, since eventually only interested in the top-K values, we can use an approximate algorithm for Maximum Inner Prod- uct Search (MIPS) (Andoni et al. 2015: Shrivastava & Li 2014) to find the K top-scoring elements. The complexity of this filtering step using MIPS is roughly O(Kp polylog|Ml).
Mention and Question Encoders. Mentions are encoded by passing the passages they are con- tained in through a BERT-large (Devlin et al. 2019) model (trained as described in (2.3). Sup- pose mention m. appears in passage d, starting at position i and ending at position J. Then f(m) W linear projection to size p. The queries encoded with a smaller BERT-like model: specifically, they are tokenized with WordPieces (Schuster & Nakajima 2012), appended to a special [CLS] token, and then passed through a 4-layer Transformer network (Vaswani et al.) (017) with the same architecture as BERT, producing an output sequence H4, The Ir functions are defined similarly to the BERT model used for SQuAD-style QA. For each hop / 1....,T, T, we add two additional Transformer layers on top of HJ, which will be trained to produce MIPS queries from the [CIS] encoding; the first added layer produces a MIPS query H to retrieve a start token, and the sec- ond added layer& MIPS query H2, to retrieve an end token. We concatenate the two and define Ge(9) (HH Hg.l. Finally, condition current progress we add the embeddings of 21-1- Specifically, we use entity embeddings E E R to construct average embedding of the set Z,-1, as 2,=, E, and define gr(g, 211 = (g) + 27", E. To avoid a large number of parameters in the model, we compute the entity embeddings an average over the word embeddings of the tokens in the entity's 'ss surface form. The computational cost of the question encoder (e(4)) is O(p²).
[H Ht], where 11 the sequence of embeddings output from BERT, and W is
Thus our total computational complexity to answer a query is Ö(K max K, μh + Kp+pp? (almost independent number of entities or mentions!), with O(u[E) + pl.M) memory store the pre- computed matrices and mention index 2
2.3 PRETRAINING THE INDEX
Ideally, we would like to train the mention encoder (m) end-to-end using labeled QA data only. However, this poses a challenge when combined with approximate nearest neighbor sencch-since after every update to the parameters of J, one would need to recompute the embeddings of all mentions in M. We thus adopt a staged training approach: we first pre-train a mention encoder f(m). then compute and index embeddings for all mentions once, keeping these embeddings fixed when training the downstream QA task. Empirically, we observed that using BERT representations "out of the box" do not capture the kind of information our task requires (Appendix C). and thus, pretraining the encoder to capture better mention understanding is a crucial step.
One option adopted by previous researchers (Seo et al. 2018) is to fine-tune BERT on SQuAD (Rajpurkar et al. 2016). However, SQuAD is limited to only 536 articles from Wikipedia, leading to
Following standard convention, in Ô notation we suppress poly log dependence terms.
5

---

Specifically, assume we are given an open-domain KB consisting of facts (e1, R, 62) specifying that the relation R holds between the subject e1 and the object e2. Then for corpus of entity-linked text passages {d we automatically identify tuples (d, (e1, R, ez]) such that dl mentions both e1 and e2. Using this data, we learn to answer slot-filling queries in reading comprehension setup, where the query q is constructed from the surface form of the subject entity e1 and a natural lan- guage description of R (e.g. "Jerry Garcia, birth place, ?"), and the answer 62 needs to be extracted from the passage d. Using string representations in ensures our pre-training setup similar to the Published as a conference paper at ICLR 2020
MetaQA
WikiData
Model
Ihop
2hop
3hop
Model
Ihop
2hop
3hop
DrQA (ots)
0,553
0.325
0.197
DrQA (ots, cascade)
0.287
0.141
0,070
PIQA (ots, cascade)
0.240
0.118
0.064
KVMemt
0.762
0.070
0.195
GraftNetf
0.825
0.362
0,402
PIQA (pre, cascade)
0.670
0.369
0.182
PullNetj
0,844
0.810
0.782
DrKIT (pre, cascade)
0.816
0.404
0.198
DrKIT (e2e) DrKIT (strong sup.)
0,844
0.860
0.876
DrKIT (e2e) -BERT index
0.834
0.469
0.244
0.845
0.871
0.871
0.643
0.294
0.165
Table 1:
(Left) MetaQA and (Right) WikiData Hits @1 for 1-3 hop sub-tasks, ots: off-the-shelf without re-
training. t: obtained from Sun et al. (2019). cascade: adapted to multi-hop setting by repeatedly applying Eq. 2 pre: pre-trained slot-filling. e2c: end-to-end trained single-hop and multi-hop queries.
a very specific distribution of questions, and is not focused on entity- and relation-centric questions. Here instead train the mention encoder using distant supervision from KB.
downstream task. In pretraining, we use the same scoring function as in previous section, but over all spans m in the passage:
s(m, e1, q) x exp (f(s) e1g,
Following Seo et al. (2016), we normalize start and end probabilities of the span separately.
For effective transfer to the full corpus setting, we must also provide negative instances during pre- training. i.e. query and passage pairs where the answer is not contained in the passage. We consider three types of hard negatives: (1) shared-entity negatives, which pair a query (c1, R, ?) with a pas- sage which mentions 61 but not the correct tail answer; (2) shared-relation negative, which pair query (ei, R, ?) with a passage mentioning two other entities ej and e/ in the same relation Rt; and (3) random negalives, which pair queries with random passages from the corpus.
For the multi-hop slot-filling experiments below, we used WikiData Vrandečie Krötzsch 2014) as our KB, Wikipedia as the corpus, and SLING (Ringgaard et al. 2017) to identity entity mentions. We restrict d be from the Wikipedia article of the subject entity reduce noise. Overall we collected 950K pairs over 550K articles. For the experiments with MetaQA, we supplemented this data with the corpus and KB provided with MetaQA, and string matching for entity linking.
EXPERIMENTS
3.1 METAQA: MULTI-HOP QUESTION ANSWERING WITH TEXT
Dataset. We first evaluate DrKIT the MetaQA benchmark for multi-hop question answering Zhang et al. 2018). MetaQA consists of around 400K questions ranging from to 3 hops con- structed by sampling relation paths from movies KB (Miller et al.] 2016)) and converting them to natural language using templates. The questions cover relations and their inverses, around 43K entities, and are paired with a corpus consisting of 18K Wikipedia passages about those entities. The questions are all designed to be answerable using either the KB or the corpus, which makes it possible to compare the performance of our "virtual KB" QA system to a plausible upper bound system that has access to a complete KB. We used the same version of the data as Sun et al. (2019) Details of the implementation are in Appendix A
Results. Table D shows the accuracy of the top-most retrieved entity (Hits@) 1) for the sub-tasks ranging from 1-3 hops, and compares to the state-of-the-art systems for the text-only setting these

---

Published as a conference paper at ICLR 2020
0.8
0.85
X0<
Hits (6)
0.3+
Hits @1
0.80
Hits
0.2
XXX
X
0.75
Mist 3-101
PulNe: S.ppp
Pust 2hop
VSR 2-hop
0.1-
*
IQUATT 2-10s
X
PRAART Shop teppp
0.6
NiziOA 2012
Cyla hhopp
DV07 2-10
oe0r hhop
MazacA Shep
5
10
15
20
25
5
10
15
20
2000 4000 6000 8000 10000 Num nearest neighbors
0/sec
Q/sec
Figure 3: Hits @1 vs Queries/sec during inference on (Left) MetaQA and (Middle) WikiData tasks, measured on a single CPU server with 6 cores. MSR: Multiistep Retriever model from Das el al. (2019a) (we only show Q/sec). (Right) Effect of varying number of nearest neighbors K during MIPS.
tasks. DrKIT outperforms the prior -fate-of-the-arl by large margin the 2-hop and 3-hop cases. The strongest prior method, PullNet (Sun et al.) 2019 2018), uses graph neural network model with learned iterative retrieval from the corpus to answer multi-hop questions. It uses the MetaQA KB during training to identify shortest paths between the question entity and answer entity, which are used supervise the text retrieval and reading modules. DrKIT, on the other hand, has strong performance without such supervision, demonstrating its capability for end-to-end learning. (Adding the same intermediate supervision DrKIT does not even consistently improve performance gives DrKIT a small lift on 1- and 2-hop questions but does not help for 3-hop questions.)
DrKIT's architecture is driven, in part, by efficiency considerations: unlike PullNet, it is designed to answer questions with minimal processing at query time. Figure 3 compares the tradeoffs between accuracy and inference time of DrKIT with PullNet as we vary K, the number of dense nearest neighbors retrieved. The runtime gains of DrKIT over PullNet range between 5x-15x.
Analysis. We perform ablations on DrKIT for the MetaQA data. First, we empirically confirm that tak- ing sum instead of max over the mentions of an en- tity hurts performance. So does removing the softmax temperature (by setting À 1). Removing the TFIDF component from Eq. 3 leads a large decrease in perfor- mance for 2-hop and 3-hop questions. This is because the TFIDF component constrains the end-to-end learn- ing to be along reasonable paths of co-occurring men- tions, preventing the search space from exploding. The results also highlight the importance of the pretraining method of [2.3) as DrKIT over an index of BERT rep- resentations without pretraining is 23 points worse in the 3-hop case. We also check the performance when the KB used for pre-training is incomplete. Even with only 50% edges retained, we see good performance-
Ablations
lhop
2hop
3hop
DrKIT
0.844
0.860
0.876
-Smm over M..
0.837
0.823
0.797
-À 1
0.836
0.752
0.799
-W/ TFIDF
0.845
0.548
0.488
BERT index
0.634
0.610
0.555
Incomplete KB for pretraining
25% KB
0.839
0.804
0.830
50% KB
0.843
0.834
0.834
(50% KB-only) 0.680
0.521
0.597
than PullNet and the state-of-the-a for KB-only method (in italics).
We analyzed 100 2-hop questions correctly answered by DrKIT and found that for 83, the intermedi- ate answers were also correct. The other 17 cases were all where the second hop asked about genre, c.g. "What are the genres of the films directed by Justin Simien?". We found that in these cases the intermediate answer was the same as the correct final answer-essentiall. the model learned to answer the question in 1 hop and copy it over for the second hop. Among incorrectly answered questions, the intermediate accuracy was only 47%, so the mistakes were evenly distributed across the two hops.
3.2 WIKIDATA: MULTI-HOP SLOT-FILLING
The MetaQA dataset has been fairly well-studied, but has limitations since it is constructed over a small KB. In this section we consider a new task, in larger scale setting with many more relations, entities and text passages. The new dataset also lets us evaluate performance in a setting where the test set contains documents and entities not seen at training time, an important issue when devising QA system that will be used in a real-world setting, where the corpus and entities in the discourse change over time, and lets us perform analyses not possible with MetaQA, such as extrapolating from single-hop to multi-hop settings without retraining.
7

---

Published as a conference paper at ICLR 2020
Dataset. We sample two subsets of Wikipedia articles, one for pre-training (2.3) and end-to-end training, and one for testing. For each subset we consider the set of WikiData entities mentioned in the articles, and sample paths of 1-3 hop relations among them, ensuring that any intermediate entity has an in-degree of no more than 100. Then we construct a semi-structured query by concatenating the surface forms of the head entity with the path of relations (e.g. "Helene Gayle, employer, founded by, ?"") The answer is the tail entity at the end of the path, and the task to extract it from the Wikipedia articles. Existing slot-filling tasks (Levy et al. 2017, [Surdeanu] (013) focus on a single- hop, static corpus setting, whereas our task considers dynamic setting which requires the system to traverse the corpus. For each setting, we create a dataset with 10K articles, 120/ passages, > 200 entities and 1.5M mentions, resulting in an index of size about 2gb. We include example queries in Appendix B
Baselines. We adapt two publicly available open-domain QA systems for this task DrQA Chen et al. 2017) and PIQA Seo et al. 2019). While DrQA is relatively mature and widely used, PIQA recent, and similar to our setup since it also answers questions with minimal computation at query time. It is broadly similar to single textual follow operation in DrKIT, but is not constructed to allow retrieved answers to be converted entities and then used in subsequent processing, so is not directly applicable to multi-hop queries. We thus also consider a cascaded architecture which repeatedly applies Eq. 2 using either of PIQA or DrQA to compute Pr(zelg: 24-1) against the corpus, retaining at most & intermediate answers in each step. We tune & in the range of 1-10, since larger values make the runtime infeasible. Further, since these models were trained on natural language questions, we use the templates released by Levy et al. (2017) to convert intermediate questions into natural text We test off off-the-shelf versions of these systems, as well as version of PIQA re- re-trained on our our sTot-filling data O We compare to a version of DrKIT trained only on single-hop queries ($..3 and similarly cascaded, and one version trained end-to-end on the multi-hop queries.
We
Results. Table (right) lists the Hits @1 1 performance on this task. Off-the-shelf open-domain QA systems perform poorly, showing the challenging nature of the task. Re-training PIQA on the slot- filling data improves performance considerably, but DrKIT trained on the same data improves on it. A large improvement over these cascaded architectures is seen with end-to-end training, which is made possible by the differentiable operation introduced in this paper. We also list the performance of DrKIT when trained against an index of fixed BeRT-large mention representations. While this is comparable to the re-trained version of PIQA, it lags behind DrKIT pre-trained using the KB, once again highlighting the importance of the scheme outlined in (2.3 We also plot the Hits @1 against Queries/sec for cascaded versions of PIQA and DrKIT in Figure 3 (middle). We observe runtime gains of 2x-3x to DrKIT due to the efficient implementation of entity mentionn expansion of 222
Analysis. In order to understand where the accuracy gains for DrKIT come from, we conduct experiments on the dataset of slot-filling queries released by Levy et al. (2017). We construct an open version of the task by collecting Wikipedia articles of all subject entities the data. A detailed discussion is in Appendix [ and here we note the main findings. PIQA trained on SQuAD only gets 30% macro-avg accuracy on this data, but this improves 46% when re-trained on our slot-filling data. Interestingly, a version of DrKIT which selects from all spans in the corpus performs similarly to PIQA (50%), but when using entity linking it significantly improves 66%. It also has 55% accuracy in answering queries about rare relations, i.e. those observed < 5 times in its training data. We also conduct probing experiments comparing the representations learned using slot-filling to entity
those by vanilla BERT. We found that while the two are comparable in detecting rypes, the slot- follfii version is significantly better at encoding entity co-occurrence information.
3.3 HOTPOTQA: MCLTI-HOP INFORMATION RETRIEVAL
Dataset. HotpotQA (Yang et al. 2018 is a recent dataset of over 100K crowd-sourced multi-hop questions and answers over introductory Wikipedia passages. We focus on the open-domain fullwiki
https://githhb... www /ttom/wwniie http://...oommmmm//n////aa/
For example, "Helene Gayle. employer?" becomes "Who the employer Helene Gayle?"
6 We tuned several hyperparameters of PIQA on our data, eventually picking the sparse first strategy, sparse weight of 0, and filter threshold of 0.2. For the SQuAD trained version, we also had remove paragraphs smaller than 50 tokens since with these the model failed completely.
8

---

Published as a conference paper at ICLR 2020
Accuracy
Model
Q/s
@
@5
@ 10
@20
Model
EM
F1
BM251
0.093
0.191
0.259
0.324
PRF-Task!
0.097
0.198
0.267
0.330
Baseline
0.288
0.381
BERT re-ranker!
0.146
0.271
0.347
0.409
+EC IR
0.354
0.462
Entity Centric IR!
0.32
0.230
0.482
0.612
0.674
+ Golden Ret
0.379
0.486
+DrKIT
0.357
0.466
DrKIT (WikiData)
0.355
0,588
0.671
0.710
DrKIT (Hotpot)
4.26
0.385
0,595
0.663
0.703
DrKIT (Combined)
0.383
0.603
0.672
0.710
Table 2: (Left) Retrieval performance on the HoipoiQA benchmark dev set. Q/s denotes the number of queries per second during inference on single 16-core CPU. Accuracy @ k is the fraction where both the correct passages are retrieved in the top kt 1; Baselines obtained from Das et al. (2019b). For DrKIT, we report the performance when the index is pretrained using the WikiData KB alonc, the HotpotQA training questions alone, using both. ": Measured on different machines with similar specs. (Right) Overall performance on the HotpotQA task, when passing 10 retrieved passages to downstream reading comprehension model (Yang)
ct al. 2018 4; From Das et al. 2019b). ? From Qi ct al. 2019 f; Results on the dev set.
setting where the two gold passages required to answer the question are not known in advance. The answers are free-form spans of text in the passages, necessarily entities, and hence our model which selects entities is not directly applicable here. Instead, inspired by recent works (Das et al. 2019b) Qi et al. 2019), we look at the challenging sub-task of retrieving the passages required to answer the questions from a pool of 5.23M. This is a multi-hop IR task, since for many questions at least one passage may be 1-2 hops away from the entities in the question. Further, each passage is about an entity (the title entity of that Wikipedia page), and hence retrieving passages is the same identifying the title entities of those passages. We apply DrKIT to this task of identifying the two entities for each question, whose passages contain the information needed to answer that question. Then we pass the top 10 passages identified this way to a standard reading comprehension architecture from Yang et (2018) to select the answer span.
Setup. We use the Wikipedia abstracts released by Yang et al. (2018) as the text corpus The total number of entities is the same as the number of abstracts, 5.23M, and we consider hyperlinks in the text mentions of the entities to whose pages they point to, leading to 22.8M total mentions in an index of size 34GB. For pretraining the mention representations, we compare using the WikiData KB as described in 42.3 to directly using the HotpotQA training questions, with TFIDF based retrieved passages as negative examples. We set Ag-au m] page of the entity denoted by m, or vice versa. For entity linking over the questions, we retrieve the top 20 entities based on the match between a bigram based TFIDF vector of the question with similar vector derived from the surface form of the entity (same as the title of the Wiki article). We found that the gold entities that need be retrieved are within 2 hops of the entities linked in this manner for 87% of the dev examples.
if either the entity e is mentioned on the
Unlike the MetaQA and WikiData datasets, however, for HotpotQA do not know the number of hops required for each question in advance. Instead, we run DrKIT for 2 hops for each question. and then take a weighted average of the distribution over entities after each hop Z To Zo + Z1 + TzZ2. Zo consists of the entities linked to the question itself, rescored based on an encoding of the question, since in some cases one or both the entities to be retrieved are in this set Z and Zn are given by Eq. The mixing weights π. are the softmax outputs of a classifier on top of another encoding of the question, learnt end-to-end end on the retrieval task. This process can be viewed as soft mixing of different templates ranging from 0 to 2 hops for answering a question, similar NQL (Cohen et al. 2019).
Results. We compare our retrieval results to those presented (Da et al. (2019b) in (Lele)](eeft). We measure the accuracy @k retrievals, which is the fraction of questions for which both the re- quired passages are in the top retrieved ones. We see an improvement in accuracy across the board,
https http:://hhotoooooo wwt.tii.ttti.ttiiaee. readme .html For example, for the question "How elephants connected Gajabrishta?", one of the passages to be retrieved is "Gajabrishta" itself.

---

Published as a conference paper at ICLR 2020
Runtime
Answer
Sup Fact
Joint
System
#Bert
s/Q
EM
F1
EM
F1
EM
F1
Baseline Yang ct al.
2018
25.23
34.40
5.07
40.69
2.63
17.85
Golden Ret (Qi al. 2019)
1.4
37.92
48.58
30.69
64.24
18.04
39.13
Semantic Ret (Ne al.
2019)
50*
40.0
45.32
57.34
38.67
70.83
25.14
47.60
HGN (Fang et al. 2019)
50"
40.01
56.71
69.16
49.97
76.39
35.63
59.86
Rec Ret (Asai et al. 2020
500"
133.2
60.04
72.96
49.08
76.41
35.35
61.18
DrKIT + BERT
1.2
1.3
42.13
51.72
37.05
59.84
24.69
42.88
Table 3: Official leaderboard evaluation the test of HotpotQA. #Bert refers to the number of calls BERT (Devlin et al. 2019) the model. s/Q denotes seconds per query (using batch size 1) for inference on single 16-core CPU. Answer. Sup Fact and Joint are the official evaluation metries for HotporQA. ": This is the minimum number of BERT calls based on model and hyperparameter descriptions in the respective papers. t Computed using code released by authors, using a batch size of L. f; Estimated based on the number of BERT calls, using 0.8s as the time for one call (without considering overhead due to other computation in the model). : One call to 5-layer Transformer, and one call to BERT.
with much higher gains @2 and @5. The main baseline is the entity-centric IR approach which runs a BERT-based re-ranker on 200 pairs of passages for each question. Importantly DrKIT also im- proves by over 10x in terms of queries per second during inference. Note that the inference time is measured using a batch size of 1 for both models for fair comparison. DrKIT can be easily run with batch sizes up 40, but the entity centric IR baseline cannot due the large number of runs of BERT for each query. When comparing different datasets for pretraining the index, there is not much difference between using the WikilData KB, or the HotpotQA questions. The latter has better accuracy @2, but overall the best performance is when using a combination of both.
In Table 2 (Right), we check the performance of the baseline reading comprehension model from Yang et al. 2018), when given the passages retrieved by DrKIT. While there is a significant improve- ment over the baseline which uses TFIDF based retrieval, we see only small improvement over the passages retrieved by the entity-centrie IR baseline, despite the significantly improved accuracy @ 10 of DrKIT. Among the 33% questions where the top 10 passages do not contain both the cor- rect passages, for around 20% the passage containing the answer is also missing. We conjecture this percentage is lower for the entity-centric IR baseline, and the downstream model is able to answer some of these questions without the other supporting passage.
Lastly, we feed the top 5 passages retrieved by DrKIT to an improved answer span extraction model based on BERT. This model implements a standard architecture for extracting answers from text, and is trained to predict both the answers and the supporting facts. Details are included in Appendix [ Table the performance of this system on the HotpotQA test set, compared with other recently published models on the leaderboard"" 19 terms of accuracy, DrKIT+BER'S reaches a modest score of 42.88 joint F1, but is considerably Taster (up to 100x) than the models which outperform it.
4 RELATED WORK
Neural Query Language (NQL) (Cohen et al., 2019) defines differentiable templates for multi-step access to symbolic KB, in which relations between entities explicitly enumerated. Here, focus on the case where the relations are implicit in mention representations derived from text. Knowledge Graph embeddings (Bordes al. 2013] Yang et al. 2014, Dettmers et al. 2018) at- tach continuous representations to discrete symbols which allow them to be incorporated in deep networks ( (Yang& & Mitchell 2017). Embeddings often allow generalization to unseen facts using relation patterns, but text corpora are more complete in the information they contain.
Talmor& & Berant 2018) also examined answering compositional questions by treating a text corpus (in their case the entire web) as a KB. However their approach consists of parsing the query into a computation tree, and running a black-box QA model on its leaves separately, which cannol be trained end-to-end. Recent papers have also looked complex QA using graph neural networks
As of February 23, 2020: https://hotppttqap www.t.tttiii... io/
10

---

Published as a conference paper at ICLR 2020
(Sun al. 2018 Cao al. 2019 Xiao al., 2019) by identifying paths of entities in text (Jing ct al. 2019) 9 Kundu et a [209 Dhingra et al. (2018). These approaches rely on identifying a small relevant pool of evidence documents containing the information required for multi-step QA. Hence, Sun al. (2019) and Ding al. (2019), incorporate dynamic retrieval process to add text about entities identified as relevant in the previous layer of the model. Since the evidence text is processed a query-dependent manner, the inference speed is slower than when it pre-processed into an indexed representation (see Figure 3) The same limitation is shared by methods which perform multi-step retrieval interleaved with a reading comprehension model (Das al. 2019a Feldman &
Cl-Yaniv 2019; Lee et al. 2019)
5 CONCLUSION
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 imitate traversal in KB over the text corpus, providing ability to follow relations in the "virtual" KB over text. We achieve state-of-the-an art results the MetaQA dataset for answering natural language questions, with 9 point increase in the 3-hop case. We also developed an efficient implementation using sparse operations and inner product search, which led 10-100x increase in Queries/sec over baseline approaches.
ACKNOWLEDGMENTS
Bhuwan Dhingra was supported by Siemens fellowship during this project. This work was sup- ported in part by ONR Grant NO0014 1112281, Google, Apple, and grants from NVIDIA.
REFERENCES
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Advances in Neural Information Processing Systems, pp. 1225-1233 2015.
Akari Asai, Kazuma Hashimoto, Hannaneh Hajishirzi, Richard Socher, and Caiming Xiong. Learn- ing to retrieve reasoning paths over wikipedia graph for question answering. In International Conference on Learning Representations, 2020.
Antoine Bordes, Nicolas Usumier, Alberto Garcia-Duran, Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi nulti-relational data. In Advances in neural information processing systems, pp. 2787-2795, 2013.
Yu Cao, Meng Fang, and Dacheng Tao. Bag: Bi-directional attention entity graph convolutional network for multi-hop reasoning question answering. In North American Association for Compu- tational Linguistics (NAACL), 2019.
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading Wikipedia to answer open- domain questions. Association for Computational Linguistics (ACL), 2017.
William Cohen, Matthew Siegler, and Alex Hofer. Neural query language: knowledge base query language for tensorflow. arXiv preprint arXiv:1905.06609 2019.
Rajarshi Das, Shehzuad Dhuliawala, Manzil Zaheer, and Andrew McCallum. Multi-step retriever- reader interaction for scalable open- open-domain question answering. International Conference on Learning Representations (ICLR), 2019a.
Rajarshi Das, Ameya Godbole, Dilip Kavarthapu, Zhiyu Gong, Abhishek Singhal, Mo Yu, Xiaoxiao Guo, Tian Gao, Hamed Zamani, Manzil Zaheer, and Andrew McCallum. Multi-step entity-centric information retrieval for multi-hop question answering. In Proceedings of the 2nd Workshop on Machine Reading for Question Answering. pp. 113-118, Hong Kong, China, November 2019b. Association for Computational Linguistics. doi: 18.18663/v 1/D19-DDI11- URL httpt::t////a..
ac Sclweb.orq/anne htw.ebbrrrr/atthooog////33 5816
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d
knowledge graph embeddings. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.

---

Published as a conference paper at ICLR 2020
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. NAACL, 2019.
Bhuwan Dhingra, Qiao Jin, Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Neural
models for reasoning multiple mentions using coreference. In North American Association for Computational Linguistics (NAACL), 2018.
Ming Ding, Chang Zhou, Qibin Chen, Hongxia Yang, and Jie Tang. Cognitive graph for multi-hop reading comprehension at scale. Association for Computational Linguistics (ACL), 2019.
Yuwei Fang, Siqi Sun, Zhe Gan, Rohit Pillai, Shuohang Wang, and lingjing Liu. Hierarchical graph network for multi-hop question answering. arXiv preprint arXiv: 1.03663,, 2019.
Yair Feldman and Ran El- Yaniv. Multi-hop paragraph retrieval for open- question answering. In Association for Computational Linguistics (ACL), 2019.
Yichen Jiang, Nitish Joshi, Yen-Chun Chen, and Mohit Bansal. Explore, propose, and assemble: An interpretable model for multi-hop reading comprehension. In Association for Computational Linguistics (ACL), 2019.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. arXiv preprint arXiv:1702.08733 2017.
Souvik Kundu, Tushar Khot, and Ashish Sabharwal. Exploiting explicit paths for multi-hop reading comprehension. In Association for Computational Linguistics (ACL), 2019.
Kenton Lee. Ming- Wei Chang, and Kristina Toutanova. Latent retrieval for weakly supervised open domain question answering. Association for Computational Linguisties (ACT.), 2019.
Omer Levy, Minjoon Seo, Eunsol Choi, and Luke Zettlemoyer. Zero-shot relation extraction via reading comprchension. In Proceedings of the 21st Conference Computational Natural Lan- guage Learning (CoNLL 2017). pp. 533-342, 2017.
Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Ja- son Weston. Key-value memory networks for directly reading documents. arXiv preprint arXiv:1606.03 2016.
Bonan Min, Ralph Grishman, Li Wan, Chang Wang, and David Gondek. Distant supervision for relation extraction with an incomplete knowledge base. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 777-782, 2013.
Sewon Min, Danqi Chen, Hannaneh Hajishirzi, and Luke Zettlemoyer. A discrete hard em approach for weakly supervised question answering. In EMNLP, 2019.
Dan Moldovan, Marius Pasca, Sanda Harabagiu, and Mihai Surdeanu. Performance issues and error analysis in an open-domain question answering system. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 33-40, Philadelphia. Pennsylvania, USA, July 2002. Association for Computational Linguistics. doi: 10.3115/1073083.10777 1073091. URL wttpt:tt:////.. //www///wwwwwwww a c org wtt.://///atoooloooo/--------
Yixin Nie, Songhe Wang, and Mohit Bansal. Revealing the importance of semantic retrieval for ma- chine reading at scale. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Process- ing (EMNLP-IJCNEL pp. 1553-2566, 2019.
Peng Qi, Xiaowen Lin, Leo Mehr, Zijian Wang, and Christopher D. Manning. Answering com- plex open-domain questions through iterative query generation. In 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Lan-
guage Processing (EMNLP-IJCNLP), 2019, URL httpt:://// http:///..p.ssst.....to edu/ edu/pubs. pubss/
qi201 112019answering. pdd
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions
for machine comprehension of text. arXiv preprint 1606v:/606.0522 2016.
12

---

Published as a conference paper at ICLR 2020
Michael Ringgaard, Rahul Gupta, and Fernando CN Pereira. Sling: A framework for frame semantic parsing. arXiv preprini urXiv: (71.:000200002, 2017.
Mike Schuster and Kaisuke Nakajima. Japanese and korean voice search. In 2012 JEEE Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2012.
IEEE,
Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. Green ai. arXiv preprini arXiv:/907. 10597, 2019.
Minjoon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. Bidirectional attention flow for machine comprehension. arXiv preprint arXiv:1611.0160; 2016.
Minjoon Sco, Tom Kwiatkowski, Ankur P Parikh, Ali Farhadi, and Hannanch Hajishirzi. Phrase- indexed question answering: A new challenge for scalable document comprehension. In EMNLP, 2018.
Minjoon Seo, Jinhyuk Lee, Tom Kwiatkowski, Ankur P Parikh, Ali Farhadi, and Hannaneh Ha- jishirzi. Real-time open open-domain question answering wikipedia with dense-sparse phrase index. In Association for Computational Linguistics (ACL), 2019.
Anshumali Shrivastava and Ping Li, Asymmetric Ish (alsh) for sublinear time maximum inner prod- uct search (mips). In Advances in Neural Information Processing Systems, pp. 2321-2329, 2014.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in nlp. arXiv preprint arXiv: 02243,2223433 2019.
Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William W Cohen. Open domain question answering using early fusion of knowledge bases and text. In Proceedings of the Conference Empirical Methods in Natural Language Processing (EMNLP), 2018.
Haitian Sun, Tania Bedrax-Weiss, and William W Cohen. Pullnet: Open domain question answer- ing with iterative retrieval on knowledge bases and text. In Proceedings of the Conference on Empirical Methods Natural Language Processing (EMNLP), 2019.
Mihai Surdeanu. Overview of the tac2013 knowledge base population evaluation: English slot filling and temporal slot filling. In TAC, 2013.
A. Talmor and J. Berant. The web as knowledge-base for answering complex questions. In North American Association for Compulational Linguistics (NAACL), 2018
Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang, Adam Poliak, R Thomas McCoy, Najoung Kim, Benjamin Van Durme, Sam Bowman, Dipanjan Das, and Ellie Pavlick. What do you learn from context? probing for sentence structure in contextualized word representations. In International Conference on Learning Representations, 2019. id-SJz8gnRcKX
forum?
tf. TeRaggedTensors. TensorFlow Ragged Tensors, 2018. URL https::/www.tensscrrt. http://www.eeee
btq/quide/raqeee Senpsggeeeeeeerrrsseeeeee
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp.
2017.
Denny Vrandečié and Markus Krötzsch. Wikidata: a free collaborative knowledge base. 2014.
Yunxuan Xiao, Yanru Qu, Lin Qiu, Hao Zhou, Lei Li, Weinan Zhang, and Yong Yu. Dynami- cally fused graph network for multi-hop reasoning. In Association for Computational Linguistics (ACL), 2019.
Bishan Yang and Tom Mitchell. Leveraging knowledge bases in Istms for improving machine read- ing. 2017.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv: arXiv: 141.65575 2014.
13

---

Published as a conference paper at ICLR 2020
Wei Yang, Yuqing Xie, Aileen Lin, Xingyu Li, Luchen Tan, Kun Xiong, Ming Li, and Jimmy Lin. End-to-end open-domain question answering with bertserini. arXiv preprint FrXiiv:902.0f1. 2019.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpoiQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the Conference on Empirical Methods in Natural Language Pro- cessing (EMNLP), 2018.
Yuyu Zhang, Hanjun Dai, Zornisaa Kozareva, Alexander Smola, and Le Song. Variational reason- ing for question answering with knowledge graph. In AAAI, 2018.
A METAQA: IMPLEMENTATION DETAILS
We use p = 400 dimensional embeddings for the mentions and queries, and 200-dimensional em- beddings each for the start and end positions. This results in index of size 750MB. When com- puting Ag-M, the entity to mention co-occurrence matrix, we only retain mentions in the top 50 paragraphs matched with 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 Zo 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 X = 4 to work best. We pretrain the index on combination of the MetaQA corpus, using the KB provided with MetaQA for distance data, and the WikiData corpus.
B WIKIDATA DATASET STATISTICS
Task
#train
#dev
#test
[teest]
[Mtestl
Dreat
Example
Mendix, industry?
lhop
16901
2467
10000
216K
1.2M
120K
A. Enterprise Software
2000 Hel het Mergelland, winner, place birth?
2hop
163607
398
9897
342K
1.9M
120K
A. Bert Grabsch + Lutherstadt Wittenberg
Magnificentl, record label, founded by, date of death?
3hop
36061
453
9899
261K
1.8M
120K
A. Prestige + Bob Weinstock +
14 Jan 2006
Table 4: WikiData dataset
Details of the collected WikiData dataset are shown in Table
C INDEX ANALYSIS
Single-hop questions and relation extraction. Levy et al. (017)) released dataset of 1M slot- filling queries of the form (e1, R, ?) paired with Wikipedia sentences mentioning é1, which was used for training systems that answered single-step slot-filling questions based on small set of candidate passages. Here we consider an open version of the same task, where answers to the queries must be extracted from a corpus rather than provided candidates. We construct the corpus by collecting and entity-linking all paragraphs in the Wikipedia articles of all 8K subject entities in the dev and test sets, leading to total of 109K passages. After constructing the TFIDF Ag-M and coreference BM-+ matrices for this corpus, we directly use our pre-trained index to answer the test set queries.
Figure (Right) shows the Hits@ performance of the Levy et al. 2017) slot-filling dataset. We report results 2 subsets of relations in addition all relations. The Rare subset comprises of rela- tions with frequencies < 5 in the training data while the 'Frequent' subset contains the rest. DrKIT on entity-mentions consistently outperforms the other phrase-based models showing the benefit of
14

---

Published as a conference paper at ICLR 2020
Probing Task
Negative Example
BERT
DrKIT
Shared
Neil Herron played for
6.05
0.850
0.876
Entity
West of Scotland.
Shared
William Paston was
0.715
0.846
Relation
British politician.
Figure 4: Left: F1 scores on Shared Entity and Shared Relation negatives. The negative examples for the Query (Neil Herron, occupation, ?). Right: Macro-avg accuracy on Levy et al. (2017) relation extraction dataset. We split the results based on frequency the relations in our WatiData training data. DrKIT-all spans refers to variant of model which selects from all spans in the corpus, instead of only entity-linke linked mentions.
indexing only entity- mentions in single-hop questions over all spans. Note that DrKit-entitess has high Hits @ performance on the Rare relations subset, showing that there is generalization to less frequent data due to the natural language representations of entities and relations.
Probing Experiments Finally, to compare the representations learned by the BERT model fine- tuned on the WikilData slot-filling task, we design two probing experiments. In each experiment, keep the parameters of the BERT model (mention encoders) being probed fixed and only train the query encoders. Similar Tenney al. (2019), here rather than only the top-most layer, where the weights are Iearned on the probing task.
weighted average of the layers of BERT
In the first experiment, train and test shared-entity negatives. Good performance here means the BERT model being probed encodes fine-grained entity-type information reliably As shown in Table 4 BERT performs well on this task, suggesting it encodes fine-grained types well.
In the second experiment, train and only on shared-relation negatives. Good performance here means that the BERT model encodes entity co-occurrence information reliably. In this probe task, we see large performance drop for BERT, suggesting it does not encode entity co-occurrence information well. The good performance of the DrKIT model on both experiments suggests that fine-tuning the slot-filling task primarily helps the contextual representations also encode entity co-occurrence information, addition to entity type information.
D HOTPOTQA ANSWER EXTRACTION
On HotpotQA, we use DrKIT to identify the top passages which are likely to contain the answer to question. We then train separate model extract the answer from concatenation of these pas- sages. This model is a standard BERT-based architecture used for SQuAD (see Devlin et al. (2019) for details), with few modifications. First, handle boolean questions, on top of the [CLS] representation from BERT to decide whether the question has a "span" " "yes" or "no" answer, respectively. During inference, if this classifier has the highest probability "span" we extract start and end position similar to Devlin et al. (2019), else we directly answer as "yes" or "no".
train 3-way classifier
Second, handle supporting fact prediction, we prepend each sentence in the concatenated passages passed to BERT with a special symbol [unused0], and train a binary classifier top of the representation of each of these symbols output from BERT. The binary classifier is trained predict 1 for sentences which are supporting facts and () for sentences which are not. During inference, we take all sentences for which the output probability of this classifier is > 0.5 as supporting facts.
The training loss is an average of the loss for the 3-way classifier (C.s), the sum of the losses for the supporting fact classifiers (Lep), and the losses for the start and end positions of span answers (Lsts ).n):
(Lets + Lip + Lst f/n)/4
A reasonable heuristic for solving this task simply detect entity with the correct type in the given sentence, since all sentences contain the subject entity.
15

---

Published as a conference paper at ICLR 2020
We train the system on passages per question, provided in the distractor setting of HotpotQA gold ones and negatives from a TFIDF retriever. We keep the gold passages at the beginning for 60% of the examples, and randomly shuffle all passages for the rest, since during inference the correct passages are likely be retrieved the top by DrKIT. Other hyperparameters include batch size 32, learning rate 5 x 10-5, number of training epochs 5, and maximum combined passage length 512.
16


Reviews:
[{"review_id": "SJx1TwS5YH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a new architecture for question answering, that can be trained in an end-to-end fashion. The model expands the entities in a given question to relevant mentions, which are in turn aggregated to a new set of entities. The procedure can be repeated for multi-hop questions. The resulting entities are returned as candidate answers. The approach relies on an index of mentions for approximate MIPS, and on sparse matrix-vector products for fast computation. Overall, the model processes queries 10x faster than previous approaches. The method provides state-of-the-art results on the MetaQA benchmark, with significant improvements on 3-hop questions. The experiments are detailed, and the paper is very well written.\n\nA few comments / questions:\n\n1. Do you have any explanation of why taking the max instead of the sum has a significant impact on the 2,3-hop performance, but only gives a small improvement for 1-hop questions?\n\n2. The same observation can be done for the temperature lambda=1 vs lambda=4, so I was wondering about the distribution of the entities you get on the output of the softmax (in Eq 4). Is the distribution very spiky, and Z_t usually only composed of a few entities? In that case, I guess lambda=4 encourages the model to explore/update more relation paths? Something that works very well in text generation is to not just set a temperature, but also to apply a softmax only on the K elements with the highest score (so the softmax is applied on K logits, and everything else is set to 0). Did you consider something like this? It may prevent the model from considering irrelevant entities, but also from considering only a few ones.\n\n3. Given the iterative procedure of the method, I wonder how well the model would generalize to more hops. Did you try for instance to train with 1/2 hops and test whether it can generalize to 3-hop questions?\n\n4. In Section 2.3, you fix the mention encoder because training the encoder would not work with the approximate nearest neighbor search (I assume this is because the index would need to be rebuilt). However, the ablation study suggests that the pretraining is critical, and one could imagine that fine-tuning the mention encoder would improve the performance even further. Instead of considering a mention encoder, could you have a lookup table of mentions (initialized with BERT applied on each mention), where mention embeddings are fine-tuned during training? The problem of the index is still there, but could you consider an exact search on the lookup table (exact search over a few million embeddings is slow, but it should still run in a reasonable amount of time using a framework like FAISS, and it would give an upper-bound of the performance you could achieve by fine-tuning the mention encoder).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1lvMjxAFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies scaling multi-hop QA to large document collections, rather than working with small candidate lists of  document/paragraphs  (as done in most of the previous work), a very important, practical and challenging direction.\n\nThey start with linking mentions to entities in a knowledge base. Every iteration of their mult-hop system produces a set of entities Z_t, relying on entities predicted on the first representation Z_{t-1} and the question representation.   In order to make training tractable, they mask 'attention'  between Z_{t-1}  and Z_t (actually mentions corresponding to Z_t).  They also use top-K relevant mentions at train and test time. As the attention score is based on dot-product, they can plug-in the approximate Maximum Inner Product Search to avoid computing the attention score for every mention in the collection. The architecture is essentially end-to-end trainable (except for specialized pretraining discussed below).   \n\nWhereas itself the architecture is not overly novel (e.g., the architecture does feel a lot similar to models in KB context, and also graph convolution networks applied to QA), there is a lot of clever engineering and the novelty is really in showing that it can work without candidate preselection.\n\nMy main worry is pretraining. In both experiments (MetaQA and the new Wikidata Slot Filling task), they pretrain the encoders using a knowledge base, and the knowledge base directly corresponds to the QA task.   E.g., for MetaQA the questions are answerable using the knowledge bases, so relation types in the knowledge base presumably correspond to relations that need to be captured in the QA multihop learning.  This specialized pretraining appears to be crucial (88% for pretraining vs 55% with BER), presumably because of the top K pruning. Though a nice trick, it is likely limiting as a knowledge base needs to be available + it probably constraints the types of mult-hop questions the apporach can handle.  Also, some of the baselines do not benefit from using the KB, and, in principle, if it is used in training, why not use the KB at test time?  (I see though that for the second dataset pretraining seems to be done on a different part of Wikipedia, I guess, to address these concerns).\n\nI was not sure how the number of hops T was selected for the model, it does not seem to be defined in the paper. Do you pretend that you know the true number of hops for each given question?\n\nThe authors experiment with reducing the size of a KB for pretraining. It apparently does not harm the first 1 hop questions, but 2 and 3-hop. Do the authors have any explanation for this?  Related to the previous question, does it mean that the model does not learn to exploit the hops for t > 1?\n\nThe evaluation is on MetaQA and on the newly introduced Wikidata task, whereas most (?) recent multi-hop QA work has focused on HotpotQA (and to certain degree WikiHop). Is the reason for not using (additionally) HotpotQA?  Is the model suitable for HotpotQA? If not, does this have to do with pretraining or the types of questions in HotpotQA?\n\nThe model definition in section 2.1 is not very easy to follow. E.g., it is not immediately clear if the model applied at every hop is the same model, and not clear how the model is made aware of the current search state (e.g., which part of the question has already processed / how the history is encoded) or even of the hop id. \n\nI would really like to see more analysis of what the model learns at every hop.\n\n-- \nAfter the rebuttal -- I appreciate the detailed feedback, extra experiments, and analysis. `I increased my score. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygDHP9oKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a model that can perform multi-hop question-answering based on a textual knowledge base. Results show that the proposed model -- DrKIT -- performed close to or better than the state of the art results over MetaQA and WikiData datasets. Ablation study is offered to show that a few tricks in the model are necessary to make it work, and comparisons with baseline models such as DrQA and PIQA are presented. The paper also provides additional means to speed up the DrKIT model using the hashing trick and approximated top-k methods.\n\nThe paper is a good one and I vote for its acceptance. Besides achieving good performance, the proposed DrKIT model makes sense, and all the parts are necessary components based on the ablation study results. In addition, the ablation study and the speed-up methods are great addition to the model to make it work better.\n\nWith this generally positive assessment said, I do have a few questions below that I hope the authors could provide some response. These are on top of the high quality of the paper, and should be best regarded as suggestions for future work.\n\n1. In equation (3), do G and F have to be TFIDF features? The likes of word2vec and GloVe (and also pershaps fastText) are trained based on co-occurences of adjacent words, and I would imagine that they will improve over TFIDF. This is just an intuition and I could be wrong, but it would be very helpful to hear the authors' opinions.\n\n2. The ablation study mentioned that the softmax temperature helps with the model. This is a nice observation, but is there any intuition behind why that is the case? I could imagine that it could be because the gradients of a saturated softmax function is small and therefore results in slow training of the model. If this is the case, both low temperature and high temperature will fail to work. It would have been better so show both ends of failing extremes in an ablation study.\n\n3. Can you discuss the similarity between DrKIT and multi-hop End-to-End Memory Networks [1]? It looks very much like an expansion of it with a fixed retrieval mechanism and by expanding the answer to a set rather than a single vector.\n\n[1] Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, Rob Fergus, End-To-End Memory Networks, NIPS 2015\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel architecture for question-answering, which is trained in an end-to-end fashion.

The reviewers were unanimous in their vote to accept. Authors are encouraged to revise addressing reviewer comments.
Decision: Accept (Talk)