A Complex KBQA System using Multiple Reasoning Paths

Figure 2 illustrates the architecture of our model. We model path probabilities using recurrent neural network with gated recurrent units (GRU). At a timestep $t$, the input hidden representations of GRU unit and predicted relation are denoted by $h_{t-1}$ and $r_{t}$ respectively. The model relies on the attention mechanism Bahdanau et al. (2015) to produce a question context vector $c_{t}$. Specifically, all the words $w_{0},w_{1},\cdots,w_{|q|-1}$ in the given question $q$ are first sent to a fixed embedding layer to acquire word embeddings $\varepsilon_{w}(w_{0}),\varepsilon_{w}(w_{1}),\cdots,\varepsilon_{w}(w_{|q|-1})$. Next we apply GRU to produce a temporary hidden state $h_{t}^{\prime}=GRU(h_{t-1},r_{t-1})$, and then apply a parameterized feed-forward neural network $a$ to calculate the similarity score $u_{tk}=a(h^{\prime}_{t},\varepsilon_{w}(w_{k}))$ of two inputs $h^{\prime}_{t}$ and $\varepsilon_{w}(w_{k})$, and then these scores are normalized into attention weights $\alpha_{tk}=\frac{\exp(u_{tk})}{\sum_{0\leq j\leq|q|-1}\exp(u_{tj})}$, which are used to produce the question context vector $c_{t}=\sum_{0\leq j\leq|q|-1}\alpha_{tj}\varepsilon_{w}(w_{j})$. In this fashion, word embeddings are combined in different ways based on attention weights to show different reasoning focuses at each timestep.

The model then concatenates temporary hidden state $h_{t}^{\prime}$, entity representation $\varepsilon_{e}(e_{t-1})$, and question context $c_{t}$ together, and passes the concatenation through a linear transformation $f$ with ReLU activation to obtain the hidden state $h_{t}=ReLU(f([h^{\prime}_{t};\varepsilon_{e}(e_{t-1});c_{t}]))$. This process is recurrently done until the model predicts a stop symbol $\textless$eop$\textgreater$¹¹1This stop mechanism is the same as how it works in a vanilla RNN. Similarly, we also attach $\textless$sop$\textgreater$ to the beginning of each sequence to denote the start state. We will omit these symbols in formulas for simplicity.. Note that the vanilla RNN attention model only has $h_{t}^{\prime}$ and $c_{t}$ when calculates $h_{t}$. We add entity representation into the calculation, since entity captures important information in the reasoning path.

The probability of predicting the $k$-th relation $\gamma_{k}$ in $\mathcal{R}$ at timestep $t$ is:

where $\varepsilon_{r}$ is the embedding function, $<>$ is the dot product between two inputs.

Given the previous entity $e_{t-1}$ and relation $r_{t}$, the next matched entity may not be unique when we query the knowledge base. For example, if $e_{t-1}$=“united states”, and $r_{t}=$ “president of”, then the resulting entity has 45 possibilities. Since we do not have additional constraints, all of them are equally likely to be selected, and hence we define:

Thus the probability of a path containing both entities and relations can be computed using the chain rule:

We assume that there are multiple valid paths $\mathbf{p}\in\mathcal{P}$ that can lead to the correct answer $y$ and they are not given by the annotator in the dataset. We treat these paths as hidden variables and we marginalize them out to compute the probability of getting the answer $y$:

where $\mathcal{P}$ is a set of all valid paths leading to the answer $y$, and $T(\mathbf{p})$ is the number of hops in the path $\mathbf{p}$.

To train our model, we would like to maximize the answer probability $p(y|q)$ using only the given answer for each training instance. To make prediction on each test case, we would like to find the answer $y$ with the highest probability.

It is a novel way that we define answer probability as in (3) in the KBQA task. Most of the existing methods assume the availability of a single ground truth path annotation and aim to maximize the probability of the given path Zhou et al. (2018). As we will demonstrate later in the Section 3.3, considering multiple paths leads to a better model performance.

In order to train our model by maximizing the marginalized answer probability given in (3), it requires summing over all valid reasoning paths from the topic entity to the answer entity in knowledge base. Thus computing this objective exactly can be intractable. As shown in the early example, some reasoning paths ($R_{5},R_{6},R_{7}$ in Figure 1) are not very helpful for training, thus should be either removed from training or assigned low probabilities. To achieve this goal, we first apply depth first search (DFS) algorithm with maximum 3 hops to get valid path candidates. The algorithm starts the traversal from the topic entity node, and ends at the answer entity node. All possible paths between the topic entity and the answer entity within 3 hops are extracted as candidates. We then set a threshold to remove paths which point to too many entities at the last hop. To further filter out bad reasoning paths, we propose to dynamically choose reasoning paths deemed as most probable by the current model during training. The overall training procedure is summarized in Algorithm 1. Note that training with this algorithm does not require ground truth reasoning path label. Labeled reasoning path is a plus, but not necessary. If it is given, we can either include the ground truth paths in $\mathcal{P}$, or use them to initialize model training.

During the prediction, we aim to select the answer $y$ with the highest marginalized probability $p(y|q)$ as defined in (3). Similar to training, we need to approximate the sum with selected paths from $\mathcal{P}$. We use a modified beam search to find paths that have high probabilities. We add two constraints to standard beam search to only select the valid paths that match the knowledge base: (1) The first relation $r_{1}$ should connect to the topic entity $e_{0}$. (2) Each triple $(e_{t-1},r_{t},e_{t})$ should match a fact in KB. Given the set of paths collected as above, we can then collect a set of candidate answers that these paths point to. For each answer $y$, we evaluate its probability $p(y|q)$ approximately using the collected paths, and among them we output the answer with the highest probability.

