A Survey of Distant Supervision Methods using PGMs
Gagan Madan
2013ME10015
Indian Institue of Technology Delhi
gaganm.me113@mech.iitd.ac.in

arXiv:1705.03751v1 [cs.AI] 10 May 2017

Abstract
Relation Extraction refers to the task of
populating a database with tuples of the
form r(e1 , e2 ), where r is a relation
and e1 , e2 are entities. Distant supervision is one such technique which tries to
automatically generate training examples
based on an existing KB such as Freebase. This paper is a survey of some of the
techniques in distant supervision which
primarily rely on Probabilistic Graphical
Models (PGMs).

1

Introduction

In the recent years, there has been an explosion of
information on the web. As the size of data available continues to expand rapidly, this provides an
interesting challenge as well as an opportunity to
researchers in NLP. While managing such large
amounts of data, and distilling the relevant information in a form that is manageable is a challenge,
the large amount of data available provides an opportunity to do this.
One possible way to manage such
large amounts of data is to populate
a database with tuples of the form
relation<entity1, entity2>,
extracted from text. Examples of such tuples
could be capital-of(Delhi, India),
PrimeMinister(Narendra Modi, India).
This simple representation is particularly useful,
as it allows answering queries on the text directly
about a given relation, and entities. To extract tuples of this form is the key objective of Relational
Extraction. Relational Extraction is a particularly
well studied problem in the NLP domain, with
many varied existing approaches to this problem.
Most of the approaches can be classified as follows:

1. Bootstrapping Methods: These methods start
with a small set of “seed” tuples, and iteratively generate patterns from the seed tuples,
recognize more tuples to be utilized as seed
tuples, thus bootstrapping into the complete
relation table. This was introduced for the
first time in DIPRE (Brin, 1998), and later
extended in Snowball (Agichtein and Gravano, 2000). Bootstrapping methods typically suffer from semantic drift, and often
have poor precision as the number of iterations increases.
2. Supervised Methods: These methods treat
the task of relational extraction as a supervised learning problem, and rely on the availability of extensive training data for extracting relations. Due to the reliance on training data, these methods usually extract tuples only from some given relations. Some
interesting approaches in this domain have
used tree kernels built on dependency parse
trees (Culotta and Sorensen, 2004), training
semi-CRFs (Sarawagi et al., 2004), and using shortest path tree kernels (Bunescu and
Mooney, 2005).
3. Open Domain IE Methods: This is a selfsupervised learning model, which utilises no
training data, but relies on redundancy of information present in the corpus. This outputs a collection of all possible tuples of the
form (e1 , r, e2 ) where e1 , e2 are two entities
related through a phrase r. The current stateof-the-art system in OpenIE is Open IE 4.0,
which is a further improvement on Reverb
(Fader et al., 2011) and Ollie (Schmitz et al.,
2012).
4. Distant Supervision: This technique automatically generates training examples and

tries to learn features based on target relational tables in a Knowledge Base (KB). Typically, large KBs such as Freebase are used
for this. This technique usually does not require any human intervention. This technique was originally introduced in the context
of biological KBs (Craven et al., 1999), but
has been successfully extended to any texts
(Mintz et al., 2009).

performed on Wikipedia, NY Times corpus and
more recently on the 2010 and 2011 KBP shared
tasks (Ji et al., 2010; Owczarzak and Dang, 2011).
Some features of the datasets are:
1. Yeast Protein Database(YPD) (Hodges et al.,
1999), PubMed, MEDLINE: The work by
(Craven et al., 1999) primarily uses the YPD
database, which includes facts about various proteins as well as links to PubMed articles that establish the fact. Further, they use
MEDLINE, a database of bibliographic information and abstracts for over nine million
articles in biomedical domain for evaluation
of their model.

5. Deep Learning Based Methods: These techniques are relatively new and utilize the
word embeddings generated by word2vec
(Mikolov et al., 2013). One of the most
successful atttempts in this domain, (Zeng
et al., 2014) uses Convolution Neural Networks (CNNs) for relational extraction.

