A Truth Discovery Approach with Theoretical Guarantee
Houping Xiao*, SUNY Buffalo; Jing Gao, ; Zhaoran Wang, Princeton University; Shiyu Wang, UIUC; Lu Su, SUNY Buffalo; Han Liu, Princeton University
In the information age, people can easily collect information about the same set of entities from multiple sources, among which conﬂicts are inevitable. This leads to an important task, truth discovery, i.e., to identify true facts (truths) via iteratively updating truths and source reliability. However, the convergence to the truths is never discussed in existing work, and thus there is no theoretical guarantee in the results of these truth discovery approaches. In contrast, in this paper we propose a truth discovery approach with theoretical guarantee. We propose a randomized gaussian mixture model (RGMM) to represent multi-source data, where truths are model parameters. We incorporate source bias which captures its reliability degree into RGMM formulation. The truth discovery task is then modeled as seeking the maximum likelihood estimate (MLE) of the truth-s. Based on expectation-maximization (EM) techniques, we propose population-based (i.e., on the limit of inﬁnite data) and sample-based (i.e., on a ﬁnite set of samples) solutions for the MLE. Theoretically, we prove that both solutions are contractive to an ϵ-ball around the MLE, under certain conditions. Experimentally, we evaluate our method on both simulated and real-world datasets. Experimental results show that our method achieves high accuracy in identifying truths with convergence guarantee.
Filed under: Graph Mining and Social Networks