Stephen Soderland

IJCAI Conference 2011 Conference Paper

Open Information Extraction: The Second Generation

• Oren Etzioni
• Anthony Fader
• Janara Christensen
• Stephen Soderland
• Mausam

How do we scale information extraction to the massive size and unprecedented heterogeneity of the Web corpus? Beginning in 2003, our KnowItAll project has sought to extract high-quality knowledge from the Web. In 2007, we introduced the Open Information Extraction (Open IE) paradigm which eschews handlabeled training examples, and avoids domain-specific verbs and nouns, to develop unlexicalized, domain-independent extractors that scale to the Web corpus. Open IE systems have extracted billions of assertions as the basis for both common-sense knowledge and novel question-answering systems. This paper describes the second generation of Open IE systems, which rely on a novel model of how relations and their arguments are expressed in English sentences to double precision/recall compared with previous systems such as TEXTRUNNER and WOE.

AIJ Journal 2010 Journal Article

Analysis of a probabilistic model of redundancy in unsupervised information extraction

• Doug Downey
• Oren Etzioni
• Stephen Soderland

Unsupervised Information Extraction (UIE) is the task of extracting knowledge from text without the use of hand-labeled training examples. Because UIE systems do not require human intervention, they can recursively discover new relations, attributes, and instances in a scalable manner. When applied to massive corpora such as the Web, UIE systems present an approach to a primary challenge in artificial intelligence: the automatic accumulation of massive bodies of knowledge. A fundamental problem for a UIE system is assessing the probability that its extracted information is correct. In massive corpora such as the Web, the same extraction is found repeatedly in different documents. How does this redundancy impact the probability of correctness? We present a combinatorial “balls-and-urns” model, called Urns, that computes the impact of sample size, redundancy, and corroboration from multiple distinct extraction rules on the probability that an extraction is correct. We describe methods for estimating Urns's parameters in practice and demonstrate experimentally that for UIE the model's log likelihoods are 15 times better, on average, than those obtained by methods used in previous work. We illustrate the generality of the redundancy model by detailing multiple applications beyond UIE in which Urns has been effective. We also provide a theoretical foundation for Urns's performance, including a theorem showing that PAC Learnability in Urns is guaranteed without hand-labeled data, under certain assumptions.

AAAI Conference 2010 Conference Paper

Panlingual Lexical Translation via Probabilistic Inference

• Mausam
• Stephen Soderland
• Oren Etzioni

The bare minimum lexical resource required to translate between a pair of languages is a translation dictionary. Unfortunately, dictionaries exist only between a tiny fraction of the 49 million possible language-pairs making machine translation virtually impossible between most of the languages. This paper summarizes the last four years of our research motivated by the vision of panlingual communication. Our research comprises three key steps. First, we compile over 630 freely available dictionaries over the Web and convert this data into a single representation – the translation graph. Second, we build several inference algorithms that infer translations between word pairs even when no dictionary lists them as translations. Finally, we run our inference procedure offline to construct PANDICTIONARY– a sense-distinguished, massively multilingual dictionary that has translations in more than 1000 languages. Our experiments assess the quality of this dictionary and find that we have 4 times as many translations at a high precision of 0. 9 compared to the English Wiktionary, which is the lexical resource closest to PANDIC- TIONARY.

AIJ Journal 2010 Journal Article

Panlingual lexical translation via probabilistic inference

• Mausam
• Stephen Soderland
• Oren Etzioni
• Daniel S. Weld
• Kobi Reiter
• Michael Skinner
• Marcus Sammer
• Jeff Bilmes

This paper introduces a novel approach to the task of lexical translation between languages for which no translation dictionaries are available. We build a massive translation graph, automatically constructed from over 630 machine-readable dictionaries and Wiktionaries. In this graph each node denotes a word in some language and each edge ( v i, v j ) denotes a word sense shared by v i and v j. Our current graph contains over 10, 000, 000 nodes and expresses more than 60, 000, 000 pairwise translations. The composition of multiple translation dictionaries leads to a transitive inference problem: if word A translates to word B which in turn translates to word C, what is the probability that C is a translation of A? The paper describes a series of probabilistic inference algorithms that solve this problem at varying precision and recall levels. All algorithms enable us to quantify our confidence in a translation derived from the graph, and thus trade precision for recall. We compile the results of our best inference algorithm to yield PanDictionary, a novel multilingual dictionary. PanDictionary contains more than four times as many translations as in the largest Wiktionary at precision 0. 90 and over 200, 000, 000 pairwise translations in over 200, 000 language pairs at precision 0. 8.