Additionally, we observe that it could be beneficial to de-emphasize the impact of the topic entity during prediction, as noted in Li et al. (2016), which can improve inference performance by avoiding generating generic predictions and reducing overfitting. Specifically, instead of searching $y^{*}$ that maximizes $p(y|q)$, we can find an answer that maximizes $\dfrac{p(y|q)}{p(y|e_{0})}$, where $p(y|e_{0})$ is the probability of getting the answer $y$ when the question only contains the topic entity word. Mathematically, one can show that this is equivalent to maximizing the point-wise conditional mutual information PMI$((y;q\backslash e_{0})|e_{0})$ between $y$ and $q\backslash e_{0}$ given $e_{0}$, where $q\backslash e_{0}$ stands for the question with the topic entity term removed. Further discussion can be found in Section 4.

We conduct experiments on 3 multi-hop KBQA datasets, WebQuestionSP (WQSP) Yih et al. (2015), ComplexWebQuestion-1.1 (CWQ) Talmor and Berant (2018), and PathQuestion-Large (PQL) Zhou et al. (2018), and use the original train/dev/test split. WQSP is a dataset that has been widely used for relation extraction and end-to-end KBQA tasks, which contains 1 or 2 hops questions. CWQ dataset is designed to study complex questions by adding more constraints to questions in WebQuestionSP. PQL is a small dataset used to study sequential questions. Its original release contains two subsets: PQL2H and PQL3H, which contains only 2-hop and 3-hop questions correspondingly. Chen et al. (2019) then combined these two subsets and renamed the unified dataset as PQL+. All of the three datasets use Freebase Google (2013) as the supporting knowledge base. Table 1 contains statistics of these datasets.

For questions with multiple answers, we use each answer to construct a question-answer (QA) pair. For WQSP and CWQ, we build a subgraph in a similar way as in Sun et al. (2018), in order to generate the entity and relation candidates. For PQL, the original paper provides a subgraph of the Freebase. We implement our model using tensorflow-1.11.0 and choose S-MART Yang and Chang (2016) and AllenNLP Gardner et al. (2017) as our entity linking tools. If multiple topic entities are extracted, we use each topic entity to construct a question-answer pair. We test three different graph embedding methods Word2vec Mikolov et al. (2013), TransE Bordes et al. (2013), and HolE Trouillon and Nickel (2017), and decide to use TransE in our final experiment based on validation performance. The threshold $k_{1}$ is set to be: 15 plus the number of answers in the ground truth answer set, and $k_{2}$ is top 50%. We adopt the average F1 score and the set accuracy as our main evaluation metrics. It is worth noticing that: except our methods’ results, all other experimental results are obtained from early published papers. Details of these models can be found from our referenced papers.

In Table 2 we compare our method to state-of-the-art models. All comparisons are divided into two groups based on different training supervisions. The upper block shows methods that are only trained with final answer as supervision, and the second block contains methods using extra annotations such as parsing results of the query. Experimental results show that our model performs better than all other methods on two datasets except for NSM Liang et al. (2017) on WQSP. Although NSM only relies on answers to train their model, it requires many prior knowledges, such as a big vocabulary to train word embeddings and graph embeddings, type label of the entity and of the relation, and pre-defined templates. The experiments from their papers show that these knowledge play a very important role in the system, e.g. F1 score drops from 69.0 to 60.7 by not using the pretrained embeddings. Also, NSM is only tested on a single dataset, i.e. WQSP. It is unclear whether they could perform consistently well on different datasets. Among all the methods, STAGG performs the best when additional annotation is provided, but we can see a clear drop between STAGG_SP and STAGG_answer when such annotation is not available.

To further disentangle the contribution of different factors in our method, we present a feature ablation test on WQSP dataset shown in Table 3. The vanilla RNN structure only maintains a hidden state and the previous prediction in the loop. Here, we show the performance boost by considering entity features in KBQA task. Instead of using greedy algorithm or beam search to output the top prediction with the highest joint probability $P(y,\mathbf{p})$, we propose to make the prediction based on marginalized probability $P(y)$, which also improves the performance by $1.8\%$. In addition, we show the benefits of using inference during training (line 6 and 7 in algorithm 1) and mutual information objective (Section (2.4)). More discussions can be found in the Section 4.

In the second set of experiment, we test our model with different objective functions and compare their results correspondingly. The objective functions are as defined in Table 4, where the paths used for training are given in the last column. The detailed explanations are given as following:

We test different ways of choosing paths and defining training objectives on WQSP and CWQ datasets. We further divide the test samples into two groups, based on whether there exist multiple possible paths between the topic entity and the answer based on KB. Table 5 show that our proposed method gives the best performance on both scenarios. The models trained with single path perform consistently worse than those trained with multiple paths. Using random ath is worse than using the given ground truth path. Between two models trained using multiple paths, the result shows the advantage of using our proposed objective.

In the third set of experiments, we test our model on PathQuestion-Large (PQL) dataset. This dataset contains synthetic questions generated by templates, and is supported by a very small knowledge base (500,000 times smaller than the full freebase). Not surprisingly, we can see the average performance on this dataset is much better than it is on the other two datasets. Recall that PQL2H and PQL3H represents two subsets with only 2 hops and 3 hops questions respectively. Table 6 shows that our method’s performance beats all the other approaches on all three subsets of PQL from 1$\%$ to 7.8$\%$ in terms of test accuracy. Especially the gap between our method to the previous state-of-the-art approach (i.e. UHop) becomes larger when the number of hops increase from 2 to 3.