PaperlayerView exact revision on arXiv

Source-linked AI summary

Incremental Knowledge Base Construction Using DeepDive

Jaeho Shin, Sen Wu, Feiran Wang, Christopher De Sa, Ce Zhang, Christopher Ré

arXiv:1502.00731v4cs.DBcs.CLcs.LG

TL;DR

KBC seeks to populate structured databases from unstructured information while supporting iterative changes to data and programs. DeepDive combines database and machine-learning techniques with sampling- and variational-based incremental inference, and its evaluation reports two-orders-of-magnitude performance improvements while keeping quality high.

  • Problem

    KBC requires efficiently improving structured-data quality as engineers repeatedly change data sources, rules, and application concepts.

  • Method

    DeepDive uses incremental grounding with delta rules and frames incremental maintenance as approximate inference that handles program and data changes together.

  • Results

    Two orders of magnitude: DeepDive improved system performance in five real KBC scenarios while keeping quality high.

  • Takeaways & Limitations

    DeepDive provides an end-to-end KBC framework that supports pay-as-you-go refinement and incremental processing across the development loop.

  • Takeaways & Limitations

    Complete materialization requires exponential space and time in the number of factor-graph variables, making it infeasible for even moderately sized graphs.

Abstract

from arXiv · show

Populating a database with unstructured information is a long-standing problem in industry and research that encompasses problems of extraction, cleaning, and integration. Recent names used for this problem include dealing with dark data and knowledge base construction (KBC). In this work, we describe DeepDive, a system that combines database and machine learning ideas to help develop KBC systems, and we present techniques to make the KBC process more efficient. We observe that the KBC process is iterative, and we develop techniques to incrementally produce inference results for KBC systems. We propose two methods for incremental inference, based respectively on sampling and variational techniques. We also study the tradeoff space of these methods and develop a simple rule-based optimizer. DeepDive includes all of these contributions, and we evaluate DeepDive on five KBC systems, showing that it can speed up KBC inference tasks by up to two orders of magnitude with negligible impact on quality.

1. INTRODUCTION

DeepDive treats KBC as an iterative process in which changing data, rules, and concepts requires efficient incremental maintenance. It combines database and machine-learning techniques for grounding and approximate inference, with experiments showing substantial speedups while maintaining quality.

  • KBC systems ingest massive unstructured document collections and aim to produce high-quality structured data, with quality assessed by precision and recall.
  • DeepDive combines a SQL-based declarative language with Markov Logic semantics for building knowledge base construction systems.
  • Grounding converts SQL-query results into a factor graph, while inference computes calibrated marginal probabilities for database tuples.
  • Incremental Grounding: Incremental grounding uses delta rules to update SQL-derived outputs after input changes, yielding up to 360× speedup in KBC systems.
  • Incremental Inference: The sampling and variational approaches vary by factor-graph size, correlation sparsity, and expected future changes; neither dominates, motivating a rule-based optimizer.
  • Experimental Evaluation Highlights: 22× faster incremental execution was observed across six snapshots compared with rerunning the systems from scratch.

Related Work

Prior work spans rule-based, declarative, and machine-learning approaches to KBC, including incremental maintenance for some restricted graphical models. DeepDive instead addresses incremental statistical inference for the more general factor graphs arising in KBC.

  • KBC research has progressed from pattern matching and rule-based systems toward machine-learning systems, while also improving individual system components.
  • Declarative information-extraction systems use view-maintenance techniques for incremental execution but do not maintain statistical inference and learning results incrementally.
  • Earlier incremental-inference methods target tree-structured or low-degree graphical models, whereas DeepDive handles more general KBC factor graphs.
  • The running KBC example extracts linguistic patterns from news articles and uses them as classifier features for identifying married pairs.

2. KBC USING DEEPDIVE

