Compositional Learning of Embeddings for Relation Paths in Knowledge Base and Text

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1434–1444, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Compositional Learning of Embeddings for Relation Paths in Knowledge Bases and Text Kristina Toutanova Microsoft Research Redmond, WA, USA Xi Victoria Lin∗ Computer Science & Engineering University of Washington Wen-tau Yih Microsoft Research Redmond, WA, USA Hoifung Poon Microsoft Research Redmond, WA, USA Chris Quirk Microsoft Research Redmond, WA, USA Abstract Modeling relation paths has offered sig- nificant gains in embedding models for knowledge base (KB) completion. How- ever, enumerating paths between two en- tities is very expensive, and existing ap- proaches typically resort to approxima- tion with a sampled subset. This problem is particularly acute when text is jointly modeled with KB relations and used to provide direct evidence for facts men- tioned in it. In this paper, we propose the first exact dynamic programming al- gorithm which enables efficient incorpo- ration of all relation paths of bounded length, while modeling both relation types and intermediate nodes in the composi- tional path representations. We conduct a theoretical analysis of the efficiency gain from the approach. Experiments on two datasets show that it addresses representa- tional limitations in prior approaches and improves accuracy in KB completion. 1 Introduction Intelligent applications benefit from structured knowledge about the entities and relations in their domains. For example, large-scale knowl- edge bases (KB), such as Freebase (Bollacker et al., 2008) or DBPedia (Auer et al., 2007), have proven to be important resources for supporting open-domain question answering (Berant et al., 2013; Sun et al., 2015; Yih et al., 2015). In biomedicine, KBs such as the Pathway Interaction Database (NCI-PID) (Schaefer et al., 2009) are crucial for understanding complex diseases such as cancer and for advancing precision medicine. ∗This research was conducted during the author’s intern- ship at Microsoft Research. While these knowledge bases are often carefully curated, they are far from complete. In non-static domains, new facts become true or are discovered at a fast pace, making the manual expansion of knowledge bases impractical. Extracting relations from a text corpus (Mintz et al., 2009; Surdeanu et al., 2012; Poon et al., 2015) or inferring facts from the relationships among known entities (Lao and Cohen, 2010) are thus important approaches for populating existing knowledge bases. Originally proposed as an alternative statis- tical relational learning method, the knowledge base embedding approach has gained a signifi- cant amount of attention, due to its simple predic- tion time computation and strong empirical perfor- mance (Nickel et al., 2011; Chang et al., 2014). In this framework, entities and relations in a knowl- edge base are represented in a continuous space, such as vectors and matrices. Whether two enti- ties have a previously unknown relationship can be predicted by simple functions of their corre- sponding vectors or matrices. Early work in this direction focuses on exploring various kinds of learning objectives and frameworks, but the model is learned solely from known direct relationships between two entities …

Content truncated to 500 words