We present an end-to-end (live) demonstration system called DeepDive that performs knowledge-base construction (KBC) from hundreds of millions of web pages. DeepDive employs statistical learning and inference to combine diverse data resources and best-of-breed algorithms. A key challenge of this approach is scalability, i.e., how to deal with terabytes of imperfect data e ciently. We describe how we address the scalability challenges to achieve web-scale KBC and the lessons we have learned from building DeepDive.
Knowledge-base construction (KBC) is the process of
populating a knowledge base (KB) with facts (or assertions)
extracted from text. It has recently received tremendous
interest from academia, e.g., CMU's NELL [
Similar to YAGO [
VLDS’12 August 31, 2012. Istanbul, Turkey.
Copyright c 2012 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. linguistic features such as named-entity mentions and dependency paths3 from terabytes of text; and (2) DeepDive performs web-scale statistical learning and inference using classic data-management and optimization techniques.
Figure 2 depicts the current architecture of DeepDive. To populate a knowledge base, DeepDive rst converts diverse input data (e.g., raw corpora and ontologies) into relational features using standard NLP tools and custom code. These features are then used to train statistical models representing the correlations between linguistic patterns and target relations. Finally, DeepDive combines the trained statistical models with additional knowledge (e.g., domain knowledge) into a Markov logic program that is then used to transform the relational features (e.g., candidate entity mentions and linguistic patterns) into a knowledge base with entities, relationships, and their provenance.
Given the amount of data and depth of processing, a key challenge is scaling feature extraction (see Figure 2). For example, while deep linguistic features such as dependency paths are useful for relationship extraction, it takes about 100K CPU hours for our NLP pipeline to nish processing ClueWeb09. Although we have access to a 100-node Hadoop cluster, we found that the throughput of Hadoop is often limited by pathological data chunks that take very long to process or even crash (due to Hadoop's no-task-leftbehind failure model). Fortunately, thanks to the Condor infrastructure4, we were able to nish feature extraction on ClueWeb09 within a week by opportunistically assigning jobs on hundreds of workstations and shared cluster machines using a best-e ort failure model.
A second scalability challenge is statistical learning and
inference. There are two aspects of scalability with
statistical learning: scale of training examples and scale of
performance. To scale up the amount of training examples for
KBC, we employ the distant supervision technique [
our con dence in a rule); this allows one to capture rules
that are likely, but not certain, to be correct. A Markov logic
program (aka Markov logic network, or simply MLN)
species what (evidence) data are available, what predictions to
make, and what constraints and correlations there are [
In addition to statistical learning and inference, we have found debugging and tuning based on the output of a KBC system to be an e ective method to improve KBC quality. To support systematic debugging and tuning, it is important that the underlying statistical models are well-calibrated, i.e., predictions with probability around p should have an actual accuracy around p as well. Such calibration is an integral part of the development process of DeepDive.
We describe the DeepDive architecture in Section 2 and some implementation details in Section 3. We summarize the lessons we have learned from DeepDive as follows: Inference and Learning. Statistical inference and learning were bottlenecks when we rst started DeepDive, but we can now scale them with data-management and optimization techniques.
Feature Extraction. Good features are a key bottleneck for KBC; with a scalable inference and learning infrastructure in place, we can now focus on gathering and tuning features for DeepDive.
Debugging and Tuning. Developing KBC systems is an iterative process; systematic debugging and tuning requires well-calibrated statistical models.
We rst describe a simple KBC model that we use in DeepDive, and then brie y discuss the infrastructure that
enables web-scale KBC in DeepDive, namely how we scale
up web-scale feature extration, machine learning for KBC,
and statistical inference in Markov logic, respectively.
A Conceptual KBC Model. DeepDive adopts the
classic Entity-Relationship (ER) model [
Relationship tables Ri 2 R.
Note that Ri can be derived from ME and MRi . By the same token, ME and MRi provide provenance that connects the KB back to the documents supporting each fact. The process of populating ME is called entity linking; the process of populating MRi is called relation extraction. Intuitively, the goal is to produce an instance J of these tables that is as large as possible (high recall) and as correct as possible (high precision). As shown in Figure 4, DeepDive populates the target KB based on signals from mention-level features (over text spans, e.g., positions, contained words, and matched regular expressions) and entity-level features (over the target KB, e.g., age, gender, and alias). 7For simplicity, we assume that all entities are known, but DeepDive supports generating novel entities for the KB as well (e.g., by clustering \dangling" mentions).
Wikipedia 3M En77es Web Search 100M Results
Freebase … 3M Facts
NLP Tools, Custom Code
Features
Candidate Men7ons:
En77es: 25B Rela7onships: 8B
Markov Logic
Program Sta+s+cal Inference
KB En77es, Rela7onships,
Proven ance
Scaling Feature Extraction at Web Scale. To scale
DeepDive to web-scale KBC tasks, we employ high-throughput
parallel computing frameworks such as Hadoop8 and
Condor for feature extraction. We use the Hadoop File System
for storage, but found a 100-node MapReduce cluster to be
insu cient for ClueWeb: (1) Hadoop's all-or-nothing
approach to failure handling hinders throughput, and (2) the
number of cluster machines for Hadoop is limited.
Fortunately, the Condor infrastructure supports a best-e ort
failure model, i.e., a job may nish successfully even when
Condor fails to process a small portion of the input data.
Moreover, Condor allows us to simultaneously leverage thousands
of machines from across a department, an entire campus, or
even the nation-wide Open Science Grid.9
Scaling Machine Learning for KBC. Traditional KBC
systems rely on manual annotations or domain-speci c rules
provided by experts, both of which are scarce resources.
To remedy these problems, recent years have seen
interest in the distant supervision approach for relation
extraction [
Scaling Statistical Inference in Markov Logic. To scale
up statistical inference in Markov logic, DeepDive employs
the Tuffy [
0.40
Precision ll,,rcFae1oR iirscePno 000...321000 F1 Recall 0.00 1.E+02 1.E+03 1.E+04 1.E+05 1.E+06 1.E+07 1.E+08
Corpus size ing step that essentially performs relational operations, and a search (or sampling) step that often comprises multiple independent subproblems. Thus, Tuffy achieves orders of magnitude speed-up in grounding (compared to Alchemy) by translating grounding into SQL statements that are executed by an RDBMS. Moreover, Tuffy performs graph partitioning at the search step to achieve scalability in inference and (serendipitously) improved quality. Felix is based on the observation that an MLN program (especially those for KBC) often contains routine subtasks such as classi cation and coreference resolution; these subtasks have specialized algorithms with high e ciency and quality. Thus, instead of solving a whole MLN with generic inference algorithms, Felix splits the program into multiple parts and solves subtasks with corresponding specialized algorithms. To resolve possible con icts between predictions from di erent tasks, Felix employs the classic dual decomposition technique. 3. IMPLEMENTATION DETAILS
A key tenet of DeepDive is that statistical learning and inference enables one to build high-quality KBC systems (see Figure 1) by combining diverse resources. We brie y describe more technical details of DeepDive to conceretely demonstrate the advantage of this approach.
Entity Linking. Recall that entity linking is the task of mapping a textual mention to a real-world entity. We run the state-of-the-art StanfordNER (Named Entity RecogniPERSON • Bill Clinton • Bill Gates • Steve Jobs • Barack Obama • … ORGANIZATION • Google Inc. • Microso; Corp. • United States • YouTube • …
Corpus EnJty MenJons
Mr. Gates was the CEO of Microso;. Google acquired Youtube in 2006. … Rela9onships FoundedBy Company
Founder …
RelaJonship MenJons Mr. Gates • “Mr.” is a male personal Jtle • “Gates” is a common name … En9ty-‐level Features Bill Gates • is a male person • is very frequently menJoned • aka William Gates III … tion)12 to extract textual mentions and corresponding entity types. DeepDive then tries to map each mention to a Wikipedia entry using the following signals: string matching, Wikipedia redirects and inter-page anchor text, Google and Bing search results that link to Wikipedia pages, entity type compatibility between StanfordNER and Freebase, person-name coreference based on heuristics and proximity, etc. We write a couple dozen MLN rules for these data resources and then train the rule weights using the entitylinking training data from TAC-KBP. Our entity-linking component achieves an F1 score of 0.80 on the TAC-KBP benchmark (human performance is around 0.90). As shown in Figure 1, DeepDive also solicits user feedback on the entity types; we plan to integrate such feedback into the statistical inference process.
Relation Extraction. The relation-extraction models in
DeepDive are trained using the methods described in Zhang
et al. [
We presented DeepDive, an end-to-end demonstration system that performs knowledge-base construction from the web. DeepDive demonstrates that a promising approach to KBC is to integrate diverse data resources and best-of-breed algorithms via statistical learning and inference. We discussed the key lessons we have learned from building DeepDive { including feature extraction, statistical learning and inference, and systematic debugging { and hope that they are of value to other researchers.
We gratefully acknowledge the support of DARPA grant FA875009-C-0181. CR is also generously supported by NSF CAREER award IIS-1054009, ONR award N000141210041, and gifts or research awards from Google, Greenplum, Johnson Controls, Inc., LogicBlox, and Oracle. We thank the generous support from the Center for High Throughput Computing and Miron Livny's Condor research group. Any opinions, ndings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily re ect the view of the above companies, DARPA, or the US government.