Learning When Not to Answer: A Ternary Reward Structure for Reinforcement Learning based Question Answering

  • 2019-04-03 18:58:24
  • Fréderic Godin, Anjishnu Kumar, Arpit Mittal
  • 0

Abstract

In this paper, we investigate the challenges of using reinforcement learningagents for question-answering over knowledge graphs for real-worldapplications. We examine the performance metrics used by state-of-the-artsystems and determine that they are inadequate for such settings. Morespecifically, they do not evaluate the systems correctly for situations whenthere is no answer available and thus agents optimized for these metrics arepoor at modeling confidence. We introduce a simple new performance metric forevaluating question-answering agents that is more representative of practicalusage conditions, and optimize for this metric by extending the binary rewardstructure used in prior work to a ternary reward structure which also rewardsan agent for not answering a question rather than giving an incorrect answer.We show that this can drastically improve the precision of answered questionswhile only not answering a limited number of previously correctly answeredquestions. Employing a supervised learning strategy using depth-first-searchpaths to bootstrap the reinforcement learning algorithm further improvesperformance.

 

Quick Read (beta)

Learning When Not to Answer:
A Ternary Reward Structure for Reinforcement
Learning based Question Answering

Fréderic Godin
Ghent University
Ghent, Belgium
[email protected]
&Anjishnu Kumar
Amazon Research
Cambridge, United Kingdom
[email protected]
&Arpit Mittal
Amazon Research
Cambridge, United Kingdom
[email protected]
Abstract

In this paper, we investigate the challenges of using reinforcement learning agents for question-answering over knowledge graphs for real-world applications. We examine the performance metrics used by state-of-the-art systems and determine that they are inadequate for such settings. More specifically, they do not evaluate the systems correctly for situations when there is no answer available and thus agents optimized for these metrics are poor at modeling confidence. We introduce a simple new performance metric for evaluating question-answering agents that is more representative of practical usage conditions, and optimize for this metric by extending the binary reward structure used in prior work to a ternary reward structure which also rewards an agent for not answering a question rather than giving an incorrect answer. We show that this can drastically improve the precision of answered questions while only not answering a limited number of previously correctly answered questions. Employing a supervised learning strategy using depth-first-search paths to bootstrap the reinforcement learning algorithm further improves performance.

Learning When Not to Answer:
A Ternary Reward Structure for Reinforcement
Learning based Question Answering


Fréderic Godin Ghent University Ghent, Belgium [email protected]                        Anjishnu Kumar Amazon Research Cambridge, United Kingdom [email protected]                        Arpit Mittal Amazon Research Cambridge, United Kingdom [email protected]

1 Introduction

A number of approaches for question answering have been proposed recently that use reinforcement learning to reason over a knowledge graph (Das et al., 2018; Lin et al., 2018; Chen et al., 2018; Zhang et al., 2018). In these methods the input question is first parsed into a constituent question entity and relation. The answer entity is then identified by sequentially taking a number of steps (or ‘hops’) over the knowledge graph (KG) starting from the question entity. The agent receives a positive reward if it arrives at the correct answer entity and a negative reward for an incorrect answer entity. For example, for the question “What is the capital of France?”, the question entity is (France) and the goal is to find a path in the KG which connects it to (Paris). The relation between the answer entity and question entity in this example is (Capitalof) which is missing from the KG and has to be inferred via alternative paths. This is illustrated in Figure 1. A possible two-hop path to find the answer is to use the fact that (Macron) is the president of (France) and that he lives in (Paris). However, there are many paths that lead to the entity (Paris) but also to other entities which makes finding the correct answer a non-trivial task.

{tikzpicture}\node

at (0,0) [circle,draw,inner sep=+0.5em] (h1) France; \nodeat (2,-0.5) [] (h7) ; \nodeat (2,-1.) [] (h8) ; \nodeat (2,-1.5) [] (h9) ; \nodeat (2.5,-1) [gray] () …; \nodeat (5,0) [circle,draw,inner sep=+0.5em] (h2) Paris; \nodeat (3,-0.5) [] (h13) ; \nodeat (3,-1.) [] (h14) ; \nodeat (3,-1.5) [] (h15) ;

\node

at (2.5,2.5) [circle,draw,inner sep=+0.5em] (h3) Macron; \nodeat (4.5,2.5) [] (h4) ; \nodeat (4.5,3) [] (h5) ; \nodeat (4.5,3.5) [] (h6) ; \nodeat (4.8,3) [gray] () …;

