基于投票一致性的众包质量评估策略岳德君

1、()Vo l 35，No 8 Aug 2 0 1 4第35 卷第8 期2014 年 8 月东 北 大 学 学 报自 然 科 学 版Journal of Northeastern University( Natural Science)doi: 10 3969 / j issn 10053026 2014 08 008基于投票一致性的众包质量评估策略1 ，于戈1 ，申德荣1 ，2( 1. 东北大学科学与，辽宁 沈阳 110819; 2.刑事学院 计算机系，辽宁 沈阳 110035)摘要: 提出一种基于投票一致性的工作者严动态评估策略，将众包任务集合划分为多个任务子集，每个任务子集看作一个工作阶段

2、 在任意工作阶段结束后，通过工作者投票的数量，以及工作者与工作组投票值一致的投票数量，对工作者的严进行评估，从而检测出不合格的工作者 然后对不合格的工作者进行动态替换，从而保证工作组的正确率满足任务的精度阈值 通过对三种真实数据集进行实验测试，证明本文提出的工作者质量动态评估和替换策略具有较效果:号:众包; 投票; 一致性; 质量评估; 动态替换文献标志码: A文章编号: 1005 3026( 2014) 08 1097 05TP 311. 13Crowdsourcing Quality Evaluation Strategies Based on VotingConsistencyYUE D

3、e-jun1 ，YU Ge1 ，SHEN De-rong1 ，YU Xiao-cong2( 1. School of Information Science Engineering， Northeastern University， Shenyang 110819，;2. Department of Computer Crime Detection，College， Shenyang 110035，CriminalCorresponding author: YUE De jun，: yuedejun ise neu edu cn)Abstract: A dynamic evaluation s

4、trategy for the worker precision based on the voting consistency is proposed The crowdsourcing task set is divided into multiple task subsets and each of them is regarded as a task phase When a task phase is finished，the whole votes and the number of the workers voting value agreeing with the workin

5、g groups one are recorded Then，the workers precision is evaluated and the unqualified workers are detected All the unqualified workers are dynamically replaced to ensure that the correct rate of the group exceeds the task accuracy threshold The effectiveness of the proposed method is evaluated using

6、 three real-w orld datasets， which shows that the method can achieve good performanceKey words: crowdsourcing; voting; consistency;quality evaluation; dynamical replacement众包是一种分布式的问题解决模式和生产模 式，工作需求者( requester) 将工作分配出去，工作者( worker) 利用业余时间完成这些零散的工作，估从而保证工作质量是当前众包研究领域中的热点问题为了保证任务的精度，现有众包应用中往往策略，一种是基于

7、黄金标准机同时可以收取一定的 由于工作者是采用自采用两种质量的策略1 3，另一由组织的工作形式，工作质量参差不齐较大制( goldenstandard mechanism)的不确定性: 一方面，有些工作者工作懈怠，随机甚至 回答问题; 另一方面，对于某些特定的任务需求，很多工作者没有特殊的专业背景，很难完种是基于投票一致性(略4 5voting consistency)的策第一种策略通常设计一些具有标准的问成任务的指标 因此，如何对工作者严进行评题，将这些问题在任务开始前或者在任务进行过收稿日期: 基金项目:2013 10 30教育部高等学校博士学科点专项科研基金资助项目( 201200421

8、10028 ) ;重点基础研究发展计划项目 ( 2012CB316201) ; 教育部 英特尔资助项目( 61033007，61003060) 专项科研基金资助项目( MOE INTEL2012 06) ;自然科学基金作者简介:( 1983 ) ，男，山东枣庄人，东北大学博士研究生; 于 戈( 1962 ) ，男，辽宁大连人，东北大学教授，博士生导师; 申德荣( 1964 ) ，女，辽宁铁岭人，东北大学教授，博士生导师东北大学学报( 自然科学版)第 35 卷1098交由工作者回答，根据答题结果对工作者严的工作者数量定义 7工作组正确率( group进行评估，进而通过机器学习的correct r

9、ate) :获得任务的最终结果6 投票一致性策略是将一个任务工作组正确率 GC( Gn ) 表示工作组中超过半数以上的工作者能够正确回答任务 t 的概率，即分配给多个工作者回答，然后将通过投(Gn ) =票方式进行整合，将大多数的意见作为最终的正确结果 由于基于黄金标准机制的策略除了任务本身之外还需要设计一些标准问题，额外增加了时间和佣金的开销，在实际应用中有很大的局限性 本文主要研究基于投票一致性的质量评估策略在当前的众包应用中，基于一致性的投票策略往往采用静态处理方式，无论工作者在执行任务过 表现如何，不再对工作者进行调整，直至任务结束 本文研究一种动态的处理方式，对工作n + 1 2GC

