Fusing Data with Correlations

Motivation

• Complementary source domains and extraction focus can make agreement-based voting miss true data, while copying or shared extraction rules can make it accept errors.These effects can produce false negatives and false positives, respectively.Source: §1 · p. 1

Example 1.1

• S1, S4, and S5 share extraction patterns, while S3 extracts complementary Infobox information, illustrating positive and negative source correlations.Union-25 accepts many false triples from correlated sources; Union-75 misses true triples because S3 is anti-correlated with three others.Source: §1 · p. 1

Related work

• Earlier data-fusion approaches focus on copying and single-truth assumptions, leaving positive correlation on true data, negative correlation, and multiple truths inadequately handled.Multiple professions can all be correct for one person.Source: §1 · pp. 1–2

Contributions

• The paper measures source quality with precision and recall, models correlations through joint precision and recall, and uses Bayesian analysis to infer triple truthfulness.It develops an exact correlation-aware solution and two approximations, then evaluates the methods on three real-world data sets and synthetic data.Source: §1 · p. 2

2.1 Data model

• Each source supplies triples, and the task is to identify the output triples that are true to form a high-quality data set.Sources are deterministic, and triples absent from a source are treated as unknown rather than false under open-world semantics.Source: §2.1 · pp. 2–3

2.2 Measuring truthfulness

• The framework estimates triple truthfulness from source outputs without requiring knowledge of how the sources derive their data.The authors assume independent triple truth and open-world semantics; they leave combining all semantics for future work.Source: §2.2 · p. 3, §2.1 · p. 3

Source quality

• Source precision is the portion of its output that is true, while recall is the portion of all true triples that it provides.Recall can be measured against the scope of a source’s input, and the techniques support either version of the calculation.Source: Source quality · p. 3

Correlation

• Joint precision measures the correctness of triples shared by a source subset, while joint recall measures the share of all correct triples that the subset jointly outputs.The paper uses these quantities to capture correlation among sources.Source: Correlation · p. 3

Positive correlation

• S1, S4, and S5 have positive correlation: their joint recall is 0.5, above the 0.3 expected under independence.They provide similar triples, with joint precision of 0.5.Source: Correlation · p. 4

Negative correlation

• S1 and S3 have negative correlation: their joint recall is 0.33, below the 0.45 expected under independence.They have little data overlap, and their joint precision is 0.33.Source: Correlation · p. 4

Problem definition

• The problem is to compute each output triple’s truth probability from source outputs and the joint precision and recall of every source subset.Those parameters number 2(2^n − 1), making the input size exponential in the number of sources.Source: Problem definition · p. 4

Independent sources (Section 3)

• Under independence, source precision and recall feed Bayesian analysis to estimate each triple’s truthfulness.For the motivating example, the independent-source method reaches F-measure .86 (precision=.75, recall=1).Source: Independent sources (Section 3) · p. 4

Correlated sources (Section 4)

• With known correlations, the method revises triple probabilities using the likelihood of the observed subset of sources and inclusion-exclusion over joint precision and recall.The authors describe correlations as often unknown and potentially positive or negative.Source: Correlated sources (Section 4) · p. 4
• 0.91 F-measure (precision=1, recall=0.83) is achieved for the motivating example with correlations, 18% higher than Union-50.The paper’s elastic approximation trades efficiency for accuracy, while the aggressive approximation reduces computation from exponential to linear at an accuracy cost.Source: Correlated sources (Section 4) · p. 4

3.1 Estimating triple probability

• Under source independence, Theorem 3.1 derives each triple’s correctness probability from the prior truth probability, source recalls, and false-positive rates.The method uses Bayes’ rule to combine the source contributions for a triple.Source: §3.1 · pp. 4–5
• A good source’s providing a triple raises its estimated truth probability, while its not providing the triple lowers it.A good source is one with recall greater than its false-positive rate.Source: §3.1 · p. 5
• For a bad source, providing a triple lowers its estimated truth probability, while not providing it raises the estimate.Source: §3.1 · p. 5

