A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> Modern information management applications often require integrating data from a variety of data sources, some of which may copy or buy data from other sources. When these data sources model a dynamically changing world (e.g., people's contact information changes over time, restaurants open and go out of business), sources often provide out-of-date data. Errors can also creep into data when sources are updated often. Given out-of-date and erroneous data provided by different, possibly dependent, sources, it is challenging for data integration systems to provide the true values. Straightforward ways to resolve such inconsistencies (e.g., voting) may lead to noisy results, often with detrimental consequences. ::: ::: In this paper, we study the problem of finding true values and determining the copying relationship between sources, when the update history of the sources is known. We model the quality of sources over time by their coverage, exactness and freshness. Based on these measures, we conduct a probabilistic analysis. First, we develop a Hidden Markov Model that decides whether a source is a copier of another source and identifies the specific moments at which it copies. Second, we develop a Bayesian model that aggregates information from the sources to decide the true value for a data item, and the evolution of the true values over time. Experimental results on both real-world and synthetic data show high accuracy and scalability of our techniques. <s> BIB001 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> Although much work in NLP has focused on simply determining what a document means, we also must know whether or not to believe it. Fact-finding algorithms attempt to identify the "truth" among competing claims in a corpus, but fail to take advantage of the user's prior knowledge and presume that truth itself is universal and objective rather than subjective. We introduce a framework for incorporating prior knowledge into any fact-finding algorithm, expressing both general "common-sense" reasoning and specific facts already known to the user as first-order logic and translating this into a tractable linear program. As our results show, this approach scales well to even large problems, both reducing error and allowing the system to determine truth respective to the user rather than the majority. Additionally, we introduce three new fact-finding algorithms capable of outperforming existing fact-finders in many of our experiments. <s> BIB002 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> This paper presents a streaming approach to solve the truth estimation problem in crowdsourcing applications. We consider a category of crowdsourcing applications where a group of individuals volunteer (or are recruited to) share certain observations or measurements about the physical world. Examples include reporting locations of gas stations that remain operational after a natural disaster or reporting locations of potholes on city streets. We call such applications social sensing. Ascertaining the correctness of reported observations is a key challenge in such applications, referred to as the truth estimation problem. This problem is made difficult by the fact that the reliability of individual sources is usually unknown a priori, since any concerned citizen may, in principle, participate. Moreover, the timescales of crowdsourcing campaigns of interest can be as small as a few hours or days, which does not offer enough history for a reputation system to converge. Instead, recent prior work, including our own, developed fact-finding algorithms to solve this problem by iteratively assessing the credibility of sources and their claims in the absence of reputation scores. Such algorithms, however, operate on the entire dataset of reported observations in a batch fashion, which makes them less suited to applications where new observations arrive continually. In this paper, we describe a streaming fact-finder that recursively updates previous estimates based on new data. The recursive algorithm solves an expectation maximization (EM) problem to determine the odds of correctness of different observations. We compare the performance of our recursive EM algorithm to a batch EM algorithm, as well as to several state-of-art fact-finders through extensive simulations. We also demonstrate convergence of the recursive algorithm to the results of the batch version through a real social sensing experiment. Our evaluation shows that the proposed approach can process data streams much more efficiently while keeping the truth estimation accuracy close to that of the (much slower) batch algorithm. Ours is therefore the first fact-finder developed with explicit consideration to the continuous update needs of crowd-sourcing applications. <s> BIB003 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> The task of data fusion is to identify the true values of data items (e.g., the true date of birth for Tom Cruise) among multiple observed values drawn from different sources (e.g., Web sites) of varying (and unknown) reliability. A recent survey [20] 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: 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. <s> BIB004 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> Information Extraction using multiple information sources and systems is beneficial due to multisource/system consolidation and challenging due to the resulting inconsistency and redundancy. We integrate IE and truth-finding research and present a novel unsupervised multi-dimensional truth finding framework which incorporates signals from multiple sources, multiple systems and multiple pieces of evidence by knowledge graph construction through multi-layer deep linguistic analysis. Experiments on the case study of Slot Filling Validation demonstrate that our approach can find truths accurately (9.4% higher F-score than supervised methods) and efficiently (finding 90% truths with only one half the cost of a baseline without credibility estimation). <s> BIB005 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> Recent years have witnessed a proliferation of large-scale knowledge bases, including Wikipedia, Freebase, YAGO, Microsoft's Satori, and Google's Knowledge Graph. To increase the scale even further, we need to explore automatic methods for constructing knowledge bases. Previous approaches have primarily focused on text-based extraction, which can be very noisy. Here we introduce Knowledge Vault, a Web-scale probabilistic knowledge base that combines extractions from Web content (obtained via analysis of text, tabular data, page structure, and human annotations) with prior knowledge derived from existing knowledge repositories. We employ supervised machine learning methods for fusing these distinct information sources. The Knowledge Vault is substantially bigger than any previously published structured knowledge repository, and features a probabilistic inference system that computes calibrated probabilities of fact correctness. We report the results of multiple studies that explore the relative utility of the different information sources and extraction methods. <s> BIB006 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> Truth discovery is a long-standing problem for assessing the validity of information from various data sources that may provide different and conflicting information. With the increasing prominence of data streams arising in a wide range of applications such as weather forecast and stock price prediction, effective techniques for truth discovery in data streams are demanded. However, existing work mainly focuses on truth discovery in the context of static databases, which is not applicable in applications involving streaming data. This motivates us to develop new techniques to tackle the problem of truth discovery in data streams. In this paper, we propose a probabilistic model that transforms the problem of truth discovery over data streams into a probabilistic inference problem. We first design a streaming algorithm that infers the truth as well as source quality in real time. Then, we develop a one-pass algorithm, in which the inference of source quality is proved to be convergent and the accuracy is further improved. We conducted extensive experiments on real datasets which verify both the efficiency and accuracy of our methods for truth discovery in data streams. <s> BIB007 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> With the popular usage of mobile devices and smartphones, crowd sensing becomes pervasive in real life when human acts as sensors to report their observations about entities. For the same entity, users may report conflicting information, and thus it is important to identify the true information and the reliable users. This task, referred to as truth discovery, has recently attracted much attention. Existing work typically assumes independence among entities. However, correlations among entities are commonly observed in many applications. Such correlation information is crucial in the truth discovery task. When entities are not observed by enough reliable users, it is impossible to obtain true information. In such cases, it is important to propagate trustworthy information from correlated entities that have been observed by reliable users. We formulate the task of truth discovery on correlated entities as an optimization problem in which both truths and user reliability are modeled as variables. The correlation among entities adds to the difficulty of solving this problem. In light of the challenge, we propose both sequential and parallel solutions. In the sequential solution, we partition entities into disjoint independent sets and derive iterative approaches based on block coordinate descent. In the parallel solution, we adapt the solution to MapReduce programming model, which can be executed on Hadoop clusters. Experiments on real-world crowd sensing applications show the advantages of the proposed method on discovering truths from conflicting information reported on correlated entities. <s> BIB008 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> The proliferation of mobile sensing and communication devices in the possession of the average individual generated much recent interest in social sensing applications. Significant advances were made on the problem of uncovering ground truth from observations made by participants of unknown reliability. The problem, also called fact-finding commonly arises in applications where unvetted individuals may opt in to report phenomena of interest. For example, reliability of individuals might be unknown when they can join a participatory sensing campaign simply by downloading a smartphone app. This paper extends past social sensing literature by offering a scalable approach for exploiting dependencies between observed variables to increase fact-finding accuracy. Prior work assumed that reported facts are independent, or incurred exponential complexity when dependencies were present. In contrast, this paper presents the first scalable approach for accommodating dependency graphs between observed states. The approach is tested using real-life data collected in the aftermath of hurricane Sandy on availability of gas, food, and medical supplies, as well as extensive simulations. Evaluation shows that combining expected correlation graphs (of outages) with reported observations of unknown reliability, results in a much more reliable reconstruction of ground truth from the noisy social sensing data. We also show that correlation graphs can help test hypotheses regarding underlying causes, when different hypotheses are associated with different correlation patterns. For example, an observed outage profile can be attributed to a supplier outage or to excessive local demand. The two differ in expected correlations in observed outages, enabling joint identification of both the actual outages and their underlying causes. <s> BIB009 </s> A Survey on Truth Discovery <s> FUTURE DIRECTIONS <s> In the era of big data, information regarding the same objects can be collected from increasingly more sources. Unfortunately, there usually exist conflicts among the information coming from different sources. To tackle this challenge, truth discovery, i.e., to integrate multi-source noisy information by estimating the reliability of each source, has emerged as a hot topic. In many real world applications, however, the information may come sequentially, and as a consequence, the truth of objects as well as the reliability of sources may be dynamically evolving. Existing truth discovery methods, unfortunately, cannot handle such scenarios. To address this problem, we investigate the temporal relations among both object truths and source reliability, and propose an incremental truth discovery framework that can dynamically update object truths and source weights upon the arrival of new data. Theoretical analysis is provided to show that the proposed method is guaranteed to converge at a fast rate. The experiments on three real world applications and a set of synthetic data demonstrate the advantages of the proposed method over state-of-the-art truth discovery methods. <s> BIB010
Although various methods have been proposed, for truth discovery task, there are still many important problems to explore. Here we discuss some future directions of truth discovery. • Unstructured data. For most of the truth discovery approaches, they assume that the inputs are available as structured data. Nowadays, more and more applications of truth discovery are dealing with unstructured data such as text. In BIB004 BIB005 , the inaccurate information can come from both text corpora and information extractors, i.e., two layers of sources. If the object difficulty is also considered, the penalty of wrong information should be distributed to three factors, corpora, extractors, and objects. This brings new challenges to source weight estimation. Further, the extracted inputs from unstructured data are much more noisy and also bring new information (uncertainty BIB002 , evidence BIB005 , etc.) to be taken into consideration. • Object relations. For most of the truth discovery approaches, they assume that objects are independent with each other. However, more and more application scenarios reveal the importance of capturing the relations among objects. In knowledge graph BIB006 , objects can be related in various ways, such as "the birth year of a person" and "the age of a person". Although some efforts BIB008 BIB002 BIB009 have been made to consider the object relations, this problem needs more explorations. A more difficult question is to automatically discover relations among objects. Due to the large scale of the involved objects, it is impossible to manually detect and encode such relations. • Source reliability initialization. Some potential disadvantages are observed on truth discovery with uniform weight initialization: (1) At the beginning of the iterative solutions, the behavior of truth discovery is identical to voting/averaging, and thus truth discovery randomly chooses outputs for tie cases. If the ways of breaking ties are different, the estimated source weights may be quite different. (2) The uniform weight initialization leads to the phenomenon that the aggregated results of truth discovery methods rely on the majority to a certain extent. Nowadays, truth discovery has been applied in more difficult tasks such as slot filling BIB005 , in which the majority of sources provide inaccurate information. Thus the performance of truth discovery may suffer from the uniform weight initialization on these tasks. These disadvantages motivate people to investigate new ways to initialize the source reliability. • Model selection. Given various truth discovery methods, how to select an appropriate one to apply to some specific tasks? Although we compare them from different aspects and give some guidelines in previous section, it is still a difficult task. Is it possible to apply various truth discovery methods together, and then combine the outputs of various methods as final output? This ensemble approach might be a possible solution to tackle the model selection challenge. • Theoretical analysis. Will the truth discovery methods promise convergence? If so, what is the rate of convergence and is it possible to bound the errors of converged results? These and many more questions need further exploration. Another interesting task is to explore the relations or even the equivalence among various truth discovery approaches. In Section 2, we show some evidences that different ways to capture the general principle are equivalent. We may better understand the relations among different truth discovery methods by exploring the equivalence among them. • Efficiency. Most of the existing truth discovery methods adopt iterative procedure to estimate source reliabilities and compute truths. This might be inefficient in practice, especially when we apply truth discovery on large-scale datasets. Some attentions have been given to the efficiency issue in streaming data scenarios BIB001 BIB010 BIB003 BIB007 . However, more efforts are needed to improve the efficiency of truth discovery for general cases. • Performance evaluation. In the current research work about truth discovery, the groundtruth information is assumed to be available for the purpose of per-formance evaluation. Unfortunately, in practice, we cannot make this assumption. For example, in the task of knowledge graph construction BIB006 , the number of involved objects is huge and it is impossible to have the groundtruths for performance validation. It requires expensive human efforts to get even a small set of labeled groundtruths. How to evaluate the performance of various truth discovery methods when the groundtruth information is missing? This becomes a big challenge for the truth discovery applications.