Latent Relation Representations for Universal Schemas
Authors: Sebastian Riedel, Limin Yao, Andrew McCallum
ICLR 2013

Abstract: Traditional relation extraction predicts relations within some fixed and finite target schema. Machine learning approaches to this task require either manual annotation or, in the case of distant supervision, existing structured sources of the same schema. The need for existing datasets can be avoided by using a universal schema: the union of all involved schemas (surface form predicates as in OpenIE, and relations in the schemas of pre-existing databases). This schema has an almost unlimited set of relations (due to surface forms), and supports integration with existing structured data (through the relation types of existing databases). To populate a database of such schema we present a family of matrix factorization models that predict affinity between database tuples and relations. We show that this achieves substantially higher accuracy than the traditional classification approach. More importantly, by operating simultaneously on relations observed in text and in pre-existing structured DBs such as Freebase, we are able to reason about unstructured and structured data in mutually-supporting ways. By doing so our approach outperforms state-of-the-art distant supervision systems.

arXiv:1301.4293v2  [cs.LG]  28 Jan 2013
Latent Relation Representations for Universal
Schemas
Sebastian Riedel
Department of Computer Science
University College London
S.Riedel@cs.ucl.ac.uk
Limin Y ao, Andrew McCallum
Department of Computer Science
University of Massachusetts at Amherst
{lmyao,mccallum}@cs.umass.edu
1 Introduction
Supervised relation extraction uses a pre-deﬁned schema of relation types (such as born-in or
employed-by). This approach requires labeling textual relations, a tim e-consuming and difﬁcult
process. This has led to signiﬁcant interest in distantly-s upervised learning. Here one aligns exist-
ing database records with the sentences in which these records have been “rendered”, and from this
labeling one can train a machine learning system as before [1 , 2]. However, this method relies on
the availability of a large database that has the desired schema.
The need for pre-existing databases can be avoided by not hav ing any ﬁxed schema. This is the
approach taken by OpenIE [3]. Here surface patterns between mentions of concepts serve as rela-
tions. This approach requires no supervision and has tremen dous ﬂexibility, but lacks the ability to
generalize. For example, OpenIE may ﬁnd F ERGUSON –historian-at–HARVARD but does not know
FERGUSON –is-a-professor-at–HARVARD.
One way to gain generalization is to cluster textual surface forms that have similar meaning [4, 5,
6, 7]. While the clusters discovered by all these methods usually contain semantically related items,
closer inspection invariably shows that they do not provide reliable implicature. For example, a
cluster may include historian-at, professor-at, scientist-at, worked-at. However, scientist-at does
not necessarily imply professor-at, and worked-at certainly does not imply scientist-at. In fact, we
contend that any relational schema would inherently be brittle and ill-deﬁned––having ambiguities,
problematic boundary cases, and incompleteness.
In response to this problem, we present a new approach: impli cature with universal schemas . Here
we embrace the diversity and ambiguity of original inputs. T his is accomplished by deﬁning our
schema to be the union of all source schemas: original input forms, e.g. variants of surface patterns
similarly to OpenIE, as well as relations in the schemas of pr e-existing structured databases. But
unlike OpenIE, we learn asymmetric implicature among relat ions and entity types. This allows us
to probabilistically “ﬁll in” inferred unobserved entity- entity relations in this union. For example,
after observing FERGUSON –historian-at–HARVARD, our system infers that FERGUSON –professor-
at–HARVARD, but not vice versa.
At the heart of our approach is the hypothesis that we should c oncentrate on predicting source
data––a relatively well deﬁned task that can be evaluated an d optimized––as opposed to modeling
semantic equivalence, which we believe will always be illusive.
To reason with a universal schema, we learn latent feature representations of relations, tuples and en-
tities. These act, through dot products, as natural parameters of a log-linear model for the probability
that a given relation holds for a given tuple. We show experimentally that this approach signiﬁcantly
outperforms a comparable baseline without latent features , and the current state-of-the-art distant
supervision method.
1
2 Model
We use R to denote the set of relations we seek to predict (such as works-written in Freebase, or
the X–heads–Y pattern), and T to denote the set of input tuples. For simplicity we assume ea ch
relation to be binary. Given a relation r ∈ R and a tuple t ∈ T the pair ⟨r, t ⟩ is a fact, or relation
instance. The input to our model is a set of observed facts , an d the observed facts for a given tuple
t := {⟨r, t ⟩ ∈ }.
Our goal is a model that can estimate, for a given relation r (such as X–historian-at–Y) and a given
tuple t (such as <F ERGUSON ,HARVARD>) a score cr,t for the fact ⟨r, t ⟩. This matrix completion
problem is related to collaborative ﬁltering. We can think o f each tuple as a customer, and each
relation as a product. Our goal is to predict how the tuple rates the relation (rating 0 = false, rating 1
= true), based on observed ratings in . We interpret cr,t as the probability p (yr,t = 1) where yr,t is
a binary random variable that is true iff⟨r, t ⟩ holds. To this end we introduce a series of exponential
family models inspired by generalized PCA [8], a probabilis tic generalization of Principle Compo-
nent Analysis. These models will estimate the conﬁdence in ⟨r, t ⟩ using a natural parameter θr,t
and the logistic function: cr,t := p (yr,t |θr,t ) := 1
1+exp(−θr,t) .
We follow[9] and use a ranking based objective function to estimate parameters of our models.
Latent Feature Model One way to deﬁne θr,t is through a latent feature model F. We measure
compatibility between relation r and tuple t as a dot product of two latent feature representations of
size KF: ar for relation r, and vt for tuple t. This gives θF
r,t := ∑ KF
k ar,k vt,k and corresponds to
the original generalized PCA that learns a low-rank factorization of Θ = ( θr,t ).
Neighborhood Model We can interpolate the conﬁdence for a given tuple and relati on based on
the trueness of other similar relations for the same tuple. In Collaborative Filtering this is referred as
a neighborhood-based approach [10]. We implement a neighborhood model N via a set o f weights
wr,r ′ , where each corresponds to a directed association strength between relations r and r′. Sum-
ming these up gives θN
r,t := ∑
r′∈t\{r} wr,r ′ .1
Entity Model Relations have selectional preferences: they allow only ce rtain types in their ar-
gument slots. To capture this observation, we learn a latent entity representation from data. For
each entity e we introduce a latent feature vector te ∈ Rl. In addition, for each relation r and
argument slot i we introduce a feature vector di. Measuring compatibility of an entity tuple and
relation amounts to summing up the compatibilities between each argument slot representation and
the corresponding entity representation: θE
r,t := ∑ arity(r)
i=1
∑ KE
k di,k tti,k .
Combined Models In practice all the above models can capture important aspec ts of the data.
Hence we also use various combinations, such as θN,F,E
r,t := θN
r,t + θF
r,t + θE
r,t .
3 Experiments
Does reasoning jointly across a universal schema help to imp rove over more isolated approaches?
In the following we seek to answer this question empirically.
Data Our experimental setup is roughly equivalent to previous wo rk [2], and hence we omit de-
tails. To summarize, we consider each pair ⟨t1, t 2⟩ of Freebase entities that appear together in a
corpus. Its set of observed facts t correspond to: Extracted surface patterns (in our case lexicalized
dependency paths ) between mentions of t1 and t2, and the relations of t1 and t2 in Freebase. We
divide all our tuples into approximately 200k training tuples, and 200k test tuples. The total number
of relations (patterns and from Freebase) is approximately 4k.
1Notice that the neighborhood model amounts to a collection o f local log-linear classiﬁers, one for each
relation r with weights wr.
2
Predicting Freebase and Surface Pattern Relations For evaluation we use two collections of
relations: Freebase relations and surface patterns. In either case we compare the competing systems
with respect to their ranked results for each relation in the collection.
Our ﬁrst baseline is MI09, a distantly supervised classiﬁer based on the work of [1]. We also
compare against Y A11, a version of MI09 that uses preprocessed pattern cluster features according
to [7]. The third baseline is SU12, the state-of-the-art Mul ti-Instance Multi-Label system by [11].
The remaining systems are our neighborhood model (N), the factorized model (F), their combination
(NF) and the combined model with a latent entity representation (NFE).
The results in terms of mean average precision (with respectto pooled results from each system) are
in the table below:
Relation # MI09 Y A11 SU12 N F NF NFE
Total Freebase 334 0.48 0.52 0.57 0.52 0.66 0.67 0.69
Total Pattern 329 0.28 0.56 0.50 0.46
For Freebase relations, we can see that adding pattern cluster features (and hence incorporating more
data) helps Y A11 to improve over MI09. Likewise, we see that t he factorized model F improves
over N, again learning from unlabeled data. This improvemen t is bigger than the corresponding
change between MI09 and Y A11, possibly indicating that our l atent representations are optimized
directly towards improving prediction performance. Our best model, the combination of N, F and E,
outperforms all other models in terms of total MAP, indicating the power of selectional preferences
learned from data.
MI09, Y A11 and SU12 are designed to predict structured relations, and so we omit them for results
on surface patterns. Look at our models for predicting tuple s of surface patterns. We again see that
learning a latent representation (F, NF and NFE models) from additional data helps substantially
over the non-latent N model.
All our models are fast to train. The slowest model trains in j ust 30 minutes. By contrast, training
the topic model in Y A11 alone takes 4 hours. Training SU12 tak es two hours (on less data). Also
notice that our models not only learn to predict Freebase relations, but also approximately 4k surface
pattern relations.
4 Conclusion
We represent relations using universal schemas. Such schemas contain surface patterns as relations,
as well as relations from structured sources. We can predict missing tuples for surface pattern rela-
tions and structured schema relations. We show this experimentally by contrasting a series of popular
weakly supervised models to our collaborative ﬁltering mod els that learn latent feature representa-
tions across surface patterns and structured relations. Mo reover, our models are computationally
efﬁcient, requiring less time than comparable methods, while learning more relations.
Reasoning with universal schemas is not merely a tool for inf ormation extraction. It can also serve
as a framework for various data integration tasks, for example, schema matching. In future work we
also plan to integrate universal entity types and attributes into the model.
References
[1] Mike Mintz, Steven Bills, Rion Snow, and Daniel Jurafsky . 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 Conferenc e on Natural Language Process-
ing of the AFNLP (ACL ’09) , pages 1003–1011. Association for Computational Linguist ics,
2009.
[2] Sebastian Riedel, Limin Yao, and Andrew McCallum. Model ing relations and their mentions
without labeled text. In Proceedings of the European Conference on Machine Learning and
Knowledge Discovery in Databases (ECML PKDD ’10) , 2010.
[3] Oren Etzioni, Michele Banko, Stephen Soderland, and Dan iel S. Weld. Open information
extraction from the web. Commun. ACM , 51(12):68–74, 2008.
3
[4] Dekang Lin and Patrick Pantel. DIRT - discovery of infere nce rules from text. In Knowledge
Discovery and Data Mining , pages 323–328, 2001.
[5] Patrick Pantel, Rahul Bhagat, Bonaventura Coppola, Tim othy Chklovski, and Eduard Hovy.
ISP: Learning Inferential Selectional Preferences. In Proceedings of NAACL HLT , 2007.
[6] Alexander Yates and Oren Etzioni. Unsupervised methods for determining object and relation
synonyms on the web. Journal of Artiﬁcial Intelligence Research , 34:255–296, 2009.
[7] Limin Yao, Aria Haghighi, Sebastian Riedel, and Andrew M cCallum. Structured relation
discovery using generative models. In Proceedings of the Conference on Empirical methods
in natural language processing (EMNLP ’11) , July 2011.
[8] Michael Collins, Sanjoy Dasgupta, and Robert E. Schapir e. A generalization of principal
component analysis to the exponential family. In Proceedings of NIPS , 2001.
[9] Steffen Rendle, Christoph Freudenthaler, Zeno Gantner , and Lars Schmidt-Thieme. Bpr:
Bayesian personalized ranking from implicit feedback. In Proceedings of UAI , 2009.
[10] Yehuda Koren. Factorization meets the neighborhood: a multifaceted collaborative ﬁltering
model. In Proceedings of the 14th ACM SIGKDD international conferenc e on Knowledge
discovery and data mining , KDD ’08, pages 426–434, New York, NY , USA, 2008. ACM.
[11] Mihai Surdeanu, Julie Tibshirani, Ramesh Nallapati, a nd Christopher D. Manning. Multi-
instance multi-label learning for relation extraction. In Proceedings of EMNLP-CoNLL , 2012.
4