DeepDive is an end-to-end, declarative framework for building KBC systems from heterogeneous data, combining relational database and probabilistic modeling ideas. It supports iterative development through integrated extraction, inference, error analysis, and design choices for semantics and feature modeling.

  • The DeepDive Framework: DeepDive builds KBC systems from unstructured, semi-structured, and structured data into a relational database of extracted facts.The pipeline may include extraction, cleaning, and integration.
  • Candidate Generation and Feature Extraction: Candidate generation uses SQL queries, while feature extractors associate linguistic and other features with possible mentions, entities, and relations.Documents are stored with NLP preprocessing, and candidate mappings produce possible database objects.
  • Discussion of Design Choices: DeepDive extends Markov Logic with user-defined functions and weight tying, allowing feature extraction code and shared model weights within declarative programs.Weight tying lets factors share weights across rules, while user-defined functions support regular expressions and scripts.
  • Error Analysis: The KBC workflow produces marginal probabilities for candidate facts, which users can threshold and inspect during iterative error analysis.A common selection threshold is p > 0.95, after which users inspect mistakes and repeat the process.
  • Semantics of a DeepDive Program: The semantics function g changes how rule grounding counts affect weights, with linear, ratio, and logical choices supporting different application assumptions.For |Up| = 10^6 and |Down| = 10^6 − 100, linear semantics yields a probability close to 1, whereas ratio semantics yields approximately 0.5 and logical semantics exactly 0.5.
  • Semantics of a DeepDive Program: DeepDive explicitly constructs factor graphs from SQL queries, with tuples represented as Boolean random variables and rule groundings represented as factors.Inference operates on the resulting factor graph using statistical techniques.

3. INCREMENTAL KBC

DeepDive incrementally maintains KBC systems by updating grounding results and approximating inference over changed factor graphs. Sampling and variational materialization expose different tradeoffs, so an optimizer selects between them based on workload conditions.

  • Incremental Grounding: Incremental grounding applies delta rules and incremental view maintenance to produce modified variables ∆V and factors ∆F from program or data changes.DeepDive updates relational derivations and then generates the changed portion of the factor graph for inference.
  • Incremental Inference: Incremental inference treats the changed factor graph as an approximate-inference problem and operates on materialized information from the original distribution.The inference phase consumes stored materialization together with modified variables ∆V and factors ∆F.
  • Sampling Approach: Sampling stores sampled possible worlds and uses Metropolis-Hastings to converge to the updated distribution, but efficiency depends on the acceptance rate and available samples.If stored samples are exhausted, the method generates fresh samples or uses another evaluation method.
  • Variational Approach: The variational approach learns a sparser approximate factor graph using a log-determinant relaxation with an ℓ1 penalty, then runs inference directly on the updated approximation.Its execution time is roughly linear in the sparsity of the approximated graph, while λ controls the sparsity-quality tradeoff.
  • Tradeoffs: For graphs larger than 20 variables, complete materialization is significantly slower than sampling or variational methods because its cost is exponential in graph size.Complete materialization stores probabilities for every possible world, requiring exponential space and time.
  • Tradeoffs: Neither incremental strategy dominates: sampling can be over two orders of magnitude faster at high acceptance rates, whereas variational inference can be more than 5× faster at 0.1% acceptance.For sparse original graphs, variational inference can be 11× faster; for dense graphs, it can be more than 7× slower than sampling.

4. EXPERIMENTS

Experiments on five KBC systems show that incremental maintenance substantially reduces development and update time while preserving high-quality outputs. Benefits vary with workload structure, and combining sampling with variational materialization improves performance.

  • Quality Over Time: 22× faster incremental execution reached the same News quality as rerunning from scratch, achieving F1 0.36 in at most 30 minutes per run.Rerun required approximately 6 hours per run, whereas Incremental required at most 30 minutes.
  • Quality Over Time: At most 4% of facts differed in probability by more than 0.05 between Incremental and Rerun, supporting similar debugging behavior.High-confidence Rerun facts appeared in Incremental and vice versa at a 99% overlap level.
  • Efficiency of Evaluating Updates: Incremental grounding achieved up to 360× speedup for feature extraction and grounding using classical incremental materialization techniques.The paper attributes this gain to standard relational database management system techniques.
  • Efficiency of Evaluating Updates: Incremental inference produced 7× to 112× speedups across News rule categories, with approximately 10× speedups for feature extraction, supervision, and inference rules.Analysis rule A1 achieved the highest speedup because its updated distribution was unchanged and sampling had a 100% acceptance rate.
  • Efficiency of Evaluating Updates: Pharmacogenomics rule I1 achieved only 3× speedup because it introduced many factors, making the updated graph 1.4× larger than the original.The additional factors made incremental evaluation expensive.
  • Materialization Time: A one-time 12-hour materialization cost for 2,000 samples was amortized across successive updates in each of the five systems.Most of the cost came from collecting twice as many samples as a single Rerun.
  • Tradeoff and Optimizer: Disabling either sampling or variational materialization slowed News execution compared with the full system.The lesion studies tested each strategy while leaving the remaining components unchanged.
  • Tradeoff and Optimizer: Using different materialization strategies for different variable groups improved performance over a baseline that selected sampling before switching to variational inference.The baseline was stronger than fixing one strategy for all groups.