10、( Gn ) = Pr ()C( pi ( 1 p j ) ) wiU wjU| U| n+12其中 U 是 G n 的子集，代表回答正确的工作者集合工作组正确率可以通过文献5中的动态规划进行计算定义 8工作阶段( task phase) : 将任务集合划分为多个任务子集，每个子集看作一个工作阶段，包含 m 个任务，在每一工作阶段结束后对工者严进行动态评估不同任务类型的精作者严进行评估度需求，及时替换不合格的工作者本文要解决的问题是: 给定工作者集合 W、任务集合 T，以及任务精度阈值 ，假设工作组大小 n 确定; 为了保证 GC( G n ) ，在任意工作相关概念的问题的提出1阶段结束后，如

11、何对工作者严并替换不合格的工作者进行动态评估本文重点研究众包应用中工作者的动态质量模型简化，假设众包任务评估和替换策略均为二元问题，工作者仅需回答“是”或者“否”;采用简单多数投票原则，即超过半数的投票值作为最终结果 下面给出相关的模型定义定义 1 任务( task) : 任务 t 为二元问题( t T) ，T 代表任务集合，工作者对 t 的投票值 v 为 0或者 1定义 2 工作者( worker) : 工作者 w( wW)对给定的任务 t 进行投票，W 代表工作者集合，投票值 v( w) 的结果为 0 或者 1定义3 工作组( group) : 工作组Gn 包含n 个工作者，对于任意任务

12、t，由工作组中所有的工作者 回答，通过投票确定最终的结果 v( Gn) 定义 4 简单多数投票( simple majority voting) : 假设工作组 Gn = w1 ，w2 ，wn ( n 为奇数) ，对于任务 t，每个工作者的投票值为( v( w1 ) ，v( w2 ) ，工作者的动态评估和替换策略2工作组正确率的计算2. 1G n = w1 ，w2 ，w n ( n给定工作组数) ，工作者严为奇为( p1 ，p2 ，p n ) ，工作组正确率可以采用动态规划的5进行计算:Pr ( CLG n ) = Pr ( CLG n ) Pn +( 5)Pr( CL其中G n 1 ) (

13、1 pn ) Pr( C0Pr( CmG m )= 1，= 0，0mn;m nG )n该可以降低工作组正确率的计算开销算法如下Input: G n = w1 ，w2 ，w n ，( p1 ，p2 ，p n )Output: 工作组正确率 GC( G n)1: m: = ( n + 1) /2;2: 初始化矩阵 A0，n0，m，矩阵元素初始值均赋值为 0;3: for i = 0: n do，v( w ) ) ，则工作组投票的最终结果为nnn + 11，v( wi) ;2i 1v( Gn ) =( 1)nn + 10，v( wi)2i 1定义 5工作者严( worker precision) :

14、 给定工作者 wi，严务 t 的概率定义 6投票正确数( correct表示 wi 能够正确回答任pi4:5:6:7:for j = 1: ( n 1) /2 + i do if i = = 0 thenAij= 1;elsevoting number) :投票正确数 C 表示工作组 Gn 中正确回答任务 t第 8 期等: 基于投票一致性的众包质量评估策略10998:Aij= Ai 1j*p j + Aij 阈值，可以计算工作者严的置信下限1*( 1 p j ) ;严置信下限( confidence定义 9lower9:10:precision) : 给定以及任务精度阈值均为 p，由end i

