PaperlayerView exact revision on arXiv

Source-linked AI summary

From Data Fusion to Knowledge Fusion

Xin Luna Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Kevin Murphy, Shaohua Sun, Wei Zhang

arXiv:1503.00302v1cs.DB

TL;DR

The paper asks whether data fusion techniques can resolve true knowledge triples despite additional noise from information extractors. It adapts three such techniques for large-scale knowledge fusion and evaluates them on extracted Web knowledge. The methods work quite well, while calibration improvements and error analysis reveal limitations and future research directions.

  • Problem

    Knowledge fusion must identify correct subject-predicate-object triples amid conflicting sources and extractor errors, extending data fusion beyond factual source errors.

  • Method

    The paper adapts three unsupervised data fusion techniques, treats each Extractor-URL pair as a provenance, and applies them to extracted knowledge.

  • Results

    Existing data fusion techniques work quite well for knowledge fusion, and refinements yield calibrated probabilities matching observed accuracy across probability ranges.

  • Takeaways & Limitations

    Truthfulness probabilities can support trusting high-probability triples, using low-probability triples as negative examples, and applying medium-probability triples in active learning.

  • Takeaways & Limitations

    Knowledge-fusion adaptations violate source-independence assumptions, while copying-detection methods do not scale to billions of Web sources and may confuse extraction errors with copying.

Abstract

from arXiv · show

The task of {\em data fusion} is to identify the true values of data items (eg, the true date of birth for {\em Tom Cruise}) among multiple observed values drawn from different sources (eg, Web sites) of varying (and unknown) reliability. A recent survey\cite{LDL+12} has provided a detailed comparison of various fusion methods on Deep Web data. In this paper, we study the applicability and limitations of different fusion techniques on a more challenging problem: {\em knowledge fusion}. Knowledge fusion identifies true subject-predicate-object triples extracted by multiple information extractors from multiple information sources. These extractors perform the tasks of entity linkage and schema alignment, thus introducing an additional source of noise that is quite different from that traditionally considered in the data fusion literature, which only focuses on factual errors in the original sources. We adapt state-of-the-art data fusion techniques and apply them to a knowledge base with 1.6B unique knowledge triples extracted by 12 extractors from over 1B Web pages, which is three orders of magnitude larger than the data sets used in previous data fusion papers. We show great promise of the data fusion approaches in solving the knowledge fusion problem, and suggest interesting research directions through a detailed error analysis of the methods.

1. INTRODUCTION

Data fusion infers true values from conflicting source data, while knowledge fusion extends this setting to extractor-generated triples and additional noise. The paper adapts data fusion methods, evaluates them at unprecedented scale, improves probability calibration, and analyzes remaining challenges.

  • Data fusion: Data fusion infers latent true values for data items from noisy, possibly missing values supplied by multiple sources.The input can be represented as an M × N data matrix of items by sources.
  • Knowledge fusion: Knowledge fusion adds an extractor dimension to source-item data, resolving correctness for subject-predicate-object triples extracted from unstructured data.The resulting input is three-dimensional rather than the two-dimensional data-fusion matrix.
  • Contributions: The paper adapts three data fusion techniques with efficient MapReduce implementations and evaluates them on 1.6B RDF triples extracted by 12 extractors from over 1 billion Web pages.This dataset is 1000 times larger than datasets used in previous data fusion experiments.
  • Contributions: Simple improvements produce a fairly well-calibrated system across high, low, and medium predicted-probability ranges.Predictions above 0.9 correspond to 0.94 accuracy, below 0.1 to 0.2 accuracy, and [0.4, 0.6) to 0.6 accuracy.
  • Contributions: The paper provides detailed error analysis and suggests future research directions for problems introduced by extractor-based knowledge fusion.It contrasts this unsupervised conflict-resolution focus with prior work emphasizing supervised extraction-quality improvement.

3. FUSING EXTRACTED KNOWLEDGE

