Complex Program Induction for Querying Knowledge Bases in the Absence of Gold Programs

Complex Program Induction for Querying Knowledge Bases in the Absence of Gold Programs Amrita Saha1 Ghulam Ahmed Ansari1 Abhishek Laddha∗1 Karthik Sankaranarayanan1 Soumen Chakrabarti2 1IBM Research India, 2Indian Institute of Technology Bombay amrsaha4@in.ibm.com, ansarigh@in.ibm.com, laddhaabhishek11@gmail.com, kartsank@in.ibm.com, soumen@cse.iitb.ac.in Abstract Recent years have seen increasingly com- plex question-answering on knowledge bases (KBQA) involving logical, quantitative, and comparative reasoning over KB subgraphs. Neural Program Induction (NPI) is a pragmatic approach toward modularizing the reasoning process by translating a complex natural lan- guage query into a multi-step executable pro- gram. While NPI has been commonly trained with the ‘‘gold’’ program or its sketch, for realistic KBQA applications such gold pro- grams are expensive to obtain. There, prac- tically only natural language queries and the corresponding answers can be provided for training. The resulting combinatorial explo- sion in program space, along with extremely sparse rewards, makes NPI for KBQA ambi- tious and challenging. We present Complex Imperative Program Induction from Terminal Rewards (CIPITR), an advanced neural pro- grammer that mitigates reward sparsity with auxiliary rewards, and restricts the program space to semantically correct programs using high-level constraints, KB schema, and in- ferred answer type. CIPITR solves complex KBQA considerably more accurately than key-value memory networks and neural sym- bolic machines (NSM). For moderately com- plex queries requiring 2- to 5-step programs, CIPITR scores at least 3× higher F1 than the competing systems. On one of the hardest class of programs (comparative reasoning) with 5–10 steps, CIPITR outperforms NSM by a factor of 89 and memory networks by 9 times.1 ∗Now at Hike Messenger 1The NSM baseline in this work is a re-implemented version, as the original code was not available. 1 Introduction Structured knowledge bases (KB) like Wikidata and Freebase can support answering questions (KBQA) over a diverse spectrum of structural complexity. This includes queries with single-hop (Obama’s birthplace) (Yao, 2015; Berant et al., 2013), or multi-hop (who voiced Meg in Family Guy) (Bast and Haußmann, 2015; Yih et al., 2015; Xu et al., 2016; Guu et al., 2015; McCallum et al., 2017; Das et al., 2017), or complex queries such as ‘‘how many countries have more rivers and lakes than Brazil?’’ (Saha et al., 2018). Complex queries require a proper assembly of selected operators from a library of graph, set, logical, and arithmetic operations into a complex procedure, and is the subject of this paper. Relatively simple query classes, in particular, in which answers are KB entities, can be served with feed-forward (Yih et al., 2015) and seq2seq (McCallum et al., 2017; Das et al., 2017) networks. However, such systems show copying or rote learning behavior when Boolean or open numeric domains are involved. More complex queries need to be evaluated as an acyclic expression graph over nodes representing KB access, set, logical, and arithmetic operators (Andreas et al., 2016a). A practical alternative to inferring a state- less expression graph is to generate an imperative sequential program to solve the query. Each step of the program selects an atomic operator and a set of …

Content truncated to 500 words