作者

Yili Fang
State Key Laboratory of Software Development
Environment, School of Computer Science and
Engineering, Beihang University
Beijing, China
[email protected]

Kai Sun
State Key Laboratory of Software Development
Environment, School of Computer Science and
Engineering, Beihang University
Beijing, China
[email protected]

Pengpeng Chen
State Key Laboratory of Software Development
Environment, School of Computer Science and
Engineering, Beihang University
Beijing, China
[email protected]

Hailong Sun
State Key Laboratory of Software Development
Environment, School of Computer Science and
Engineering, Beihang University
Beijing, China
[email protected]

摘要

在众包中，有一个重要的任务类别，包含一系列有序的子任务，我们称之为多阶段任务（Multi-phase Tasks，MPT），例如旅游规划、翻译和微写作。现有的结果推断方法对于处理MPT是无效的。MPT的阶段级子任务之间的约束关系不能被忽略，原因有两个。首先，在没有阶段处理的情况下处理MPT是无效的，例如，对于旅游规划，推荐一个完整的旅游规划路线，并使用现有的方法来推断个体工人产生的最终结果，由于缺乏灵活性，很难满足各种要求。其次，虽然MPT由一组阶段级子任务组成，但不适合简单地将MPT拆分为子任务并使用top-k方法推荐最终结果；因为这不仅会增加成本，而且会失去阶段之间的约束关系。因此，它需要一种处理MPT的新方法。本研究首先引入MPT的概念来识别这些特殊的任务。其次，提出了一种基于决策树的MPT众包协同工作流任务生成和最终结果组合控制框架。第三，提出了一个概率图模型来描述每个MPT阶段的子任务，并设计了一种基于最大似然的结果推断方法。最后，基于实际的出行规划任务，进行了大量的实验，实验结果表明，该方法与目前最先进的方法相比具有优越性。

CCS CONCEPTS：Human-centered computing→Computer supported cooperative
work;

关键词：众包、结果推断、质量控制、计划、多阶段任务

ACM Reference format

Yili Fang, Pengpeng Chen, Kai Sun, and Hailong Sun. 2017. A Decision Tree
Based Quality Control Framework for Multi-phase Tasks in Crowdsourcing.
In Proceedings of ChineseCSCW ’17, Chongqing, China, September 22–23,
2017, 8 pages.
https://doi.org/10.1145/3127404.3127408

1 介绍

众包的目的是利用群众的智慧来解决计算机仍然难以解决的问题。它在各种应用中都取得了成功，特别是在数据管理领域[12]，从简单的任务（如图像标记[7]、字符识别[19]）到复杂的任务（如文本编辑[18]）。为了获得高质量的众包任务结果，特别是复杂的任务[22]，许多研究[5，17]越来越多地寻求自动协作工作流，其中请求者提交一组任务，平台将每个任务分配给多个工人。然后通过汇总这些工人提交的答案来推断结果。

这项工作调查了一类特殊的众包任务，如旅游规划[14]、微写作[18，22]和翻译，我们称之为多阶段任务（MPT）。处理MPT由有序的阶段序列组成，其中每个阶段负责处理子任务，并依赖于其前一阶段。例如，图1（a）显示了一个旅游规划示例，其中一个请求者正在计划在北京的一日游，其中有一些受欢迎的旅游景点。旅游规划由多个景点组成，与MPT的各个阶段相对应。众包中有两种类型的结果推断方法。一个将每个MPT视为一个整体[4]，这可能无法保证每个子任务的最佳处理；另一个在子任务级别[15]执行推断，由于忽略子任务之间的约束，可能无法实现全局优化。因此，现有的结果推断方法对MPT是无效的[3]。以旅游规划为例，一方面，要求每个工人完成任务的所有阶段，并提交一轮众包的总体结果；随后，选择这些工人提供的旅游规划。无论选择哪一个，一些受欢迎的景点可能会因为相应工人的有限利益而丢失。因此，图1（b）所示的第一种设计方法得到的最终结果很难满足请求者的要求。另一方面，如图1（c）所示，要求工人提供一套单独的景点，并选择K个顶级景点来制定旅游规划。然而，这种方法不考虑景点之间的交通成本。例如，从天安门到中国长城的一条生成路线通常太远，无法进行一日游。因此，这些推荐算法[2，15]是无效的。因此，需求目标，即尽一切努力实现建议的目标，以及各阶段之间的约束关系，如交通便利性，在众包中是不可忽视的。因此，这两种方法都不适用于MPT。处理MPT有两个主要挑战。在有限的预算下，生成众包任务以保持任务各个阶段之间约束关系的完整性是非常重要的。此外，如何在不缺乏各阶段兼容性的情况下进行阶段级结果聚合和最终结果组合也是一个挑战。为了解决这两个难题，本文研究了任务生成和结果推断两个问题。

（a） 北京一日游的旅游规划建议

（b） 通过推荐直接引出完整的旅游路线

（c） 通过Top-K方法引出景点，然后将它们组装成旅游路线

图1:MPT任务和两种众包方法的结果。斑点的颜色越深，斑点就越受欢迎

