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

j
}, /0) with c
j
= (n, I, b). We now can rewrite the
problem into a relation instantiation problem for incomplete classes, by creating a
new class c
j
with the name of class c
j
as the only instance. A relation r
k
is intro-
duced to express the original inhabits (or is-a) relation between the instances and
the class itself. That is, O = ({c
j
, c
i
}, r) with c
j
= (n
0
, I, b), c
j
= (n
00
, {n}, true) and
r = (is a, c
j
, c
i
, true, J), with J = {(a, b)|b = n ∧ a ∈ I
j
}.
Without loss of generality we can thus focus on an approach to solve the in-
complete relation instantiation problem here. We will focus on the identification of
statements containing a subject – relation – object triplets.
A common approach in web information extraction is to formulate queries con-
sisting of all pairs of the names of known instances of the subject and object classes.
The number of hits is used by Cilibrasi and Vitanyi [2007] to compute a distance
between instances, while Mika creates a network of related instances in a similar
fashion [Mika, 2007]. Knees et al. [2004] use the total number of search results
(i.e. the numbers of
hits) of queries with two instances to classify musical artists.
Gligorov et al. [2007] use the number of hits of combinations of instances from two
separate ontologies as a distance measure used in ontology mapping. De Boer et
al. [2006] use combinations of names of art styles and periods to create a mapping
between the two.
Hence, if we are interested in the relation named
was born in and the subject
class c
s
containing the instance
John F. Kennedy, we can combine this instance with
all instances in object class c
o
into queries. The search results are then processed in
some fashion to identify evidence for the
was born in relation between the queried
instances.
Although this approach is a straightforward method to collect relevant texts on
the web, we observe the following drawbacks.

---

26
•
Large number of queries. This approach leads to |I
s
| · |I
o
| queries and has
therefore in general no Google complexity linear in the total number of in-
stances.
•
Not generally applicable. As such an approach assumes the classes to be
complete, it cannot be used to solve the general ontology population problem
for incomplete classes.
•
No solution for relation identification. The co-occurrence of two instances
in a document does not necessarily reflect the intended relation. Hence, ei-
ther the query needs to be more specific [Cimiano & Staab, 2004] or the
documents need to be processed [Knees et al., 2004].
As an alternative, we formulate queries containing
one known instance. Such
an approach would lead to a Google complexity linear in the number of instances in
O
0
, if we formulate a constant number of queries per instance. Having formulated
a query containing an instance, the texts retrieved by the search engine are to be
processed to recognize an instance of the other class and evidence for the relation
between the two.
A very simple language model. The web as a corpus – and especially the collec-
tion of snippets returned by a search engine – is multi-lingual and contains typo’s,
broken sentences, slang, jokes, and other irregularities. As no representative an-
notations or reliable tools are available for such data, we choose to opt for a very
simple language model to identify instances and their relations.
We focus on sentences where the instances of the subject and object class are
related by a small text fragment. We ignore the rest of the context. Given a relation