2. Freebase-Wikipedia: This dataset is a dump
of all Wikipedia articles which have been
sentence tokenized by Metaweb Technologies, the developers of Freebase. This is the
main dataset used by (Mintz et al., 2009) for
Distant Supervision.

While a major focus currently in NLP is on deep
learning techniques, as KBs become better with
time, it makes sense to focus on techniques that
can leverage the power of KBs. With this in mind,
it makes sense to focus on Distant Supervision,
a technique which requires minimal human intervention and is primarily based on utilising large
scale KBs such as Freebase.

2

Problem Definition

We define the task of distant supervision formally
in the notation given by (Min et al., 2013):
Given a knowledge base (KB), D, a set of relations
R, the KB D contains tuples of the form r(e1 , e2 ),
where r ∈ R, and e1 and e2 are entities known to
be related by the relation r. Further, we are given
a corpus, C, which contains natural language text.
The task in Distant Supervision is to align the corpus C with the KB D, i.e. to automatically generate training examples for relational extraction by
labelling relational mentions in C with relations in
D. Formally, this requires labelling set of entity
mentions (e1 , e2 ) present in C with some r ∈ R or
OT HER. Most works treat the OT HER class
as negative training examples.

3
3.1

3. NY Times: This dataset was developed by
(Riedel et al., 2010) by aligning Freebase relations with the NY Times dataset. They use
StanfordNER to find relevant entity mentions
in the text.

Datasets and Knowledge Bases
Datasets

Some of the earliest work in Distant Supervision
was motivated by research in the biomedical domain. Therefore, the first model by (Craven et al.,
1999) primarily relied on database from medical sources. Subsequently, evaluations have been

4. KBP: This dataset was primarily used for
evaluation by (Surdeanu et al., 2012). The
training relations here are a were generated
from the 2010 and 2011 KBP shared tasks
(Ji et al., 2010; Owczarzak and Dang, 2011),
which is a subset of Wikipedia Infoboxes
from 2008.
3.2

Knowledge Bases

Most Distant Supervision approaches typically use
Freebase (Bollacker et al., 2008) as the KB for the
task. Freebase is a publicly available database of
semantic data. It contains relations from various
sources, primarily from Wikipedia text boxes. It
has around 9 million entities and around 7300 relations. Some of the largest relations are shown in
Table 1.

4

Distant Supervision using PGMs

In this section, we describe the various models
proposed for Distant Supervision using Probabilistic Graphical Models (PGMs). We begin our discussion with the simplest model, based on a Naive
Bayes classifier, and move to models using more
complicated PGMs.

Table 1: 10 largest Freebase relations (Mintz et al., 2009)
Relation name
Size
Example
/people/person/nationality
281107 John Dugard, South Africa
/location/location/contains
253223 Belgium, Nijlen
/people/person/profession
208888 Dusa McDuff, Mathematician
/people/person/place of birth
105799 Edwin Hubble, Marshfield
/dining/restaurant/cuisine
86213
MacAyos Mexican Kitchen, Mexican
/business/business chain/location
66529
Apple Inc., Apple Inc., South Park, NC
/biology/organism classification rank 42806
Scorpaeniformes, Order
/film/film/genre
40658
Where the Sidewalk Ends, Film noir
/film/film/language
31103
Enter the Phoenix, Cantonese
4.1

Distant Supervision in Biomedical
Domain (Craven et al., 1999)