具体地说，本研究首先提出了一个基于决策树的MPT众包处理框架，该框架控制了MPT阶段对应子任务的动态生成以及最终结果的组合。其次，提出了一个概率图形模型来推断每个阶段的结果，并对每个工人的任务难度和错误率进行了建模。与之前的工作不同[14]，该方法根据决策树的路径整合了所有阶段之间的约束关系，这些路径是有序分布的。这可以减少每个阶段中所需的候选答案的数量以及工人总数。综上所述，主要贡献如下。

• 确定了一个重要的众包任务类别，即MPT，它由一个有序的子任务序列组成。据我们所知，这是首次尝试将多阶段任务描述为众包中的一个常见任务类别。
• 提出了一种基于决策树的MPT众包工作流任务生成和最终结果组合控制框架。
• 提出了一种概率图模型，对MPT各阶段的子任务进行建模，并设计了一种基于众包工作者答案的EM算法来推断子任务的结果。
• 以实际的出行规划任务为例，进行了一系列的实验。实验结果表明，该方法在结果质量和成本上均优于现有方法。

本文的其余部分组织如下。第2节将问题形式化并概述框架。第3节分别介绍了基于决策树的工作流控制方法和结果推断方法。实验装置和结果见第4节。第5节讨论了相关工作，并在第6节中得出结论。

2 问题形式化和框架

2.1 问题形式化

本节将主要问题形式化。多阶段任务（MPT）包含多个阶段级别的子任务，每个子任务对应于最终结果的一个组件。关联流程中涉及多个依赖项，每个阶段都可以生成一个结果。MPT需要解决的问题有两个：任务生成和结果推断。

对于MPT，阶段(k)的任务生成取决于直接前置阶段(k-1)生成的结果，并可能影响直接后续阶段(k+1)的任务生成。如果每个阶段级别的任务生成都生成一组候选任务$T_k = \{ t_{kl} | l \in I_{T_k}\}$Tk​={tkl​∣l∈ITk​​}，与$N$N个阶段对应的候选任务集可以表示为$\mathcal{T} = \{ T_1,T_2,...,T_k,...,T_N \}$T={T1​,T2​,...,Tk​,...,TN​}，然后我们可以表示由$\mathcal{T}$T生成的一个MPT为$T=(t_{1l_1},t_{2l_2},...,t_{kl_k},...,t_{Nl_N})$T=(t1l1​​,t2l2​​,...,tklk​​,...,tNlN​​)。这里$t_{kl_k} \in T_k$tklk​​∈Tk​是一个阶段级子任务。 任务生成问题可以定义如下。

定义2.1（MPT-生成，MPT-Generation MPT-G）。给定对应于所有阶段$\mathcal{T}=(T_1，T_2,...,T_k,...,T_N)$T=(T1​，T2​,...,Tk​,...,TN​)的候选任务集,其中$T_k=\{t_{kl}\}$Tk​={tkl​}并且$t_{kl}$tkl​是阶段$k$k的第$l^{th}$lth候选子任务。

MPT生成问题是以降低成本和提高质量为目标从$\mathcal{T} = \{ T_1,T_2,...,T_k,...,T_N \}$T={T1​,T2​,...,Tk​,...,TN​}查找一个子任务序列$T=(t_{1l_1},t_{2l_2},...,t_{kl_k},...,t_{Nl_N})$T=(t1l1​​,t2l2​​,...,tklk​​,...,tNlN​​)。

正如我们所讨论的，成功的任务生成可以过滤掉不需要生成的子任务，从而降低成本并提高质量。对于MPT,来说，直接产生一个完整的MPT并众包几乎不能带来令人满意的结果。另外，虽然MPT是由一组原子级阶段子任务组成的，但由于相间约束关系的丢失，不适合简单地将其拆分为多个子任务并发布每个子任务。因此，要解决MPT的生成问题，必须考虑约束关系。

对于MPT，我们的目标是通过聚合每个阶段中不同工人的所有子任务输出来推断出一个令人满意的结果。结果推断在处理MPT的众包协同工作流程中是必不可少的，它会影响后续阶段的结果质量和任务生成。给出了MPT T的候选回答集$R=\{ R_1,R_2,...,R_k,...,R_N\}$R={R1​,R2​,...,Rk​,...,RN​}，这里，$R_k = \{ r_{kl} \}$Rk​={rkl​}，我们给出了结果推断的定义2.2，如下所示。

定义2.2（结果推断问题，Result inference Problem，RIP）。给出了由$\mathcal{T}$T产生的MPT $T=(t_{1l_1},t_{2l_2},...,t_{kl_k},...,t_{Nl_N})$T=(t1l1​​,t2l2​​,...,tklk​​,...,tNlN​​)，以及噪声候选回答集$\mathcal{R}=\{ R_1,R_2,...,R_k,...,R_N\}$R={R1​,R2​,...,Rk​,...,RN​}，这里，$r_{kl} \in R_k$rkl​∈Rk​表示$k$k阶段的候选回答 $l$l，结果推断问题是从$\mathcal{R}$R得到结果$R'=(r_{1l_1},r_{2l_2},...,r_{kl_k},...,r_{Nl_N})$R′=(r1l1​​,r2l2​​,...,rklk​​,...,rNlN​​)，目的是推断出与大众合作一样高质量的结果。

