PaperlayerView exact revision on arXiv

Source-linked AI summary

A Bayesian Approach to Discovering Truth from Conflicting Sources for Data Integration

Bo Zhao, Benjamin I. P. Rubinstein, Jim Gemmell, Jiawei Han

arXiv:1203.0058v1cs.DBcs.LG

TL;DR

Conflicting claims and uneven source reliability make truth finding a central data-integration challenge, especially when multiple values may be true. The paper introduces an unsupervised Bayesian Latent Truth Model that separates false-positive and false-negative source quality and supports scalable inference. Experiments on two real-world datasets show an advantage over state-of-the-art truth-finding methods.

  • Problem

    Data integration must derive complete and accurate records from conflicting sources, but prior approaches do not adequately handle multiple true values or distinguish two types of source errors.

  • Method

    The Latent Truth Model is an unsupervised Bayesian graphical model that treats truth as latent and generates observations using separate false-positive and false-negative source-quality factors.

  • Results

    The method shows a clear advantage over state-of-the-art truth-finding methods on two real-world datasets.

  • Takeaways & Limitations

    Separating two-sided source quality lets the model naturally support multiple truths while incorporating source priors and incremental data integration.

  • Takeaways & Limitations

    A single scalar quality measure can conflate false positives with false negatives, such as high precision with low recall, producing misleading source judgments.

Abstract

from arXiv · show

In practical data integration systems, it is common for the data sources being integrated to provide conflicting information about the same entity. Consequently, a major challenge for data integration is to derive the most complete and accurate integrated records from diverse and sometimes conflicting sources. We term this challenge the truth finding problem. We observe that some sources are generally more reliable than others, and therefore a good model of source quality is the key to solving the truth finding problem. In this work, we propose a probabilistic graphical model that can automatically infer true records and source quality without any supervision. In contrast to previous methods, our principled approach leverages a generative process of two types of errors (false positive and false negative) by modeling two different aspects of source quality. In so doing, ours is also the first approach designed to merge multi-valued attribute types. Our method is scalable, due to an efficient sampling-based inference algorithm that needs very few iterations in practice and enjoys linear time complexity, with an even faster incremental variant. Experiments on two real world datasets show that our new method outperforms existing state-of-the-art approaches to the truth finding problem.

1. INTRODUCTION

The truth finding problem is to derive complete and accurate merged records from conflicting sources whose reliability differs. The paper proposes an unsupervised Bayesian model that separates false positives and false negatives, supports multiple truths, and enables scalable batch or incremental inference.

  • Motivation: Conflicting source claims make it difficult to derive complete and accurate integrated records, a challenge termed the truth finding problem.Examples include incomplete author lists and incorrect authors across online book sellers.
  • Motivation: Majority voting can produce false positives, requires an impractical supervised threshold choice, and does not learn source reliability across datasets.Changing the threshold trades false positives for false negatives, while voting treats sources equally over time.
  • Limitations of prior methods: Existing approaches are not designed for entities with multiple simultaneously true values, such as books with several authors.They generally determine only the single most confident truth for each entity.
  • Core insight: False positives and false negatives need separate modeling because they need not correlate when sources make multiple claims about multi-valued attributes.Some sources omit true values, while others introduce erroneous data; modeling both aspects enables multiple truths.
  • Approach: The Latent Truth Model is an unsupervised Bayesian graphical model that infers truth and two-sided source quality through a generative error process.It treats truth as a latent random variable and uses collapsed Gibbs sampling with linear time complexity in practice.
  • Capabilities: LTM incorporates source priors for low-volume settings and supports batch or online streaming integration for incremental data.The incremental mode reuses quality learned at the current stage instead of batch retraining on cumulative data.

2. PROBLEM FORMULATION