5. CONCLUSION

The paper presents DeepDive as a declarative KBC framework that combines SQL-based incremental processing with approximate inference. Across five real KBC scenarios, these techniques improved execution time by two orders of magnitude while maintaining quality suitable for development.

  • 5. CONCLUSION: DeepDive combines a declarative KBC language with SQL-based incremental processing and a tradeoff space of approximate inference techniques.The framework addresses changes to both KBC programs and data.
  • 5. CONCLUSION: Two orders of magnitude of performance improvement were achieved in five real KBC scenarios while quality remained high enough to support development.The conclusion attributes the result to approximate inference techniques applied to changing programs and data.

A. ADDITIONALTHEORETICALDETAILS

The paper reports that its three sampling semantics—Linear, Logical, and Ratio—affect convergence speed.

  • A. ADDITIONALTHEORETICALDETAILS: Linear, Logical, and Ratio semantics have an impact on the convergence speed of the sampling procedure.The paper describes these findings in Section A.1 and provides a proof in Section A.2.

A.1 Convergence Results

The convergence analysis studies Gibbs sampling under several semantics and program families, combining experiments with upper and lower bounds. It finds that semantics and program structure materially affect convergence, with polynomial-time guarantees for important hierarchical cases.

  • Types of Programs: The analysis considers voting and hierarchical programs, allowing weighted tuples, evidence variables, and weights independent of the number of variables.These program families are motivated by KBC applications.
  • Convergence Bounds: For voting programs with Logical semantics, τ(n)=O(n log n), with convergence within ε after τ(n) log(1+ε^-1) steps.The bounds are supported using coupling and a generalized coupon-collector analysis.
  • Convergence Experiments: Figure 13 varies |U|+|D| with |U|=|D| and measures time to approach Q’s correct marginal probability within 1%.All variables are non-evidence variables in this experiment.
  • Convergence Experiments: Linear semantics converges much more slowly than Ratio or Logical semantics in the voting-program experiment.The experiment shows that semantic choice affects Gibbs-sampling performance.
  • Convergence Bounds: Hierarchical programs with non-overlapping bodies converge in O(N log N log(1+ε^-1)) time under Logical or Ratio semantics.N denotes the number of factors; the result concerns sampling guarantees rather than exact evaluation.
  • Scope of Guarantees: The convergence guarantees coexist with computational hardness: evaluating hierarchical programs is #P-hard, and simple non-hierarchical programs can require exponential Gibbs-sampling time.The paper provides no dichotomy theorem and guarantees sampling rather than exact evaluation.
  • Asymptotic Analysis: Hierarchical programs converge in polynomial time under Logical semantics as domain size grows.The analysis attributes this to the absence of variables with influence on the final result that grows with N.

A.2 Proofs of Convergence Rates