The paper constructs a Web-scale knowledge base by combining diverse extractors and adapts data-fusion techniques to estimate the correctness of extracted triples. Its analysis exposes substantial variation and extraction-driven noise, while local closed-world evaluation provides a practical but limited quality measure.

  • 3.1.1 Knowledge base: 80% of extracted triples come from DOM content and 19% from text, while half of Web pages contribute only one triple.Content-type contributions depend partly on extractor capabilities, and overlap between content types is small.
  • 3.1.1 Knowledge base: The system builds a knowledge base from Web content using multiple extractors that identify triples, link entities, and link predicates.These tasks introduce extraction errors beyond factual errors in source data.
  • 3.2.1 Quality of extracted knowledge: The evaluation uses the local closed-world assumption: an absent triple is false only when its subject-predicate pair appears in Freebase.Triples for subject-predicate pairs missing from Freebase are excluded from the gold standard.
  • 3.2.1 Quality of extracted knowledge: The assumption is valid for functional predicates but can wrongly mark true triples as false for incomplete non-functional predicates.The authors nevertheless report that most predicates have only one or two true values, so the assumption works well in practice.
  • 3.2.1 Quality of extracted knowledge: 30% estimated accuracy and extraction errors dominate source errors, with triple-identification and entity-linkage errors each affecting 44% of sampled false triples.Predicate-linkage errors affect 20%, while only 4% are attributed solely to Web sources; some triples contain multiple errors.

4. APPLYINGDATAFUSIONMETHODSTO KNOWLEDGE FUSION

The paper adapts three data-fusion methods to knowledge fusion by modeling extractor–source combinations as provenances, then evaluates and refines them at large scale. POPACCU and ACCU outperform VOTE on ranking or calibration, while granularity, filtering, and gold-standard initialization improve results but leave substantial errors.

  • Method adaptation: Three adapted methods—VOTE, ACCU, and POPACCU—are evaluated, with VOTE serving as the baseline.The methods are implemented for the knowledge-fusion setting.
  • Method adaptation: Each (Extractor, URL) pair is treated as a provenance, reducing the three-dimensional input to data-fusion-compatible sources.Provenance support may reflect either multiple Web sources or multiple extractors.
  • Evaluation: ACCU achieves the highest AUC-PR, while POPACCU has the lowest weighted deviation and VOTE performs worst on both reported comparisons.The evaluation uses calibration measures and precision–recall curves.
  • Evaluation: VOTE underestimates many true triples and performs poorly when only one or two provenances support a data item.Its probability can be 0.7 for a triple supported by 7 of 10 provenances, and 1 or 0.5 with only one or two provenances.
  • Refinements: Using extractor, site, predicate, and pattern granularity reduces weighted deviation by 13% and increases AUC-PR by 5% versus (Extractor, URL) granularity.Finer granularity can distinguish triple quality, but overly fine provenance can leave too little support for evaluation.
  • Refinements: Together, the refinements reduce weighted deviation by 13% and increase AUC-PR by 12%, while gold-standard initialization alone reduces weighted deviation by 21% and increases AUC-PR by 18%.The combined changes also raise the share of triples receiving predicted probabilities from 91.8% to 99.4%; gold-standard initialization can overfit with fine-grained provenances.

5. FUTURE DIRECTIONS

Existing data-fusion methods show promise for knowledge fusion, but their assumptions leave substantial room for improvement and motivate more radical changes.

  • Small modifications to existing data-fusion methods can produce reasonable results for knowledge fusion.
  • Improving knowledge-fusion quality will require more radical changes to the basic assumptions of data-fusion methods.
  • Future research directions are sketched to address the remaining limitations of current methods.

1. Distinguishing mistakes from extractors and from sources

Treating provenance only as a source–extractor combination can hide systematic extractor errors, so fusion should distinguish extractor mistakes from source errors.

  • Triples with 100 provenances have accuracy 0.6, while those with 1000 provenances have accuracy 0.75.
  • For the same provenance count, triples extracted by at least 8 extractors have 70% higher average accuracy than triples extracted by one extractor.
  • Representing provenance as the cross product of Web source and extractor buries the signal associated with the number of extractors.
  • Separating extractor mistakes from erroneous Web-source information would allow their qualities to be evaluated independently.

2. Identifying complex correlations between extractors and between sources

Knowledge fusion must model dependence more richly than ordinary copying detection because extractors can correlate or anti-correlate, while existing source-pair methods do not scale.

  • ACCU and POPACCU assume independent data sources, but their adapted sources are Extractor–URL pairs and therefore are not independent.
  • Copying-detection techniques do not scale to billions of Web sources and can mistake shared extraction errors for copying evidence.
  • Among 66 extractor pairs, 53% are independent according to the Kappa measure.
  • The Kappa measure distinguishes positive correlation, negative correlation, and independence while accounting for intersections expected under independence.
  • Future work should scale methods for reasoning about copying between Web sources and richer extractor correlations.