This section formalizes truth finding for multi-valued attributes: infer which entity-attribute facts are true and estimate each source’s quality from raw claims without supplied truths.

  • 2. PROBLEM FORMULATION: The formulation handles attribute types individually, while noting that LTM can later be extended to use global quality.The paper simplifies the discussion by considering one attribute type at a time.
  • 2.1 Data Model: The model assumes one multi-valued attribute type and represents input as triples containing an entity, attribute value, and source.This supports structured data such as book authors and movie casts.
  • 2.1 Data Model: The raw database contains unique rows of the form (e, a, c), while the fact table deduplicates entity-attribute pairs and assigns each fact an identifier.A fact may appear in multiple raw-database rows because multiple sources can provide it.
  • 2.1 Data Model: Claims are Boolean observations tied to fact identifiers and sources: associated sources generate positive claims, while participating sources that omit a fact generate negative claims.Sources absent from an entity’s raw-database records generate no claims for that entity.
  • 2.1 Data Model: The claim-table construction treats omission as negative evidence only when a source provides other facts for the same entity.For example, Netflix’s omission of Emma Watson generates a negative claim, whereas Hulu’s complete absence of movie-cast claims generates none.
  • 2.2 Problem Definitions: Truths are Boolean variables associated with facts, but the input does not provide their values; the system must infer them and produce a truth table.Evaluation compares algorithmically generated truth tables with a human-generated truth table.
  • 2.2 Problem Definitions: The truth-finding task outputs inferred truths for all facts in a raw database that contains no truth information.The facts are the distinct entity-attribute pairs represented in the database.
  • 2.2 Problem Definitions: A second task automatically infers source quality for the attribute type, indicating source reliability and supporting source selection, crawler diagnosis, and priors for new data.Truth and source quality are computed together because each informs the other.

3. TWO-SIDED SOURCE QUALITY

This section argues that source quality must distinguish false positives from false negatives. It motivates modeling sensitivity and specificity independently so truth inference can treat these error types differently.

  • 3.1 Revisiting Quality Measures: Source quality can be evaluated through a confusion matrix by treating each source as a classifier that makes true or false predictions about facts.The same measures can also be applied to truth-finding mechanisms viewed as ensembles of source classifiers.
  • 3.1 Revisiting Quality Measures: Precision measures the correctness of positive claims, while accuracy measures the correctness of all positive and negative claims.These are scalar summaries of source behavior derived from confusion-matrix counts.
  • 3.1 Revisiting Quality Measures: Sensitivity measures how often true facts are claimed true, whereas specificity measures how often false facts are claimed false.One minus sensitivity is the false-negative rate, and one minus specificity is the false-positive rate.
  • 3.2 Limitations of Precision: Precision-only methods ignore negative claims, limiting their ability to reject erroneous values when multiple values may simultaneously be true.A source with precision 2/3 may still receive credence for a false claim despite its other correct positive claims.
  • 3.3 Limitations of Accuracy: Accuracy alone also conflates false positives and false negatives, forcing low-precision and low-recall sources to receive the same treatment.A source can have high precision but low recall, so discounting it for omissions may also discount its reliable positive claims.
  • 3.3 Limitations of Accuracy: Netflix and BadSource.com can obtain equal accuracy despite different error profiles, making accuracy unable to distinguish their positive claims appropriately.Netflix has more false negatives but no false positives, while BadSource.com introduces false information through low precision.
  • 3.3 Limitations of Accuracy: The paper models sensitivity and specificity as independent quality measures to represent the complete spectrum of source errors.Sensitivity is associated with false negatives and specificity with false positives; the model assigns them independent random variables and priors.
  • 3.3 Limitations of Accuracy: These two-sided measures can preserve confidence in Netflix’s positive claims despite its omissions while penalizing BadSource.com’s low specificity.The approach is intended for unsupervised settings where fact truths are unknown.

4. LATENT TRUTH MODEL