This paper was the first attempt at using an existing database to generate training examples from
a text corpus. While the model itself was very
simple, it was in many ways ahead of its time.
Since there were no large scale general knowledge
databases available around that time, while this
model was used successfully in domain specific
contexts such as genetics (Jenssen et al., 2001), it
wasn’t until when large scale KBs such as Freebase became available that this technique started
becoming relevant.
The paper considers the task of extracting relations of the type subcellular-localization(Protein,
Subcellular-Structure), which represent the various subcellular structures in which proteins may
be present. The authors first construct a labelled
set of instances which contain the target relation.
This is done by selecting six proteins and querying them in MEDLINE, which is a corpus of abstracts of biomedical journals. The abstracts are
then hand-annotated with instances of the target
relation, subcellular-localization. This resulted in
a total of 33 instances of the target relation. This is
used to train a Naive Bayes classifier, and later for
evaluating the Distant Supervision trained model.
The Distant Supervision model, the authors
consider the Yeast Protein Database (Hodges et al.,
1999), which includes a subcellular-localization
field for many proteins, as well as a hyperlink to
the reference article in PubMed. Each of these entries, along with the reference is used as a weakkly
learned instance for relation extraction. After
cleaning up the dataset, the authors generate a set
of 336 relational instances described in 633 sentences. The sentences that do not mention the relational instance are treated as negative training ex-

Figure 1: Naive Bayes Model (Pham and Ruz,
2009)

amples.
The Figure 1 shows the simple Naive Bayes
model.
Given a document d of n words,
(w1 , w2 , · · · , wn ), the probability that the document belongs to the class cj ∈ C is given by:
P (cj |d) =

P (cj )Πni=1 P (wi |cj )
P (d)

(1)

In this case, there are only two classes, positive and negative, denoting whether the relation is
present or not. In order to test whether r(x, y) is
a valid relation, all sentences containing both the
entities x and y are considered. Further, two approaches are considered. In the first approach, for
each sentence, if the predicted class is positive, the
extracted relation is returned, else no relation is returned. In the second approach, for each relation a
confidence is calculated as follows:
conf idence = 1−ΠN
k=1 [1−P (c = positive|sk )]
(2)
where sk is the kth sentence that contains both the
entities x and y. If the cconfidence is above a
threshold, the relation is predicted as positive, and
otherwise negative. The authors further evaluate
the trained model on the MEDLINE dataset, and
observe an increase in performance as compared

to the Naive Bayes model trained on the MEDLINE dataset, with cross-validation.
They further add parse tree based features as
well to their model, and learn the features through
an algorithm similar to FOIL. This leads to a further increase in the accuracy of the model.
While this model itself is very simple, one of the
key contributions of this paper was the novel idea
of generating training data through distant supervision and then using the generated data to learn
features.
4.2

Distant Supervision using Freebase
(Mintz et al., 2009)

This paper describes the key idea of Distant Supervision in a domain independent setting, and uses
Freebase as the KB for distant supervision.
The key assumption is that if two entities participate in a relation, a sentence that contains
mentions of both the entities, should express the
relation.
The intuition behind this approach is to generate a training set of entity pairs that participate in
a given set of relations. Entities are tagged with
NER tools in the training step and if a sentence
contains two entities known to be an instance of
some Freebase relation, features are extracted and
added to the feature vector for that relation. However, since sentences could possibly express incorrect relations, a multiclass logistic regression
is trained to learn weights on the noisy extracted
features.
At the time of testing, given a sentence, entities are identified using NER tools, and every pair
of entities that appear together is considered a potential relation. For each entity pairs, features are
extracted and the regression classifier predicts a
relation name for every entity pair based on the
extracted features.
The lexical features extracted are:
• Sequence of words between entities
• POS tags of these words
• A flag indicating the order of appearance
• A window of k words to the left of entity 1
• A window of k words to the right of entity 2
The syntactic features are extracted by building a
dependency parse tree. The features are:

• Dependency path between entities
• A window node for each entity: A window
node is a node connected to one of the entities, but is not in the dependency path.
All the features in the classifier are used in conjunction. For two features to match, all the subfeatures should match. This is done in order to have
high precision features at the cost of low recall.
It is shown that this algorithm is able to extract
high precision patterns for a large number of relations, while the held out evaluation shows that
combination of lexical and syntactic features performs the best.
4.3