3.2 Estimating source quality

• The source-quality method derives false-positive rate from precision and recall rather than directly counting false triples in the training data.Direct counts can shift when the training data’s mix of false triples changes; recall is counted over true triples provided by at least one source.Source: §3.2 · p. 5
• With equal recall, a higher-precision source providing a triple raises its estimated truth probability; with equal precision above the prior, higher recall makes absence more informative.Source: §3.2 · p. 5

Comparison with LTM [25]

• Unlike LTM, the independent model uses Bayesian maximum-a-posteriori inference, derives false-positive rates from precision and recall, and estimates source quality from training data.LTM uses Beta distributions and iteratively estimates triple truthfulness and source quality.Source: Comparison with LTM [25] · pp. 5–6
• Both approaches assume triple independence and open-world semantics, and compute triple probabilities using source recall and false-positive rates.Source: Comparison with LTM [25] · p. 5
• The independent-source model is comparable to LTM [25] in general and sometimes better; the correlation model obtains considerably better results than LTM.Source: Comparison with LTM [25] · p. 6

4. FUSING CORRELATED SOURCES

• Replicas should count like one source, while overlapping true triples with independent mistakes raise confidence and shared false triples lower it.The examples contrast joint recall and false-positive rates across these correlation patterns.Source: §4 · p. 6
• For complementary sources, rare overlaps can be highly trusted, while a triple supplied by only one source is not penalized for that lack of agreement.The example assumes very low joint recall and near-zero joint false-positive rate for overlaps.Source: §4 · p. 6

4.1 Exact solution

• The exact solution extends the independence-based probability calculation using joint recall and joint false-positive rates for source subsets.It computes the conditional probabilities of observed source outputs given that a triple is true or false.Source: §4.1 · p. 6
• With correlations, t8 receives probability 0.37 and is correctly classified as false, unlike under the independence assumption.Although four of five sources provide t8, the correlation among S1, S4, and S5 reduces their contribution.Source: §4.1 · p. 7
• The exact computation is exponential in the number of sources that do not provide a triple, making it impractical for many sources.The paper therefore introduces approximations for the conditional probabilities.Source: §4.1 · p. 7

4.2 Aggressive approximation

• The aggressive approximation uses correlation parameters to adjust source recall and false-positive rates, reducing computation to linear time.It requires 2n + 1 correlation parameters rather than an exponential number of joint parameters.Source: §4.2 · p. 7
• The aggressive approximation can perform badly for replicas and complementary sources; identical outputs yield the prior probability, while pairwise-complementary sources can yield invalid probabilities.The paper also states that it matches the independence-based method when all sources are independent.Source: §4.2 · p. 7

• For true or false triples, each correlation factor is the corresponding joint recall or false-positive rate divided by the product of the individual sources' rates.The paper defines separate factors for true and false triples.Source: §I · p. 7
• A factor above 1 indicates positive correlation and below 1 indicates negative correlation; sources may differ in correlation across true and false triples.The examples include sources independent for true triples but negatively correlated for false triples.Source: §I · p. 7

• Under the partial-independence assumptions, the correlation factors can be rewritten to derive the simplified parameters used by the approximation.The section applies the assumptions to obtain equations for C+ parameters.Source: §II · pp. 7–8
• The example assumes S4 is independent of {S1, S2, S3} and of {S1, S2, S3, S5}, yielding an equality among joint recalls and correlation factors.The resulting relation is C123C12345 = C1234C1235.Source: §II · p. 7

III. Transformation

• The transformation rewrites the equation into the same simplified form as Definition 4.5.Source: §III · p. 8

4.3 Elastic approximation