此外，结果推断方法也会影响任务的生成。因此，适合于开发与任务生成方法相对应的结果推断方法。

对于定义2.1，我们主要关注降低总成本，并给出定义2.2，重点是提高最终结果的质量。

2.2 众包框架

在本节中，我们概述了MPT的多阶段众包框架，如图2所示，其中任务生成、众包、结果推断和结果组合是四个主要步骤。

图2：处理MPT的众包框架概述

• 步骤1： 任务生成分阶段执行。在每个阶段中，当前阶段的任务是根据前一阶段的结果生成的。
• 步骤2： 将任务从众包平台提交给多个工人，用于多阶段众包处理。
• 步骤3： 在接收到每个阶段的工人的输出之后，此步骤的目标是从MPT的每个阶段推断聚合结果。如果当前阶段不是最终阶段，则在步骤1中根据当前阶段的结果生成下一个任务。否则，所有阶段的结果将在步骤4中合并。
• 步骤4： 结果组合生成MPT的最佳最终结果，该结果是提交给请求者的关联序列。

在这个过程中，任务生成、阶段级结果推理和结果组合都是由我们基于决策树的方法控制的。我们认为这种框架是处理各种MPT的通用框架。

3 约束决策树模型

在这一部分中，首先，我们给出了一个概率模型来形式化每个阶段级子任务的回答过程，并给出了结果推理模型来形式化RIP问题（第3.1节）。第二，第3.2节描述了阶段级子任务之间的约束关系。第三，将结果推理方法引入决策树模型，考虑约束关系控制任务生成。然后，我们应用这个决策树模型来获得组合结果（第3.3节）。

3.1 阶段级推理的概率模型

本节介绍了一个基于投票的概率模型，将阶段级子任务的众包过程形式化，并提出了计算阶段级子任务结果满意度的阶段级结果推理方法。

我们从建模生成MPT的过程开始。将上一阶段的选定结果设为$R=(r_{1l_1},r_{2l_2},...,r_{{k-1}l_{k-1}})$R=(r1l1​​,r2l2​​,...,rk−1lk−1​​)，$R'=(r_{1l_1},r_{2l_2},...,r_{kl_k})$R′=(r1l1​​,r2l2​​,...,rklk​​)是一个由以前所有阶段的提交结果组成的序列。基于当前阶段的候选答案集（$R_k=\{ r_{k1},r_{k2},...,r_{kl} \}$Rk​={rk1​,rk2​,...,rkl​}）,我们雇佣工人投票来决定哪个候选回答$r_{kl} \in R_k$rkl​∈Rk​可以与前一阶段$R$R的结果相结合，生成当前阶段的结果序列$R'=(r_{1l_1},r_{2l_2},...,r_{Nl_N})$R′=(r1l1​​,r2l2​​,...,rNlN​​)。图3显示了包含MPT典型特征的旅游规划任务。任务界面显示推荐的目标和当前路径的结果。要求工人根据当前路径的结果决定候选景点是否优于当前路径。

图3：旅游规划的任务界面

由于一轮投票很难产生足够的高质量的结果推理输出，因此我们开发了一种基于工作流任务生成的迭代投票方法。给出了随先验概率$P_R(q)$PR​(q)的未知质量$q$q的当前阶段$R$R的结果，以及随先验概率$P_{R'}(q')$PR′​(q′)的未知质量$q'$q′的下一阶段$R'$R′的结果。投票过程将持续到足以推断出哪个结果更好（$R$R或$R'$R′）。然后我们模拟投票过程。首先，我们给出一些假设：

1. 每个工人都很勤奋，也就是说每个工人都尽力完成所有的任务。事实上，他/她仍然可能犯错误，表现出很低的能力，因此建模错误率很重要；
2. 每个工人都是独立的，不会受到其他答案的影响。

如图4所示，我们为每个子任务提供了众包流程的因果结构。设$t \in T_k$t∈Tk​表示$k$k阶段的子任务，工人$i$i提交的$T_k$Tk​子任务$t$t的一个输出$v_i$vi​主要取决于三个因素：

图4：MPT中每个阶段子任务$t$t的概率图

1. 子任务的难度$d \in [0,1]$d∈[0,1]。一般来说，$d$d越高，子任务越难完成，因此工人完成的质量就越高；
2. 工人$i$i提交答案的独立误差参数$\lambda_i \in(0,1)$λi​∈(0,1)。
3. $z$z是子任务$t$t的基本真值，它是概率模型的潜在值。利用这种因果结构，我们可以给出一个概率模型来形式化每个阶段中每个子任务的回答过程。首先，我们定义$d$d如下。

$d = d(q,q′) = 1 − (q − q′)^\mathcal{M},\tag{1}$d=d(q,q′)=1−(q−q′)M,(1)