15、fend forlimit ofG n，不妨设所有工作者严11: end for12: GC( G n )陪审团知p ，当 p = p 时 GC( G n)= An( n + 1) /2;，称 p 为工作组 G n 在 水平下的严下限置信13: retrun GC( G n ) 设工作组 G n 中选择正确的工作者数量2. 2工作者严估计为Y，Y 服从二项分布Y P( Y k) ，则B( n，p) ，令 M( k，p)=在任务初始化时，假设工作者严均未知本文将采用工作者严在每一工作阶段结束后对进行估计( )ni knp ( 1 p) ni ( 4)iM( k，p) =P( Y k)=i假设工作

16、者 w 回答任务 t 时做出的选择为使用分部积分公式可得X，可以看出服从伯努利分布 B ( 1，p ) ，即X n!p( k 1) ! ( n k) !0 xM( k，p) =k 1( 1 x)dx，nkP( X = 1) = p = 1 P( X = 0) ( 不妨设 X = 1 表示回答正确) 设 p 的先验分布为( 0，1) 上的均匀分布，即( k 1) ( 5)设P( k) 是方程M( k，p) = 的唯一根，由于P( k) ( k 1) 满足方程1， p( 0，1) ;( p)( 2)=0，p( 0，1) n!P( k)假设某一工作阶段结束后，工作者已经完成了l 项任务，l 项投票可