\draw

[-¿,dashed] (h1) – node[above] Capital of (h2) ; \draw[-¿,gray] (h1) – (h7) ; \draw[-¿,gray] (h1) – (h8) ; \draw[-¿,gray] (h1) – (h9) ; \draw[-¿] (h1) – node President of-1 (h3) ; \draw[-¿,gray] (h13) – (h2) ; \draw[-¿,gray] (h14) – (h2) ; \draw[-¿,gray] (h15) – (h2) ; \draw[-¿] (h3) – node Lives in (h2) ; \draw[-¿,gray] (h3) – (h4) ; \draw[-¿,gray] (h3) – (h5) ; \draw[-¿,gray] (h3) – (h6) ;

Figure 1: Fictional graph for the the question “What’s the capital of France?”. The relation (Capitalof) does not exist in the graph and thus an alternative path needs to be used that leads to the correct answer.

The standard evaluation metrics used for these systems are metrics developed for web search such as Mean Reciprocal Rank (MRR) and [email protected], where k ranges from 1 to 20. We argue that this is not a correct evaluation mechanism for a practical question-answering system (such as Alexa, Cortana, Siri, etc.) where the goal is to return a single answer for each question. Moreover it is assumed that there is always an answer entity that could be reached from the question entity in limited number of steps. However this cannot be guaranteed in a large-scale commercial setting and for all KGs. For example, in our proprietary dataset used for the experimentation, for 15.60% of questions the answer entity cannot be reached within the limit of number of steps used by the agent. Hence, we propose a new evaluation criterion, allowing systems to return ‘no answer’ as a response when no answer is available.

We demonstrate that existing state-of-the-art methods are not suited for a practical question-answering setting and perform poorly in our evaluation setup. The root-cause of poor performance is the reward structure which does not provide any incentive to learn not to answer. The modified reward structure we present allows agents to learn not to answer in a principled way. Rather than having only two rewards, a positive and a negative reward, we introduce a ternary reward structure that also rewards agents for not answering a question. A higher reward is given to the agent for correctly answering a question compared to not answering a question. In this setup the agent learns to make a trade-off between these three possibilities to obtain the highest total reward over all questions.

Additionally, because the search space of possible paths exponentially grows with the number of hops, we also investigate using Depth-First-Search (DFS) algorithm to collect paths that lead to the correct answer. We use these paths as a supervised signal for training the neural network before the reinforcement learning algorithm is applied. We show that this improves overall performance.

2 Related work

The closest works to ours are the works by Lin et al. (2018), Zhang et al. (2018) and Das et al. (2018), which consider the question answering task in a reinforcement learning setting in which the agent always chooses to answer.11 1 An initial version of this paper has been presented at the Relational Representation Learning Workshop at NeurIPS 2018 as Godin et al. (2018). Other approaches consider this as a link prediction problem in which multi-hop reasoning can be used to learn relational paths that link two entities. One line of work focuses on composing embeddings (Neelakantan et al., 2015; Guu et al., 2015; Toutanova et al., 2016) initially introduced for link prediction, e.g., TransE (Bordes et al., 2013), ComplexE (Trouillon et al., 2016) or ConvE (Dettmers et al., 2018). Another line of work focuses on logical rule learning such as neural logical programming (Yang et al., 2017) and neural theorem proving (Rocktäschel and Riedel, 2017). Here, we focus on question answering rather than link prediction or rule mining and use reinforcement learning to circumvent that we do not have ground truth paths leading to the answer entity.

Recently, popular textual QA datasets have been extended with not-answerable questions (Trischler et al., 2017; Rajpurkar et al., 2018). Questions that cannot be answered are labeled with ‘no answer’ option which allows for supervised training. This is different from our setup in which there are no ground truth ‘no answer’ labels.

{tikzpicture}\node

at (0,0) [rectangle,draw,inner sep=+0.3em] (h1) LSTM; \nodeat (2,0) [inner sep=+0.3em] (h3) ; \nodeat (4,0) [rectangle,draw,inner sep=+0.3em] (h4) LSTM; \nodeat (6,0) [inner sep=+0.3em] (h5) ; \nodeat (8,0) [rectangle,draw,inner sep=+0.3em] (h6) LSTM; \draw[-¿] (h1) – node[above] 𝒉1 (h3) ; \draw[-¿] (h3) – node[above] 𝒉t-1 (h4) ; \draw[-¿] (h4) – node[above] 𝒉t (h5) ; \draw[-¿] (h5) – node[above] 𝒉T-1 (h6) ;

