Proceedings of the ACL-IJCNLP 2009 Conference Short Papers, pages 57–60,
Suntec, Singapore, 4 August 2009.
c
2009 ACL and AFNLP
A Framework for Entailed Relation Recognition
Dan Roth Mark Sammons V.G.Vinod Vydiswaran
University of Illinois at Urbana-Champaign
{danr|mssammon|vgvinodv}@illinois.edu
Abstract
We define the problem of recognizing entailed re-
lations – given an open set of relations, find all oc-
currences of the relations of interest in a given doc-
ument set – and pose it as a challenge to scalable
information extraction and retrieval. Existing ap-
proaches to relation recognition do not address well
problems with an open set of relations and a need
for high recall: supervised methods are not eas-
ily scaled, while unsupervised and semi-supervised
methods address a limited aspect of the problem, as
they are restricted to frequent, explicit, highly lo-
calized patterns. We argue that textual entailment
(TE) is necessary to solve such problems, propose
a scalable TE architecture, and provide preliminary
results on an Entailed Relation Recognition task.
1 Introduction
In many information foraging tasks, there is a need
to find all text snippets relevant to a target concept.
Patent search services spend significant resources
looking for prior art relevant to a specified patent
claim. Before subpoenaed documents are used in
a court case or intelligence data is declassified, all

2 Entailed Relation Recognition (ERR)
In the task of Entailed Relation Recognition, a cor-
pus and an information need are specified. The
corpus comprises all text spans (e.g. paragraphs)
contained in a set of documents. The information
need is expressed as a set of tuples encoding rela-
tions and entities of interest, where entities can be
of arbitrary type. The objective is to retrieve all
relevant text spans that a human would recognize
as containing a relation of interest. For example:
Information Need: An organization acquires weapons.
Text 1: the recent theft of 500 assault rifles by FARC
Text 2: the report on FARC activities made three main ob-
servations. First, their allies supplied them with the 3” mor-
tars used in recent operations. Second,
Text 3: Amnesty International objected to the use of artillery
to drive FARC militants from heavily populated areas.
An automated system should identify Texts 1 and
2 as containing the relation of interest, and Text 3
as irrelevant. The system must therefore detect
relation instances that cross sentence boundaries
(“them” maps to “FARC”, Text 2), and that re-
quire inference (“theft” implies “acquire”, Text 1).
It must also discern when sentence structure pre-
cludes a match (“Amnesty International use
artillery” does not imply “Amnesty International
57
acquires artillery”, Text 3).
The problems posed by instances like Text 2
are beyond the scope of traditional unsuper-

stance suffices to complete the QA task, but does
not meet the needs of the task outlined here.
Recognizing relation instances requiring infer-
ence steps, in the absence of labeled training data,
requires a level of text understanding. A suit-
able proxy for this would be a successful Textual
Entailment Recognition (TE) system. (Dagan et
al., 2006) define the task of Recognizing Textual
Entailment (RTE) as: a directional relation be-
tween two text fragments, termed T – the entailing
text, and H – the entailed text. T entails H if, typ-
ically, a human reading T would infer that H is
most likely true. For relation recognition, the rela-
tion triple (e.g. “Organization acquires weapon”)
is the hypothesis, and a candidate text span that
might contain the relation is the text. The def-
inition of RTE clearly accommodates the range
of phenomena described for the examples above.
However, the more successful TE systems (e.g.
(Hickl and Bensley, 2007)) are typically resource
intensive, and cannot scale to large retrieval tasks
if a brute force approach is used.
We define the task of Entailed Relation Recog-
nition thus: Given a text collection D, and an in-
formation need specified in a set of [argument, re-
lation, argument] triples S: for each triple s ∈ S,
identify all texts d ∈ D such that d entails s.
The information need triples, or queries, encode
relations between arbitrary entities (specifically,
these are not constrained to be Named Entities).

cision, as it filters irrelevant texts.
3.1 Implementation of SERR
In the ELR stage, we use a structured query that
allows more precise search and differential query
expansion for each query element. Semantic units
in the texts (e.g. Named Entities, phrasal verbs)
are indexed separately from words; each index is
58
SERR Algorithm
SETUP:
Input: Text set D
Output: Indices {I} over D
for all texts d ∈ D
Annotate d with local semantic content
Build Search Indices {I} over D
APPLICATION:
Input: Information need S
EXPANDED LEXICAL RETRIEVAL (ELR)(s):
R ← ∅
Expand s with semantically similar words
Build search query q
s
from s
R ← k top-ranked texts for q
s
using indices {I}
return R
SERR:
Answer set A ← ∅
for all queries s ∈ S