IJCAI Conference 2007 Conference Paper

• Michele Banko
• Michael J Cafarella
• Stephen Soderland
• Matt Broadhead
• Oren Etzioni

Traditionally, Information Extraction (IE) has focused on satisfying precise, narrow, pre-specified requests from small homogeneous corpora (e. g. , extract the location and time of seminars from a set of announcements). Shifting to a new domain requires the user to name the target relations and to manually create new extraction rules or hand-tag new training examples. This manual labor scales linearly with the number of target relations. This paper introduces Open IE (OIE), a new extraction paradigm where the system makes a single data-driven pass over its corpus and extracts a large set of relational tuples without requiring any human input. The paper also introduces TextRunner, a fully implemented, highly scalable OIE system where the tuples are assigned a probability and indexed to support efficient extraction and exploration via user queries. We report on experiments over a 9, 000, 000 Web page corpus that compare TextRunner with KnowItAll, a state-of-the-art Web IE system. TextRunner achieves an error reduction of 33% on a comparable set of extractions. Furthermore, in the amount of time it takes KnowItAll to perform extraction for a handful of pre-specified relations, TextRunner extracts a far broader set of facts reflecting orders of magnitude more relations, discovered on the fly. We report statistics on TextRunner's 11, 000, 000 highest probability tuples, and show that they contain over 1, 000, 000 concrete facts and over 6, 500, 000 more abstract assertions.

AIJ Journal 2005 Journal Article

Unsupervised named-entity extraction from the Web: An experimental study

• Oren Etzioni
• Michael Cafarella
• Doug Downey
• Ana-Maria Popescu
• Tal Shaked
• Stephen Soderland
• Daniel S. Weld
• Alexander Yates

The KnowItAll system aims to automate the tedious process of extracting large collections of facts (e. g. , names of scientists or politicians) from the Web in an unsupervised, domain-independent, and scalable manner. The paper presents an overview of KnowItAll's novel architecture and design principles, emphasizing its distinctive ability to extract information without any hand-labeled training examples. In its first major run, KnowItAll extracted over 50, 000 class instances, but suggested a challenge: How can we improve KnowItAll's recall and extraction rate without sacrificing precision? This paper presents three distinct ways to address this challenge and evaluates their performance. Pattern Learning learns domain-specific extraction rules, which enable additional extractions. Subclass Extraction automatically identifies sub-classes in order to boost recall (e. g. , “chemist” and “biologist” are identified as sub-classes of “scientist”). List Extraction locates lists of class instances, learns a “wrapper” for each list, and extracts elements of each list. Since each method bootstraps from KnowItAll's domain-independent methods, the methods also obviate hand-labeled training examples. The paper reports on experiments, focused on building lists of named entities, that measure the relative efficacy of each method and demonstrate their synergy. In concert, our methods gave KnowItAll a 4-fold to 8-fold increase in recall at precision of 0. 90, and discovered over 10, 000 cities missing from the Tipster Gazetteer.

AAAI Conference 1994 Conference Paper

Corpus-Driven Knowledge Acquisition for Discourse Analysis

• Stephen Soderland

The availability of large on-line text corpora provides a natural and promising bridge between the worlds of natural language processing (NLP) and machine learning (ML). In recent years, the NLP community has been aggressively investigating statistical techniques to drive part-of-speech taggers, but application-specific text corpora can be used to drive knowledge acquisition at much higher levels as well. In this paper we will show how ML techniques can be used to support knowledge acquisition for information extraction systems. It is often very difficult to specify an explicit domain model for many information extraction applications, and it is always labor intensive to implement hand-coded heuristics for each new domain. We have discovered that it is nevertheless possible to use ML algorithms in order to capture knowledge that is only implicitly present in a representative text corpus. Our work addresses issues traditionally associated with discourse analysis and intersentential inference generation, and demonstrates the utility of ML algorithms at this higher level of language analysis. The benefits of our work address the portability and scalability of information extraction (IE) technologies. When hand-coded heuristics are used to manage discourse analysis in an information extraction system, months of programming effort are easily needed to port a successful IE system to a new domain. We will show how ML algorithms can reduce this development time to a few days of automated corpus analysis without any resulting degradation of overall system performance.