\node

at (0,-1) [inner sep=+0.3em] (x1) 𝒓0,𝒆q;

\node

at (4,-1) [inner sep=+0.3em] (x4) 𝒓t,𝒆t;

\node

at (8,-1) [inner sep=+0.3em] (x6) 𝒓T,𝒆T; \draw[-¿] (x1) – (h1) ;

\draw

[-¿] (x4) – (h4) ; \draw[-¿] (x6) – (h6) ;

(a) History LSTM
{tikzpicture}\node

at (0,0) [rectangle,draw,inner sep=+0.3em] (h1) FFNN (f); \nodeat (0,-1) [inner sep=+0.3em] (x1) 𝒓q,𝒆t,𝒉t; \draw[-¿] (x1) – (h1) ;

\node

at (3,0) [rectangle,draw,inner sep=+0.3em,minimum width=3.1cm] (a1) 𝒓t+1,1𝒆t+1,1; \nodeat (3,-0.5) [inner sep=+0.3em] (a2) ; \nodeat (3,-1) [rectangle,draw,inner sep=+0.3em,minimum width=3.1cm] (a3) 𝒓t+1,|At|𝒆t+1,|At|;

\node

at (1.5,1) [inner sep=-0.1em] (d) ;

\draw

[-¿] (h1) – (d) ; \draw[-¿] (a1) – (d) ;

\node

at (1.5,2) [inner sep=+0.3em] (out) π; \draw[-¿] (d) – node[right] softmax (out) ;

(b) Policy network at timestep t
Figure 2: Figure 1(a) illustrates the LSTM which encodes history of the path taken. The output at timestep t is used as input to the policy network, illustrated in Figure 1(b), to determine which action to take next.

3 Background: Reinforcement learning

We base our work on the recent reinforcement learning approaches introduced in Das et al. (2018) and Lin et al. (2018). We denote the knowledge graph as 𝒢, the set of entities as , the set of relations as and the set of directed edges between entities of the form l=(e1,r,e2) with e1,e2 and r. The goal is to find an answer entity ea given a question entity eq and the question relation rq, when (eq,rq,ea) is not part of graph 𝒢.

We formulate this problem as a Markov Decision Problem (MDP) (Sutton and Barto, 1998) with the following states, actions, transition function and rewards:

States.

At every timestep t, the state st is defined by the current entity et, the question entity eq and relation rq, for which et,eq and rq. More formally, st=(et,eq,rq).

Actions.

For a given entity et, the set of possible actions is defined by the outgoing edges from et. Thus At={(r,e)|(et,r,e)𝒢}.

Transition function.

The transition function δ maps st to a new state st+1 based on the action taken by the agent. Consequently, st+1=δ(st,At)=δ(et,eq,rq,At).

Rewards.

The agent is rewarded based on the final state. For example, in Das et al. (2018) and Lin et al. (2018) the agent obtains a reward of 1 if the correct answer entity is reached as the final state and 0 otherwise (i.e., R(sT)=𝕀{eT=ea}).

3.1 Training

We train a policy network π using the REINFORCE algorithm of Williams (1992) which maximizes the expected reward:

J(𝜽)=𝔼(eq,rq,ea)𝒢𝔼a1,,aTπ[R(sT|eq,rq)] (1)

in which at is the action selected at timestep t following the policy π, and 𝜽 are the parameters of the network.

The policy network consists of two parts: a Long Short-Term Memory (LSTM) network which encodes the history of the traversed path, and a feed-forward neural network to select an action (at) out of all possible actions. Each entity and relation have a corresponding vector 𝒆t,𝒓td. The action atAt is represented by the vectors of the relation and entity as 𝒂t=[𝒓t+1;𝒆t+1]2d. The LSTM encodes the history of the traversed path and updates its hidden state each timestep, based on the selected action:

𝒉t=LSTM(𝒉t-1,𝒂t-1) (2)

This is illustrated in Figure 1(a).

