参考文献
来源：VLDB
作者：Xin Luna Dong，Laure Berti-Equille，
Divesh Srivastava
下载地址：
http://lunadong.com/publication/
dependence_vldb.pdf
背景介绍
许多数据管理软件需要集成来自多个源的数据，然而，不同来源经常提供互相冲突的数据，有些是真的，有些是假的。为了向用户提供高质量的数据，数据集成系统需要解决冲突，发现真值。通常情况下，我们认为大多数源提供的数据为真实数据，因此我们可以应用投票把大多数源提供的数据看作真实数据。
不幸的是，数据源之间的互相复制很常见，尤其是在web上。一个数据源提供的值，无论真假，都可以被许多其他数据源复制，正如Vladimir Lenin所说“谎言说多了就变成了事实”。在这种情况下，从冲突的数据中分辨出真实数据变得非常棘手。
图1 丰富多彩的互联网信息来源
本文提出了一种新方法，它考虑了真值发现中数据源之间的依赖关系，该技术不仅考虑了两个源是否共享相同的值，还考虑了共享值的真假。共享相同的值并不一定意味着来源依赖，但是当数据源共享很多相同的假值，就很有可能是互相依赖的。
考虑表1中的五个数据源，它提供了五位研究人员的隶属关系信息，只有S1提供了所有正确数据。但是由于S3提供的隶属关系被S4和S5复制（复制了一些错误信息），简单投票就会认为它们提供的值占多数，因此对三位研究人员给出错误的结果。
表1 五个数据源提供的五位研究人员的隶属关系
数据源依赖检测
假设S由两种类型的数据源组成：独立数据源和抄袭者。我们通过观察他们的数据应用贝叶斯分析去计算S1和S2是独立的概率。我们的计算需要几个参数：n(n>1)，每个对象的基础域中的错误数量；c(0<c≤1)，抄袭者提供的值是抄袭的概率；ε(0≤ε<n/n+1)错误率—独立来源提供假值的概率。我们关注这三组对象：Ot表示S1和S2提供相同真值的对象集合；Of表示他们提供相同假值的对象集合；Od表示他们提供不同值的对象集。通常两个独立来源提供相同的错误值是小概率事件，因此我们固定Ot∪Of和Od，S1和S2提供的共同错误值越多，越可能是互相依赖的。另一方面，如果固定Ot和Of，S1和S2提供的不同值越少，越可能是互相依赖的。我们用Φ观察Ot，Of和Od，用kt，kf和kd分别表示他们的大小。
图2 Of,Ot,Od关系图
我们首先考虑S1和S2是独立的情况，用S1⊥S2表示。由于只有一个真值所以S1和S2为对象O提供相同真值的概率是
在统一错误值分布条件下，数据源为对象O提供假值的概率是ε/n，因此S1和S2为对象O提供相同假值的概率是
S1和S2在对象O上提供不同值的概率为（用Pd表示）
根据独立值假设，Φ的条件概率为
接下来考虑S1和S2依赖的情况，用S1~S2表示。S1和S2为对象O提供相同值有两种情况，第一，有c概率一个来源从另一个来源抄袭了v，所以v有1-ε的可能是真，ε的可能是假；第二，有1-c的概率两个来源独立的提供v，其真假的概率与S1和S2独立的情况相同。因此我们有
最后，S1和S2提供不同值情况下的概率，即S1独立提供值，该值与S2提供的不同
现在我们可以通过贝叶斯计算S1~S2的概率
这里α=Pr(S1∼S2)(0<α<1)是两个数据源的先验概率。
方程（8）有以下几个属性：
1.令kt+kf和kd不变，当kf增加时，依赖的概率增加；
2.令kt+kf+kd不变，当kt+kf增加且kt和kf都没有减少时，依赖的概率增加；
3.令kt和kf不变，当kd减少时，依赖的概率减小。
应用投票计数
我们介绍了如何判断来源是否互相依赖，然而，抄袭者也有可能独立地提供一些值，直接忽略这些值是不合适的。
我们从确定性的知道源之间的依赖关系开始讨论，随后讨论概率性依赖的情况。考虑对象O有一个特定值v，So(v)是提供该值的数据源集合。我们可以画一个依赖图G，对每一个S∈So(v)，都有一个节点，每一个S1，S2∈So(v)且S1抄袭S2，都有一条从S1到S2的边。
对每一个S∈So(v)，我们用d(S,G)表示S的出度，对应于S复制数据源的数量，如果d(S,G)=0，则S是独立的并且其对v的投票计数是1，否则，对于S抄袭的每个源S’，S提供独立于S’的值的概率是1-c。根据独立复制假设，S独立的提供v的概率是
v关于G的总票数为
方程（8）只计算依赖概率而不表示其方向，因此我们必须枚举所有可能的依赖图并根据图的概率加权计算投票计数总和。设Do是可能对So(v)有依赖的数据源集合，我们用p(D)表示D∈Do的概率。考虑一个子集D⊆Do有m个依赖关系，根据独立复制假设，D中的依赖关系概率为
由于每个依赖关系可以具有两种方向，因此存在多达2m个具有这组依赖关系的非循环依赖图。直观来看，图中的独立源越多，图中所有源提供相同值的可能性就越小。通过贝叶斯分析，我们可以计算每个图的概率。
由于存在指数数量的依赖图，通过枚举所有这些投票计数代价很大，为了使分析可拓展，我们找到一种在多项式时间内估计投票计数的方法。我们通过逐个考虑数据来估计投票数，对于每个源S，用Pre(S)表示已经考虑过的源集合，并用Post(S)表示尚未考虑的集合。我们采用贪婪算法并按照这样的顺序考虑数据源：在第一轮中，选择与最高概率相关的数据源；在以后的轮次中，每次选择一个数据源，该数据源最大程度依赖于之前选择的一个源。
现在考虑在确定数据源的顺序后如何计算v的投票数。设S是投票给v的数据源，用P(S~S0)表示源S和S0之间依赖的概率。S独立于Pre(S)中的任何数据源提供v的概率为（由I(S)表示）
投票计数的总票数为
找到真值
一旦我们知道每个值的投票计数，我们就可以通过投票找到真值。但是计算投票计数需要知道数据源之间的依赖关系概率，而计算依赖关系的概率需要知道真值。他们之间存在互相依赖关系，我们通过迭代计算他们来解决问题。迭代的计算每对数据源之间的依赖概率和每个值的投票计数，然后对于每个对象，将最大投票计数的值作为真值，重复此过程直到投票结果收敛。
由于篇幅原因，文章中源精确度计算和实验部分在这里没有详细介绍，有兴趣的同学可以阅读原文进一步了解。
关于 天 方 夜 “谈”
天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。
方班人有自己的浪漫，
我们探讨知识，谈论理想，
采摘科研的繁星，
脚下是星辰大海。
天：代表我们的理想犹如天空般浩荡
方：代表方班
夜：代表代码人的冷静与静谧
谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”