17、以看作是一组样本值X1 =( k 1) ! ( n k0) ! x( 1 x)dxk1nk，( 6)=可以看出，x ，X = x ，X = x 对于任意 x ，如果 x = 1 表122lliiP( k)当 k ( k，n+ 1) ( 分布的分位数) ( 7)= k示工作者投票值与工作组投票值一致，x = 0 表示i= ( n + 1)/2 时，可以计算 G n 在 水平下的工作者投票值与工作组投票值相反置信下限 p 为 ( ( n+ 1) /2，( n + 1) /2) 利用公式，p 的后验分布密度为ll如果在某一工作阶段结束后，工作组正确率 ixlx i( 1 p)p11( p |x1 ，

18、x2 ，xl )=l低于任务精度阈值，则替换所有工作者严低ll i ix( 1 p)lxpdp110于 p 的工作者 由于工作组正确率的计算相对繁llBeta( 1 xi + 1，l+ 1 1 xi ) ( 3)琐，通过文献9中的步简化以将替换规则进一ll这是参数为( 1 xi+ 1，l + 1 1 xi )的Beta 分给定工作组数) ，工作者严= w1 ，w2 ，w n ( n为奇G n布 由于 Beta( a，b) 的分布期望值为 a / ( a+ b) ，为( p1 ，p2 ，p n) ，对于任意 p i 1 l( xi + 1) + 21所以 p 的后验期望估计值为l0. 5，假设工

19、作者严均值 珔p都有n( pi )p=i在任务的运行过，只需工作者回答/ n，则 GC( G n)珔p 任意工作阶段结束问题的数量，以及工作者与工作组投票值一致的问题数量 在任意工作阶段结束后，动态地对工人i 1后，如果工作者严均值超过任务精度阈值且任意工作者严均超过 0. 5，则可以保证工作的现有投票进行统计，即可对工作者严动态估计进行组正确率超过任务精度阈值，不需要对工作者进行替换工作者替换策略在对工作者严 完成评估以后，需要替换不合格的工作者 替换的原则是保证工作组的正确率大于任务精度阈值假设工作组中工作者数量 n 固定，且工作者2. 3替换算法要求工作者严必须严格大于0. 5，否则必须

20、替换 但是在任务执行过，对工作者进行替换需要额外的开销，为了减少不必要的替换，该算法并不是严格地将低于严置信下限的工作者替换掉，如果能保证工作组正确率一直高于任务精度阈值，则保留当前的工作者工作组替换算法如下具有相同的严定理( Condorcetp ( p 0. 5) ，由陪审团theorem ) 7 8可知，工作组Jury的正确率随着 p 的增加单调递增 给定任务精度东北大学学报( 自然科学版)第 35 卷1100Input: G n= w1 ，w2 ，w n ，任务精度阈值 ，严14:15:16:17:end ifend for return G n;end if置信下限 pOutput:

21、 新工作组 G n1: 通过统计之前投票结果计算当前的工作者严谨度( p1 ，p2 ，p n) ;n18: end if2: 工作组精度均值 珔p= pi ;3实验评估i 13: if 珔p and 任意 p i 均大于 0. 5本实验的硬件环境为 HP 电脑，8GB 内存，双核4:5: else6:7:8:9:10:11:12:13:return G n ;处理器主频3. 2GHz采用2012( a) 实验采用三个真实数据集，即 IC dataset2， SOT dataset10和Gender Hobby dataset11计算 GC( G n) ;GC( G n) 将精度小于 0. 5

22、的用户进行替换;return G n ;elsefor i = 1: nif p i p替换 wi;if三个数据集中任务的正确均为已知，工作者回答问题的正确率如图 1 所示 可以看出，IC dataset中工作者严最高，均值在 0. 85 左右，SOT dataset 中工作者严大多数在 0. 7至 0. 85 之间，Gender Hobby dataset 中工作者严的波动幅度最大，均值在 0. 7 左右图 1 三组数据集中的工作者严Fig. 1 Worker precision of three datasets( a)IC; ( b)SOT;( c)Gender Hobby不同数据集的特

23、点，实验中设置的参数 如下: IC dataset 工作阶段的任务数量设置为 8， 任务精度阈值为 0. 9，工作组大小分别选取 5，7， 9，11; SOT dataset 工作阶段的任务数量设置为8，任务精度阈值为 0. 9，工作组大小分别为 5，9， 13，17; Gender Hobby dataset 工作阶段的任务数量设置为 10，精度阈值为 0. 8，工作组大小分别为 5，7，9，11本文提出的动态替换策略将与其他两种策略进行比较 第一种为不替换策略，该策略随机选择每种策略均终的精度指标执行 5 次，取平均值作为最三种数据集的实验结果如图 2 所示 可以看出，采用替换策略可以有效

24、提高工作组的正确率， 两种动态替换策略均可以达到任务的精度阈值要 求 同时，采用动态替换策略的工作组正确率随着工作者数量的增加严格递增 图 2a 中，采用严格动态替换策略和动态替换策略具有相同的正确 率; 而图 2b 和图 2c 中，采用严格动态替换策略的正确率并没有随着工作者数量的增多而显著提 高，因为替换后的工作者为随机选择，当候选工作工作者，任务执行过不替换工作者; 第二种为严格动态替换策略，任意工作阶段完成后，所有精者数量较多时，无法保证其严一定达到置信度阈值小于置信下限的工作者被严格替换下限，并且替换较为频繁会产生额外的不确定风险 如果当前工作组能够满足任务精度阈值的要三种策略在选择

25、工作者为随机选择，实验中第 8 期等: 基于投票一致性的众包质量评估策略1101求，继续使用严略; 该众包任务的精度需求，阶段性地比较的工作者可以获取较为满意的结果 本文提出的工作者严动态对不合格的工作者进果证明了该动态评估评并及时替换 实验结和替换策略的有效性，评估和替换策略具有较高的足任务的精度需求性，能够较好满为众包应用中质量管理方面的研究工作奠定了基础参考文献:1Perona P，Welinder P Online crowdsourcing: rating annotators and obtaining cost effective labelsC/ / Computer Visi

26、on and Pattern ecognition Workshop San Fr sco: IEEE Computer Society，2010: 25 32Manas J，Hector G M，Aditya P Evaluating the crowd with confidenceC/ / Proceedings of ACM SIGKDD New York: ACM Press，2013: 686 694Snow ，Connor B O，Jurafsky D，et al Cheap and fast but is it good? evaluating non expert annot

27、ations for natural language tasksC/ / Proceedings of the Conference on Empirical Methods in Natural Language Processing New York: ACM Press，2008: 254 263Liu X，Lu M Y，Ooi B C，et al CDAS: a crowdsourcing data234analytics systemJ Proceedings of the2012，5( 10) : 1040 1051VLDB Endowment，5Cao C C，She J Y，Tong Y X，et al Whom to ask? Jury selection for decision making tasks on micro blog J Proceedings of the VLDB Endowment，2012，5 ( 11 ) : 149515066，等 众包质量策略及评估算法研究J 计算机学报，2013，36( 8) : 1636 1649( Zhang Zhi qiang，Pang Ju sheng，Xie Xiao qin，et ales