Finally, the feed-forward neural network (f) combines the history 𝒉t, the current entity representation 𝒆t and the query relation 𝒓q. Using softmax, we compute the probability for each action by calculating the dot product between the output of f and each action vector 𝒂t:

π(at|st)=softmax(𝑨tf(𝒉t,𝒆t,𝒓q)) (3)

in which 𝑨t|At|×2d is a matrix consisting of rows of action vectors 𝒂t. This is illustrated in Figure 1(b). During training, we sample over this probability distribution to select the action at, whereas during inference, we use beam search to select the most probable path.

4 Evaluation

User-facing question answering systems inherently face a trade-off between presenting an answer to a user that could potentially be incorrect, and choosing not to answer. However, prior work in knowledge graph question-answering (QA) only considers cases in which the answering agent always produces an answer. This setup originates from the link prediction and knowledge base completion tasks in which the evaluation criteria are [email protected] and Mean Reciprocal Rank (MRR), where k ranges from 1 to 20. However, these metrics are not an accurate representation of practical question-answering systems in which the goal is to return a single correct answer or not answer at all. Moreover, using these metrics result in the problem of the model learning ‘spurious’ paths since the metrics encourage the models to make wild guesses even if the path is unlikely to lead to the correct answer.

We therefore propose to measure the fraction of questions the system answers (Answer Rate) and the number of correct answers out of all answers (Precision) to measure the system performance. We combine these two metrics by taking the harmonic mean and call this the QA Score. This can be viewed as a variant of the popular F-Score metric, with answer rate used as an analogue to recall in the original metric.

5 Proposed method

In this section, we will first introduce the supervised learning technique we used to pretrain the neural network before applying the reinforcement learning algorithm. Next we will describe the ternary reward structure.

5.1 Supervised learning

Typically in reinforcement learning, the search space of possible actions and paths grows exponentially with the path length. Our problem is no exception to this. Hence an imitation learning approach could be beneficial here where we provide a number of expert paths to the learning algorithm to bootstrap the learning process. This idea has been explored previously in the context of link and fact prediction in knowledge graphs where Xiong et al. (2017) proposed to use a Breadth-First-Search (BFS) between the entity pairs to select a set of plausible paths. However BFS favours identification of shorter paths which could bias the learner. We therefore use Depth-First-Search (DFS) to identify paths between question and answer entities and sample up to 100 paths to be used for the supervised training. If no path can be found between the entity pair we return a ‘no answer’ label. Following this, we train the network using reinforcement learning algorithm which refines it further. Note that it is not guaranteed that the set of paths found using DFS are all most efficient. However as we show in our experiments, bootstrapping with these paths provide good initialization for the reinforcement learning algorithm.

5.2 Ternary reward structure

As mentioned previously, we encounter situations when the answer entity cannot be reached in the limited number of steps taken by an agent. In such cases, the system should return a special answer ‘no answer’ as the response. We can achieve this by adding a synthetic ‘no answer’ action that leads to a special entity eNOANSWER. This is illustrated in Figure 3. In the framework of Das et al. (2018) a binary reward is used which rewards the learner for the answer being wrong or correct. Following a similar protocol, we could award a score of 1 to return ‘no answer’ when there is no answer available in the KG. However, we cannot achieve reasonable training with such reward structure. This is because there is no specific pattern for ‘no answer’ that could be directly learned. Hence, if we reward a system equally for correct or no answer, it learns to always predict ‘no answer’. We therefore propose a ternary reward structure in which a positive reward is given to a correct answer, a neutral reward when eNOANSWER is selected as an answer, and a negative reward for an incorrect answer. More formally:

