Few-Shot Complex Knowledge Base Question Answering via Meta Reinforcement Learning (2020)

Abstract: Complex question-answering (CQA) involves answering complex natural-language questions on a knowledge base (KB). However, the conventional neural program induction (NPI) approach exhibits uneven performance when the questions have different types, harboring inherently different characteristics, e.g., difficulty level. This paper proposes a meta-reinforcement learning approach to program induction in CQA to tackle the potential distributional bias in questions. Our method quickly and effectively adapts the meta-learned programmer to new questions based on the most similar questions retrieved from the training data. The meta-learned policy is then used to learn a good programming policy, utilizing the trial trajectories and their rewards for similar questions in the support set. Our method achieves state-of-the-art performance on the CQA dataset (Saha et al., 2018) while using only five trial trajectories for the top-5 retrieved questions in each support set, and meta-training on tasks constructed from only 1% of the training set. We have released our code at https://github.com/DevinJake/MRL-CQA .

## introduction knowledge-base question-answering (kbqa) interrogates a knowledge-base (kb) @xcite @xcite by interpreting natural-language questions as logical forms (annotations), which can be directly executed on the kb to yield answers (denotations) @xcite . kbqa includes simple questions that retrieve answers from single-hop triples ("what is donald trump's nationality") @xcite , multi-hop questions that infer answers over triple chains of at least 2 hops under specific constraints ("who is the president of the european union 2012") @xcite , and complex questions that involve set operations ("how many rivers flow through india and china") @xcite . in particular, complex question answering (cqa) @xcite is a sophisticated kbqa task in which a sequence of discrete actions-e.g., set intersection and union, counting, comparison-needs to be executed, and is the subject of this paper. consider the complex question "how many rivers flow through india and china?". we first form a set of entities whose type is river and flow in china from the kb. we then form another set for rivers that flow through india. the answer is then generated by counting the entities in the intersection of the two sets. more concretely, the question is transformed into the action sequence "select (china, flow, river), intersection (india, flow, river), count", which is executed on the kb to yield the answer. as such, the cqa task results in a massive search space beyond just entities in the kb and includes (lists of) boolean values and integers. multi-hop questions only require the join operator. in contrast, cqa requires various types of additional symbolic reasoning, e.g., logical, comparative, and quantitative reasoning @xcite , where a more diverse array of complex queries is involved @xcite . the massive search space and complex queries make cqa considerably challenging and more complicated than multihop question answering. due to the difficulty of collecting annotations, the existing cqa dataset @xcite only contains the denotations for each question. the literature takes two approaches to deal with the missing annotations. the first approach aims to transform learning a cqa model into learning by demonstration, aka imitation learning, where a pseudo-gold action sequence is produced for the questions in the training set @xcite . this is done by employing a blind search algorithm, i.e., breadth-first search (bfs), to find a sequence of actions whose execution would yield the correct answer. this pseudo-gold annotation is then used to train the programmer using teacher forcing, aka behaviour cloning. however, bfs inevitably produces a single annotation and is ignorant to many other plausible annotations yielding the correct answer. to alleviate this issue, a second approach was proposed based on reinforcement learning (rl) to use the search policy prescribed by the programmer @xcite @xcite . compared to bfs which is a blind search algorithm, the rl-trained programmer can be regarded as an informed search algorithm for target programs. therefore, the rl policy not only addresses the limitation of the 1-to-1 mapping between the questions and annotations, but also produces reasonable programs faster than bfs. the conventional approach to cqa is to train one model to fit the entire training set, and then use it for answering all complex questions at the test time. however, such a one-size-fits-all strategy is sub-optimal as the test questions may have diversity due to their inherently different characteristics @xcite . for instance, in the cqa dataset, the samples could be categorized into seven different types, e.g., those capturing logical/comparative/quantitative reasoning. the length and complexity of questions in one group are likely to differ from those in other groups. therefore, action sequences relevant to different groups may have significant deviations, and it is hard to learn a one-size-fits-all model that could adapt to varied types of questions. an exception is @xcite , which proposes a few-shot learning approach, i.e., s2a, to solve the cqa problem with a retriever and a meta-learner. the retriever selects similar instances from the training dataset to form tasks, and the meta-learner is trained on these tasks to learn how to quickly adapt to a new task created by the target question of interest at the test time. however, guo et al. (2019) make use of teacher forcing within the learning by demonstration approach, which suffers from the aforementioned drawbacks. also, though s2a is the most similar to ours, the tasks are very different. s2a aims to answer context-dependent questions, where each question is part of a multiple-turn conversation. on the contrary, we consider the different task where the questions are single-turn and have no context. thus, a novel challenge arises in re-trieving accurate support sets without conversationbased context information. in this paper, we propose a meta-rl approach for cqa (mrl-cqa), where the model adapts to the target question by trials and the corresponding reward signals on the retrieved instances. in the meta-learning stage, our approach learns a rl policy across the tasks for both (i) collecting trial trajectories for effective learning, and (ii) learning to adapt programmer by effectively combining the collected trajectories. the accumulated general knowledge acquired during meta-learning enables the model to generalize over varied tasks instead of fitting the distribution of data points from a single task. thus, the tasks generated from tiny (less than 1%) portion of the training data are sufficient for meta learner to acquire the general knowledge. our method achieves state-of-the-art performance on the cqa dataset with overall macro and micro f1 scores of 66.25% and 77.71%, respectively. ## meta-rl for complex question answering the problem we study in this paper is transforming a complex natural-language question into a sequence of actions, i.e., a sequence-to-sequence learning task. by executing the actions, relevant triples are fetched from the kb, from which the answer to the question is induced. we tackle this problem with few-shot meta reinforcement learning to decrease the reliance on data annotation and increase the accuracy for different questions. let q denote the input sequence, including the complex question and the kb artifacts, i.e., entities, relations, and types in kb that are relevant to the problem. let τ denotes the output sequence, i.e., an action sequence that the agent generates to answer the question. let r(τ |q) ∈ [0, 1] denotes the partial reward feedback that tells whether or not the action sequence yields the correct answer. to simplify the notation, we denote the reward function by r(τ ). the training objective is to maximize the expected reward by optimizing the parameter θ of the policy π(τ |q; θ), i.e., improving the accuracy of the policy in answering unseen questions. for the test, the agent needs to generate an action sequence τ * for the input sequence using a search algorithm, e.g., greedy decoding, which is then executed on kb to get the answer. ## experiments in this section, we present the empirical evaluation of our mrl-cqa framework. dataset. we evaluated our model on the largescale cqa (complex question answering) dataset @xcite . generated from the wikidata kb @xcite , cqa contains 944k/100k/156k qa pairs for training, validation, and testing, respectively. in the cqa dataset, each qa pair consists of a complex, natural-language question and the corresponding ground-truth answer (i.e., denotation). we note that annotations, i.e., gold action sequences related to the questions, are not given in the cqa dataset. the cqa questions are organized into seven categories of different characteristics, as shown in the based on the length of the induced programs and performance of the best models, we further organized the seven categories into two groups: easy-the first four categories, and hard-the last three types, in ## conclusion cqa refers to answering complex natural language questions on a kb. in this paper, we propose a meta-learning method to npi in cqa, which quickly adapts the programmer to unseen questions to tackle the potential distributional bias in questions. we take a meta-reinforcement learning approach to effectively adapt the meta-learned programmer to new questions based on the most similar questions retrieved. to effectively create the support sets, we propose an unsupervised retriever to find the questions that are structurally and semantically similar to the new questions from the training dataset. when evaluated on the large-scale complex question answering dataset, cqa, our proposed approach achieves state-of-the-art performance with overall macro and micro f1 score of 66.25% and 77.71%, respectively. in the future, we plan to improve mrl-cqa by designing a retriever that could be optimized jointly with the programmer under the meta-learning paradigm, instead of manually pre-defining a static relevance function. other potential directions of research could be toward learning to cluster questions into fine-grained groups and assign each group a set of specific initial parameters, making the model finetune the parameters more precisely.