The convergence proofs use coupling arguments to bound total variation distance for voting under different projection semantics. Logical and ratio semantics converge in O(n log n), whereas linear semantics require exponential time.

  • Coupling bounds total variation distance by comparing a Gibbs sampler with a process initialized at the stationary distribution.The correlated-flip coupler uses shared random inputs and samples the same variable in both chains.
  • O(n log n) steps suffice for voting with logical or ratio projection semantics under bounded weights and linear-sized U and D.The upper bound holds for any ε > 0 after τ(n) log(ε^-1) steps, with τ(n) = O(n log n).
  • O(n log n) steps are necessary for logical or ratio semantics because convergence requires sampling all variables.The lower bound follows from the coupon collector’s problem.
  • 2^O(n) steps suffice for voting with linear projection semantics when variable weights are bounded independently of n.The upper bound gives τ(n) = 2^O(n) for achieving total variation distance at most ε.
  • 2^O(n) steps are necessary for linear projection semantics in the voting example.A sampler can remain exponentially long in a state where Q is included, keeping its distribution far from stationarity.

B.1 Decomposition with Inactive Variables

DeepDive decomposes factor graphs around active variables so inactive-variable groups can be materialized independently. Because optimal grouping is NP-hard, it uses a greedy merging heuristic, with decomposition helping most systems.

  • Active variables are those targeted for improvement in the next KBC iteration, while inactive variables are not needed there.An interest area identifies relevant relations, and dependency analysis determines potentially changed variables.
  • Conditioning on active variables partitions inactive variables into conditionally independent sets that can be materialized separately.Grouping these sets yields a more succinct factor graph for inference.
  • Optimal grouping is NP-hard because shared active variables can make combined groups cheaper than separate materializations.The grouping problem can be reduced to WeightedSetCover.
  • DeepDive greedily merges groups to reduce inference runtime while limiting repeated materialization of active variables.The heuristic starts with one inactive variable per group and iteratively combines groups.
  • Removing decomposition leaves A1 2% faster but slows both feature extraction and supervision-rule workloads.NoDecomposition selects one materialization strategy for the whole factor graph, whereas DeepDive decomposes it.

B.2 Materialization Time

DeepDive evaluates materialization under an 8-hour budget, measuring how many samples each system can collect when both sampling and variational approaches are materialized.

  • 8 hours is the materialization budget used to compare how many samples different systems can collect.The full materialization phase runs for all systems and includes both sampling and variational approaches.

B.3 Incremental Learning

DeepDive supports incremental learning when new labeled documents introduce features and training examples. Its SGD+Warmstart approach reaches near-optimal loss faster than the baselines.

  • Newly labeled documents can introduce both new features and new training examples, motivating incremental learning.Distant supervision can create new labeled data heuristically without human intervention.
  • DeepDive’s SGD+Warmstart reaches within 10% of optimal loss faster than SGD-Warmstart and gradient descent.The comparison uses the News dataset with rules F2 and S2.
  • 2× faster than SGD-Warmstart and about 10× faster than gradient descent are the reported speedups for reaching within 10% of optimal loss.Warmstart begins from a model with lower loss.

B.4 Discussion of Concept Drift

DeepDive’s incremental approach remains useful under concept drift, but its advantage over rerunning from scratch is smaller because distribution changes reduce the benefit of incremental inference. The evaluation finds warmstart still helps convergence, while per-iteration costs remain similar.

  • Concept drift: Concept drift occurs when streaming training examples come from a changing distribution, requiring systems to adapt and potentially forget old information.The paper notes that its KBC applications had not exhibited quality issues from concept drift, but other applications might.
  • Experimental validation: The study evaluates concept drift using 9,324 chronologically ordered emails and a spam-classification task with logistic regression.Training uses either the first 10% or first 30% of emails, with the remaining 70% for testing.
  • Results: Both Incremental and Rerun converge to the same loss under concept drift, but Incremental converges faster initially because warmstart begins from a lower loss.The reported convergence benefit comes from warmstart rather than stronger final quality.
  • Results: Incremental and Rerun take roughly the same time per iteration because large distribution changes cause Incremental to reject almost all samples and switch to variational inference.For the evaluated logistic-regression setting, this variational computation is similar to the original model.
  • Discussion: Concept drift still leaves Incremental better than restarting from scratch, although the benefit from incremental inference is smaller than without drift.The reduced advantage follows the paper’s observation that the new and materialized distributions differ substantially.
Loading 1502.00731v4…