• ELASTIC starts from the linear approximation and gradually adjusts results by relaxing assumptions at successive levels.At each level it corrects terms by replacing approximate coefficients with exact ones.Source: §4.3 · p. 8
• In the example, aggressive approximation, level-0 adjustment, and level-1 adjustment yield 0.3, 0.6, and 0.59, respectively; stopping after a constant number of levels can get close to the exact solution.Source: §4.3 · p. 8
• For n sources, m triples, and adjustment level λ, ELASTIC takes O(m · n^λ) time and requires O(m · n^λ) correlation parameters.Source: §4.3 · p. 8

Datasets

• The datasets span varied source quality: RESTAURANT sources mostly have high precision and recall, REVERB sources have fairly low precision and recall, and BOOK sources vary in precision and mostly have low recall.These differences provide a range of evaluation scenarios.Source: Datasets · p. 9

Comparisons

• PRECREC estimates triple truthfulness from source precision and recall; PRECRECCORR extends it with source correlations, using clusters and cross-cluster independence for BOOK.Clustering addresses BOOK's large number of correlation parameters and limited support data.Source: Comparisons · p. 9

Metrics

• Precision, recall, and F-measure assess binary decisions, while PR and ROC curves assess ranked truthfulness estimates; execution time is also reported.The curves plot precision versus recall and true-positive rate versus false-positive rate, respectively.Source: Metrics · p. 9

5.1 Real-World Data

• 5.2% higher F-measure, 10.3% higher AUC-PR, and 3.3% higher AUC-ROC on average for PRECRECCORR versus PRECREC across datasets.The improvements in AUC-PR and AUC-ROC are more pronounced than the F-measure improvement, which can be muted by thresholding.Source: §5.1 · p. 9, Figure 4 · p. 10
• PRECRECCORR is one order of magnitude slower than PRECREC on average, while level-3 elastic approximation finishes in half the time.For BOOK, the level-3 approximation takes 40 minutes; maximum parallelization reduces PRECRECCORR runtime to 80 seconds.Source: §5.1 · p. 10
• Detected correlations vary by dataset and truth status; BOOK's true- and false-triple clusters contain mostly different sources, with only two strongly correlated in both.For REVERB and RESTAURANT, the detected groups also differ between true and false triples.Source: §5.1 · pp. 10–11
• Level-3 elastic approximation is close to the exact PRECRECCORR result across all three datasets, with much shorter execution time.The heuristic is not guaranteed to improve estimates at every level.Source: §5.1 · p. 10, Figure 5 · p. 11

5.2 Synthetic Data

• With independent sources, PRECREC improves over existing approaches and PRECRECCORR performs similarly; with positive correlation on true triples or negative correlation on false triples, PRECRECCORR outperforms all alternatives.The independent-source experiments use five sources and 1,000 triples; the correlated experiments examine both correlation patterns.Source: §5.2 · p. 11

Data fusion

• Prior data-fusion approaches jointly infer truth and source quality but assume conflicting-triple, closed-world semantics; COSINE, 3ESTIMATE, and LTM assume source independence.Source: §6 · pp. 11–12

Correlation between sources

• Unlike copying-focused methods, this approach models positive non-copying and negative correlations under independent-triple, open-world semantics.It may boost contributions from providers correlated on true triples and reduce penalties from non-providers anti-correlated on true triples.Source: §6 · p. 12

Other correlation measures

• Compared with Qi et al. and Kappa, the paper measures correlation through joint precision and recall for source subsets, distinguishing positive and negative correlations on true and false data.The measure considers correlation for every subset of sources.Source: §6 · p. 12

• PRECREC and PRECRECCORR achieve significant fusion improvements and perform well on low-quality datasets that challenge other techniques.Source: §7 · p. 12
• The algorithms require no prior knowledge of possible correlations, and their parameters can be computed from a training set.Source: §7 · p. 12
• Independent-triple, open-world semantics allow multiple truth values for an entity, but may not fit attributes such as a single birth date.Source: §7 · p. 12
• Source quality may vary by domain; although domains can be modeled separately, automatically deriving the right subdivisions is not straightforward.Source: §7 · p. 12