Program Transfer for Answering Complex Questions over Knowledge Bases (2022)

Abstract: Program induction for answering complex questions over knowledge bases (KBs) aims to decompose a question into a multi-step program, whose execution against the KB produces the final answer. Learning to induce programs relies on a large number of parallel question-program pairs for the given KB. However, for most KBs, the gold program annotations are usually lacking, making learning difficult. In this paper, we propose the approach of program transfer, which aims to leverage the valuable program annotations on the rich-resourced KBs as external supervision signals to aid program induction for the low-resourced KBs that lack program annotations. For program transfer, we design a novel two-stage parsing framework with an efficient ontology-guided pruning strategy. First, a sketch parser translates the question into a high-level program sketch, which is the composition of functions. Second, given the question and sketch, an argument parser searches the detailed arguments from the KB for functions. During the searching, we incorporate the KB ontology to prune the search space. The experiments on ComplexWebQuestions and WebQuestionSP show that our method outperforms SOTA methods significantly, demonstrating the effectiveness of program transfer and our framework. Our codes and datasets can be obtained from https://github.com/THU-KEG/ProgramTransfer .

## introduction answering complex questions over knowledge bases (complex kbqa) is a challenging task requiring logical, quantitative, and comparative reasoning over kbs @xcite . recently, the program induction (pi) paradigm, which gains increasing study in various areas @xcite @xcite ., * corresponding author program relate find relate filter concept filter concept find question what barcelona facility where fc barcelona plays can i visit? answer camp nou what and filter concept tourist attraction relate tourist attractions find barcelona find fc barcelona relate arena stadium filter concept sports facility 2021), emerges as a promising technique for complex kbqa @xcite @xcite . given a kb, pi for complex kbqa aims to decompose a complex question into a multi-step program, whose execution on the kb produces the answer. fig. 1 presents a complex question and its corresponding program whose functions take kb elements (i.e., entities, relations and concepts) as arguments. e.g., the relation tourist attractions is the argument of function relate. for most kbs, the parallel question-program pairs are lacking because such annotation is both expensive and labor-intensive. thus, the pi models have to learn only from question-answer pairs. typically, they take the answers as weak supervision and search for gold programs with reinforcement learning (rl) @xcite @xcite . the combinatorial explosion in program space, along with extremely sparse rewards, makes the learning challenging. abundant attempts have been made to improve the stability of rl algorithms with pseudo-gold programs @xcite , noise-stabilizing wrapper @xcite , or auxiliary rewards @xcite . despite promising results, they re-quire significant human efforts to develop carefullydesigned heuristics or are constrained to relatively simple questions. recently, for several kbs, there emerge questionprogram annotation resources @xcite . thanks to the supervision signals (i.e., program annotation for each question), the pi models on these rich-resourced kbs achieve impressive performance for even extremely complex questions, and are free from expert engineering. intuitively, leveraging these supervision signals to aid program induction for low-resourced kbs with only weak-supervision signals (i.e., questionanswer pairs) is a promising direction. in this paper, we formalize it as program transfer. in practice, program transfer is challenging due to the following reasons: (a) domain heterogeneity. the questions and kbs across domains are both heterogeneous due to language and knowledge diversity @xcite to address the above problems, we propose a novel two-stage parsing framework with an efficient ontology-guided pruning strategy. first, we design a sketch parser to parse the question into a program sketch (the left side in fig. 1 ), which is composed of functions without arguments. as baroni (2019) points out, the composition of functions well captures the language compositionality. translation from questions to sketches is thus relevant to language compositional structure and independent of kb structure. therefore, our sketch parser can transfer across kbs. second, we design an argument parser to fill in the detailed arguments (typically kb elements) for functions in the sketch. it retrieves relevant kb elements from the target kb and ranks them according to the question. specifically, it identifies kb elements with their label descriptions and relies on language understanding to resolve unseen ones. we further propose an ontology-guided pruning strategy, which introduces high-level kb ontology to prune the candi-date space for the argument parser, thus alleviating the problem of huge search space. specifically, the sketch parser is implemented with a seq2seq model with the attention mechanism. the argument parser identifies elements through semantic matching and utilizes pre-trained language models @xcite for language understanding. the high-level ontology includes the domain and range of relations and entity types. in evaluation, we take the wikidata-based kqa pro as the source, freebase-based complexwe-bquestions and webquestionsp as the target domain datasets. experimental results show that our method improves the f1 score by 14.7% and 2.5% respectively, compared with sota methods that learn from question-answer pairs. our 2 related work kbqa. kbqa aims to find answers for questions expressed in natural language from a kb, such as freebase @xcite , dbpedia @xcite and wikidata @xcite . current methods for kbqa can be categorized into two groups: 1) semantic parsing based methods @xcite @xcite @xcite , which learn a semantic parser that converts questions into intermediate logic forms which can be executed against a kb; 2) information retrieval based methods @xcite @xcite @xcite @xcite , which retrieve candidate answers from the topic-entity-centric subgraph and then rank them according to the questions. recently, semantic parsing for kbqa has gained increasing research attention because the methods are effective and more interpretable. multiple kinds of logical forms have been proposed and researched, such as sparql (hommeaux, 2011), λ-dcs @xcite , λ-calculus @xcite , query graph @xcite , program @xcite . pi aims to convert questions into programs, and is in line with semantic parsing. cross-domain semantic parsing. cross-domain semantic parsing trains a semantic parser on some source domains and adapts it to the target domain. some works @xcite @xcite pool together examples from multiple datasets in different domains and train a single sequence-to-sequence model over all examples, sharing parameters across domains. however, these methods rely on annotated logic forms in the target domain. to facilitate low-resource target domains, @xcite adapts to target domains with a very limited amount of annotated data. other works consider a zero-shot semantic parsing task @xcite , decoupling structures from lexicons for transfer. however, they only learn from the source domain without further learning from the target domain using the transferred prior knowledge. in addition, existing works mainly focus on the domains in overnight @xcite , which are much smaller than large scale kbs such as wikidata and freebase. considering the complex schema of large scale kbs, transfer in ours setting is more challenging. ## problem formulation in this section, we first give some necessary definitions and then formulate our task. knowledge bases. knowledge base describes concepts, entities, and the relations between them. it can be formalized as @xmath0, e, r, t }. c, e, r and t denote the sets of concepts, entities, relations and triples respectively. relation set r can be formalized as @xmath1, r c } ∪ r l , where r e is instanceof, r c is subclassof, and r l is the general relation set. t can be divided into three disjoint subsets: (1) instanceof triple set program is composed of symbolic functions with arguments, and produces an answer when executed against a kb. each function defines a basic operation on kb and takes a specific type of argument. for example, the function relate aims to find entities that have a specific relation with the given entity. formally, a program y is denoted as o here, o is a pre-defined function set, which covers basic reasoning operations over kbs @xcite . according to the argument type, o can be devided into four disjoint subsets: @xmath2, representing the functions whose argument type is entity, concept, relation and empty respectively. program induction. given a kb, and a complex natural language question @xmath3, w 2 , • • • , w |x| , it aims to produce a program y that generates the right answer z when executed against kb. program transfer. in this task, we have access to the source domain data @xmath4, d s , where d s contains pairs of question and program {(x s i , y s i )} n s @xmath5; and target domain data @xmath6, d t , where d t contains pairs of question and answer {(x t i , z t i )} n t @xmath7. we aim at learning a pi model to translate a question x for kb t into program y, which produces the correct answer when executed on kb t . ## framework as mentioned in the introduction, to perform program transfer for complex kbqa, we need to address three crucial problems: (1) what to transfer when both questions and kbs are heterogeneous? (2) how to deal with the kb elements unseen in the external annotations? (3) how to prune the search space of input arguments to alleviate the huge search space problem? in this section, we introduce our two-stage parsing framework with an ontology-guided pruning strategy, which is shown in fig. 2 . sketch parser argument parser fil.con. what relate find fil.con. relate ontology instanceof subclassof plac e of birt h nationality te a m s o w n e d tea ms own ed tea ms ow ne d lo c a t io n he ad co ac h hea d coa ch p la y e r entity-level triples sports team owner person steve bisciotti 𝒆 𝒊 𝒆 𝒋 𝒆 𝒌 sketch hockey team sports team football team baltimore ravens football coach coach john harbaugh sports team fil.con. steve bisciotti find team owned relate coach fil.con. head coach relate what ... ... . . . . . . instanceof instanceof question: who is the coach of the team owned by steve bisciotti? program figure 2: we design a high-level sketch parser to generate the sketch, and a low-level argument parser to predict arguments for the sketch. the arguments are retrieved from candidate pools which are illustrated by the color blocks. the arguments for functions are mutually constrained by the ontology structure. for example, when the second function relate finds the argument teams owned, the candidate pool for the third function fil.con. (short for filterconcept) is reduced to the range of relation teams owned. translation from question to sketch is relevant to language compositionality, and irrelevant to kb structure. therefore, the sketch parser can generalize across kbs. here, the candidate pool p contains the relevant elements in kb t , including concepts, entities, and relations. in a real kb, the candidate pool is usually huge, which makes searching and learning from answers very hard. therefore, we propose an ontology-guided pruning strategy, which dynamically updates the candidate pool and progressively reduces its search space. in the following we will introduce the implementation details of our sketch parser (section 4.1), argument parser (section 4.2) and training strategies (section 4.3).