ArcaneQA: Dynamic Program Induction and Contextualized Encoding for Knowledge Base Question Answering

ArcaneQA: Dynamic Program Induction and Contextualized Encoding for Knowledge Base Question Answering Yu Gu The Ohio State University Columbus, Ohio, USA gu.826@osu.edu Yu Su The Ohio State University Columbus, Ohio, USA su.809@osu.edu Abstract Question answering on knowledge bases (KBQA) poses a unique challenge for seman- tic parsing research due to two intertwined challenges: large search space and ambigui- ties in schema linking. Conventional ranking- based KBQA models, which rely on a can- didate enumeration step to reduce the search space, struggle with flexibility in predicting complicated queries and have impractical run- ning time. In this paper, we present ArcaneQA, a novel generation-based model that addresses both the large search space and the schema link- ing challenges in a unified framework with two mutually boosting ingredients: dynamic pro- gram induction for tackling the large search space and dynamic contextualized encoding for schema linking. Experimental results on mul- tiple popular KBQA datasets demonstrate the highly competitive performance of ArcaneQA in both effectiveness and efficiency.1 1 Introduction Modern knowledge bases (KBs) contain a wealth of structured knowledge. For example, FREEBASE (Bol- lacker et al., 2008) 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 (Sullivan, 2020). 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 pars- ing problem (Zelle and Mooney, 1996; Zettlemoyer and Collins, 2005) with the goal of mapping a nat- ural language question into a logical form that can be executed against the KB (Berant et al., 2013; Cai and Yates, 2013; Yih et al., 2015). Compared with other semantic parsing settings such as text-to- SQL parsing (Zhong et al., 2017; Yu et al., 2018), 1Data and code: dki-lab/ArcaneQA Question: Which wine in Tulum valley has the most alcohol? Program: (ARGMAX (AND (JOIN Tulum_Valley wine_sub_region) wine) percentage_alcohol) (JOIN #1 wine_sub_region) (JOIN #1 contains) (AND #2 wine) (JOIN #2 color) (ARGMAX #3 percentage_alcohol) Tulum_Valley Step 3 (a) Program Induction #1 #2 #3 (b) Contextualized Encoding Step 2 Step 1 Step 1 Step 3 (ARGMAX #3 vintage) Figure 1: KBQA is commonly modeled as semantic parsing with the goal of mapping a question into an executable program. (a) A high-level illustration of our program induction procedure. The target program is in- duced by incrementally synthesizing a sequence of sub- programs (#1-3). The execution of each subprogram can significantly reduce the search space of subsequent subprograms. (b) Alignments between question words and schema items at different steps achieved by a BERT encoder. A pre-trained language model like BERT can jointly encode the question and schema items to get the contextualized representation at each step, which further guides the search process. 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 …

Content truncated to 500 words