A rcane QA : Dynamic Program Induction and Contextualized Encoding for Knowledge Base Question Answering (2022)

Abstract: Question answering on knowledge bases (KBQA) poses a unique challenge for semantic parsing research due to two intertwined challenges: large search space and ambiguities in schema linking. Conventional ranking-based KBQA models, which rely on a candidate enumeration step to reduce the search space, struggle with flexibility in predicting complicated queries and have impractical running time. In this paper, we present ArcaneQA, a novel generation-based model that addresses both the large search space and the schema linking challenges in a unified framework with two mutually boosting ingredients: dynamic program induction for tackling the large search space and dynamic contextualized encoding for schema linking. Experimental results on multiple popular KBQA datasets demonstrate the highly competitive performance of ArcaneQA in both effectiveness and efficiency.

## introduction modern knowledge bases (kbs) contain a wealth of structured knowledge. for example, freebase @xcite contains over 45 million entities and 3 billion facts across more than 100 domains, while google knowledge graph has amassed over 500 billion facts about 5 billion entities @xcite . question answering on knowledge bases (kbqa) has emerged as a user-friendly solution to access the massive structured knowledge in kbs. kbqa is commonly modeled as a semantic parsing problem @xcite with the goal of mapping a natural language question into a logical form that can be executed against the kb @xcite @xcite . compared with other semantic parsing settings such as text-to-sql parsing @xcite , where the underlying data is moderate-sized, the massive scale and the broad-coverage schema of kbs makes kbqa a uniquely challenging setting for semantic parsing research. the unique difficulty stems from two intertwined challenges: large search space and ambiguities in schema linking. on the one hand, transductive semantic parsing models that are highly effective in other semantic parsing settings @xcite struggle with the large vocabulary size and often generate logical forms (i.e., formal queries) foot_1 that are not faithful to the underlying kb @xcite . therefore, a candidate enumeration and ranking approach is commonly adopted for kbqa @xcite @xcite @xcite @xcite . however, these methods have to make various compromises on the complexity of admissible logical forms to deal with the large search space. not only does this limit the type of answerable questions, but it also leads to impractical runtime performance due to the time-consuming candidate enumeration @xcite . on the other hand, schema linking, foot_2 i.e., mapping natural language to the corresponding schema items in the kb (e.g., in figure 1 , wine sub region is a linked schema items), is also a core challenge of kbqa. compared with text-to-sql parsing @xcite @xcite , the broad schema of kbs and the resulting ambiguity between schema items makes accurate schema linking more important and challenging for kbqa. recent studies show that contextualized joint encoding of natural language questions and schema items with bert @xcite can significantly boost the schema linking accuracy @xcite . however, existing methods still struggle with the large search space and need to encode a large number of schema items, which is detrimental to both accuracy and efficiency. we present arcaneqa (dynamic program induction and contextualized encoding for question answering), a generation-based kbqa model that addresses both the large search space and the schema linking challenges in a unified framework. compared with the predominant ranking-based kbqa models, our generationbased model can prune the search space on the fly and thus is more flexible to generate diverse queries without compromising the expressivity or complexity of answerable questions. inspired by prior work @xcite @xcite , we model kbqa using the encoder-decoder framework. however, instead of top-down decoding with grammar-level constraints as in prior work, which does not guarantee the faithfulness of the generated queries to the underlying kb, arcaneqa performs dynamic program induction @xcite , where we incrementally synthesize a program by dynamically predicting a sequence of subprograms to answer a question; i.e., bottom-up parsing @xcite . each subprogram is grounded to the kb and its grounding (i.e., denotation or execution results) can further guide an efficient search for faithful programs (see figure 1(a) ). in addition, we unify the meaning representation (mr) for programs in kbqa using s-expressions and support more diverse operations over the kb (e.g., numerical operations such as count/argmin/argmax and diverse graph traversal operations). at the same time, we employ pre-trained language models (plms) like bert to jointly encode the question and schema items and get the contextualized representation of both, which implicitly links words to the corresponding schema items via self-attention. one unique feature to note is that the encoding is also dynamic: at each prediction step, only the set of admissible schema items determined by the dynamic program induction process needs to be encoded, which allows extracting the most relevant information from the question for each prediction step while avoiding the need to encode a large number of schema items. figure 1( b) illustrates the contextualization of different steps via the attention heatmaps of bert. in this example, the attention of each question word over candidate schema items serves as a strong indicator of the gold items for both steps (i.e., wine sub region for step 1 and percentage alcohol for step 3). the two key ingredients of our model are mutually boosting: dynamic program induction significantly reduces the number of schema items that need to be encoded, while dynamic contextualized encoding intelligently guides the search process. our main contribution is as follows: a) we propose a novel generation-based kbqa model that is flexible to generate diverse complex queries while also being more efficient than ranking-based models. b) we propose a novel strategy to effectively employ plms to provide contextualized encoding for kbqa. c) we unify the meaning representation (mr) of different kbqa datasets and support more diverse operations. d) with our unified mr, we evaluate our model on three popular kbqa datasets and show highly competitive results. generation-based kbqa. to relax the restriction on candidate enumeration, some recent efforts are made to reduce the search space using beam search @xcite @xcite , however, @xcite and @xcite can only generate programs of path structure, while lan and jiang (2020) follow the query graph structure proposed by @xcite . a few recent studies @xcite formulate semantic parsing over the kb as sequence transduction using encoderdecoder models to enable more flexible generation. @xcite apply schema-level constraints to eliminate ill-formed programs from the search space, however, they do not guarantee the faithfulness of predicted programs. similar to @xcite , our dynamic program induction uses kb contents-level constraints to ensure the faithfulness of generated programs, but we extend it to handle more complex and diverse questions and also use it jointly with dynamic contextualized encoding. using plms in semantic parsing. plms have been widely applied in many semantic parsing tasks, typically being used to jointly encode the input question and schema items @xcite @xcite . however, plms have been under-exploited in kbqa. one major difficulty of using plms in kbqa lies in the high volume of schema items in a kb; simply concatenating all schema items with the input question for joint encoding, as commonly done in text-to-sql parsing, will vastly exceed plms' maximum input length. existing kbqa models either use plms to provide features for downstream classifiers @xcite or adopts a pipeline design to identify a smaller set of schema items beforehand and only use plms to encode these identified items @xcite , which can lead to error propagation. by comparison, arcaneqa can fully exploit plms to provide contextualized representation for the question and schema items dynamically, where only the most relevant schema items are encoded at each step. more recently, @xcite use t5 @xcite to output a new program given a program as input, while t5's decoder generates free-formed text and does not always produce faithful programs. by contrast, ar-caneqa only uses plms for encoding and uses its customized decoder with a faithfulness guarantee. in this paper, we follow @xcite to use s-expressions as our meaning representation due to their expressivity and simplicity. to support more diverse operations over the kb, we extend their definitions with two additional functions cons and tc, which are used to support constraints with implicit entities and temporal constraints respectively (see details in appendix a). for implicit entities, consider the question "what was elie wiesel's father's name?", whose target query involves two entities: elie wiesel and male. the entity male is an implicit constraint rather than a named entity, 4 and it is used as an argument of cons in the target logical form: (cons (join people.person.children elie wiesel) people.person.gender male). tc works in a similar way, with the difference being that the constraint should be a temporal expression (e.g., 2015-08-10) rather than an implicit entity. ## experimental setup datasets. we evaluate arcaneqa on three kbqa datasets covering diverse kb queries. grailqa @xcite is a large-scale kbqa dataset that contains complex questions with various functions, including comparatives, superlatives, and counting. it evaluates the generalizability of kbqa at three levels: i.i.d., compositional and zero-shot. graphq @xcite also contains questions of diverse nature. it is particularly challenging because it exclusively focuses on non-i.i.d. generalization. foot_4 webqsp @xcite is a clean subset of webq @xcite with annotated logical forms. all questions in it are collected from google query logs, featuring more realistic and complicated information needs such as questions with temporal constraints. the total number of questions in grailqa, graphq, and webq is 64,331, 5,166, and 4,737 respectively. evaluation metrics. for grailqa, we use their official evaluation script with two metrics, em, i.e., program exact match accuracy, and f1, which is computed based on the predicted and the gold answer set. for graphq and webqsp, we follow the standard practice and report f1.