The Latent Truth Model is a Bayesian network that jointly infers fact truth and two-sided source quality from observed claims. It represents truth probabilities, truth labels, source specificity and sensitivity, and claim observations in a generative model.

  • Model overview: LTM is a Bayesian network for inferring the truth of facts and the quality of data sources.Its nodes represent observed values, latent values, or unknown parameters, with dependencies encoded by directed edges.
  • Source quality: Each source has separate specificity and sensitivity variables to distinguish false positives from false negatives.Specificity models erroneous claims about false facts, while sensitivity models whether true facts are reported.
  • Prior assumptions: LTM supports prior beliefs about source quality and fact truth, using specified priors or uniform priors when stronger beliefs are unavailable.Beta priors model source false-positive rates and sensitivity, while truth probabilities can also receive prior distributions.
  • Fact truth: LTM models each fact with a latent truth probability and a latent Boolean truth label.The truth label depends on the truth probability, allowing the model to distinguish the two error types during inference.
  • Claim observations: Each claim observation depends on the referred fact's truth and the asserting source's quality.For false facts, specificity affects whether observations are false; for true facts, sensitivity affects whether observations are true.

5. INFERENCE ALGORITHMS

The inference procedure estimates latent fact truths from observed claims using collapsed Gibbs sampling, then derives source-quality estimates from the inferred truths. The method has linear time complexity and supports incremental fitting for streaming data.

  • Truth inference: The MAP truth assignment maximizes the joint probability of latent truths given the observed claim data.Final predictions can instead average post-burn-in, thinned samples and classify facts as true at an expectation threshold of 0.5.
  • Truth inference: Collapsed Gibbs sampling iteratively resamples each fact's truth conditional on other truth variables and source-quality counts.Conjugacy integrates out truth probabilities, specificity, and sensitivity during sampling.
  • Efficiency: O(|C|) or O(|S| × |F|) time complexity makes the collapsed Gibbs sampler linear in the number of claims and more scalable than O(2^|F|) brute-force search.Brute-force inference searches all possible truth assignments, whereas the sampler avoids that exponential search.
  • Source-quality inference: Source-quality estimates are obtained after truth prediction through closed-form MAP estimates based on expected source counts and Beta priors.The same counts also support estimating measures such as precision.
  • Incremental inference: For streaming data, learned source quality becomes the prior for future increments, so each update depends only on the new data size.The model can also assume medium-term stability and periodically retrain batch-style or incrementally.

6. EXPERIMENTS

Experiments on real-world and synthetic datasets evaluate LTM against prior truth-finding methods, examining effectiveness, robustness to source quality, and behavior with conflicting multi-valued facts. LTM generally achieves stronger and more stable truth-finding performance, while explicitly modeling sensitivity and specificity supports multi-valued truth inference.

  • Experimental setup: LTM and its incremental variant were evaluated against prior methods, voting, and LTMpos on two real-world datasets, with synthetic data used to stress-test low source quality.The datasets cover book authors and movie directors; labeled subsets support evaluation, while the synthetic data varies expected sensitivity and specificity.
  • Effectiveness: LTM and LTMinc achieved significantly better accuracy and F1 than competing approaches on both datasets, with nearly perfect performance on the book data.Movie performance was lower because the movie dataset was intentionally made more difficult, and LTMinc showed no significant difference from LTM.
  • Threshold behavior: LTM remained stable across thresholds on book data and outperformed other methods across thresholds 0.2 to 0.9 on the more difficult movie data.Voting and 3-Estimates required lower or specific optimal thresholds, while several alternatives were conservative or overly optimistic.
  • Quantitative evaluation: AUC results showed LTM’s clear advantage on movie data and identified it as the superior method overall across both datasets.AUC measures how correctly methods rank random facts by their scores in ROC space.
  • Robustness: LTM accuracy stayed close to 1 until source specificity or sensitivity fell below 0.6, then declined faster with decreasing specificity than sensitivity.Accuracy fell to around 0.5 when specificity was about 0.3 or sensitivity about 0.1, indicating nearly random prediction.
  • Source quality: The results support modeling sensitivity and specificity separately because source behavior can differ across these two measures and multi-valued attributes require accounting for negative claims.3-Estimates benefited from negative claims but had lower recall, while methods without negative claims could predict everything as true.

6.3 Efficiency