sentation. The former is constrained to select a
single predicate-argument structure from each re-
sult, which is compared to the query component-
by-component using similarity measures similar to
the LexPlus system. PTE-relaxed drops the single-
predicate constraint, and can be thought of as a
‘bag-of-constituents’ model. In both, features are
extracted based on the predicate-argument compo-
nents’ match scores and their connecting structure,
and the rank assigned by ELR. These features are
used by a classifier that labels each result as ‘rel-
evant’ or ‘irrelevant’. Training examples are se-
lected from the top 7 results returned by ELR for
queries corresponding to entailment pair hypothe-
ses from the RTE development corpora; test exam-
ples are similarly selected from results for queries
from the RTE test corpora (see section 3.2).
3.2 Entailed Relation Recognition Corpus
To assess performance on the ERR task, we de-
rive a corpus from the publicly available RTE
data. The corpus consists of a set S of informa-
tion needs in the form of [argument, relation, argu-
ment] triples, and a set D of text spans (short para-
graphs), half of which entail one or more s ∈ S
while the other half are unrelated to S. D com-
prises all 1, 950 Texts from the IE and IR sub-
tasks of the RTE Challenge 1–3 datasets. The
shorter hypotheses in these examples allow us to
automatically induce their structured query form
from their shallow semantic structure. S was au-

Table 2. Comparison of performance of SERR with
different TE algorithms. Numbers in parentheses are
standard deviations.
Table 1 compares the results of SERR with and
59
# System RTE 1 RTE 2 RTE 3 Avg. Acc.
LexPlus 49.0 65.2 [3] 76.5 [2] 66.3
PTE-relaxed 54.5 (1.0) 68.7 (1.5) [3] 82.3 (2.0) [1] 71.2 (1.2)
PTE-strict 64.8 (2.3) [1] 71.2 (2.6) [3] 76.0 (3.2) [2] 71.8 (2.6)
Table 3. Performance (accuracy) of SERR system variants on RTE challenge
examples; numbers in parentheses are standard deviations, while numbers in
brackets indicate where systems would have ranked in the RTE evaluations.
Comparisons
Standard TE 3,802,500
SERR 13,650
Table 4. Entailment compar-
isons needed for standard TE
vs. SERR
without the ELR’s semantic enhancements. For
each rank k, the entries represent the proportion of
queries for which the correct answer was returned
in the top k positions. The semantic enhancements
improve the number of matched results at each of
the top 3 positions.
Table 2 compares variants of the SERR imple-
mentation. The baseline labels every result re-
turned by ELR as ‘relevant’, giving high recall
but low precision. PTE-relaxed performs better
than baseline, but poorly compared to PTE-strict
and LexPlus. Our analysis shows that LexPlus

tailed Relation Recognition task, based on Tex-
tual Entailment, and implemented a solution that
shows that a Textual Entailment Recognition sys-
tem can be scaled to a much larger IE problem
than that represented by the RTE challenges. Our
preliminary results demonstrate the utility of the
proposed architecture, which allows strong perfor-
mance in the RTE task and efficient application to
a large corpus (table 4).
Acknowledgments
We thank Quang Do, Yuancheng Tu, and Kevin
Small. This work is funded by a grant from Boeing
and by MIAS, a DHS-IDS Center for Multimodal
Information Access and Synthesis at UIUC.
References
[Banko and Etzioni2008] M. Banko and O. Etzioni. 2008.
The Tradeoffs Between Open and Traditional Relation Ex-
traction. In ACL-HLT, pages 28–36.
[Culotta and Sorensen2004] A. Culotta and J. Sorensen.
2004. Dependency Tree Kernels for Relation Extraction.
In ACL, pages 423–429.
[Dagan et al.2006] I. Dagan, O. Glickman, and B. Magnini,
editors. 2006. The PASCAL Recognising Textual Entail-
ment Challenge., volume 3944. Springer-Verlag, Berlin.
[Fellbaum1998] C. Fellbaum. 1998. WordNet: An Electronic
Lexical Database. MIT Press.
[Harabagiu and Hickl2006] S. Harabagiu and A. Hickl. 2006.
Methods for Using Textual Entailment in Open-Domain
Question Answering. In ACL, pages 905–912.
[Hickl and Bensley2007] A. Hickl and J. Bensley. 2007. A