R(sT)={rposif eT=ea,0if eT=eNOANSWER,rnegif eT{ea,eNOANSWER} (4)

with rpos>0 and rneg<0. The idea is that the agent receives a larger reward for a correct answer compared to not answering the question, and a negative reward for incorrectly answering a question compared to not answering the question. In the experimental section, we show that this mechanism provides better performance.

{tikzpicture}\node

at (0,0) [circle,draw,inner sep=+0.5em] (h1) France; \nodeat (2,-0.5) [] (h7) ; \nodeat (2,-1.) [] (h8) ; \nodeat (2,-1.5) [] (h9) ; \nodeat (2.5,-1) [gray] () …; \nodeat (0,-2.5) [circle,draw,inner sep=+0.3em,red,text width=1.2cm,align=center] (h11) No Answer; \nodeat (5,0) [circle,draw,inner sep=+0.5em] (h2) Paris; \nodeat (3,-0.5) [] (h13) ; \nodeat (3,-1.) [] (h14) ; \nodeat (3,-1.5) [] (h15) ; \nodeat (5,-2.5) [circle,draw,inner sep=+0.3em,red,text width=1.2cm,align=center] (h12) No Answer;

\node

at (2.5,2.5) [circle,draw,inner sep=+0.5em] (h3) Macron; \nodeat (4.5,2.5) [] (h4) ; \nodeat (4.5,3) [] (h5) ; \nodeat (4.5,3.5) [] (h6) ; \nodeat (4.8,3) [gray] () …; \nodeat (4.8,4.8) [circle,draw,inner sep=+0.3em,red,text width=1.2cm,align=center] (h10) No Answer;

\draw

[-¿,dashed] (h1) – node[above] Capital of (h2) ; \draw[-¿,gray] (h1) – (h7) ; \draw[-¿,gray] (h1) – (h8) ; \draw[-¿,gray] (h1) – (h9) ; \draw[-¿,red] (h1) – node No answer (h11) ; \draw[-¿,red] (h2) – node No answer (h12) ; \draw[-¿] (h1) – node President of-1 (h3) ; \draw[-¿,gray] (h13) – (h2) ; \draw[-¿,gray] (h14) – (h2) ; \draw[-¿,gray] (h15) – (h2) ; \draw[-¿] (h3) – node Lives in (h2) ; \draw[-¿,gray] (h3) – (h4) ; \draw[-¿,gray] (h3) – (h5) ; \draw[-¿,gray] (h3) – (h6) ; \draw[-¿,red] (h3) – node No answer (h10) ;

Figure 3: Fictional graph for the the question “What’s the capital of France?”. The relation (Capitalof) does not exist in the graph and thus an alternative path needs to be used that leads to the correct answer. To avoid that the agent returns an incorrect answer when not finding the correct answer, a ‘no answer’ relation is added between every entity node and a special ‘no answer’ node, to be able to return ‘no answer’.
Table 1: Results on FB15k-237 dataset.
Model [email protected] [email protected] MRR Precision Answer Rate QA Score
(Das et al., 2018) 0.217 0.456 0.293 0.217 1 0.357
(Lin et al., 2018) 0.329 0.544 0.393 0.329 1 0.495
RL 0.2475 0.4032 0.2983 0.2475 1 0.3968
Supervised 0.2474 0.4929 0.3276 0.2474 1 0.3967
Supervised + RL 0.2736 0.5015 0.3469 0.2736 1 0.4296
No Answer RL 0.2345 0.3845 0.2831 0.4011 0.5847 0.4758
All 0.2738 0.4412 0.3286 0.4835 0.5663 0.5216
Table 2: Results on Alexa69k-378 dataset.
Model [email protected] [email protected] MRR Precision Answer Rate QA Score
(Das et al., 2018) 0.1790 0.2772 0.2123 0.1790 1 0.3036
(Lin et al., 2018) 0.1915 0.3184 0.2358 0.1915 1 0.3214
RL 0.1677 0.2716 0.2031 0.1677 1 0.2872
Supervised 0.1471 0.3142 0.203 0.1471 1 0.2565
Supervised + RL 0.1937 0.3045 0.2312 0.1937 1 0.3245
No Answer RL 0.1564 0.2442 0.1858 0.3892 0.4019 0.3955
All 0.1865 0.294 0.2229 0.3454 0.5401 0.4213
Table 3: Statistics of various datasets.
#queries
#ent #rel #facts valid test
FB15k-237
14,505 237 272,115 17,535 20,466
Alexa69k-378
69,098 378 442,591 55,186 55,474

6 Experimental setup

We evaluate our proposed approach on a publicly available dataset, FB15k-237 (Toutanova and Chen, 2015) which is based on the Freebase knowledge graph and a proprietary dataset Alexa69k-378 which is a sample of Alexa’s proprietary knowledge graph. Both the public dataset and the proprietary dataset are good examples of real-world general-purpose knowledge graphs that can be used for question answering. FB15k-237 contains 14,505 different entities and 237 different relations resulting in 272,115 facts. Alexa69k-378 contains 69,098 different entities and 378 different relations resulting in 442,591 facts. We follow the setup of Das et al. (2018), using the same train/val/test splits for FB15k-237. For Alexa69k-378 we use 10% of the full dataset for validation and test. For both datasets, we add the reverse relations of all relations in the training set in order to facilitate backward navigation following the approach of previous work. Similarly, a ‘no op’ relation is added for each entity between the entity and itself, which allows the agent to loop/reason multiple consecutive steps over the same entity. An overview of both datasets can be found in Table 3.

We extend the publicly available implementation of Das et al. (2018) for our experimentation. We set the size of the entity and relation representations d at 100 and the hidden state at 200. We use a single layer LSTM and train models with path length 3 (tuned using hyper-parameter search). We optimize the neural network using Adam (Kingma and Ba, 2015) with learning rate 0.001, mini-batches of size 256 with 20 rollouts per example. During the test time, we use beam search with the beam size of 100. Unlike Das et al. (2018), we also train entity embeddings after initializing them with random values. Reward values are set as rpos=10 and rneg=-0.1 after performing a coarse grid search for various reward values on the validation set. For all experiments, we selected the best model with the highest QA Score on the corresponding validation set.

7 Results

The results of our experiments for FB15k-237 and Alexa69k-378 are given in Table 1 and Table 2 respectively.

Supervised learning

For FB15k-237, we see that the model trained using reinforcement learning (RL) scores as well as the model trained using supervised learning. This makes supervised learning using DFS a strong baseline system for question answering over knowledge graphs, and for FB15k-237 in particular. On Alexa69k-378, models trained using supervised learning score lower on all metrics compared to RL. When combining supervised learning with RL overall performance increases.

No answer

When we train RL system with our ternary reward structure (No Answer RL), the precision and QA score increase significantly on both datasets. For FB15k-237, our No Answer RL model decided not to answer over 40% of the questions, with an absolute [email protected] reduction of only 1.3% over standard RL. Moreover, of all the answered questions, 40.11% were answered correctly compared to 24.75% of the original question-answering system: an absolute improvement of over 15%. This resulted in the final QA Score of 47.58%, around 8% higher than standard RL and 12% higher than Das et al. (2018).

Similarly, 60% of the questions did not get answered on Alexa69k-378. This resulted in [email protected] decrease of roughly 1% but compared to standard RL, the precision increased from 16.77% to 38.92%: an absolute increase of more than 20%. The final QA Score also increased from 28.72% to 39.55%, and also significantly improved over Das et al. (2018) and Lin et al. (2018). The results indicate that using our method allows us to improve the precision of the question-answering system by choosing the right questions to be answered by not answering many questions that were previously answered incorrectly. This comes at the expense of not answering some questions that previously could be answered correctly.

All

Finally, all methods were combined in a single method. First the model was pretrained in a supervised way. Then the model was retrained using RL algorithm with ternary reward structure. This jointly trained model obtained better QA scores than any individually trained model. On FB15k-237, a QA score of 52.16% is obtained which is an absolute improvement of 4.58% over the best individual model and 2.66% over Lin et al. (2018). Similarly, on Alexa69k-378, an absolute improvement of 2.57% over the best individual result is obtained, almost 10% absolute improvement over Lin et al. (2018). Sample results from our method are given in Table 4 and Table 5.

Table 4: Example paths of correctly answered questions on FB15k-237. Note that the fact (eq,rq,ea) is not part of the KG.
{tikzpicture} \node[style=font=] at (0, 1) (z) Question: eq = Bruce Broughton, rq = Profession. Answer: ea = Music Composer;
{tikzpicture} \node[style=font=] at (0, 0) (a) Bruce Broughton; \node[style=font=] at (4, 0) (b) Oscar Best Music; \node[style=font=] at (8, 0) (c) Nino Rota; \node[style=font=] at (11, 0) (d) Music Composer; \draw[-¿,thick](a) – node[above,style=font=] Award Nominee (b); \draw[-¿,thick](b) – node[above,style=font=] Award Winner (c); \draw[-¿,thick](c) – node[above,style=font=] Profession (d);
{tikzpicture} \node[style=font=] at (0, 1) (z) Question: eq = Washington nationals, rq = Sports Team Sport. Answer: ea = Baseball;
{tikzpicture} \node[style=font=] at (0, 0) (a) Washington Nationals; \node[style=font=] at (4, 0) (b) National League; \node[style=font=] at (8, 0) (c) Milwaukee Braves; \node[style=font=] at (11, 0) (d) Baseball; \draw[-¿,thick](a) – node[above,style=font=] Sports League-1 (b); \draw[-¿,thick](b) – node[above,style=font=] Sports League (c); \draw[-¿,thick](c) – node[above,style=font=] Sports Team Sport (d);
Table 5: Example question from FB15k-237, incorrectly answered by (Das et al., 2018) and not answered by our system. Note that the fact (eq,rq,ea) is not part of the KG.
{tikzpicture} \node[style=font=] at (0, 1) (z) Question: eq = Sherlock holmes (movie), rq = Story By. Answer: ea = Conan Doyle;
{tikzpicture} \node[style=font=] at (0, 0) (a) Sherlock holmes (movie); \node[style=font=] at (5, 0) (b) Wardrobe Supervisor; \node[style=font=] at (8, 0) (c) Wardrobe Sup.; \node[style=font=] at (11, 0) (d) Wardrobe Sup.; \draw[-¿,thick](a) – node[above,style=font=] Film Crew Role (b); \draw[-¿,thick](b) – node[above,style=font=] No op (c); \draw[-¿,thick](c) – node[above,style=font=] No op (d);
{tikzpicture} \node[style=font=] at (0, 0) (a) Sherlock holmes (movie); \node[style=font=] at (5, 0) (b) Wardrobe Supervisor; \node[style=font=] at (8, 0) (c) No answer; \node[style=font=] at (11, 0) (d) No answer; \draw[-¿,thick](a) – node[above,style=font=] Film Crew Role (b); \draw[-¿,thick](b) – node[above,style=font=] No answer (c); \draw[-¿,thick](c) – node[above,style=font=] No answer (d);
{tikzpicture}

[scale=0.8] {axis}[ xlabel=Positive Reward, ylabel=Percentage, xmin=0, xmax=15, ymin=0, ymax=1, xtick=0,5,10,15, xticklabels=0,5,10,15, ytick=0,0.25,0.5,0.75,1, yticklabels=0%,25%,50%,75%,100%, legend style=at=(1,1),anchor=north east, ymajorgrids=true, grid style=dashed ] \addplot[ color=blue, mark=square, ] coordinates (0.625,0.3438)(1.25,0.5152)(2.5,0.4523)(5,0.4226)(10,0.4011)(15,0.3814) ; \addlegendentryPrecision \addplot[ color=green, mark=star, ] coordinates (0.625,0.0031)(1.25,0.1988)(2.5,0.4036)(5,0.5444)(10,0.5847)(15,0.5726) ; \addlegendentryAnswer Rate \addplot[ color=red, mark=otimes, ] coordinates (0.625,0.0062)(1.25,0.2869)(2.5,0.4266)(5,0.4759)(10,0.4758)(15,0.4579) ; \addlegendentryQA score

Figure 4: Influence of changing the positive reward for FB15k-237. The negative reward is fixed at rneg=-0.1 and the neutral reward is fixed at rneutral=0.
{tikzpicture}

[scale=0.8] {axis}[ xlabel=Negative Reward, ylabel=Percentage, xmin=-0.5, xmax=0, ymin=0, ymax=1, ytick=0,0.25,0.5,0.75,1, yticklabels=0%,25%,50%,75%,100%, legend style=at=(1,1),anchor=north east, ymajorgrids=true, grid style=dashed ] \addplot[ color=blue, mark=square, ] coordinates (-0.5,0.5013)(-0.25,0.4435)(-0.1,0.4011)(-0.05,0.3741)(-0.025,0.3742) ; \addlegendentryPrecision \addplot[ color=green, mark=star, ] coordinates (-0.5,0.3459)(-0.25,0.5071)(-0.1,0.5847)(-0.05,0.6156)(-0.025,0.6194) ; \addlegendentryAnswer Rate \addplot[ color=red, mark=otimes, ] coordinates (-0.5,0.4094)(-0.25,0.4732)(-0.1,0.4758)(-0.05,0.4654)(-0.025,0.4665) ; \addlegendentryQA score

Figure 5: Influence of changing the negative reward for FB15k-237. The positive reward is fixed at rpos=10 and the neutral reward is fixed at rneutral=0.

Reward tuning

An important part of increasing the QA score is to select the right combination of rewards. Therefore, we ran additional experiments where we varied either the positive or negative reward, keeping the other rewards fixed. In Figure 4, the precision, answer rate and QA score are shown when varying the positive reward and keeping the neutral and negative rewards fixed. When, the positive reward is very small (rpos=0.625), almost no question is answered. When the positive reward rpos is 1.25, roughly 20% of the questions are answered with a 50% precision. After that, the precision starts declining and the answer rate starts increasing, resulting in an overall increase in QA score. The QA score plateaus between 5 and 10 and then starts decreasing slowly. In Figure 5, the precision, answer rate and QA score are shown when varying the negative reward and keeping the neutral and positive rewards fixed. In this case, the highest QA score is achieved when the negative reward is between -0.25 and -0.1. As long as the negative reward is lower than zero, a wrong answer gets penalized and the QA score stays high.

8 Conclusions

In this paper, we addressed the limitations of current approaches for question answering over a knowledge graph that use reinforcement learning. Rather than only returning a correct or incorrect answer, we allowed the model to not answer a question when it is not sure about it. Our ternary reward structure gives different rewards for correctly answered, incorrectly answered and not answered questions. We also introduced a new evaluation metric which takes these three options into account. We showed that we can significantly improve the precision of answered questions compared to previous approaches, making this a promising direction for the practical usage in knowledge graph-based QA systems.

References

  • Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems (NIPS).
  • Chen et al. (2018) Wenhu Chen, Wenhan Xiong, Xifeng Yan, and William Yang Wang. 2018. Variational knowledge graph reasoning. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HTL).
  • Das et al. (2018) Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alexander J. Smola, and Andrew McCallum. 2018. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. International Conference on Learning Representations (ICLR).
  • Dettmers et al. (2018) Tim Dettmers, Minervini Pasquale, Stenetorp Pontus, and Sebastian Riedel. 2018. Convolutional 2d knowledge graph embeddings. In Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI).
  • Godin et al. (2018) Fréderic Godin, Anjishnu Kumar, and Arpit Mittal. 2018. Using ternary rewards to reason over knowledge graphs with deep reinforcement learning. In Workshop on Relational Representation Learning (NeurIPS).
  • Guu et al. (2015) Kelvin Guu, John Miller, and Percy Liang. 2015. Traversing knowledge graphs in vector space. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
  • Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the International Conference on Representation Learning (ICLR).
  • Lin et al. (2018) Xi Victoria Lin, Richard Socher, and Caiming Xiong. 2018. Multi-hop knowledge graph reasoning with reward shaping. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP).
  • Neelakantan et al. (2015) Arvind Neelakantan, Benjamin Roth, and Andrew McCallum. 2015. Compositional vector space models for knowledge base completion. In Proceedings of the Annual Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processing (ACL-IJCNLP).
  • Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018. Know what you don’t know: Unanswerable questions for squad. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL).
  • Rocktäschel and Riedel (2017) Tim Rocktäschel and Sebastian Riedel. 2017. End-to-end differentiable proving. In Advances in Neural Information Processing Systems (NIPS).
  • Sutton and Barto (1998) Richard S. Sutton and Andrew G. Barto. 1998. Introduction to Reinforcement Learning, 1st edition. MIT Press, Cambridge, MA, USA.
  • Toutanova and Chen (2015) Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In 3rd Workshop on Continuous Vector Space Models and Their Compositionality (ACL).
  • Toutanova et al. (2016) Kristina Toutanova, Victoria Lin, Wen-tau Yih, Hoifung Poon, and Chris Quirk. 2016. Compositional learning of embeddings for relation paths in knowledge base and text. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL).
  • Trischler et al. (2017) Adam Trischler, Tong Wang, Xingdi Yuan, Justin Harris, Alessandro Sordoni, Philip Bachman, and Kaheer Suleman. 2017. Newsqa: A machine comprehension dataset. In Proceedings of the 2nd Workshop on Representation Learning for NLP (ACL).
  • Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016. Complex embeddings for simple link prediction. In Proceedings of the International Conference on Machine Learning (ICML).
  • Williams (1992) Ronald J. Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning.
  • Xiong et al. (2017) Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP).
  • Yang et al. (2017) Fan Yang, Zhilin Yang, and William W. Cohen. 2017. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems (NIPS).
  • Zhang et al. (2018) Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J. Smola, and Le Song. 2018. Variational reasoning for question answering with knowledge graph. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI).