引用：L. Qiao, F. Tang and J. Liu, "Feedback Based High-Quality Task Assignment in Collaborative Crowdsourcing," 2018 IEEE 32nd International Conference on Advanced Information Networking and Applications (AINA), Krakow, 2018, pp. 1139-1146.

摘要

协同众包适用于需要一群工人才能完成的任务，协同众包通常需要获取这些工人亲和度的有关信息。然而，很少有研究如何准确评估工人亲和度以及工人能力的工作。在这种情况下，冷启动众包平台中的任务分配问题将更加困难。在本文中，我们设计了一个新的协同众包框架，这个框架允许任务请求者或工人向任务执行者或同事提供反馈。使用反馈中的信息，我们可以构建模型以更准确的评估工人亲和度和工人能力，并在此基础上提出了测量任务与一组工人之间匹配程度的测量方式。接下来，我们提出了一个叫做FCC-SA的启发式任务分配方法，可以平均的将熟练的工人分配给所有协同任务。最后，我们聘请了大量的工人进行实验，测试我们的模型和算法，实验结果表明，我们的FCC-SA算法明显优于其他的具有代表性的相关方案，我们提出的新测量方式也比传统的测量方式具有更好的精度。

关键词 众包；协同；任务分配；

介绍

众包融合了人类智慧和计算机智慧，是处理一些计算机难以解决的复杂任务的工具之一，很多众包平台已经得了巨大的成功。除了一些简单的众包任务，如图片标签或URL验证，还有越来越多的复杂任务，如文档编辑、翻译，这不仅需要多种能力，还需要在许多场合进行协作。

协同众包的关键因素之一是工人亲和度，它反映了工人之间协作的熟练程度。据我们所知，很少有工作研究如何获得工人的亲和度。除了工人的亲和度，工人的能力在高质量的任务分配中也起到了很重要的作用，但是在一个多人参与的协同众包系统中，人员变更频繁，很少有工人可以与其他所有人协作。除非我们对一些工人进行长期观察，或者在他们进入系统之前对他们的能力提前进行检测，否则很难评估每个新来者的能力水平。但显然，使用这些方法会产生巨大的成本，且难以进行。

为了解决上述问题，在本文中，我们尝试通过要求任务请求者和工人提供一次性反馈来简化此过程，我们称之为基于反馈的协同众包(FCC)。首先，用优化对象正式定义FCC问题。在此基础上，我们分别构建表示工人亲和度和表示工人能力的模型。对于构建工人亲和度矩阵的稀疏矩阵问题，我们采用矩阵分解方法得到每个时隙的亲和度评估。根据工人和任务请求者的反馈信息，更新工人亲和度矩阵和能力值。在这两个模型的基础上，我们定义了衡量匹配度的标准、工作和工人之间的关系。其次，我们提出一个叫做FCC-SA的启发式算法，平均分配熟练工人和低熟练工人。该算法具有自适应性，能够动态地确定任务应该分配给哪个工人或哪一组工人。最后，基于实际数据集对模型和任务分配算法进行了实验验证。

概述及问题的提出

FCC的框架如图1所示。

FCC框架描述了系统在一轮中的一项活动。首先任务请求者在系统中发布一个协同众包任务，然后系统根据一些特定的算法将任务分配给一组工作工人。在一组工人完成任务后，任务请求者向整个工人组提供反馈，同时要求工人评估同一组中的所有其他工人。根据所有来自任务请求者和工人的反馈，更新工人的亲和度和能力水平。任务请求者的反馈反映了任务的质量，这对于评估团队中工人的能力水平是非常重要的。

考虑最常见的众包场景，有一组工人W={w_i|1≤i≤N_W}和一组任务T={t_j|1≤j≤N_T},其中N_W表示工人数量，N_T表示任务数量。每个工人都与属性S_wi相关联，表示w_i的能力水平，将其缩放在[0,1]区间中。每个任务都与属性des_tj、rq_tj相关联，des_tj表示对任务的描述，包括截止日期或能力要求等信息，rq_tj表示任务所需的最大工人数。另外，我们使用了a_wiwt来表示w_i和w_t之间的亲和度，其中a_wiwi=0且a_wiwt=a_wtwi。亲和度的初始值需要根据其他信息计算。

我们的平台旨在将每个任务分给一组工人G_tj，设||X||表示集合X的大小，因此||G_tj||≤||rq_tj||。我们使用m（G_tj）来表示工人组G_tj在t_j上生成的质量。因此我们简单的定义我们的优化对象如图2所示。（2）表示任务不能分配给超过需求的工人，（3）表示工人不能同时分配两个或以上的任务。

另外，我们使用h_tj表示任务t_j的任务请求者的反馈，范围在[-5,5]区间内，f_wiwt表示w_i对w_t的反馈，范围在[-5,5]区间内。上文中提到的变量都是可变的，因此算法无法确保得到最佳质量，只能通过自适应近似算法来优化最终结果。

任务与工人的匹配度测量

3.1工人亲和度

为了获得工人间关系信息，须设定如图3所示的亲和度矩阵。

任务执行后根据反馈信息得到如图4所示的反馈矩阵。

通过多次任务反馈对工人亲和度矩阵进行不断更新。

3.2工人能力

工人能力的差异智能通过工人间的反馈来反映，根据请求者及其他工人的反馈，按照如图5的方式更新工人能力。

3.3匹配度测量

我们使用加权平均值作为G_tj组内的亲和度I(G_tj)，使用组内工人能力平均值作为组内能力S(G_tj)。最后，我们提出衡量任务和一组工人匹配程度的标准，如图6所示。

FCC-SA任务分配算法

在测量了任务和工人之间的匹配度后，我们可以进行实际的任务分配。FCC-SA任务分配算法步骤如下：

1.按照工人的能力水平和亲和度对他们进行排序；

2.按照所需工人数量对任务进行反向排序；

3.将工人逐个放入工作中；

4.当工人数量满足某些任务所需的数量时则跳转到下一个任务；

5.更新工人亲和度矩阵和工人能力。

FCC-SA任务分配算法性能评估

我们使用协同句子翻译作为评估我们算法性能的主要任务，任务是将视频中的英文字幕翻译成中文。根据视频长度的不同对工人的要求也不同。工人被要求与其他同事在线工作，他们可以在工作和沟通的同时观察他人的结果，系统每天都会发布任务，并且工人需要在任务发布当天完成任务以便我们可以根据反馈更新他们的配置文件。任务质量总体评级如图8（a）所示，任务完成度如图8（b）所示，任务执行时间如图8（c）所示。

从图8（a）中可以看出随着时间推移，所有算法都提高了任务质量，而FCC-SA算法具有更快的提高速度。从图8（b）中可以看出，其他算法的任务完成度开始下降或保持相对稳定，只有FCC-SA算法呈上升趋势。系统还会记录每个人的工作执行时间，图8（c）显示了不同算法下每人每100字的平均翻译时间，从图中可以看出，我们的FCC-SA具有最低的转换时间。

结论

本文介绍了基于反馈的协同众包(FCC)问题，用以解决一些需要一组工人协同完成的任务。我们提出了一个FCC框架，允许任务请求者和工人向其他人提供反馈，并在此基础上，我们提出了一个测量方法，以定量捕捉任务和工人群体之间的关系。我们设计了一个启发式FCC-SA算法，使整个分配质量最大化。我们将我们的算法和测量方法与其他算法和模型进行了比较，结果显示，本文的方案表现出了更好的性能。

致谢:

此文由南京大学软件学院2019级硕士孙加辉翻译转述。