数据学习
AI博客
原创AI博客
大模型技术博客
期刊会议
学术世界
期刊出版社
领域期刊
SCI/SCIE/SSCI/EI简介
期刊列表
会议列表
所有期刊分区
学术期刊信息检索
JCR期刊分区查询
CiteScore期刊分区查询
中科院期刊分区查询
管理 - UTD24期刊列表
管理 - AJG(ABS)期刊星级查询
管理 - FMS推荐期刊列表
计算机 - CCF推荐期刊会议列表
南大核心(CSSCI)
合工大小核心
合工大大核心
AI资源仓库
AI领域与任务
AI研究机构
AI学术期刊
AI论文快讯
AI数据集
AI开源工具
数据推荐
AI大模型
国产AI大模型生态全览
AI模型概览图
AI模型月报
AI基础大模型
AI大模型排行榜
大模型综合能力排行榜
大模型编程能力排行榜
OpenLLMLeaderboard中国站
AI大模型大全
大模型部署教程
在线聊天大模型列表
2023年度AI产品总结
Crowdsourced Data Management: A Survey
小木
TKDE
2016-09
2511
2017/04/20 20:50:51
[TOC] 任何重要的数据管理和分析任务都无法完全依靠“算法”解决。这些任务,如实体识别、情感分析、图像识别等,都可以通过使用人类的认知能力增强解决方案。众包平台就是一种这样可以获取人类能力的平台。在这篇文章中,作者主要介绍了众包数据管理中的三个重要的问题: > 1. 质量控制(Quality Control):工作者可能会返回不正确的或者噪音数据,我们需要有效的技术来获取高质量的结果。 2. 成本控制(Cost Control):众包并不是免费的,成本控制是一个很重要的问题。 > 3. 延时控制(Latency Control):人工作业可能比较慢,特别是相比较计算机而言,因此,延时控制技术很有必要。 ------------ 此外,众包数据管理还涉及到一些重要的操作:任务设计、众包操作设计和最优化。我们将先简单的介绍这些内容。
![](http://www.datalearner.com/resources/blog_images/922f1749-9063-4d1d-820d-8843f5e8d2d6.png)
#### 一、任务设计 ##### 1.1 任务类型 在实际中,任务的类型主要包括如下几种: 1. 单选:工作者从多个选项中选择一个正确的结果。 2. 多选:工作者从多个选项中选择不定数量的正确结果。 3. 评分:工作者对多个对象进行评分,如对餐馆打分。 4. 聚类:工作者将多个不同的对象分到几组中。 5. 标注:工作者为每个对象提供一个标签,如图像描述的物体等。 ##### 1.2 任务设定 任务的 设计主要考虑三个方面: ###### 1.2.1 定价 通常价格都是在几美分到几美元之间。定价是一个非常复杂的博弈问题,通常情况下,高价格可以吸引更多的人来工作,从而减少延时,但是却不能显著提高回答的质量。 ###### 1.2.2 时间设定 我们可以对任务进行时间限制,对于每个任务要限制时间。 ###### 1.2.3 质量控制 我们可以通过众包平台来进行质量控制,也可以自己设计质量控制的方法。后面我们会详细讨论。 #### 二、质量控制 从众包平台中获取结果通常是不一致且容易混淆的。现有的研究提出了很多种方法来解决这个问题。最基本的模型是使用某种工作者模型(worker model)来为用户建模,并采取多种质量控制策略进行质量控制,如去除低质量用户或者是欺诈者等,讲每项任务分配给多个工作者,然后聚合结果等。 ##### 2.1 工作者(用户)建模 质量控制的第一步就是对工作者将进行建模。在这里我们主要讨论两部分内容,一个是工作者建模,另一个是计算模型参数的方法。 ###### 2.1.1 工作者(用户)建模 现有的工作已经有了很多的方法来为工作者的质量进行建模,我们总结如下: **工作者概率模型:**在这类模型中,工作者通常用一个参数$q\in [0,1]$来建模,这就是工作者回答正确的概率,即: ```math q = \text{Pr(the worker's answer = taks's true answer)} ``` 比如说,如果某个工作者有70%的可能性回答出正确的答案,那么模型中,该用户的参数就是$q=0.7$。由于$q$是一个概率,因此有两种拓展方式: 1)以更广的范围代替,即它的范围不再是[0,1],而是$(-\infty,\infty)$。值越高,表明这个用户越有可能选择一个正确的结果。 2)信任,即引入一个新的参数“置信区间”来表明这个工作者的参数的信任程度为多少。一般情况下,工作者回答的问题越多,关于工作者参数$q$的信任度就越高。 **混淆矩阵:**混淆矩阵通常是在单选任务(比如从$l$个可能的结果中选择一个)中使用的。例如,一项情感分析的任务是告诉工作者从一个给定的语句中选择正确的情感倾向(正向/负向/中立)。那么这个答案就包含三种可能。那么这个混淆矩阵就是一个$3 \times 3$的矩阵: ```math Q=\left[ \begin{matrix} Q_{1,1}& Q_{1,2} & \cdots & Q_{1,l} \\ Q_{2,1}& Q_{2,2} & \cdots & Q_{2,l} \\ Q_{3,1}& Q_{3,2} & \cdots & Q_{3,l} \end{matrix} \right] ``` 这里,第j行表示成$Q\_{j}=[Q\_{j,1},Q\_{j,1},\cdots,Q\_{j,l}]$,其含义是当正确答案是第j个答案的时候,回答者回答的各种结果的概率。因此,$Q\_{j,k}$表示正确答案是j的时候,回答者回答结果是k的概率。即: ```math \text{Pr(the worker's answer is k} \space|\space \text{task's true answer is j)} ``` **偏差与方差:**偏差与方差是两个统计参数,用来刻画工作者做定量任务的能力。定量任务一般是问用户一些定量的问题,而不是一些预先定义的答案,比如数出图片中鸟的个数。偏差,一般表示成$\varepsilon \in (-\infty,\infty)$,表示一个工作者的平均估计错误。比如,一个工作者通常会高估某个数量,那么$\varepsilon > 0$,否则$\varepsilon < 0$。方差,通常表示成$\sigma^2 \in [0,\infty)$,表示偏差附近的波动。比如,某个任务的真实数量为$t$,某个工作者的标注结果服从一个高斯分布$o \sim N(t+\varepsilon , \sigma^2)$。 **跨任务的多技巧:**一个工作者在不同的任务下可能准确率不一样。比如某些工作者可能在回答关于“书”的问题的时候准确率较高,但是在“减肥”方面的能力较弱。因此,又坐着提出不同的工作者在不同的任务下应当有不同的准确率,即有一个参数向量$\bar{q}=[q_1,\cdots,q_n]$,这里的$n$表示任务的数量,其中$q_i \in [0,1]$。 **跨领域的多技巧:**与上一个方案不同,这个方案强调不同的工作者在不同领域的能力不同。假设我们有$n=100$个翻译任务,其中20个是从德语到英语,剩下的是法语到汉语。这个例子中,有$K=2$个领域,一般情况下,一个工作者的能力$\bar{q}$是由K维向量构成。即只能表征用户在某个领域下的工作能力。 ###### 2.1.2 工作者模型参数的计算 推断以上模型的参数主要包括几大类方法。 **质量检测:**质量检测包括一组金牌任务(知道正确答案的任务)。工作者必须通过质量检测之后才能回答真正的问题。基于工作者的回答,我们可以得出工作者质量。 **黄金注入法:**黄金注入法将金牌任务与普通任务混合到一起,基于用户对金牌任务的回答情况来推测用户的质量。 **基于EM的方法:**基于EM的算法利用了所有工作者对所有任务的回答结果,采用迭代的方式计算每个工作者的质量参数和每项任务的真实答案,直至收敛。这个方法的直觉是经常给出正确答案的工作者通常会被给予更高的质量参数,该用户给的答案一般也会被更可能选定为真实答案。一般情况下EM算法都是两步。举个例子来说,比如隐变量包含了每项任务的真实答案的概率分布以及包含工作者质量的参数、先验等。在E步骤,我们将根据工作者质量和先验知识来计算每项任务的真实答案;而在M步中,我们则基于每个任务的真实答案来计算工作者的质量和先验参数。 **基于图的方法:**基于图的方法是把每个工作者当做是一个节点,然后使用图模型推断工作者模型。比如有些工作将工作者和任务当做是二部图,并突出概念传播算法推导工作者模型参数。 ##### 2.2、工作者消除 工作者消除是根据工作者模型消除低质量的工作者或者是欺诈者,是一个非常常见的提升质量的策略。工作者消除有很多方法,一个简单的方法是使用质量检测或者黄金注入法。比如,在一个工作者回答真实任务之前,工作者必须要通过质量测试。基于工作者对黄金任务的回答,回答者质量就可以计算了。也有一些专门的欺诈者侦测算法是基于更复杂的工作者模型。 ##### 2.3、答案聚合 由于单个用户具有一定的偏差,大部分工作任务都被选择很多用户同时进行解答。然后从这些工作者中推断任务的真实答案。特别地,投票策略可以被看成是一个函数,有两个输入参数:1)任务的答案;2)每个工作者的质量。输出是推断的任务结果。典型的投票策略包括:取多数结果,加权取多数结果,贝叶斯投票等。 第一种方式很简单,就是取获取票数最多的结果。比如,有个问题:IBM是否就是“深蓝”,三个回答者(质量分别为0.2,0.6,0.9)的答案是“是”,“是”和“否”。那么第一种策略就是改答案是“是”(该选项得票最多)。第二种策略是选择“否”。因为每个回答者质量不同,回答“是”的工作者的权重之和是0.8,小于0.9。贝叶斯投票就是利用贝叶斯公式来计算真实答案的概率分布。在这个例子中,假设每均匀先验,则有: ```math \text{Pr(true answer is Yes)} \propto 0.2 \times 0.6 \times (1-0.9) = 0.012 ``` ```math \text{Pr(true answer is No)} \propto (1-0.2) \times (1-0.6) \times 0.9 = 0.288 ``` 通过正规化之后我们知道贝叶斯投票策略返回的是“否”。根据答案结果是否是随机的,有研究者将投票策略分成确定性投票策略和随即投票策略。研究显示,**随机投票策略可能会提高错误案例分析的误差范围**。 ##### 2.4、任务分配 由于每个工作者的质量在不同任务下不同,更好的任务分配策略可以提高结果。现有的工作主要包括两类:1)基于工作者的分配策略,即分配一个工作者子集给各个任务。2)基于任务的,即对每个工作者分配一个任务子集; 在基于工作者的分配场景中,给定一个任务和一组工作者,直觉上具有较高质量的工作者应当被分配到这个任务上。此外,还有成本的因素需要考虑。每个工作者的成本可以通过工作者自己提出,也可以通过工作者的信息学习得到(如注册日期,学历等)。考虑工作者预算,Cao等提出了“Jury选择问题”: > 给定一个任务,一组工作者(质量与成本已知)和所有的预算,如何选择一组工作者子集然后最大化任务质量,但不超过预算。 为了解决这个问题,Cao提出首先在给定的工作者子集情况下计算质量,称为“Jury质量”(JQ)。为了描述一个工作者的质量,我们可以使用类似工作者质量这种模型,实际上定义JQ就是定一个投票策略: > 给定已知质量的一组工作者,如何计算JQ,即用户返回正确结果的概率? 注意到工作者的答案是未知的,为了解决这个问题,我们需要考虑工作者答案的所有可能。Zheng等人证明了在给定JQ的定义下使用贝叶斯投票策略是一种最优策略。它要不差于任何一种策略。同时,也有人证明计算贝叶斯投票策略的JQ是一个NP难问题。为了减少计算的复杂度,他们提出了一个$O(|S|^3)$复杂度的近似算法,能保持误差在1%内。 而在基于任务的场景中,每当一个工作者来临的时候,现有的工作都要选择出一组最有信息的任务是当前工作者能获取最好的结果。这个问题的定义为: > 给定n个任务,当一个工作者来临的时候,哪k个任务应当被分配给当前的工作者? 当一个工作者来临的时候,我们从收集的答案中计算每项任务的不确定性。有很多种方法可以计算不确定性。Liu等人使用了一个质量敏感的答案模型来定义用户的不确定性。而Zheng等人则发现不同的众包应用可能有不同的质量定义方法。一个众包应用首先要定义一个质量矩阵(如准确性、F值等)来优化。为了满足这个条件,一个分配算法可以决定哪些任务要被分配到当前工作者上。 #### 三、成本控制 尽管众包平台的有效性证明了众包的低成本,但成本依然是一个重要的问题。因此众包数据管理的一个重要问题就是如何保证质量的前提下进行成本控制。这一节,作者会介绍五种成本控制方法。 **修剪(Pruning):**第一种方法是使用计算机算法去除不需要人工检查的任务。这项技术的出发点是,很多情况下有很多任务计算机都是可以完成的,我们可以使用人工来完成最有挑战性的任务。这种思想广泛运用在众包连接和搜索任务中。比如,很多搜索连接算法都是用系一个基于计算机的技术,叫相似性连接,去掉相似性低于一定值的结果。但这个方法一个风险就是可能剪枝算法有问题,这样就把一些计算机不好处理的任务交给算法了。 **任务选择(Task Selection):**任务选择在前面的内容中已经提到过,它可以用来提高众包的质量。但是从另一个角度看,它也可以用来降低成本。 **减少答案(Answer Deduction):**在有些情况下,众包的任务是有内在联系的。特别的,给定一组任务,当我们从工作者那里获得答案之后,我们可以使用这些信息来推断其它任务的一些答案,节省成本。 **抽样(Sampling):**基于抽样的策略就是让工作者只回答数据样本的问题,这种情况经常发生在数据清理的任务中。 **混杂方法(Miscellaneous):**还有些方法是专门为某些任务设计的。这里就不展开说了。 #### 四、延时控制 为了控制时间问题,通常的做法是提高任务的价格,一般情况下,更高的价格可以吸引更高的工作者,减少完成任务的时间。因此,一般性的做法可以采用动态定价的方法,紧急的任务采用更高的价格。 #### 五、众包运营 为了提高实际的运用,有很多的众包运营方式。很多技术都被用于在成本、质量和延时之间进行权衡。如下图所示,作者列出了所有的运营方法。
![](http://www.datalearner.com/resources/blog_images/7f45d7b2-418b-42fb-a188-fc37818dc65f.png)
##### 5.4 Top-K与排序 给定一组项目$O = { o\_1,\cdots,o\_n }$,其中的项目是可比较的但是算法可能很难比较,top-k的任务就是选择k个项目$R={ o\_1,\cdots,o\_k}$。 ###### 5.4.1 工作流 为了让工作者可以找出top-k的项目,我们需要产生一些任务。产生任务的方式有两种。第一种是用单选的方式,第二种是评分的方式。第一种是两两比较,选择好的,第二种是给每个项目一个分数。第二种方法有一些缺点,首先它比第一种要复杂,工作者压力较大,其次工作者也比较难给出准确的评分,不同评分组的项目不好比较。因此基于评分的方法通常准确率较低。 **成对比较:**成对比较采用单选任务类型,每个任务比较两个项目。为了降低成本,现有的方法使用一种选择策略,其中每轮任务有b组成对的词语比较。基于众包的比较结果决定下一轮比较的b组词。为了减少众包错误,每个任务都被赋给好几个工作者,最终的结果可以按照如基于权重的投票策略来聚合答案。为了给结果建模,可以使用有向图模型,节点是项目,边是聚合的比较答案。对于每个项目对$(o_i,o_j)$,如果聚合的结果是$o_i \succ o_j $,那么就从$o_i$到$o_j$连个边,权重就是聚合的偏好结果。 **结果推断:**给定任务的结果,结果推断主要就是为了推断查询结果,即top-k的项目集合或者一个排序列表。总共有五种方法:1)基于得分的方法;2)循环降低方法;3)机器学习方法;4)基于堆的方法;5)混合方法。 1)基于得分的方法:研究者已经证明以最大的概率寻找top-1项目是一个NP难问题。因此,推断top-k的问题也是一个NP难问题。一些基于得分的方法提出来以一个分数$s_i$赋给每个项目$o_i$,并以最大的得分结果选出top-k的项目。下面,我们说一说如何赋给项目这些分数。 **BordaCount**:项目$o_i$的得分是其出度。 **Copeland**:项目$o_i$的得分是其出度减去入读。 **Local**:上述两个方法仅仅考虑了每个项目的邻居节点,局部top-k算法则是考虑2跳邻居,因此项目有一个更大的得分。 **入度**:该模型则是基于贝叶斯模型计算项目的得分。它在给定聚合偏好的情况下,计算概率$o_i \succ o_j$,然后使用该概率来计算得分。 **修改的PageRank**:它通过考虑众包的比较结果扩展了原始的PageRank算法。 **RankCentrality**:基于随机游走的项目得分计算。 **ELO**:这是一个棋牌排序系统,可以用来计算$s_i$的得分。 2)迭代降低算法 迭代降低算法不停地消除在top-k中概率低的项目,直到只有k个项目为止。 **迭代式**:它首先使用基于得分的模型计算每个项目的分数,然后把最低得分的一半项目去除。然后再次计算直到只剩k个项目。 **PathRank**:PathRank的主要思想对每个节点进行“反”深度有限搜索,它通过遍历每个节点内部邻居来反转图。如果它可以发现一个条路径,其长度大于k,它就消除这些项目。 **AdaptiveReduce**:开始的时候有n个项目。然后它选择一个信息集合并在top-k个答案中使用这个集合消除较低概率的项目。重复这个步骤直到找到top-k个项目。 3)机器学习方法 这类方法假设每个项目有一个潜在的得分,它服从一个分布。然后他们使用机器学习技术来估计这个得分。最终他们使用这个潜在的得分排序项目并获取top-k算法。 4)基于堆的方法 #### 六、众包优化和系统 #### 七、众包平台 #### 八、研究挑战
赏
支付宝扫码打赏
如果文章对您有帮助,欢迎打赏鼓励作者
Back to Top