Case-based Reasoning for Natural Language Queries over Knowledge Bases (2021)

Abstract: It is often challenging to solve a complex problem from scratch, but much easier if we can access other similar problems with their solutions — a paradigm known as case-based reasoning (CBR). We propose a neuro-symbolic CBR approach (CBR-KBQA) for question answering over large knowledge bases. CBR-KBQA consists of a nonparametric memory that stores cases (question and logical forms) and a parametric model that can generate a logical form for a new question by retrieving cases that are relevant to it. On several KBQA datasets that contain complex questions, CBR-KBQA achieves competitive performance. For example, on the CWQ dataset, CBR-KBQA outperforms the current state of the art by 11% on accuracy. Furthermore, we show that CBR-KBQA is capable of using new cases without any further training: by incorporating a few human-labeled examples in the case memory, CBR-KBQA is able to successfully generate logical forms containing unseen KB entities as well as relations.

## introduction humans often solve a new problem by recollecting and adapting the solution to multiple related problems that they have encountered in the past @xcite @xcite . in classical artificial intelligence (ai), case-based reasoning (cbr) pioneered by @xcite , tries to incorporate such model of reasoning in ai systems @xcite @xcite . a sketch of a cbr system @xcite comprises of -(i) a retrieval module, in which 'cases' that are similar to the given problem are retrieved, (ii) a reuse module, where the solutions of the retrieved cases are reused to synthesize a new solution. often, the new solution does not work and needs more revision, which is handled by a (iii) revise module. in its early days, the components of cbr were implemented with symbolic systems, which had their limitations. for example, finding similar cases and synthesizing new solutions from them is a challenging task for a cbr system implemented with symbolic components. however, with the recent advancements in representation learning @xcite , the performance of ml systems have improved substantially on a range of practical tasks. given a query, cbr-kbqa uses a neural retriever to retrieve other similar queries (and their logical forms) from a case memory (e.g. training set). next, cbr-kbqa generates a logical form for the given query by learning to reuse various components of the logical forms of the retrieved cases. however, often the generated logical form does not produce the right answer when executed against a knowledge base (kb). this can happen because one or more kb relations needed are never present in the retrieved cases or because kbs are woefully incomplete @xcite (figure 1 ). to alleviate such cases, cbr-kbqa has an additional revise step that aligns the generated relations in the logical form to the query entities' local neighborhood in the kb. to achieve this, we take advantage of pre-trained relation embeddings from kb completion techniques (e.g. trans-e @xcite ) that learn the structure of the kb. it has been shown that neural seq2seq models do not generalize well to novel combinations of previously seen input (lake and @xcite . however, cbr-kbqa has the ability to reuse relations from multiple retrieved cases, even if each case contains only partial logic to answer the query. we show that cbr-kbqa is effec- legend grounded kb entities people.person.parents type:person who is gimli's father's sibling in the hobbit? tive for questions that need novel combination of kb relations, achieving competitive results on multiple kbqa benchmarks such as webquestionssp @xcite , complexwebquestions (cwq) @xcite and compositionalfree-basequestions (cfq) @xcite . for example, on the hidden test-set of the challenging cwq dataset, cbr-kbqa outperforms the best system by over 11% points. we further demonstrate that cbr-kbqa, without the need of any further fine-tuning, also generalizes to queries that need relations which were never seen in the training set. this is possible due to cbr-kbqa's nonparametric approach which allows one to inject relevant simple cases during inference, allowing it to reuse new relations from those cases. in a controlled human-in-the-loop experiment, we show that cbr-kbqa can correctly answer such questions when an expert (e.g. database administrator) injects a few simple cases to the case memory. cbr-kbqa is able to retrieve those examples from the memory and use the unseen relations to compose new logical forms for the given query. generalization to unseen kb relations, without any re-training, is out of scope for current neural models. currently, the popular approach to handle such cases is to re-train or fine-tune the model on new examples. this process is not only time-consuming and laborious but models also suffer from catastrophic forgetting @xcite , making wrong predictions on examples which it previously predicted correctly. we believe that the controllable properties of cbr-kbqa are essential for qa models to be deployed in real-world settings and hope that our work will inspire further research in this direction. recent works such as realm @xcite ) and rag @xcite retrieve relevant paragraphs from a nonparametric memory for answering questions. cbr-kbqa, in contrast, retrieves similar queries w.r.t the input query and uses the relational similarity between their logical forms to derive a logical form for the new query. cbr-kbqa is also similar to the recent retrieve and edit framework @xcite for generating structured output. however, unlike us they condition on only a single retrieved example and hence is unlikely to be able to handle complex questions that need reuse of partial logic from multiple questions. moreover, unlike cbr-kbqa, retrieve and edit does not have a component that can explicitly revise an initially generated output. the contributions of our paper are as follows -(a) we present a neural cbr approach for kbqa capable of generating complex logical forms conditioned on similar retrieved questions and their logical forms. (b) since cbr-kbqa explicitly learns to reuse cases, we show it is able to generalize to unseen relations at test time, when relevant cases are provided. (c) we also show the efficacy of our revise step of cbr-kbqa which allows to correct generated output by aligning it to local neighborhood of the query entity. (d) lastly, we show that cbr-kbqa significantly outperforms other competitive models on several kbqa benchmarks. ## model this section describes the implementation of various modules of cbr-kbqa. in cbr, a case is defined as an abstract representation of a problem along with its solution. in our kbqa setting, a case is a natural language query paired with an executable logical form. the practical importance of kbqa has led to the creation of an array of recent datasets @xcite @xcite @xcite @xcite . in these datasets, a question is paired with an executable logical form such as sparql, sql, s-expression or graph query. all of these forms have equal representational capacity and are interchangeable @xcite . figure 2 shows an example of two equivalent logical forms. for our experiments, we consider sparql programs as our logical form. formal definition of task: let q be a natural language query and let k be a symbolic kb that needs to be queried to retrieve an answer list a containing the answer(s) for q. we also assume access to a training set @xmath0, ℓ 1 ), (q 2 , ℓ 2 ), . . . (q n , ℓ n )} of queries and their corresponding logical forms where q i , ℓ i represents query and its corresponding logical form, respectively. a logical form is an executable query containing entities, relations and free variables (figure 2 ). cbr-kbqa first retrieves k similar cases d q from d ( § 2.1). it then generates a intermediate logical form ℓ inter by learning to reuse components of the logical forms of the retrieved cases ( § 2.2). next, the logical form ℓ inter is revised to output the final logical form ℓ by aligning to the relations present in the neighborhood subgraph of the query entity to recover from any spurious relations generated in the reuse step ( § 2.3). finally, ℓ is executed against k and the list of answer entities are returned. we evaluate our kbqa system by calculating the accuracy of the retrieved answer list w.r.t a held-out set of queries. ## limitations and future work to the best of our knowledge, we are the first to propose a neuralized cbr approach for kbqa. we showed that our model is effective in handling complex questions over kbs, but our work also has several limitations. first, our model relies on the availability of supervised logical forms such as sparql queries, which can be expensive to annotate at scale. in the future, we plan to explore ways to directly learn from question-answer pairs @xcite . even though, cbr-kbqa is modular and has several advantages, the retrieve and reuse components of our model are trained separately. in future, we plan to explore avenues for end to end learning for cbr.