The efficiency experiments examine convergence and runtime for LTM and LTMinc. LTM converges quickly and scales linearly, while LTMinc is recommended for efficient online prediction after periodic offline source-quality updates.

  • 6.3.1 Convergence Rate: LTM reached accuracy 0.85 after 7 iterations and achieved optimal accuracy with extremely low variation after 50 iterations.Additional iterations did not improve performance further, indicating rapid practical convergence.
  • 6.3.2 Runtime: LTM and prior algorithms have linear complexity in the number of claims, while LTMinc is much more efficient because it avoids iteration during online prediction.The authors recommend periodically running standard LTM offline to update source quality, then deploying LTMinc online.
  • 6.3.2 Runtime: Linear regression of LTM runtime against dataset size achieved an R2 score of 0.9913, establishing empirical scalability.The analysis used running time as a function of the number of claims.

7. DISCUSSIONS

The discussion reports linear runtime scaling for LTM inference and outlines extensions addressing broader source, attribute, loss, and adversarial settings.

  • Extensions: LTM can jointly model multiple attribute types by sharing source-quality priors across attributes.The proposed extension introduces source-specific quality priors α0,s and α1,s regularized by a global prior.
  • Scalability: R2 = 0.9913 for the linear regression of runtime across varying claim counts supports an approximately linear cost for 100 LTM iterations.The measurements concern runtime for 100 iterations with varying numbers of claims.
  • Extensions: An entity-clustering extension would allow source quality to vary across groups of entities rather than remain constant for every entity.The example contrasts IMDB’s potential accuracy on horror movies with its accuracy on dramas.
  • Extensions: For real-valued losses, a Gaussian observation model could replace LTM’s binary Bernoulli error model.The motivating examples include inexact term matches and numerical attributes.
  • Extensions: LTM assumes sources have reasonable specificity and precision, so adversarial sources with mostly false data remain outside its intended setting.Such sources can artificially increase benign sources’ specificity and make their false data harder to detect.

8. RELATED WORK

Related work approaches truth finding through inconsistency resolution, source-quality modeling, constraints, background information, extraction confidence, copying detection, and semi-supervision.

  • Truth finding: Earlier data-integration research addressed inconsistency resolution and source-quality modeling, while later work formally introduced truth finding.Other methods used integer programming for truth constraints and frameworks incorporating background information.
  • Truth finding: Previous models incorporated extraction confidence, record-merging difficulty, sensor-network EM inference, and other setting-specific signals into truth finding.The paper implements most of the previous algorithms for comparison.
  • Other data-integration aspects: Other data-integration studies modeled source copying, multiple attributes, semi-supervised record similarity, and additional data-source relationships.Detecting copying can discount support for erroneous data and improve truth-finding accuracy.

9. CONCLUSIONS

The paper concludes that LTM models two-sided source quality and multiple truths while providing efficient inference and support for prior knowledge and streaming data.

  • Contributions: LTM represents false positives and false negatives separately because they may not correlate when entities can have multiple true facts.Truth is introduced as a latent variable in the generative error process.
  • Evaluation: Experiments on two real-world datasets show a clear advantage over state-of-the-art truth-finding methods.A source-quality case study also supports considering two aspects of source quality.
  • Inference: Collapsed Gibbs sampling provides inference that converges quickly and has linear cost with respect to data size.The convergence and cost claims are reported from experiments.
  • Practical extensions: LTM can incorporate prior knowledge about truth or source-quality distributions and operate in an online streaming setting.The streaming setting extends the method beyond batch processing.

A. DETAILS OF INFERENCE

The inference-details passage rewrites a conditional distribution with Bayes’ rule, expands its terms, and substitutes those expressions to obtain the target equation.

  • Conditional derivation: Bayes’ rule rewrites the conditional distribution of t_f given t_−f and the observed data.This is presented as the starting point for the inference derivation.
  • Conditional derivation: The derivation first rewrites the first term in Equation (4), then evaluates the remaining terms separately.The passage organizes the calculation into component substitutions.
  • Conditional derivation: Substituting the rewritten terms into Equation (4) yields Equation (2).The displayed beta-function expression is used in the intermediate algebra.
Loading 1203.0058v1…