3. Handling non-functional predicates properly

Current data-fusion models assume functional predicates, but most extracted knowledge is non-functional; future methods should represent multiple truths and predicate-specific functionality.

  • 72% of predicates and 76% of data items have non-functional predicates, invalidating the models’ functionality assumption.
  • The functionality assumption accounts for 65% of false negatives in the error analysis.
  • When POPACCU+ predicts probability below 0.1, real accuracy is 0.2 despite the invalid functionality assumption.
  • Future methods should handle both functional and non-functional predicates, including cases with multiple truths.
  • A promising direction is learning each predicate’s degree of functionality, such as nearly functional spouse versus highly non-functional acted-in.

4. Considering hierarchical value spaces

The paper argues that treating object values as unrelated categories misses truths and evidence encoded by hierarchical and similar relationships. Value hierarchies can support multiple simultaneous truths and reduce false negatives.

  • Ignoring value hierarchy accounts for 35% of false negatives in the reported results.
  • Hierarchically related values can both be true, such as USA and California as Steve Jobs’s birth places.
  • Evidence for specific values can aggregate into support for a broader hierarchical value, such as cities in California supporting California.
  • Similar representations or numerical values may also provide partial support rather than being treated as completely different.
  • Existing similarity methods address strings and numbers, but the paper calls for reasoning about entity hierarchy and similarity in extracted triples.

5. Leveraging confidence of extractions

The paper examines how extractor confidence can inform knowledge fusion despite differing, uncalibrated confidence scales. Filtering low-confidence triples loses substantial coverage, motivating principled integration across models and extractors.

  • All implemented models assume deterministic data and treat extracted triples equally, although 99.5% of triples include extractor confidence.
  • Because confidence may be uncalibrated and differs across extractors, the paper seeks a principled way to incorporate it across model types.
  • Confidence distributions differ sharply across extractors, with some scores near 0 or 1 and others concentrated near 0.5.
  • Filtering at a confidence threshold as low as 0.1 loses 15% of extracted triples.

6. Using data from low-coverage sources judiciously

The paper highlights a trade-off in using low-coverage provenance data: filtering small samples improves probability prediction but leaves some triples without estimates.

  • Filtering provenances with low sample sizes can significantly improve probability prediction but can leave triples without any probability estimate.

7. Improving the closed world assumption

The paper identifies limitations of the local closed world assumption in evaluation and initialization, because incomplete ground truth can misclassify correct model decisions. It suggests uncertain ground truths as a way to relax the assumption while retaining negatives.

  • The local closed world assumption can be invalid when Freebase lacks correct values or more specific values.
  • 50% of false positives are actually correct model decisions under the local closed world assumption.
  • Assigning confidence to ground-truth facts could reduce penalties for conflicts with uncertain truths while still producing negative examples.

8. Knowledge fusion for an open domain

This paper’s knowledge-fusion setting assumes that subjects and predicates already exist in a knowledge base. Future expansion to new entities, predicates, and types would introduce additional noise requiring further treatment.

  • 8. Knowledge fusion for an open domain: The current study restricts knowledge fusion to triples whose subjects and predicates already exist in a knowledge base such as Freebase.The authors identify adding new entities, predicates, and types as future enrichment tasks.
  • 8. Knowledge fusion for an open domain: Discovering new entities can be framed as reconciliation applied to extracted triples.
  • 8. Knowledge fusion for an open domain: Future knowledge-base enrichment would introduce additional noise beyond that addressed in this study.The passage specifically identifies new entities, predicates, and types as sources of further noise.

6. CONCLUSIONS

The paper adapts and refines data-fusion techniques for the harder knowledge-fusion problem, evaluating them at very large scale. Existing techniques work fairly well, but their inherent limitations motivate further research.

  • 6. CONCLUSIONS: The study adapts three existing data-fusion techniques and evaluates them on 1.6B unique knowledge triples extracted using 12 extractors from more than 1B data sources.
  • 6. CONCLUSIONS: Existing data-fusion techniques work quite well for solving the knowledge-fusion problem.
  • 6. CONCLUSIONS: The paper analyzes the inherent limitations of these techniques and identifies research directions for making them more suitable for knowledge fusion.
Loading 1503.00302v1…