Information extraction from the web using a search engine Citation for published version (apa)

s
, c
o
}, {r}), with the set of relation instances J non-empty. The identification of
patterns is done in two phases: a collection and an evaluation phase.
In the collecting phase of Ravichandran and Hovy’s algorithm, queries are for-
mulated to identify potential patterns expressing the relation r. Subsequently, the
collected text fragment are evaluated to select the most precise ones. A sketch of
this algorithm is given in Table 3.1.
The algorithm presented is used in a question-answering setting for so-called
factoid questions [Voorhees, 2004]. Using the terminology introduced in the pre-
vious chapter, such questions correspond to functional relations.
We address the issue of extracting patterns, since we observed a number of
drawbacks of Ravichandran and Hovy’s work with respect to the application of
such patterns in a more general information extraction setting.

---

3.1 Identifying Effective Patterns
33
• Ravichandran and Hovy focus only on functional relations. In a general
information extraction setting, we cannot assume that all relations are func-
tional.
• The use of precise patterns can lead to a low recall of relevant search results.
The criterion for selecting patterns, precision, is therefore not the only ba-
sis for a pattern to lead to relevant search results. Although Ravichandran
and Hovy use a threshold to filter out rare phrases, for the more frequently
occurring phrases, precision is the only selection criterion.
• When querying an arbitrary instance, the probability of retrieving sentences
that both contain the unqueried instance as well as one of the predefined
patterns is not very high.
Hence, we propose both different evaluation criteria as well as an adapted
mechanism to collect and evaluate the patterns. We present a domain-independent
method to identify
effective rather than precise patterns representing relations. We
call a pattern effective, if it links many instance-pairs in the snippets found with a
search engine. Hence, the use of an effective pattern should lead to snippets con-
taining instances in the related class with high levels of precision and recall. The
identification of effective patterns is important, since we want to perform as few
queries to a search engine as possible to limit the use of its services.
3.1.1 Problem Description
We are interested to identify effective patterns for a given relation between two
classes. To discover such patterns, we require the set of relation instances J to be
non-empty.
Hence, using the terminology as posed in Chapter 2, we consider an ontology
O with one single relation, i.e. O = ({c
s
, c
o
}, {r}), with J non-empty. Here,
r = (n, c
s
, c
o
, J)). We do not require that c
s
6= c
o
.
The Effective Pattern Extraction Problem. Given is an ontology O with relation
r and a non-empty set of relation instances for r. Identify effective patterns that
express relation r.
2
For example, we consider the classes with names
Author and Book Title and
the relation named
has written. We assume that J contains some relation instances,
e.g. (
Leo Tolstoy, War and Peace) and (G¨unter Grass, Die Blechtrommel). The
aim is then to find natural language phrases that relate authors to the titles of their
books, such as the simple pattern
wrote. Thus, if we query a pattern in combination
with the name of an author (e.g.
Umberto Eco wrote), we want the search results
of this query to contain the books by this author.

---

34
3.1.2 The Effective Pattern Extraction Algorithm
We present an algorithm to identify effective patterns for relations. For reasons of
simplicity we only focus on infix patterns, contrary to the approach by Ravichan-
dran and Hovy. As we are interested in subject – relation – object triplets, we
expect the relation to be expressed in text in between the two instances. There-
fore, the pre- and postfix parts of the patterns are expected to mainly function as
a means to detect the location of instances in the text. We consider this to be a
separate concern and return to this topic in the next section.
From the set J of relation instances we select a set T ⊆ J to identify patterns
from text and a validation set V ⊆ I