Multi Instance Learning (MIL) (Riedel
et al., 2010)

This paper argues that the key assumption in
current Distant Supervision tecniques, that each
sentence which mentions the two related entities
is an expression of the given relation is too strong
and leads to noisy patterns that hurts the precision.
This paper relaxes this assumption to:
If two entities participate in a relation, at least
one sentence that mentions these two entities
might express that relation.
While this assumption is clearly better, it comes
with additional complexity in both testing and
training. The paper further suggests a undirected
graphical model, which addresses both the tasks of
predicting relation between entities and predicting
which sentences express this relation.
The Figure 2 (Riedel et al., 2010) shows an instance for the Factor Graph model. Consider the
example shown in the figure. The KB contains
the relation founded(Roger McNamee, Elevation
Partners). Consider the sentence “Elevation Partners , the 1.9 billion private equity group that was
founded by Roger McNamee ...”. This sentence
contains mentions of both the entities, as well as
expresses the correct relation. Now consider the
sentence “Roger McNamee , a managing director at Elevation Partners , ...”. While this sentence
does contain mentions of both the entities, it does
not express the correct relation.
The model uses two types of hidden variables.
Given a pair of entities, S and D, that appear together in at least sentence, a variable Y denotes
the relation between them if it exists and N A otherwise. In Figure 2, Y is set to f ounded. Further,
for the ith sentence that mentions both the entities, the authors define a boolean relation mention

Figure 2: Factor Graph Model (Riedel et al., 2010)

The feature φjoin
denotes whether the feature φm
j
j
is active for any of the relation mentions which are
correct w.r.t Y .
Inference in this setting is primarily performed
by Gibbs sampling. Learning on the other hand
is done by SampleRank, which is a ranked based
learning framework. Since each step of inference
is usually the bottleneck in learning, SampleRank
has been shown to be efficient in training for
models in which inference is intractable.
Q
Φr (y)Φjoin (y, z, x) i Φm (zi , xi )
P (Y = y, Z = z|x) =
Zx
(3)
Finally, in this setting, an error reduction of
where Φr denotes the bias of the model towards a
31% is observed in the NY Times dataset.
relation type y, and is defined as Φr = exp(θyr ).
The function Φm is defined as a function over xi
4.4 MultiR (Hoffmann et al., 2011)
as:
One of the issues in the model by (Riedel et al.,
variable Zi , which is true iff the ith sentence is indeed mentioning the relation Y . The entity mentions in the ith sentence are refered to as Si and
Di respectively. Additional information about the
ith sentence is stored in the observed variable xi .
This is collected across all sentences that mention
the entities to get the vector x. Further, Z is used
to denote the state of all mention candidates. The
conditional distribution is given by:

Φm (zi , xi ) = exp(

X

θjm φm
j (zi , xi ))

(4)

j

The feature functions φm
j (zi , xi ) are those defined
above as lexical and syntactic features, while the
factor Φj oin(y, z, x) is defined as:
Φjoin (y, z, x) = exp(

X join join

θj,y φj

(z, x)) (5)

j

where φjoin
(z, x) is defined as:
j
φjoin
(z, x) = 1if f ∃i : zi = 1&φm
j (zi , xi ) = 1
j
(6)

2010) is that it does not allow relations to overlap,
i.e. for any pair of entities e1 and e2 , there cannot
exist two facts r(e1 , e2 ) and q(e1 , e2 ). This paper
firther relaxes this assumption by constructing a
graphical model as shown in Figure 3.
The other obvious change is in the conditional
extraction model, which is now given by:
P (Y = y, Z = z|x) =
Y
1 Y join r
(7)
Φ
(y , z)
Φextract (zi , xi )
Zx r
i
where the functions are the same as those defined
above.

Figure 3: (a) Plate model of the network (b) an example network for entities Steve Jobs, Apple (Hoffmann
et al., 2011)

Figure 4: MIML plate model (Surdeanu et al.,
2012)

