Learning the truth vector in high dimensions
Learning the truth vector in high dimensions
复制标题
DOI：
10.1016/j.jcss.2019.12.002
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Hu Ding;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Hu Ding;Jinhui Xu
真相发现是数据分析相关领域中出现的一个重要的学习问题。它涉及从从许多不可靠来源获取的数据集中找到最值得信赖的信息。这个问题已经被广泛研究，并且已经提出了许多技术。然而，所有这些都是启发式的，没有任何质量保证。在本文中，我们将该问题表述为高维几何优化问题，称为基于熵的几何方差。依靠一些新颖的几何技术，我们进一步发现了这个问题的新见解。我们首次表明，真相发现问题可以通过保证解决方案的质量来解决。特别是，在一些合理的假设下，可以在近线性时间内实现 (1+ ϵ) 近似。我们希望我们的算法对其他数据相关的应用程序有用。
Truth Discovery is an important learning problem arising in data analytics related fields. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. The problem has been extensively studied and a number of techniques have already been proposed. However, all of them are of heuristic nature and do not have any quality guarantee. In this paper, we formulate the problem as a high dimensional geometric optimization problem, called Entropy based Geometric Variance. Relying on a number of novel geometric techniques, we further discover new insights to this problem. We show, for the first time, that the truth discovery problem can be solved with guaranteed quality of solution. Particularly, it is possible to achieve a (1+ ϵ)-approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications.