SCI论文（www.lunwensci.com）:
摘要：为了在有限的预算内尽可能提高标签任务的可靠性，考虑异构群智感知中的任务分配问题。使用多臂赌博机算法，通过加权投票机制得到任务的信誉得分，对模型使用UCI真实数据集进行验证。实验结果表明，多臂赌博机算法在动态学习工人能力、提高标签任务可靠性方面表现较好。随着预算的增加，准确性趋于最优任务分配策略。因此，该算法不仅能够动态学习工人能力，而且能进行有效任务分配，解决群智感知异构性问题。
关键词：多臂赌博机算法；群智感知；异构性；任务分配
Task Allocation of Heterogeneous Crowdsensing Based on Multi Arm Bandit
YAO Qiuyan
(School of Optical-electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093)
【Abstract】：In order to improve the reliability of label tasks as much as possible within a limited budget,the task allocation problem in heterogeneous crowdsensing is considered.The multi arm bandit algorithm is used to obtain the reputation score of the task through the weighted voting mechanism,and the model is verified using UCI real data set.The experimental results show that the multi arm bandit performs well in dynamically learning workers'ability and improving the reliability of label tasks.With the increase of budget,the accuracy tends to the optimal task allocation strategy.Therefore,the algorithm can not only dynamically learn workers'ability,but also effectively allocate tasks to solve the problem of crowdsensing heterogeneity.
【Key words】：multi arm bandit;crowdsensing;heterogeneity;task allocation
0引言
标签任务在机器学习领域应用广泛，标签数据的数量和质量显著影响机器学习算法的性能。然而，现有的从专家处收集可靠的标签非常不划算。近几年出现的群智感知服务[1]，使我们能够以较低开销从工人处收集标签数据。
群智感知网络主要关注分析工人能力并将收集到的带有噪音的标签数据进行聚合。通常，加权投票机制用于标签聚合，以工人的能力作为权重。许多现有方法使用期望最大化算法对标签静态数据聚合，进而评估工人能力以及真实标签[2]。然而，如何自适应收集标签往往被忽略。另外，大多数现有的任务分配方法以在线方式运行，例如，为了处理这种探索(学习工人能力)和利用(收集标签数据)，文献[3]根据工人的表现动态进行工人采样。本文我们提出基于多臂赌博机算法的异构群智感知网络任务分配方法(Multi Arm Bandit Task Allocation，MAB-TA)，使用权重对工人能力进行建模，通过动态学习降低工人能力的不确定性。
1相关工作
任务分配是群智感知网络研究的重要方向，目前主要有两类方法：推式和拉式[4]。在拉式方法中，工人自己寻找符合自身条件的任务。在推式方法中，感知网络控制分配任务给哪个工人。最近，由于任务异构性增加，许多研究者开始研究异构群智感知。文献[5]试图根据工人的信誉得分为标签任务定价以最大化任务发布者的效用。文献[6]提出一个完全分布式的异构任务分配解决方案。
本文算法设计受到多臂赌博机算法的启发，目前，文献[7]提出利用多臂赌博机算法选择在预算约束条件下信息量最大的用户，文献[8]将任务分配过程分为多轮,每轮覆盖所有任务，然后在预算有限约束下招募工人最大化感知质量。本文的做法借鉴文献[8]，一方面在探索阶段保证每种异构任务被多个工人覆盖；另一方面在利用阶段每轮分配一个任务给最有能力的工人。
2多臂赌博机的任务分配
2.1问题描述
假设我们有N个未标签的任务，索引为L={1,…,N}，其中每一个任务都为类型集C中的某一类型c，其中，|C|=C。
让
为N个任务未知的真实标签，y∈{-1,1}。每一次，对于一个给定的任务从M个工人(W={1,2,…,M})中选择一个工人，提供标签(可能带有噪音)并在总预算B中消耗一个单位。目标是找到合适的任务工人对以在有限的预算内尽可能多的收集到可靠标签。然后，把收集到的标签聚合以估计任务真实的标签。群智感知标签任务分配框架如图1所示。
设y
i,j是是工人j提供的任务i(类别ci)的标签，定义工人j提供ci类任务的权重为
，权重与工人完成该类任务的能力成正相关。权重在一开始是一个不确定数
值，通过不断学习将得到较为准确的评估。然后使用加权投票机制，计算真实标签y的估计值，如式(1)所示：
2.2工人能力探索阶段
探索阶段以批处理的方式运行，主要目的是探索工人的能力，因此对每一种类型选择N'个任务(C×N'≪N)。并让M个工人对这C N'个任务进行标签，C N'个任务的索引集为L1c。由于此时工人能力不确定，因此在进行标
签聚合时赋予所有工人相同的权重，如式(2)所示：
其中，yi为任务i的信誉得分。定义累计损失衡量工人完成标签任务的质量，即
其中，
为指示函数，当
时输出1，意
味着当工人提供的标签与聚合后的标签不一致时，会产生1的损失。本阶段总共消耗的预算为B1=MCN'<B，因此下一阶段的预算为B2=B−B1，探索阶段的具体步骤如下所示：
步骤1：已知C种类型，每种类型选择N'个任务；步骤2：从M个工人处收集对这C N'任务的标签；步骤3：使用式(2)进行标签聚合；
步骤4：使用式(3)计算累计损失；
步骤5：预算减少到B2，剩余任务索引集为
2.3任务分配利用阶段
在这一阶段，将使用预算B2得到剩余N−CN'个任务的工人-任务对，根据式(1)的加权投票机制，在t步选择具有最低信誉得分的标签任务执行，即
对于这个选定的标签任务，应选择最有能力完成该任务的工人。另外，工人的可靠性是在2.2节学习的内容。在工人选择中了解哪个工人可靠和选择被认为可靠的工人之间存在权衡，为了解决这一权衡问题，将任务分配建模成多臂赌博机。在每个步骤中，将一单位的预算分配给一组行动中的一个并获得环境给予的一些可观察的损失，目标是在整个分配过程中最小化损失。对于任务类型c，按照式(5)计算工人权重：
其中，tc为类型c的标签任务的出现次数，ηtCc为与tc相关的学习率，使用指数性加权是多臂赌博机算法的
常用形式。根据指数加权规则，以正比于wj,tc的概率pj,t选择工人jt执行标签任务it。接着获得工人jt对任务it的标签yit,jt，并以此计算任务信誉得分yit以及标签估计值it并获得工人jt的完成任务损失为
该损失的无偏形式为下式(6):
最后，我们更新与当前任务具有相同类型的任务的累计损失Loss以及信誉得分。任务分配利用阶段的具体步骤如下所示：
步骤1：根据式(4)选择t步执行的任务it；
步骤2：得到it的类型c，并更新tc←tc+1；
步骤3：设置
，并根据式(5)计算权重；
步骤4：选择工人jt的概率为
步骤5：获得标签yit,jt，根据式(1)计算任务信誉得分以及标签估计；
步骤7：更新无偏损失jt,t；
步骤8：如果任务it已被所有工人标记，则从L中剔除；
步骤9：重复上述过程，直到L2c为空。
3实验结果与分析
3.1基准数据集
我们在3个二分类数据集上进行实验：电离层数据集(N=351)，乳腺癌数据集(N=569)，硬币数据集(N=1372)，它们模拟群智感知网络中的标签任务，所有任务的标签都真实可用。为了模拟真实的异构情况，首先使用K-means算法将这三个数据集分别聚类成C=3、4、5。由于这3个数据集中没有工人，因此在上述异构群智网络中生成模拟工作者(M=30、40、50)。
3.2实验结果
将MAB-TA与下面3种算法进行了比较：Crowd-Sense[4]、MTS-WS[9]和Naïve，指标为准确性，即真实标签被正确估计所占的比例。
(1)CrowdSense：首先计算每一个工人的能力估计，然后计算任务信誉得分，制定最优工人子集，并不断迭代考虑是否对任务的工人子集进行替换。
(2)MTS-WS：考虑基于上下文感知信息的任务分配，将上下文信息分为工人的内部能力以及外部能力，实现平台利润最大化。
(3)Naïve：随机选择一个任务-工人对，并使用加权投票机制进行标签聚合。
在不同预算水平上比较所有方法的准确性，结果如图2、图3、图4所示。
3.3结果讨论
MAB-TA的准确性在3个数据集上都优于其他方法，这表明MAB-TA可以在具有异构性的群智感知网络中更好地提高标签准确性。另外，在所有情况下，MTS-WS的表现都很差，有的甚至比Naive还要差，原因是因为MTS-WS在每一步都对可靠工人的子集进行抽样，根据工人在先前任务中的标签表现计算其置信区间上限，然而在异构群智网络环境中，在以前的任务中可靠的工人完全可能在下一个任务上表现很差这使得MTS-WS无法动态地正确了解工人的可靠性。尽管CrowdSense也采用了动态抽样工人子集的机制，但其探索利用的标准使其有机会随机选择一些可能在下一个任务中可靠的工人。
4结语
本文提出了一个基于多臂赌博机算法的异构群智感知网络任务分配方案。通过实验证明了MAB-TA在异构群智感知网络标签任务中的可用性，分析表明，随着预算趋于无穷大，MAB-TA的性能收敛到最优策略的性能。
参考文献
[1]陈荟慧.面向移动群智感知的高质量数据收集方法研究[D].西安:西北工业大学,2017.
[2]丁岳伟,王飘.基于社交平台的众包质量控制算法研究[J].软件导刊,2017,16(12):90-93.
[3]余敦辉,袁旭,张万山,等.基于动态阈值的时空众包在线分配算法[J].计算机应用,2020,40(3):658-664.
[4]于彦,江先亮,金光.移动群智感知系统的任务分配方法研究综述[J].无线通信技术,2021,30(4):10-15.
[5]SUN Y,TAN W N.A Trust-aware Task Allocation Method Using Deep Q-learning for Uncertain Mobile Crowdsourcing[J].Human Centric Computing&Information Sciences,2019,9(1):25.
[6]张金宏,王兴伟,黄敏,等.绿色互联网中面向节能的分布式拓扑管理机制[J].计算机学报,2017,40(7):1517-1529.
[7]方文凤,周朝荣,孙三山.移动群智感知中任务分配的研究[J].计算机应用研究,2018,35(11):3206-3212.
[8]GAO GJ,WUJ,YAN Z Y,et al.UnknownWorker Recruitment with Budget and Covering Constraints for Mobile Crowdsensing[C]//2019 IEEE 25th International Conference on Parallel and Distributed Systems(ICPADS),2019:539-547.
[9]王静.基于强化学习的群智感知激励机制研究[D].合肥:中国科学技术大学,2021.
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！
文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/jisuanjilunwen/40993.html
