Banko 2007 Open Information Extraction from the Web

Citation

Banko, M., Cafarella, M., Soderland, S., Broadhead, M. and Etzioni, O. 2007. Open Information Extraction from the Web. In Proceedings of IJCAI.

Online version

An online version of this paper is available at [1].

Summary

This paper introduces a novel approach to iteratively extract information from the web in the open domains, it also presents TextRunner, a large-scale open information extraction system with its current results and statistics.

Key Contributions

The biggest contribution claimed by the authors in this paper is the new paradigm of open information extraction which does not require any human input, it makes a single run through the data and generates large set of relational tuples. Another contribution of this paper is the analysis of TextRunner system and its current results.

Algorithms

• Pattern, Relations and the Duality

The authors first presents the problem of pattern extraction with target relations. Then the author shows a test problem of extracting (author, book-title) pairs and explain the patterns in details. The author gives an observation of the duality between the two, in such that given a good set of patterns, we can build a good set of tuples for the target relation and we also have the converse property - given a good set of tuples, we can build a good set of patterns.

• The DIPRE (Dual Iterative Pattern Relation Extraction) Algorithm

The algorithm is proposed for extracting relations using the pattern relation duality. The detail is as follows:

1. R' <- Sample

Start a small sample, R' of the target relation. This sample is given by the user and can be very small. In the tests of author and titles, the author uses a list of five books with authors.

2. O <- FindOccurrences(R';D)

Then, find all occurrences of tuples of R' in D. Along with the tuple found, keep the context of every occurrence (url and surrounding text).

3. P <- GenPatterns(O)

Generate patterns based on the set of occurrences. As mentioned by the author, this routine must generate patterns for sets of occurrences with similar context. The patterns need to have a low error rate, so it is important that they are not overly general. The higher the coverage of the patterns the better. However, a low coverage can be compensated for with a larger database.

4. R' <- MD(P)

Search the database for tuples matching any of the patterns.

5. If R' is large enough, return. Else go to step 2.

Experiments and Evaluation

The author uses a repository of 24 million web pages, which is part of the Stanford WebBase and is used for Google Search Engine as of 1998. The author also mentions an exclusion of the amazon pages due to crawling difficulty. The experiments start with only five books as the seed and a simple pattern, it grows with considerably fast-pace, although there are some bogus and it seems to be getting a lot of sci-fiction books as the author mentioned. At the final iteration, it has over 15,000 unique book titles.

The author chose a small set of output for manual verification. And it turns out that 19 out of 20 are correct with only one exception which refers to an article instead of a book. It also shows that many of the books are not in the Amazon list or other catalogs, which tells the power of information extraction over the web.