Learning in this setting is done based on approximations which lead to Perceptron-style additive parameter updates (Collins, 2002). The
first approximation is to do online learning instead
of the full optimization. The second approximation is to replace expectations with maximizations
(Viterbi approximation).
It was experimentally shown that this model has
a better precision and recall as compared to the
model proposed by (Riedel et al., 2010).
4.5

Multi-Instance Multi-Label (MIML)
(Surdeanu et al., 2012)

This paper also tries to relax the assumption that
each relations between entities can overlap. The
plate model is shown in Figure 4. The model structure is very similar to that proposed by (Hoffmann
et al., 2011), however training is done by Expectation Maximization (EM). In the E step, latent mention labels are assigned using the current model

Figure 5: MIML-semi plate model (Min et al.,
2013)

and in the M step, the model is retrained to maximize the log likelihood of the data using the current assignments.
It was observed that while this model performs
better than the one proposed by (Riedel et al.,
2010), it does not perform as good as (Hoffmann
et al., 2011), especially around extremities. The
authors however claim that this model is more stable as it yields a smoother curve.
4.6

MIML-semi (Min et al., 2013)

This paper builds on the work by (Surdeanu et al.,
2012) and shows that due to the incomplete nature
of KBs, a significant number of negative examples
generated are actually false negatives. They correct this problem by modelling the bag-level noise
caused by incomplete KBs, in addition to modelling instance level noise using the MIML model.
The plate diagram is shown in Figure 5. The input
to the model is a list of n bags with labels Positive (P) or unlabelled (U) for each relation r. The
model adds another set of latent variables, l, which
models the true bag level labels, to combine the la-

Table 2: Summary of Distant Supervision Techniques
Key Assumptions/
Model
Contributions
If r(e1 , e2 ) ∈ KB,
Distant
then ∀ s such that
4.2
Supervision
e1 , e2 ∈ sentences,
s expresses the relation r
If r(e1 , e2 ) ∈ KB,
Multi Instance ∃ s such that
4.3
Learning
e1 , e2 ∈ sentences, and
s expresses the relation r
Allows overlapping
4.4 MultiR
relations for entities
Allows overlapping
4.5 MIML
relations for entities
Addresses false negatives
generated due to
4.6 MIML-semi
incomplete KB
bels y and the MIML layers. Training is done by
an EM algorithm similar to that proposed by (Surdeanu et al., 2012).
This model achieves a better performance than
both MIML as well as MultiR on the KBP dataset.
Another interesting approach in modelling
missing data is presented in (Ritter et al., 2013),
which could not be studied due to lack of time.
An interesting aspect of Distant Supervision was
also presented in (Bunescu and Mooney, 2007),
which primarily addresses the task of Multi Instance Learning as a supervised learning problem,
solved by SVMs. A summary of the distant supervision techniques along with their key contributions is presented in Table 2.

5

Conclusions

Relation Extraction is a particularly well studied
problem in the NLP domain. In this paper, we focussed on one of the technique of Distant Supervision, which utilises a large Knowledge Base, such
as Freebase to generate training examples for relational extraction. We reviewed some of the models
in Distant Supervision, and presented a summary
of some of the key contributions of each model.

