Learning Relational Dependency Networks for Relation Extraction

Abstract: We consider the task of KBP slot filling -- extracting relation information from newswire documents for knowledge base construction. We present our pipeline, which employs Relational Dependency Networks (RDNs) to learn linguistic patterns for relation extraction. Additionally, we demonstrate how several components such as weak supervision, word2vec features, joint learning and the use of human advice, can be incorporated in this relational framework. We evaluate the different components in the benchmark KBP 2015 task and show that RDNs effectively model a diverse set of features and perform competitively with current state-of-the-art relation extraction.

The problem of knowledge base population (KBP) – constructing a knowledge base (KB) of facts gleaned from a large corpus of unstructured data – poses several challenges for the NLP community. Commonly, this relation extraction task is decomposed into two subtasks – entity linking, in which entities are linked to already identified identities within the document or to entities in the existing KB, and slot filling, which identifies certain attributes about a target entity.
We present our work-in-progress for KBP slot filling based on our probabilistic logic formalisms and present the different components of the system. Specifically, we employ Relational Dependency Networks BIBREF0 , a formalism that has been successfully used for joint learning and inference from stochastic, noisy, relational data. We consider our RDN system against the current state-of-the-art for KBP to demonstrate the effectiveness of our probabilistic relational framework.
Additionally, we show how RDNs can effectively incorporate many popular approaches in relation extraction such as joint learning, weak supervision, word2vec features, and human advice, among others. We provide a comprehensive comparison of settings such as joint learning vs learning of individual relations, use of weak supervision vs gold standard labels, using expert advice vs only learning from data, etc. These questions are extremely interesting from a general machine learning perspective, but also critical to the NLP community. As we show empirically, some of the results such as human advice being useful in many relations and joint learning being beneficial in the cases where the relations are correlated among themselves are on the expected lines. However, some surprising observations include the fact that weak supervision is not as useful as expected and word2vec features are not as predictive as the other domain-specific features.
We first present the proposed pipeline with all the different components of the learning system. Next we present the set of 14 relations that we learn on before presenting the experimental results. We finally discuss the results of these comparisons before concluding by presenting directions for future research.
We present the different aspects of our pipeline, depicted in Figure FIGREF1 . We will first describe our approach to generating features and training examples from the KBP corpus, before describing the core of our framework – the RDN Boost algorithm.
Given a training corpus of raw text documents, our learning algorithm first converts these documents into a set of facts (i.e., features) that are encoded in first order logic (FOL). Raw text is processed using the Stanford CoreNLP Toolkit BIBREF1 to extract parts-of-speech, word lemmas, etc. as well as generate parse trees, dependency graphs and named-entity recognition information. The full set of extracted features is listed in Table TABREF3 . These are then converted into features in prolog (i.e., FOL) format and are given as input to the system.
In addition to the structured features from the output of Stanford toolkit, we also use deeper features based on word2vec BIBREF2 as input to our learning system. Standard NLP features tend to treat words as individual objects, ignoring links between words that occur with similar meanings or, importantly, similar contexts (e.g., city-country pairs such as Paris – France and Rome – Italy occur in similar contexts). word2vec provide a continuous-space vector embedding of words that, in practice, capture many of these relationships BIBREF2 , BIBREF3 . We use word vectors from Stanford and Google along with a few specific words that, experts believe, are related to the relations learned. For example, we include words such as “father” and “mother” (inspired by the INLINEFORM0 relation) or “devout”,“convert”, and “follow” ( INLINEFORM1 relation). We generated features from word vectors by finding words with high similarity in the embedded space. That is, we used word vectors by considering relations of the following form: INLINEFORM2 , where INLINEFORM3 is the cosine similarity score between the words. Only the top cosine similarity scores for a word are utilized.
One difficulty with the KBP task is that very few documents come labeled as gold standard labels, and further annotation is prohibitively expensive beyond a few hundred documents. This is problematic for discriminative learning algorithms, like the RDN learning algorithm, which excel when given a large supervised training corpus. To overcome this obstacle, we employ weak supervision – the use of external knowledge (e.g., a database) to heuristically label examples. Following our work in Soni et al. akbc16, we employ two approaches for generating weakly supervised examples – distant supervision and knowledge-based weak supervision.
Distant supervision entails the use of external knowledge (e.g., a database) to heuristically label examples. Following standard procedure, we use three data sources – Never Ending Language Learner (NELL) BIBREF4 , Wikipedia Infoboxes and Freebase. For a given target relation, we identify relevant database(s), where the entries in the database form entity pairs (e.g., an entry of INLINEFORM0 for a parent database) that will serve as a seed for positive training examples. These pairs must then be mapped to mentions in our corpus – that is, we must find sentences in our corpus that contain both entities together BIBREF5 . This process is done heuristically and is fraught with potential errors and noise BIBREF6 .
An alternative approach, knowledge-based weak supervision is based on previous work BIBREF7 , BIBREF8 with the following insight: labels are typically created by “domain experts” who annotate the labels carefully, and who typically employ some inherent rules in their mind to create examples. For example, when identifying family relationship, we may have an inductive bias towards believing two persons in a sentence with the same last name are related, or that the words “son” or “daughter” are strong indicators of a parent relation. We call this world knowledge as it describes the domain (or the world) of the target relation.
To this effect, we encode the domain expert's knowledge in the form of first-order logic rules with accompanying weights to indicate the expert's confidence. We use the probabilistic logic formalism Markov Logic Networks BIBREF9 to perform inference on unlabeled text (e.g., the TAC KBP corpus). Potential entity pairs from the corpus are queried to the MLN, yielding (weakly-supervised) positive examples. We choose MLNs as they permit domain experts to easily write rules while providing a probabilistic framework that can handle noise, uncertainty, and preferences while simultaneously ranking positive examples.
We use the Tuffy system BIBREF10 to perform inference. The inference algorithm implemented inside Tuffy appears to be robust and scales well to millions of documents.
For the KBP task, some rules that we used are shown in Table TABREF8 . For example, the first rule identifies any number following a person's name and separated by a comma is likely to be the person's age (e.g., “Sharon, 42”). The third and fourth rule provide examples of rules that utilize more textual features; these rules state the appearance of the lemma “mother” or “father” between two persons is indicative of a parent relationship (e.g.,“Malia's father, Barack, introduced her...”).
To answer Q1, we generated positive training examples using the weak supervision techniques specified earlier. Specifically, we evaluated 10 relations as show in Table TABREF20 . Based on experiments from BIBREF8 , we utilized our knowledge-based weak supervision approach to provide positive examples in all but two of our relations. A range of 4 to 8 rules are derived for each relation. Examples for the organization relations INLINEFORM0 and INLINEFORM1 were generated using standard distant supervision techniques – Freebase databases were mapped to INLINEFORM2 while Wikipedia Infoboxes provides entity pairs for INLINEFORM3 . Lastly, only 150 weakly supervised examples were utilized in our experiments (all gold standard examples were utilized). Performing larger runs is part of work in progress.
The results are presented in Table TABREF20 . We compared our standard pipeline (individually learned relations with only standard features) learned on gold standard examples only versus our system learned with weak and gold examples combined. Surprisingly, weak supervision does not seem to help learn better models for inferring relations in most cases. Only two relations – INLINEFORM0 , INLINEFORM1 – see substantial improvements in AUC ROC, while F1 shows improvements for INLINEFORM2 and, INLINEFORM3 , and INLINEFORM4 . We hypothesize that generating more examples will help (some relations produced thousands of examples), but nonetheless find the lack of improved models from even a modest number of examples a surprising result. Alternatively, the number of gold standard examples provided may be sufficient to learn RDN models. Thus Q1 is answered equivocally, but in the negative.
Previous research BIBREF11 has demonstrated that joint inferences of the relations are more effective than considering each relation individually. Consequently, we have considered a formalism that has been successfully used for joint learning and inference from stochastic, noisy, relational data called Relational Dependency Networks (RDNs) BIBREF0 , BIBREF12 . RDNs extend dependency networks (DN) BIBREF13 to the relational setting. The key idea in a DN is to approximate the joint distribution over a set of random variables as a product of their marginal distributions, i.e., INLINEFORM0 INLINEFORM1 INLINEFORM2 . It has been shown that employing Gibbs sampling in the presence of a large amount of data allows this approximation to be particularly effective. Note that, one does not have to explicitly check for acyclicity making these DNs particularly easy to be learned.
In an RDN, typically, each distribution is represented by a relational probability tree (RPT) BIBREF14 . However, following previous work BIBREF12 , we replace the RPT of each distribution with a set of relational regression trees BIBREF15 built in a sequential manner i.e., replace a single tree with a set of gradient boosted trees. This approach has been shown to have state-of-the-art results in learning RDNs and we adapted boosting to learn for relation extraction. Since this method requires negative examples, we created negative examples by considering all possible combinations of entities that are not present in positive example set and sampled twice as many negatives as positive examples.
While most relational learning methods restrict the human to merely annotating the data, we go beyond and request the human for advice. The intuition is that we as humans read certain patterns and use them to deduce the nature of the relation between two entities present in the text. The goal of our work is to capture such mental patterns of the humans as advice to the learning algorithm. We modified the work of Odom et al. odomAIME15,odomAAAI15 to learn RDNs in the presence of advice. The key idea is to explicitly represent advice in calculating gradients. This allows the system to trade-off between data and advice throughout the learning phase, rather than only consider advice in initial iterations. Advice, in particular, become influential in the presence of noisy or less amout of data. A few sample advice rules in English (these are converted to first-order logic format and given as input to our algorithm) are presented in Table TABREF11 . Note that some of the rules are “soft" rules in that they are not true in many situations. Odom et al. odomAAAI15 weigh the effect of the rules against the data and hence allow for partially correct rules.
We now present our experimental evaluation. We considered 14 specific relations from two categories, person and organization from the TAC KBP competition. The relations considered are listed in the left column of Table TABREF13 . We utilize documents from KBP 2014 for training while utilizing documents from the 2015 corpus for testing.
All results presented are obtained from 5 different runs of the train and test sets to provide more robust estimates of accuracy. We consider three standard metrics – area under the ROC curve, F-1 score and the recall at a certain precision. We chose the precision as INLINEFORM0 since the fraction of positive examples to negatives is 1:2 (we sub-sampled the negative examples for the different training sets). Negative examples are re-sampled for each training run. It must be mentioned that not all relations had the same number of hand-annotated (gold standard) examples because the 781 documents that we annotated had different number of instances for these relations. The train/test gold-standard sizes are provided in the table, including weakly supervised examples, if available. Lastly, to control for other factors, the default setting for our experiments is individual learning, standard features, with gold standard examples only (i.e., no weak supervision, word2vec, advice, or advice).
Since our system had different components, we aimed to answer the following questions:
To address our next question, we assessed our pipeline when learning relations independently (i.e., individually) versus learning relations jointly within the RDN, displayed in Table TABREF22 . Recall and F1 are omitted for conciseness – the conclusions are the same across all metrics. Joint learning appears to help in about half of the relations (8/14). Particularly, in person category, joint learning with gold standard outperforms their individual learning counterparts. This is due to the fact that some relations such as parents, spouse, siblings etc. are inter-related and learning them jointly indeed improves performance. Hence Q2 can be answered affirmatively for half the relations.
Table TABREF24 shows the results of experiments comparing the RDN framework with and without word2vec features. word2vec appears to largely have no impact, boosting results in just 4 relations. We hypothesize that this may be due to a limitation in the depth of trees learned. Learning more and/or deeper trees may improve use of word2vec features, and additional work can be done to generate deep features from word vectors. Q3 is answered cautiously in the negative, although future work could lead to improvements.
Table TABREF26 shows the results of experiments that test the use of advice within the joint learning setting. The use of advice improves or matches the performance of using only joint learning. The key impact of advice can be mostly seen in the improvement of recall in several relations. This clearly shows that using human advice patterns allows us to extract more relations effectively making up for noisy or less number of training examples. This is in-line with previously published machine learning literature BIBREF17 , BIBREF18 , BIBREF19 , BIBREF20 in that humans can be more than mere labelers by providing useful advice to learning algorithms that can improve their performance. Thus Q4 can be answered affirmatively.
Relation factory (RF) BIBREF16 is an efficient, open source system for performing relation extraction based on distantly supervised classifiers. It was the top system in the TAC KBP 2013 competition BIBREF21 and thus serves as a suitable baseline for our method. RF is very conservative in its responses, making it very difficult to adjust the precision levels. To be most generous to RF, we present recall for all returned results (i.e., score INLINEFORM0 ). The AUC ROC, recall, and F1 scores of our system against RF are presented in Table TABREF28 .
Our system performs comparably, and often better than the state-of-the-art Relation Factory system. In particular, our method outperforms Relation Factory in AUC ROC across all relations. Recall provides a more mixed picture with both approaches showing some improvements – RDN outperforms in 6 relations while Relation Factory does so in 8. Note that in the instances where RDN provides superior recall, it does so with dramatic improvements (RF often returns 0 positives in these relations). F1 also shows RDN's superior performance, outperforming RF in most relations. Thus, the conclusion for Q5 is that our RDN framework performas comparably, if not better, across all metrics against the state-of-the-art.
We presented our fully relational system utilizing Relational Dependency Networks for the Knowledge Base Population task. We demonstrated RDN's ability to effectively learn the relation extraction task, performing comparably (and often better) than the state-of-art Relation Factory system. Furthermore, we demonstrated the ability of RDNs to incorporate various concepts in a relational framework, including word2vec, human advice, joint learning, and weak supervision. Some surprising results are that weak supervision and word2vec did not significantly improve performance. However, advice is extremely useful thus validating the long-standing results inside the Artificial Intelligence community for the relation extraction task as well. Possible future directions include considering a larger number of relations, deeper features and finally, comparisons with more systems. We believe further work on developing word2vec features and utilizing more weak supervision examples may reveal further insights into how to effectively utilize such features in RDNs.

Figure and table captions:
Fig. 1. Pipeline Full RDN relation extraction pipeline
Table 1. Standard NLP Features Features derived from the training corpus used by our learning system. POS - part of speech. NE - Named Entity. DPR - root of dependency path tree.
Table 2. Rules for KB Weak Supervision A sample of knowledge-based rules for weak supervision. The first value defines a weight, or confidence in the accuracy of the rule. The target relation appears at the end of each clause. “PER”, “ORG”, “NUM” represent entities that are persons, organizations, and numbers, respectively.
Table 3. Advice Rules Sample advice rules used for relation extraction. We employed a total of 72 such rules for our 14 relations.
Fig. 2. Example regression tree for the siblings relation. This tree states that the weight for the relation being true is higher if either “husband” or “wife” appear between the entities.
Table 4. Relations The relations considered from TAC KBP. Columns indicate the number of training examples utilized – both human annotated (Gold) and weakly supervised (WS), when available – from TAC KBP 2014 and number of test examples from TAC KBP 2015. 10 relations describe person entities (per) while the last 4 describe organizations (org).
Table 5. Weak Supervision Results comparing models trained with gold standard examples only (G) and models trained with gold standard and weakly supervised examples combined (G+WS).
Table 6. Joint Learning Results comparing relation models learned individually (IL) and jointly (JL).
Table 8. Advice Results comparing models trained without (-Adv) and with advice (+Adv).
Table 9. RelationFactory (RF) vs RDN Values in bold indicate superiour performance against the alternative approach.

Questions about this paper:
How do they incorporate human advice?

Answers:
by converting human advice to first-order logic format and use as an input to calculate gradient