Mining Inference Formulas by Goal-Directed Random Walks

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1379–1388, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Mining Inference Formulas by Goal-Directed Random Walks Zhuoyu Wei1,2, Jun Zhao1,2 and Kang Liu1 1 National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing, 100190, China 2 University of Chinese Academy of Sciences, Beijing, 100049, China {zhuoyu.wei, jzhao, kliu}@nlpr.ia.ac.cn Abstract Deep inference on a large-scale knowledge base (KB) needs a mass of formulas, but it is almost impossible to create all formulas man- ually. Data-driven methods have been pro- posed to mine formulas from KBs automat- ically, where random sampling and approx- imate calculation are common techniques to handle big data. Among a series of method- s, Random Walk is believed to be suitable for knowledge graph data. However, a pure ran- dom walk without goals still has a poor ef- ficiency of mining useful formulas, and even introduces lots of noise which may mislead in- ference. Although several heuristic rules have been proposed to direct random walks, they do not work well due to the diversity of for- mulas. To this end, we propose a novel goal- directed inference formula mining algorithm, which directs random walks by the specific inference target at each step. The algorithm is more inclined to visit benefic structures to infer the target, so it can increase efficiency of random walks and avoid noise simultane- ously. The experiments on both WordNet and Freebase prove that our approach is has a high efficiency and performs best on the task. 1 Introduction Recently, various knowledge bases (KBs), such as Freebase (Bollacker et al., 2008), WordNet (Miller, 1995), Yago (Hoffart et al., 2013), have been built, and researchers begin to explore how to make use of structural information to promote performances of several inference-based NLP applications, such as text entailment, knowledge base completion, ques- tion and answering. Creating useful formulas is one of the most important steps in inference, and an ac- curate and high coverage formula set will bring a great promotion for an inference system. For ex- ample, Nationality(x, y) ∧ Nationality(z, y) ∧ Lan- guage(z, w) ⇒ Language(x, w) is a high-quality for- mula, which means people with the same nationality probably speak the same language. However, it is a challenge to create formulas for open-domain KBs, where there are a great variety of relation types and it is impossible to construct a complete formula set by hand. Several data-driven methods, such as Induc- tive Logic Programming (ILP) (Muggleton and De Raedt, 1994) and Markov Logic Network (MLN) (Richardson and Domingos, 2006), have been pro- posed to mine formulas automatically from KB da- ta, which transform frequent sub-structures of KBs, e.g., paths or loops, into formulas. Figure 1.a shows a sub-graph extracted from Freebase, and the for- mula mentioned above about Language can be gen- erated from the loop in Figure 1.d. However, the running time of these traditional probabilistic infer- ence methods is unbearable over large-scale …

Content truncated to 500 words