UHop: An Unrestricted-Hop Relation Extraction Framework for Knowledge-Based Question Answering

Proceedings of NAACL-HLT 2019, pages 345–356 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 345 UHop: An Unrestricted-Hop Relation Extraction Framework for Knowledge-Based Question Answering Zi-Yuan Chen1, Chih-Hung Chang1, Yi-Pei Chen2, Jijnasa Nayak3, Lun-Wei Ku1,4 Institute of Information Science, Academia Sinica1 University of Massachusetts Amherst2 National Institute of Technology, Rourkela3 Most Joint Research Center for AI Technology and All Vista Healthcare4 {zychen,lance5,lwku}@iis.sinica.edu.tw yipeichen@cs.umass.edu, jijnasa23@gmail.com Abstract In relation extraction for knowledge-based question answering, searching from one en- tity to another entity via a single relation is called “one hop”. In related work, an exhaus- tive search from all one-hop relations, two-hop relations, and so on to the max-hop relations in the knowledge graph is necessary but expen- sive. Therefore, the number of hops is gener- ally restricted to two or three. In this paper, we propose UHop, an unrestricted-hop frame- work which relaxes this restriction by use of a transition-based search framework to replace the relation-chain-based search one. We con- duct experiments on conventional 1- and 2- hop questions as well as lengthy questions, in- cluding datasets such as WebQSP, PathQues- tion, and Grid World. Results show that the proposed framework enables the ability to halt, works well with state-of-the-art models, achieves competitive performance without ex- haustive searches, and opens the performance gap for long relation paths. 1 Introduction A knowledge graph (KG) is a powerful graph structure that encodes knowledge to save and or- ganize it, and to provide users with direct access to this knowledge via various applications, one of which is question answering, or knowledge- based question answering (KBQA). In the knowl- edge graph, beliefs are commonly represented by triples showing relations between two enti- ties, such as LocatedIn(NewOrleans, Louisiana), where the two entities are nodes and their rela- tion is the edge connecting them in the knowl- edge graph. Given a natural language question, a KBQA system returns its answer if it is included in the knowledge graph; the process of answering a question can be transformed into a traversal that starts from the question (topic) entity and searches for the appropriate path to the answer entity. In the literature (Yu et al., 2017; Yin et al., 2016; Yih et al., 2015) KBQA is decomposed into topic entity linking, which determines the start- ing entity corresponding to the question, and re- lation extraction, which finds the path to the an- swer node(s). Theoretically, relation extraction finds paths of any length, that is, paths that contain any number of relation links, or hops (between two nodes), as long as it reaches the answer node. In previous work, models consider all relation paths starting from the topic entity (Yu et al., 2017; Yin et al., 2016; Yih et al., 2015); we call these relation-chain-based methods. Two main difficul- ties for these methods are that processing through all relations in a KG is not practical as the com- bination of these relations is nearly infinite, and that the number of candidate paths grows exponen- tially …

Content truncated to 500 words