其中$\mathcal{M}$M是经过训练的常数。很容易检查$d \in [0,1]$d∈[0,1]。同时，问题的难度直接影响到工人回答的准确性。我们将$\mu(d)$μ(d)定义为具有难度$d$d子任务上一个工人的准确度。工人的准确度随着$t$t中难度$d$d的增加而单调降低。这里，$\mu(d) \rightarrow 0.5$μ(d)→0.5时$d \rightarrow 1$d→1而$\mu(d) \rightarrow 1$μ(d)→1时$d \rightarrow 0$d→0。因此，我们一般给出一个函数来计算精度，如下所示。

$\mu(d) =\frac{1}{2} [1 + (1 − d)^{\lambda_i}].\tag{2}$μ(d)=21​[1+(1−d)λi​].(2)

一般情况下，通过训练集，我们可以通过最大似然估计得到所有工人的误差参数$\lambda_i$λi​。同时，我们推断出$i^{th}$ith工人正确回答子任务$t$t的概率$P(v_i=1|q,q')$P(vi​=1∣q,q′)如下：

$\begin{aligned} &If \ q'>q \ P(v_i=1|q,q')=\mu(d(q,q'));\\ &If \ q'\leq q \ P(v_i=1|q,q')=1-\mu(d(q,q')).\tag{3} \end{aligned}$​If q′>q P(vi​=1∣q,q′)=μ(d(q,q′));If q′≤q P(vi​=1∣q,q′)=1−μ(d(q,q′)).​(3)

设$\overrightarrow{v_M}=\langle v_1,...,v_M \rangle$vM​​=⟨v1​,...,vM​⟩为M个工人给出的投票输出，其中$v_i \in \{0,1\}$vi​∈{0,1}。基于$q$q和$q′$q′的概率分布（$P_{R|v_i}(q)$PR∣vi​​(q)和$P_{R|v_i}(q')$PR∣vi​​(q′)），我们可以得出概率$P_{R|v_{i+1}}(q)$PR∣vi+1​​(q)，它表示需要投票$v_{i+1}$vi+1​的概率。这里，$\overrightarrow{v_{i+1}}$vi+1​​表示已知$i$i票，将生成$v_{i+1}$vi+1​（当前未知）。

$\begin{aligned} P_{R|\overrightarrow{v_{i+1}}}(q) &\propto P(v_{i+1}|q,\overrightarrow{v_i})\times P_{R|\overrightarrow{v_i}}(q)\\ &=P(v_{i+1}|q)\times P_{R|\overrightarrow{v_i}}(q)\\ &=\int_{0}^{1}P(v_{i+1}|q,q')\times P_{R'|\overrightarrow{v_i}}(q')dq'\times P_{R|\overrightarrow{v_i}}(q).\tag{4} \end{aligned}$PR∣vi+1​​​(q)​∝P(vi+1​∣q,vi​​)×PR∣vi​​​(q)=P(vi+1​∣q)×PR∣vi​​​(q)=∫01​P(vi+1​∣q,q′)×PR′∣vi​​​(q′)dq′×PR∣vi​​​(q).​(4)

类似的方程可以用来计算$R'$R′的后验概率。

$\begin{aligned} P_{R|\overrightarrow{v_{i+1}}}(q') &\propto P(v_{i+1}|q',\overrightarrow{v_i})\times P_{R'|\overrightarrow{v_i}}(q')\\ &=P(v_{i+1}|q')\times P_{R'|\overrightarrow{v_i}}(q')\\ &=\int_{0}^{1}P(v_{i+1}|q,q')\times P_{R|\overrightarrow{v_i}}(q)dq\times P_{R'|\overrightarrow{v_i}}(q').\tag{5} \end{aligned}$PR∣vi+1​​​(q′)​∝P(vi+1​∣q′,vi​​)×PR′∣vi​​​(q′)=P(vi+1​∣q′)×PR′∣vi​​​(q′)=∫01​P(vi+1​∣q,q′)×PR∣vi​​​(q)dq×PR′∣vi​​​(q′).​(5)

现在我们将序列$R$R与序列$R'$R′的改进率表示为$imp(R,R')=E(q)/E(q')$imp(R,R′)=E(q)/E(q′)，$E(·)$E(⋅)表示数学期望值。我们可以用它来推断替代结果序列的满意度水平。

本节将每个阶段级子任务的回答过程形式化，并给出结果推理模型，其中描述了阶段级子任务结果的满意度。它是通过影响子任务编号和结果序列质量来控制第3.3节中的工作流的准备工作。

3.2 捕捉约束关系

在这一部分中，我们提出了阶段之间约束关系的定义，这对于任务生成和结果推断至关重要。我们构造了一个关系图，其中节点是阶段之间的候选景点，边缘是每个候选对的约束关系。为了量化本阶段$T_k$Tk​的候选景区$r_{kl}$rkl​与下一阶段$T_{k+1}$Tk+1​的候选景区$r_{k+1l}$rk+1l​之间的约束关系，我们引入了如下的$tra_T(r_{kl},r_{k+1l'})$traT​(rkl​,rk+1l′​)。

$tra_T(r_{kl},r_{k+1l'})=\prod_{j=1}^{J}weight_j(r_{kl},r_{k+1l'}), \tag{6}$traT​(rkl​,rk+1l′​)=j=1∏J​weightj​(rkl​,rk+1l′​),(6)

其中，$j \leq J$j≤J，J，$J$J表示受约束关系的因子数，$weight_l(r_{kl},r_{k+1l'})$weightl​(rkl​,rk+1l′​)表示因子$J$J中从节点$r_{kl}$rkl​到节点$r_{k+1l'}$rk+1l′​的约束水平。它可以从外部知识库（mapMicroblog）获得。例如，我们可以量化旅行规划的约束关系，如下所示。

$tra_T(r_{kl},r_{k+1l'})=\left\{\begin{matrix} \prod\limits_{j=1}^{2}weight_j(r_{kl},r_{k'l'}), &k'=k+1, \\ 0, &otherwise, \end{matrix}\right.\tag{7}$traT​(rkl​,rk+1l′​)=⎩⎨⎧​j=1∏2​weightj​(rkl​,rk′l′​),0,​k′=k+1,otherwise,​(7)

这里，这里，$weight_1(·)$weight1​(⋅)表示我们可以从地图（谷歌地图或百度地图）获得的从$r_{kl}$rkl​节点到$r_{k+1l'}$rk+1l′​节点的标准化运输距离。$weight_2(·)$weight2​(⋅)表示从Internet（例如，交通网站1）获得的从节点$r_{kl}$rkl​到节点$r_{k+1l'}$rk+1l′​的拥塞水平。

3.3 控制任务生成和结果组合的约束决策树模型

在本节中，我们提出了一个基于约束决策树（Constrained Decision Tree，CDT）的模型来控制任务生成、阶段级结果推理和结果组合，并给出了决策树模型的定义如下。

定义3.1（约束决策树模型-Constrained Decision Tree Model，CDT）。CDT是一个有标签的决策树$T=(\mathcal{R},E)$T=(R,E)，其中$\mathcal{R}=\{ R_1, R_2,···,R_k,···,R_N\}$R={R1​,R2​,⋅⋅⋅,Rk​,⋅⋅⋅,RN​}表示树的节点，$R_k$Rk​表示树中的$k$k层对应于阶段$k$k中的候选答案的节点。边$\langle r_{kl},r_{k+1l'} \rangle\in E$⟨rkl​,rk+1l′​⟩∈E表示阶段$k+1中$k+1中的候选答案$r_{k+1l'}$rk+1l′​取决于阶段k的候选答案$r_{kl}$rkl​， 而它的权重依据满意度和约束关系。

基于CDT，我们可以将结果组合问题转化为从根到叶的最优序列搜索问题，同时考虑了满足度和约束关系。例如，图5显示了以“天安门”为起点的旅游规划CDT。结果组合问题是从6条候选路由中选择一条最能满足请求者的路由。

图5：包含候选景点的决策树

为了评估一个完整的结果序列的满意度，我们基于我们的阶段级推理模型，引入了树中每个边的满意度得分$sat_T(R)$satT​(R)，如下所示。

（1）如果序列仅由根组成，则$sat_T(R)=1$satT​(R)=1。

（2）如果序列$R'$R′是通过在序列$R$R后面添加一个项而生成的，则$sat_T(R,R')=imp(R,R')\times sat_T(R)$satT​(R,R′)=imp(R,R′)×satT​(R)，其中第3.1节中定义的$imp(R,R')$imp(R,R′)表示序列$R$R与序列$R'$R′之间的改进比。

同时，我们还定义了转换分数$tra_T(R)$traT​(R)来评估树中每个边对应的约束关系。因此，我们将转换分数作为评估结果序列的另一个标准，如下所示。

$tra_T(R)=\sum_{n=0}^{k-1}tra_T(r_{kl},r_{k+1l'}).\tag{8}$traT​(R)=n=0∑k−1​traT​(rkl​,rk+1l′​).(8)

在第3.2节中，我们将$tra_T(r_{kl},r_{k+1l'})$traT​(rkl​,rk+1l′​)表示为$r_{kl}$rkl​和$r_{k+1l'}$rk+1l′​之间的转换分数，对应于两个阶段之间的约束水平。这里，$tra_T(R)$traT​(R)表示方程式8中计算的序列$R$R的转换分数。

因此，我们使用综合得分$score_T(R)$scoreT​(R)来表示序列R的得分相对于满意度得分和转换分数。$score_T(R)$scoreT​(R)计算如下。

$score_T(R)=sat_T(R) - \beta\times tra_T(R),\tag{9}$scoreT​(R)=satT​(R)−β×traT​(R),(9)

其中$\beta$β是平衡用户满意度和交通约束的因子。

以旅行规划为例，$\beta$β是满意度水平与约束关系的平衡因子，从阶段层面推荐出行路线。这里，我们设置$\beta=\frac{1}{N}$β=N1​，其中$N$N表示请求者希望旅游的景点数量。当用图5所示的树$T$T中的目的地“水立方”计算推荐旅游路线的得分时，对于推荐旅游路线$seq= \{天安门,奥林匹克公园,鸟巢、水立方\}$seq={天安门,奥林匹克公园,鸟巢、水立方}，我们可以计算$sat_t(seq)=0.4×0.5×0.3=0.06$satt​(seq)=0.4×0.5×0.3=0.06，$tra_T(seq)=0.3+0.4+0.4=1.1$traT​(seq)=0.3+0.4+0.4=1.1。然后得到$score_T(seq)=0.06−1.1×0.25=−0.215$scoreT​(seq)=0.06−1.1×0.25=−0.215。

备注1。给定的CDT $T=(\mathcal{R},S)$T=(R,S)，如果T中每个叶节点的深度都是N，那么CDT是一个完整的树，表示为$Compl(T)$Compl(T)，最优结果属于包含MPT的N阶段对应的所有结果序列的集合。

从请求者的角度来看，完整序列和部分序列之间存在语义差异，即完整的结果序列不能进一步扩展。

如果MPT中的阶段数为N，则CDT是一个完整的树。给定集合R中各项目之间的转换分数，我们可以计算出一个可能结果序列的潜在分数，得到N项的最佳结果序列如下。

$\theta^*=\mathop{\arg\min}\limits_{R'\in Compl(T)}score_T(R').\tag{10}$θ∗=R′∈Compl(T)argmin​scoreT​(R′).(10)

在方程10的基础上，引入了算法1来控制我们的工作流程，并得到了一个最佳的结果序列。

算法1.任务生成和结果组合

算法1控制处理MPT T的CDT中所有节点对应的T的工作流的所有阶段，并逐阶段生成结果序列R′。然后我们递归地计算结果序列的潜在得分（第11-12行）。在获得转换概率后，如何获取改进率是关键。当序列R’得到所有投票，序列R得到零投票时，满意度得分最大。在这里，我们可以得到序列R的最高分数。最后，该算法返回具有最大潜在分数的结果序列。因此，当一个序列的长度达到$N$N并且该序列具有最高的潜在分数时，该算法就可以停止。很明显，问题的数量是如此之多，我们不能把每一个问题都用尽。因此，在算法1中，我们采用一种贪心的方法来解决这个问题，也就是说，我们对具有最高潜在分数的结果序列提出问题。这种方法是有效的，可以找到MPT结果序列的最佳组合。然而，它会引起局部最优问题。因此，我们开发了算法2来改进算法1。在算法2中，我们选择k个具有top-k潜在得分的结果序列来实现阶段级任务的生成，以便尽快找到最优的结果序列，减少子任务的数量。

算法2.用top-k方法改进任务生成和结果组合

4 实验

在本节中，我们在一组具有代表性的MPT上进行了一系列广泛的实际实验，并与最先进的方法相比，给出了我们所提出方法的评估结果。

4.1 实验设置

在我们的实验中，我们选择了一系列的任务：关于热门景点的北京一日游的旅游规划。它包含了MPT的典型特征，其中每个任务由一组子任务和子任务之间的约束关系组成，这些关系对于从人群中获得高质量的结果至关重要。此外，我们还开发了一个名为 CrowdTP的旅行规划系统，这是一个开放源代码和可用的。

从三个方面进行评估：

1. 算法2中k的值如何影响MPT中生成的子任务的数量；
2. 我们的投票方法是否能够降低成本；
3. 我们的算法生成的结果序列是否比现有的方法更能满足请求者。

我们系统的工人库由60名本地大学生组成，并由其他一些学生对结果进行评估。为了获得未知的参数，如误差率$\lambda$λ和困难度$\omega$ω，我们引入了100个吸引任务，并要求我们池中的所有工人学习我们的投票模型的参数，然后我们得到了任务难度$\omega \in (0.5,0.7)$ω∈(0.5,0.7)和每个工作人员的误差率$\lambda \in (0.6,0.7)$λ∈(0.6,0.7)。一般来说，我们假设在实验中从Beta分布Beta(1,9)中抽取初始序列P和每个节点对应的序列$R'$R′的质量。

4.2 K对成本的影响

在本实验中，我们探讨了k在top-k中对MPT生成子任务数的影响。K被设置为不同的数字（即2、3、4）。结果如图6所示。由于生成的子任务数量与众包成本密切相关，生成的子任务越多，成本就越高。我们认为，当每个子任务的奖励固定时，根据生成子任务的数量来衡量MPT的成本是公平的。我们还可以观察到，生成更多的子任务会导致最终结果序列中更多的景点。生成的子任务的数量也与我们方法中k的值有关：我们方法中的k越大，生成的子任务越多。具体来说，当$k=2$k=2时，我们的方法生成的子任务平均比我们的方法$k=3$k=3和$k=4$k=4少350和550个。

图6：生成的子任务数随k而变化

4.3 不同方法的总成本

在本节中，我们根据与所有阶段的子任务数相关的总成本来评估两种方法的性能。我们将我们的方法与之前的名为CrowdPlanr的工作[8]进行了比较。我们分别测量两个运行系统中的景点数量（即生成子任务的数量）。结果如图7所示。无论景点数量如何变化，我们的系统CrowdTP生成的子任务都要比CrowdPlanr生成的子任务少得多。因为，在我们方法的每个阶段级任务生成中，都考虑了需求和流量成本来过滤掉一些不需要生成的子任务。特别是，我们可以比CrowdPlanr少完成1.92×104个子任务。

图7：生成的子任务数随方法而变化

4.4 用户满意度评价

本实验旨在评估本系统所产生的规划是否比现有方法更能满足需求。一般来说，由于缺乏基本事实，很难衡量生成的规划的有用性。因此，我们邀请了另外20名工人来评估使用CrowdPlanr[14]和CrowdTP生成的路线。这是一个二元分类任务，要求工人判断哪条路线能更好地满足特定的要求。图8表明，与群体规划者相比，我们的系统CrowdTP可以实现更高的不同任务的用户满意度。特别是对于任务4，我们的方法的满意度平均比众筹者高63.3%。因为，我们的方法考虑了MPT每个阶段的流量成本和请求者的偏好。

图8：不同MPT的用户满意度

5 相关工作

在众包市场中，由于未知的众包工人提供的答案往往是嘈杂和不可靠的，因此众包面临的两个核心挑战是设计工作流和保证结果质量。随后，从两个角度对现有工程进行了简要总结。

在众包的任务处理方法上，现有的众包应用跨越了广泛的任务范围，大致可以分为两类：原子任务和复合任务。原子任务不能分为子任务，工人处理的结果不能分为图像标记[10]、同行评分[3]和情绪分析等组件。复合任务通常由一组子任务组成，最终结果由一系列答案组成。此外，本文还将复合任务分为两个子类：组合任务和MPT。组合任务可以转换为一组子任务，每个子任务都需要众包。典型的组合任务包括手写识别、视频识别和任何类型的原子任务分组。然而，MPT不能用同样的方法解决。由于结果是由一组具有某些内部关系的组件组成的，因此很难整体或部分地解决。大量的众包任务属于这一类，例如旅游规划[14]、微写作[22]和翻译[20]等。以前的方法总是将此任务设计为一个整体，以收集最终结果。据我们所知，以前很少有工作来合理控制MPT的质量。

为了获得更高质量的众包结果，以前的工作使用工作流控制众包。对于原子任务，有一个通用的工作流来控制结果的质量。对于复杂的任务，工作流包含两类：分布式工作流[9，11]和迭代工作流[5]。分布式工作流的目的是处理组合任务。它将一个任务分为几个子任务，每个子任务由常规工作流处理，最后将它们组合成一个提交给请求者的完整结果。迭代工作流主要处理一些复杂的任务，这些任务不能通过运行一个完整的通用工作流来达到高质量，并且运行一些通用工作流的迭代来提高结果的质量。

与以往的研究相比，本研究的重点是处理MPT的工作流。虽然激动人心的先前工作成功地处理了MPT的特殊情况-例如，FFV是MPT（微写）[1，13]的一种特殊情况-建议在三个阶段更正和缩短文本：查找、修复、验证。但是，没有通用的工作流来处理MPT。因此，本研究提出一个新颖的工作流程来处理这些任务。

在各种工作流中，结果推理对于控制质量也很重要。多数投票是从多个工人的回答中推断结果的一种众所周知的方法。早期多数投票的工作并没有考虑到工人准确性之间的差异，但对于大多数工人能够正确处理的简单任务是有效的。然而，这种方法可能导致低质量的结果，在困难的任务或能力较弱的工人。为了考虑工人的准确性，建议进行加权多数投票[16]。提出了各种解决方案，如EM和贝叶斯方法来估计工人的精度[16]。

为了进一步改进多数投票策略，有两条研究线与众包任务的具体类型有关。对于孤立的任务，一些文献[6，15]提出了基于概率模型的结果推理方法，以处理不准确和最小化成本，即要求不同的工人执行相同的任务，直到对结果达成共识。对于复杂的任务，一些研究给出了基于概率图形模型的其他推理方法，利用多迭代策略，使用质量敏感的回答模型来处理任务[13]。Askit使用了类似熵的技术[2]。Qasca研究了质量感知推理方法[21]。与这些结果推理方法相比，本研究考虑了众包中多个阶段之间的依赖关系，从而使工作流具有更好的质量。

6 结论

本研究主要探讨复杂作业众包中的品质控制问题。我们确定了一类任务，即多阶段任务，对于这些任务，约束关系对于实现更好的结果质量至关重要。提出了一种基于决策树的MPT众包工作流任务生成和最终结果组合控制框架。提出了一种概率图模型来描述相位级子任务处理和结果推理。以实际的出行规划任务为例，进行了一系列的实验研究。实验结果表明，该方法能以较低的成本获得较高的质量。

7 致谢

This work was supported partly by the National Key Research and Development Program of China under Grant No. 2016YFB1000804, the National Basic Research 973 Program of China under Grant Nos. 2014CB340304, 2015CB358700, and the State Key Laboratory of Software Development Environment under Grant No. SKLSDE- 2017ZX-14. The corresponding author of this paper is Hailong Sun.

参考文献

[1] Michael S Bernstein, Greg Little, Robert C Miller, Bjorn Hartmann, Mark S Ackerman, David R Karger, David Crowell, and Katrina Panovich. 2015. Soylent: a word processor with a crowd inside. Commun. ACM 58, 8 (2015), 85–94.

[2] Rubi Boim, Ohad Greenshpan, Tova Milo, Slava Novgorodov, Neoklis Polyzotis, andWang-Chiew Tan. 2012. Asking the Right Questions in Crowd Data Sourcing. In Proceedings of ICDE’12. IEEE, 1261–1264.

[3] Anirban Dasgupta and Arpita Ghosh. 2013. Crowdsourced Judgement Elicitation with Endogenous Proficiency. In Proceedings of WWW’13. ACM, 319–330.

[4] Anhai Doan, Raghu Ramakrishnan, and Alon Y Halevy. 2011. Crowdsourcing systems on the world-wide web. Commun. ACM 54, 4 (2011), 86–96.

[5] Yili Fang, Hailong Sun, Guoliang Li, Richong Zhang, and Jinpeng Huai. 2016. Effective Result Inference for Context-Sensitive Tasks in Crowdsourcing. In Proceedings of DASFAA’16. Springer, 33–48.

[6] Jianhong Feng, Guoliang Li, Henan Wang, and Jianhua Feng. 2014. Incremental Quality Inference in Crowdsourcing. In Proceedings of DASFAA’14. Springer, 453–467.

[7] Tao Han, Hailong Sun, Yangqiu Song, Yili Fang, and Xudong Liu. 2016. Incorporating External Knowledge into Crowd Intelligence for More Specific Knowledge Acquisition. In Proceedings of IJCAI’16. AAAI Press, 1541–1547.

[8] Haim Kaplan, Ilia Lotosh, Tova Milo, and Slava Novgorodov. 2013. Answering Planning Queries with the Crowd. Proc. VLDB Endow. 6 (2013), 697–708.

[9] Aniket Kittur, Boris Smus, and Robert Kraut. 2011. CrowdForge: Crowdsourcing Complex Work. In Proceeding of CHI’11. ACM, 1801–1806.

[10] Aditya Kurve, David J Miller, and George Kesidis. 2015. Multicategory Crowdsourcing Accounting for Variable Task Difficulty, Worker Skill, and Worker Intention. IEEE Trans. Knowl. Data Eng. 27 (2015), 794–809.

[11] Edith Law and Haoqi Zhang. 2011. Towards Large-scale Collaborative Planning: Answering High-level Search Queries Using Human Computation. In Proceedings of AAAI’11. 1210–1215.

[12] Guoliang Li, Jiannan Wang, Yudian Zheng, and Michael J. Franklin. 2016. Crowdsourced Data Management: A Survey. IEEE Trans. on Knowl. and Data Eng. 28, 9 (2016), 2296–2319.

[13] Tran Thanh Long, Trung Dong Huynh, Avi Rosenfeld, Sarvapali D. Ramchurn, and Nicholas R. Jennings. 2015. Crowdsourcing Complex Workflows under Budget Constraints. In Proceedings of AAAI’15. AAAI Press, 1298–1304.

[14] I. Lotosh, T. Milo, and S. Novgorodov. 2013. CrowdPlanr: Planning made easy with crowd. In Proceedings of ICDE’13. 1344–1347.

[15] Mahyar Salek, Yoram Bachrach, and Peter Key. 2013. Hotspotting: A Probabilistic Graphical Model for Image Object Localization Through Crowdsourcing. In Proceedings of AAAI’13. AAAI Press, 1156–1162.

[16] Victor S. Sheng, Foster Provost, and Panagiotis G. Ipeirotis. 2008. Get Another Label? Improving Data Quality and Data Mining Using Multiple, Noisy Labelers. In Proceedings of KDD’08. ACM, 614–622.

[17] James Sprinks, Jessica Wardlaw, Robert Houghton, Steven Bamford, and Jeremy Morley. 2017. Task Workflow Design and its impact on performance and volunteers’ subjective preference in Virtual Citizen Science. International Journal of Human-Computer Studies 104 (2017), 50–63.

[18] Jaime Teevan, Shamsi T. Iqbal, and Curtis von Veh. 2016. Supporting Collaborative Writing with Microtasks. In Proceedings of CHI’16. ACM, 2657–2668.

[19] Luis Von Ahn, Benjamin Maurer, Colin McMillen, David Abraham, and Manuel Blum. 2008. recaptcha: Human-based character recognition via web security measures. Science 321, 5895 (2008), 1465–1468.

[20] Omar F. Zaidan and Chris Callison-Burch. 2011. Crowdsourcing Translation: Professional Quality from Non-professionals. In Proceedings of ACL’11. Association for Computational Linguistics, 1220–1229.

[21] Yudian Zheng, Jiannan Wang, Guoliang Li, Reynold Cheng, and Jianhua Feng. 2015. QASCA:A Quality-Aware Task Assignment System for Crowdsourcing Applications. In Proceedings of SIGMOD’15. ACM, 1031–1046.

[22] Yeshuang Zhu, Shichao Yue, Chun Yu, and Yuanchun Shi. 2017. CEPT: Collaborative Editing Tool for Non-Native Authors. In Proceedings of CSCW’17. ACM, 273–285.