A Survey on Truth Discovery <s> Relations among objects <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> BIB001 </s> A Survey on Truth Discovery <s> Relations among objects <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> BIB002 </s> A Survey on Truth Discovery <s> Relations among objects <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> BIB003 </s> A Survey on Truth Discovery <s> Relations among objects <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> BIB004 </s> A Survey on Truth Discovery <s> Relations among objects <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> BIB005
Most of the truth discovery methods assume that objects are independent. In practice, objects may have relations and could affect each other. For example, "the birth year of a person" has strong relation with "the age of a person", and "A is the father of B" indicates that "B is the son of A". Such prior knowledge or common sense about object relations could improve the results of truth discovery. In BIB001 , prior knowledge is translated into propositional constraints that are integrated into each round of truth discovery process. Specifically, each fact (an object and its corresponding value) is represented as a [0, 1] variable, and then according to the prior knowledge, related facts are combined into propositional constraints. A cost function is defined as the difference between the original results solely based on truth discovery and new results which satisfy the propositional constraints. By minimizing the cost, the probability of each fact to be true is "corrected" according to prior knowledge during each iteration. To guarantee the feasibility of this optimization problem, for each object, an augmented "unknown" answer is incorporated to relax the constraints and avoid the possible conflicts among constraints. In BIB002 , information extraction and truth discovery methods are combined to solve Slot Filling Validation task which aims to determine the credibility of the output information extracted by different systems from different corpora. The authors construct a Multi-dimensional Truth-Finding Model (MTM) which is a heterogeneous network including systems, corpora, extracted information, and weight matrices between them. Similar to the iterative truth discovery process, the credibility of the extracted information is propagated within the network to infer the reliabilities of both systems and corpora, and in turn, the reliabilities of systems and corpora are used to refine the credibility of the extracted information. To initialize the credibility, the authors consider the dependent relationship among different slots (object) by constructing a knowledge graph. For example, "Adam is a child of Mary" should have high credibility if we already believe that "Bob is a child of Mary" and "Adam is a sibling of Bob". Temporal and spatial relations also exist among objects. For example, today's high temperature for New York City has correlation with the one of yesterday, and the nearby segments of roads may have correlated traffic conditions. Such temporal and spatial relations among objects can be captured to benefit truth discovery procedure. Recently,  and BIB003 model the temporal relations among evolving objects on categorical data and continuous data respectively, while BIB004 and BIB005 can handle both temporal and spatial relations on categorical data and continuous data respectively. Further, BIB005 demonstrates that capturing the relations among objects can greatly improve the performance of truth discovery as objects may receive insufficient observations in many real-world applications.