12.36 自适应任务分配技术
上节介绍的众包工人领域差异性对众包质量控制提出了两点新的要求，第一，能否估计众包工人在不同领域可能存在较大差异的准确率，并随着工人答题不断对估计进行更新；第二，能否根据估计的准确率，自适应地将任务分配给所属领域的“专家”，即准确率高的工人。为了达成这两点要求，本文提出自适应的任务分配技术 iCrowd。
图 3 给出了自适应任务分配 iCrowd 技术框架。该技术针对一组众包任务（Microtasks）进行分配，通过众包平台（Crowdsourcing Platform）利用众包进行求解。每当工人（Worker）请求任务时，iCrowd 对工人的类型进行如下判断。
● 针对新工人（New Worker），iCrowd 通过Warm-Up 模块分配一些考试题（Q-Tasks），并通过工人的答案（QTask Answers）初步估计其准确率。
● 针 对 已 通 过 考 试 题 的 工 人（QualifiedWorker），自适应分配模块（Adaptive Assigner）对其进行任务分配：通过准确率估计模块（AccuracyEstimator）分析其已完成的历史任务，估计出工人在不同领域的准确率，进而通过任务分配模块（Microtask Assigner）将任务分配给准确率最高的工人进行解答。注意，以上估计 - 分配过程是不断进行的，随着工人答题数量的增加，准确率的估计会持续更新，任务分配也会根据更新的准确率自适应的修正。
框架中最核心的挑战在准确率估计（AccuracyEstimator）和任务分配（Microtask Assigner）模块，下面简介它们的思想，具体技术细节见文献 [34]。
准确率估计：核心的想法是把众包任务构建成图模型，结点表示任务，边表示任务之间的领域相似关系。例如，在判断篮球运动员国籍时，可以把每一任务建模成结点，如果两个任务比较相似，则在他们之间建一条边，并标注上相似性。其中相似性可以基于文本相似性，或是实体关系在知识库中的结构进行定义。基于上述图模型，准确率估计首先计算某一工人在已回答问题上的准确率，进而基于此估计其在未回答问题上的准确率。例如，某工人在补全篮球运动员的任务上表现出色，而在补全政治家的任务上很差，估计技术就给与前者相似的任务较大准确率，与后者相似的任务较小准确率。为了实现这一想法，在技术上，iCrowd 将估计问题形式化为综合考虑局部相似性和全局相似性的优化问题，并给出了高效策略进行优化求解与更新。
自适应任务分配：核心的想法是将某一任务分配给能完成它的准确率最高的 k 个工人。在此前提下，还需要考虑尽快将任务完成，从而进一步触发准确率估计模块更新工人的准确率。iCrowd 将自适应任务分配进行了形式化，证明找到最优分配方案是一个 NP 难问题，并提供了一个有效的方法进行近似求解。此外，iCrowd 也提出了考试题挑选方法，其基本想法是挑选那些“影响力”最大的任务作为考试题，使工人回答了这些任务后，iCrowd 可以在最大范围内估计他在其它题目可能的准确率。