References
Eugene Agichtein and Luis Gravano. 2000. Snowball: Extracting relations from large plain-text collections. In Proceedings of the fifth ACM conference
on Digital libraries. ACM.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim
Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM
SIGMOD international conference on Management
of data. AcM.
Sergey Brin. 1998. Extracting patterns and relations from the world wide web. In International
Workshop on The World Wide Web and Databases.
Springer.
Razvan Bunescu and Raymond Mooney. 2007. Learning to extract relations from the web using minimal
supervision. In ACL.
Razvan C Bunescu and Raymond J Mooney. 2005. A
shortest path dependency kernel for relation extraction. In Proceedings of the conference on human
language technology and empirical methods in natural language processing. Association for Computational Linguistics.
Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings
of the ACL-02 conference on Empirical methods in
natural language processing-Volume 10. Association for Computational Linguistics.
Mark Craven, Johan Kumlien, et al. 1999. Constructing biological knowledge bases by extracting information from text sources. In ISMB.
Aron Culotta and Jeffrey Sorensen. 2004. Dependency
tree kernels for relation extraction. In ACL. Association for Computational Linguistics.
Anthony Fader, Stephen Soderland, and Oren Etzioni.
2011. Identifying relations for open information extraction. In EMNLP. Association for Computational
Linguistics.
Peter E Hodges, Andrew HZ McKee, Brian P Davis,
William E Payne, and James I Garrels. 1999. The
yeast proteome database (ypd): a model for the organization and presentation of genome-wide functional data. Nucleic Acids Research .
Raphael Hoffmann, Congle Zhang, Xiao Ling, Luke
Zettlemoyer, and Daniel S Weld. 2011. Knowledgebased weak supervision for information extraction
of overlapping relations. In Proceedings of the 49th
Annual Meeting of the Association for Computational Linguistics: Human Language TechnologiesVolume 1. Association for Computational Linguistics.

Tor-Kristian Jenssen, Astrid Lægreid, Jan Komorowski, and Eivind Hovig. 2001. A literature network of human genes for high-throughput analysis
of gene expression. Nature genetics .
Heng Ji, Ralph Grishman, Hoa Trang Dang, Kira Griffitt, and Joe Ellis. 2010. Overview of the tac 2010
knowledge base population track. In Third Text
Analysis Conference (TAC 2010).
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In NIPS.
Bonan Min, Ralph Grishman, Li Wan, Chang Wang,
and David Gondek. 2013. Distant supervision for
relation extraction with an incomplete knowledge
base. In HLT-NAACL. pages 777–782.
Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. 2009. Distant supervision for relation extraction without labeled data. In Proceedings of
the Joint Conference of the 47th Annual Meeting of
the ACL and the 4th International Joint Conference
on Natural Language Processing of the AFNLP:
Volume 2-Volume 2. Association for Computational
Linguistics.
Karolina Owczarzak and Hoa Trang Dang. 2011.
Overview of the tac 2011 summarization track:
Guided task and aesop task. In Proceedings of the
Text Analysis Conference (TAC 2011), Gaithersburg,
Maryland, USA, November.
Duc Truong Pham and Gonzalo A Ruz. 2009. Unsupervised training of bayesian networks for data
clustering. In Proceedings of the Royal Society of
London A: Mathematical, Physical and Engineering
Sciences. The Royal Society.
Sebastian Riedel, Limin Yao, and Andrew McCallum.
2010. Modeling relations and their mentions without labeled text. In Joint European Conference
on Machine Learning and Knowledge Discovery in
Databases. Springer.
Alan Ritter, Luke Zettlemoyer, Oren Etzioni, et al.
2013. Modeling missing data in distant supervision
for information extraction. Transactions of the Association for Computational Linguistics .
Sunita Sarawagi, William W Cohen, et al. 2004. Semimarkov conditional random fields for information
extraction. In NIPS.
Michael Schmitz, Robert Bart, Stephen Soderland,
Oren Etzioni, et al. 2012. Open language learning for information extraction. In Proceedings of
the 2012 Joint Conference on Empirical Methods
in Natural Language Processing and Computational
Natural Language Learning. Association for Computational Linguistics.

Mihai Surdeanu, Julie Tibshirani, Ramesh Nallapati,
and Christopher D Manning. 2012. Multi-instance
multi-label learning for relation extraction. In Proceedings of the 2012 joint conference on empirical
methods in natural language processing and computational natural language learning. Association for
Computational Linguistics.
Daojian Zeng, Kang Liu, Siwei Lai, Guangyou Zhou,
Jun Zhao, et al. 2014. Relation classification via
convolutional deep neural network. In COLING.