Peer review:
[Review]:
The paper studies techniques for inferring a model of entities and relations capable of performing basic types of semantic inference (e.g., predicting if a specific relation holds for a given pair of entities).  The models exploit different types of embeddings  of entities and relations.

The topic of the paper is interesting and the contribution seems quite sufficient for a workshop paper. It should motivate an interesting discussion on how these models can be generalized to be applied to more complex datasets and semantic tasks (e.g.,  inferring these representation from natural language texts), and, in general,  on representation induction methods for semantic tasks. 

The only concern I have about this paper is that it does not seem to properly cite much of the previous work on related subjects.  Though it mentions techniques for clustering semantically similar expressions, it seems to suggest that there has not been much work on inducing, e.g., subsumptions. However,  there has been a lot of  previous research on learning entailment (aka inference) rules (e.g.,  Chkolvsky and Pantel 2004; Berant et al, ACL 2011;  Nakashole et al, ACL 2012). Even more importantly, some of the very related work on embedding relations is not mentioned, e.g.,  Bordes et al (AAAI 2011), or, very closely related,  Jenatton et al (NIPS 2012).  However, these omissions may be understandable given the short format of the paper. 

Pros:
--  Interesting topics
--  Fairly convincing experimental results
Cons:
--  Previous work on embedding relations is not discussed.