Learning Relational Features with Backward Random Walks

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 666–675, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Learning Relational Features with Backward Random Walks Ni Lao Google Inc. nlao@google.com Einat Minkov University of Haifa einatm@is.haifa.ac.il William W. Cohen Carnegie Mellon University wcohen@cs.cmu.edu Abstract The path ranking algorithm (PRA) has been recently proposed to address relational classification and retrieval tasks at large scale. We describe Cor-PRA, an enhanced system that can model a larger space of relational rules, including longer relational rules and a class of first order rules with constants, while maintaining scalability. We describe and test faster algorithms for searching for these features. A key contribution is to leverage backward random walks to efficiently discover these types of rules. An empirical study is conducted on the tasks of graph-based knowledge base inference, and person named entity extraction from parsed text. Our results show that learning paths with constants improves performance on both tasks, and that modeling longer paths dramatically improves performance for the named entity extraction task. 1 Introduction Structured knowledge about entities and the relationships between them can be represented as an edge-typed graph, and relational learning methods often base predictions on connectivity patterns in this graph. One such method is the Path Ranking Algorithm (PRA), a random-walk based relational learning and inference framework due to Lao and Cohen (2010b). PRA is highly scalable compared with other statistical relational learning approaches, and can therefore be applied to perform inference in large knowledge bases (KBs). Several recent works have applied PRA to link prediction in semantic KBs, as well as to learning syntactic relational patterns used in information extraction from the Web (Lao et al., 2012; Gardner et al., 2013; Gardner et al., 2014; Dong et al., 2014). A typical relational inference problem is illustrated in Figure 1. Having relational knowledge represented as a graph, it is desired to infer additional relations of interest between entity pairs. For example, one may wish to infer whether an AthletePlaysInLeague relation holds between nodes HinesWard and NFL. More generally, link prediction involves queries of the form: which entities are linked to a source node s (HinesWard) over a relation of interest r (e.g., r is AlthletePlaysInLeague)? PRA gauges the relevance of a target node t with respect to the source node s and relation r based on a set of relation paths (i.e., sequences of edge labels) that connect the node pair. Each path πi is considered as feature, and the value of feature πi for an instance (s, t) is the probability of reaching t from s following path πi. A classifier is learned in this feature space, using logistic regression. PRA’s candidate paths correspond closely to a certain class of Horn clauses: for instance, the path π = ⟨AthletePlaysForTeam, TeamPlaysInLeague⟩, when used as a feature for the relation r = AthletePlaysForLeague, corresponds to the Horn clause AthletePlaysForTeam(s, z) ∧ TeamPlaysInLeague(z, t) → AthletePlaysForLeague(s, …

Content truncated to 500 words