A fundamental problem in data fusion is to determine the veracity of multi-source data in order to resolve conflicts. While previous work in truth discovery has proved to be useful in practice for specific settings, sources' behavior or data set characteristics, there has been limited systematic comparison of the competing methods in terms of efficiency, usability, and repeatability. We remedy this deficit by providing a comprehensive review of 12 state-of-the art algorithms for truth discovery. We provide reference implementations and an in-depth evaluation of the methods based on extensive experiments on synthetic and real-world data. We analyze aspects of the problem that have not been explicitly studied before, such as the impact of initialization and parameter setting, convergence, and scalability. We provide an experimental framework for extensively comparing the methods in a wide range of truth discovery scenarios where source coverage, numbers and distributions of conflicts, and true positive claims can be controlled and used to evaluate the quality and performance of the algorithms. Finally, we report comprehensive findings obtained from the experiments and provide new insights for future research. As online user-generated content grows exponentially, the reliance on Web data is inevitably growing in every application domain. However, data can be biased, noisy, outdated, incorrect, and thus, misleading and unreliable. Massive data coming from multiple sources amplifies the difficulty of ascertaining information veracity. The problem of truth discovery is intellectually and technically interesting enough to have attracted a lot of prior studies, from the artificial intelligence and the database communities, sometimes investigated under the names of fact-checking [9] , information credibility [13] , information corroboration [8] , data fusion [14, 10] , conflicting data integration [5] , or knowledge fusion [7] . Truth discovery problem can be formulated as follows. Given a set of assertions claimed by multiple sources, label each claimed value as true or false and compute the reliability of each source. One major line of work extends truth discovery models by incorporating prior knowledge either about the claimed assertions (e.g., . SIMPLELCA and GUESSLCA [13] ) or about the source reputation via trust assessment (e.g., SourceRank [1] ). Another important line of research aims at iteratively computing and updating the trustworthiness of a source as a function of the belief in its claims, and then the belief score of each claim as a function of the trustworthiness of the sources asserting it (e.g., TRUTHFINDER [17] ). In this line, several probabilistic models have been proposed to incorporate various aspects beyond source trustworthiness and claim belief, namely: the dependence between sources (e.g., DEPEN and its extensions [3] ), the temporal dimension in discovering evolving truth [6] , the difficulty of ascertaining the veracity of certain claims (e.g., COSINE, 2-and 3-ESTIMATES [8]), and the management of collections of entities (e.g., LTM [18] ) or linked data [9] . There are a number of challenges in truth discovery. The first challenge is a theoretical one since it is difficult to formalize a method general enough to handle various data set characteristics and truth discovery scenarios. We observe that none of the methods constantly outperforms the others in terms of precision and a "one-fits-all" approach does not seem to be achievable. Another challenge is related to the usability of the methods. Assumptions of truth discovery models and complex parameter setting make current approaches still difficult to use and apply to the wide diversity of information available on the Web. Related Work. Previous comparative studies such as the work of Li et al. [11] and [10] are based on real-world data sets and gold standards because, in practice, the complete ground truth often does not exist or is out-of-reach. Such gold standards are samples of the ground truth (generally less than 10% of the original data set's size). We claim that they are not statistically significant to be legitimately used for evaluating and comparing existing methods in a systematic way. Moreover, previous comparisons did not study important algorithmic aspects of the methods such as parameter settings, time complexity, repeatability, computational issues, scalability, and convergence of the algorithms. They did not test them extensively for a wide range of truth discovery scenarios systematically generated with the control of the complete ground truth distribution. The experimental framework and data set generator we propose for comparing the methods are novel, practical contributions to the field, so that others can use and extend them for benchmarking, parameter setting and tuning of existing and new truth discovery algorithms. Publicly-available data sets with complete ground truth are notoriously difficult to obtain. The data set generator can serve as a useful proxy for what-if scenarios and reproducibility, to understand, in a systematic way, the data set characteristics that have significant impact on the performance and quality of the algorithms. The goals of our study are: (1) To provide a clear explanation of each algorithm, and allow comparison of their properties by using common notation, termiarXiv:1409.6428v1 [cs.DB] 23 Sep 2014  To provide reference implementations of these algorithms against which future algorithms can be compared, new data sets can be analyzed, and on top of which algorithms for different problems or applications can be built, and finally, (3) To perform a thorough experimental evaluation of the algorithms over a variety of data sets and report their performance and quality for a wide spectrum of parameter settings. This paper is structured as follows. In Section 2, we define the problem of truth discovery and describe the algorithms in detail. In Section 3, we present our comparative study based on synthetic data sets systematically generated to demonstrate the quality of the algorithms in various truth discovery scenarios. Then, we study scalability, and finally, we evaluate the methods on five real-world data sets. In Section 4, we recapitulate our findings and conclude the paper. We consider the truth discovery algorithms that take, as input data, a set of claims in the form of quadruplets (claimID, sourceID, dataItemID, value) and infer, as output result, a Boolean truth label for each claim. In addition, the truth discovery algorithms may also return T s , the truthworthiness of each source s, and C v , the confidence of each value v. For example, consider the four sources in the example of Table 1(a) adapted from [5] . They provide claims on affiliation of four researchers such as (c1,S1,Stonebraker:AffiliatedTo,MIT). Source coverage (Cov) is 1 for S 1 , .25 for S 2 , and .75 for S 3 and S 4 . Only S 1 actually provides a correct value for each data item, from d 1 to d 4 , in conformance with the ground truth (GT). Depending on the number of distinct values per data item (Conf) -e.g., d 1 -d 3 have 2 distinct values -some algorithms can make random guessing or wrong decisions if some sources copy claims from another source. In Table 1 (b), source truthworthiness has been computed by DE-PEN and TRUTHFINDER algorithms. The precision is computed from the number of true positives in (GT) also returned by the algorithms (.75 and .25, respectively). Truthworthiness of S 1 is .0489 for TRUTHFINDER, whereas it is .0323 for DEPEN. Table 1(c) shows the confidence of each value computed by TRUTHFINDER. The values considered to be true by this algorithm are in bold. As illustrated by this example, truth discovery algorithms may have different precision and output results depending on parameter setting and data set characteristics. In this paper, we study the effect of both on the quality and performance of 12 truth discovery algorithms from the literature. We use the notations presented in Table 2. Each truth discovery algorithm is presented in detail with its pseudocode where refers to the computation of value confidence C v , and refers to the computation of source truthworthiness, T S . We study the impact of various parameter settings on the quality of each algorithm and we analyze time complexity in Table 3 . We made several choices for the consistency and fairness of our study. First, we initialized source truthworthiness T S to .8 for all algorithms because it maximizes the precision of most algorithms. Second, we use the Book data set for this preliminary parameterization study. The Book data set has been formatted in different versions so that all algorithms can be compared from the same input data set. Third, we use the same convergence test for all algorithms: the difference of source truthworthiness cosine similarity between two successive iterations to be less than or equal to a given threshold, δ, as we will describe in this section. We will discuss these choices at the end of the section and conclude on this first set of experiments dedicated to parameter setting. Due to the space limitation, we had to limit the presentation of our results but we invite the reader to access the full set of the experimental results and codes in [2]. Algorithm. TRUTHFINDER relies on the honesty of the sources and follows the heuristics that a source providing mostly true claims for many data items will likely provide true claims for other objects. In Algorithm 2.1, the probability of a value being wrong is (1 − T s ). Thus, if the value is provided by many sources, then its probability of being wrong is s∈S v (1 − T s ). Following this general idea, the source truthworthiness in TRUTHFINDER is T s = v∈V S C v /|V S | in and the confidence score of a value is σ v = − s∈S v ln(1 − T S ). Logarithm is used to avoid underflow of the truthworthiness when the quantities are small. TRUTHFINDER adjusts the confidence score of a claim so that it incorporates the influence (or support) that similar claims may have mutually on each other as (v, v ). For instance, for a multi-valued data item, a source providing the values (AuthorA,AuthorB) for a book will support another source that provides the values (AuthorA,AuthorB,AuthorC) for the same book (but not inversely). The weight of such support between the values is controlled by the parameter ρ ∈ [0, 1]. The final confidence of a claim is then computed in with a logistic function to be positive. The damping factor γ compensates the effect when sources with similar values are actually dependent. Since TRUTHFINDER computes similarity between values, it can be dramatically affected by the number of distinct values to compare which explains relatively lower performance when the number of conflicts is high. Finally, TRUTHFINDER uses the difference of source truthworthiness cosine similarity between two successive iterations to be less than or equal to a given threshold, δ. The value with the highest confidence is then selected as the true value among the other (false) values for a given data item. Parameter Setting. TRUTHFINDER has three different parameters to be set: ρ, γ, and T S . We vary every parameter value while fixing the other parameters' values as reported in the next table. Variables Precision ρ = .5, T S = .8 γ from .2 to .8 No significant change ρ = .5, γ = .1 T S from 0 to .99 No significant change γ = .1, T S = .8 ρ from .2 to .8 Max (.9777) for ρ = .5 We vary δ, the convergence threshold from .001 to 1E−5 without any change in precision but increasing of execution time from 435 ms to 526 ms (≈ +21%) for the Book data set. Finally, we use δ = .001 and the values that maximize the precision for the Book data set: ρ = .5, γ = .1, and T S = .8 (noted in the table). Three algorithms have been proposed in 2010 by Galland et al. in [8], namely COSINE, 2-ESTIMATES, and 3-ESTIMATES. COSINE in Algorithm 2.2 starts by initializing the confidence of each value and the truthworthiness of each source. Then, it iteratively computes source truthworthiness in as a linear function of the truthworthiness achieved in the previous iteration. For each claimed value, the value confidence is computed as a function of the current truthworthiness scores of the sources claiming this value minus the truthworthiness scores of disagreeing sources in . 2-ESTIMATES in Algorithm 2.3 is a probabilistic model for estimating source truthworthiness and value confidence. As in CO-SINE, 2-ESTIMATES takes into consideration disagreeing sources for every data item while computing the value confidence. It starts by initializing source truthworthiness and iteratively computes the value confidence in as a function of both agreeing and disagreeing sources claiming different values. Then, it computes the source truthworthiness in as a function of the confidence of all values for all data items provided by the source. Finally, both value confidence and source truthworthiness are normalized after each iteration with Normalize function. 3-ESTIMATES in Algorithm 2.4 uses a third parameter beside T S and C v : the value error factor, v . Then, for each value, the algorithm computes the value confidence in as a function of the value error factor and the truthworthiness of each source providing the value, as well as the truthworthiness of the sources claiming other values. The confidence is normalized and used to compute a new error factor per value which is also normalized. Finally, the source truthworthiness is computed in and normalized as a function of the value confidence and the error factor. As mentioned by the authors, the normalization function is critical for these algorithms to reach convergence to a non-local optima but the setting of λ is not documented in the original paper. Moreover, the authors used a fix point computation for testing convergence. Since they did not recommend it for being costly and not guaranteeing the convergence in Algorithm 2.5: LTM(S , D, V, K, burnin, thin, α, β) ∀s ∈ S v : n s,tv,ov ← n s,tv,ov + 1 ∀s ∈ Sv : n s,tv,ov ← n s,tv,ov + 1 Sampling: some cases, we used the same convergence test as TRUTHFINDER with δ = .001. Parameter Setting. Information corroboration algorithms include four parameters to be initialized: T s , η for COSINE, λ, and v . We initialize T s = .8. For COSINE, we set η to 0.2 since it maximizes the precision. In our parameterization analysis on the Book data set, we faced unstable results for 3-ESTIMATES from one execution to another giving different results for precision, accuracy, and recall for certain values of λ. As shown in the table, based on 100 runs with λ = .8, the 95% confidence interval of precision varies from .9214 to .9587. Finally, for the Book data set, we select T S = .8, η = .2 for COSINE, λ = .5, and v = .4 for 3-ESTIMATES. Latent Truth Model (LTM) proposed in 2012 by Zhao et al. [18] uses Bayesian networks for estimating the truth. LTM has two important assumptions on the format of the data sets it can handle: (1) the data set should contain only one attribute with atomic values and (2) LTM can handle multiple true values for the same data item. For example, in the case of the Book data set where a list of authors provided by a source s is (AuthorA,AuthorB), LTM actually takes as input two claims from s, each one having an atomic value that can be true such as: (c1,s,ThisBook:AuthorOf,AuthorA) and (c2,s,ThisBook:AuthorOf,AuthorB). LTM considers, for each source, its prior probability of true positive and negative errors, noted (α 1,1 , α 1,0 ) as source sensitivity, as well as its prior probability of false positive and negative errors, noted (α 0,1 , α 0,0 ) as source specificity. Finally, values with confidence higher than .5 are considered to be true, thus, for some data item, LTM may not detect any true value. Algorithm. In Algorithm 2.5, LTM maintains four counters for each source, noted n s,tv,ov , where t v is the Boolean truth label for each value v, and o v is whether value v is actually claimed by the source or not. LTM first initializes the label of each claim randomly and updates the counters of each source. In each iteration, LTM samples each truth label from its distribution conditioned on all other truth labels, and the source counters are updated accordingly. LTM uses a collapsed Gibbs sampling process with K, the number of iterations required to define the sample size as (K − burnin)/thin. Then, LTM updates the values truth probability in by discarding the first set of samples (burnin parameter) and, for every n samples in the remainder (thin), LTM computes the average to prevent correlation between adjacent samples. Since LTM relies on the random initialization of the truth labels, as well as random sampling, we can not report the precision of one single run. In the original paper, average precision over 10 runs was reported. In our experiment, we reported the average precision over 100 runs because we observed fluctuating results with wide standard deviations over 10 runs. LTM does not compute source truthworthiness which gives an advantage in terms of execution time. Parameter Setting. Nine parameters have to be set in LTM: (K, burnin, thin): the collapsed Gibbs sampling process parameters, α = (α 1,1 , α 1,0 , α 0,1 , α 0,0 ), the prior true/false positive/negative claim counts for the sources, and β = (β 1 , β 0 ), the prior true and false counts for the data item-value pairs. We study the values proposed by the authors for all parameters on the Book data set: varying one parameter and fixing the others successively and we observe: (1) No significant changes in the precision of LTM, neither for (K, burnin, thin) = (50, 10, 1), (500, 100, 9) or (2000, 100, 9) nor for β = (.1, .1) or (.5, .5). (2) For high α 0,1 and α 1,0 (.7 to .9) and low α 0,0 and α 1,1 (.1 to .3), the precision algorithm was low with high standard deviation (±0.32 in average) and minimal precision in the 95% confidence interval over 100 runs. We did not consider this parameter setting for α because of too high variability of precision. (3) For the remaining permutations of α 1,1 , α 1,0 , α 0,1 , and α 0,0 , LTM reaches stability in precision for 100 runs with small 95% confidence intervals (.002 in average) as follows. Finally, we select (K, burnin, thin) = (500, 100, 9), α = (.9, .1, .9, .1) and β = (.1, .1) to get maximal precision average over 100 runs on the Book data set. Maximum Likelihood Estimation (MLE) proposed in 2012 by Wang et al. in [16] is based on the Expectation Maximization (EM) algorithm to quantify the reliability of sources and the correctness of their observations. MLE only deals with Boolean positive observations (e.g., data items such as thisPerson-hasKids with True or False value). Negative observations are ignored. To be able to test MLE on the Book data set, we reformated every claim such as (c1,s,ThisBook:AuthorOf,(AuthorA,AuthorB)) such as two claims: (c1,s,ThisBook:AuthorOf:AuthorA,True) and (c2,s,ThisBook:AuthorOf:AuthorB,True). Algorithm. In Algorithm 2.6, MLE starts with initializing the sources' parameters: a(s), the probability that source s reports a value to be true when its indeed true and b(s), the probability that s reports a value to be true when it is in reality false (similar to source sensitivity α 1,1 and α 1,0 in LTM). In the Expectation step, MLE iteratively computes the conditional probability of a value v to be true based on its source probabilities (a(s), b(s)), and on the probabilities of the sources not providing v (∀s ∈ Sv). Then, it iteratively computes the confidence of each value in . In the Maximization step, MLE updates the sources probabilities a(s) and b(s) in . The Expectation-Maximization steps are repeated until convergence of both a(s) and b(s). An important observation of MLE algorithm is when the number of sources tends to be very large, source probabilities tend to zero and C v tends to 0/0. MLE can not be used with a large number of sources (> 5,000). Parameter Setting. Two parameters are needed in MLE: r and β 1 to compute the initial parameters of the sources, a(s) and b(s). β 1 is the overall prior truth probability of the claims (similarly to LTM). r is the probability that a source provides a value for all data items. In its original paper, MLE is tested on a synthetic data set with no indication on how to set these parameters. So, for the Book data set, we successively vary r and β 1 using a uniform constant value for all sources parameters initialization. Variables Precision, Accuracy, Recall r = .5 for all sources β 1 from .1 to .9 All equal to 1 for β 1 = .5 β 1 = .5 r from .1 to .9 All equal to 1 for r = .5 Finally, we select β 1 = .5 and r = .5 uniformly constant for all sources to get precision, accuracy, and recall equal to 1. [5] and further extended in [6, 4] is the first Bayesian truth detection model that takes into consideration the copying relationships between sources. DE-PEN penalizes the vote count of a source if the source is detected to be a copier of another source. DEPEN is presented with 4 extensions in its original paper [5] . Our study focuses on DEPEN, ACCU, ACCUSIM, and ACCUNODEP: ACCU extends DEPEN model and relaxes the assumption that the sources have the same accuracy and for each data item, all independent sources have no longer the same probability of providing a true value. ACCUSIM extends ACCU to take into account value similarity, and ACCUNODEP assumes that all sources are independent. Algorithm. Algorithm 2.7 presents DEPEN and starts by initializing all sources' truthworthiness to .8. For every data item, it selects the true value by majority voting, and computes the dependence between sources with CompDepen(s i , s j , α, n) function where α is the a priori probability that s i and s j are dependent, and n is the number of false values per data item. To iteratively compute the value confidence in , the sources claiming the considered value are first ordered by their dependence probabilities with orderByDepen(S v ) function. Then, each source's voteCount is computed in a way that minimizes the vote if the source is dependent on other sources in Pre, the list of ranked sources, such as voteCount= s j ∈Pre (1 − c.depen(s,s j )), with c the probability that a value provided by a copier is copied. voteCount is then weighted by t scores , the source's score to compute the value confidence. Source truthworthiness is computed iteratively in as a function of the confidence of all values claimed by the sources. True values are expected to be the values with the highest confidence. In ACCUNODEP, no dependence computation is needed, and voteCount is always 1. In ACCU and ACCUSIM, the algorithm computes value confidence with t scores = ln(nT s /(1 − T s )), whereas in DEPEN, t scores = 1. In ACCUSIM, the value similarity is considered for the confidence computation in each iteration and, ρ v ∈V d C v .sim(v , v) is added to C v (similarly to TRUTHFINDER). It is worth noticing that DEPEN model and its extensions estimate the source voteCount for a given value based on ordering the sources by decreasing dependence probability. This ordering could be different from one run to the next, because two sources with the same dependence probabilities could appear in different positions. We observed that this dependence-based ordering introduced small fluctuations of the quality metrics for 20 executions of the models with the same parameterization on the Book data set. In particular, we observe DEPEN precision (.9814 ± .0002), ACCU precision (.9741 ± .0061) and ACCUSIM precision (.9413 ± .0051). To mitigate this problem, we decided to use the lexical ordering rather than the dependence probability-based ordering of the sources. This sightly improves the quality of the models by +.02 (DEPEN LEX precision .9814, ACCU LEX precision .9809, and ACCUSIM LEX precision 0.973) for the Book data set and it also improves the stability of the results that remain constant from one run to another. Parameter Setting. Fixing ρ = .5 and n = 100, we study various parametrization setting reported in the table. Finally, we select α = .2, T S = .8, c = .8 for DEPEN and ACCUNODEP and c = .1 for ACCU and c = .05 for ACCUSIM.
Waguih et al. REF point out that the sparse ground truth is not statistically signi cant to be legitimately leveraged for the accuracy evaluation and comparison of methods.
Truth Discovery Algorithms: An Experimental Evaluation
ArXiv
ArXiv
Computer Science