客服电话:15682930301

计算机网络论文

当前位置: 毕业论文>计算机论文>计算机网络论文 > 正文

基于细粒度用户可靠性的众包任务分配研究

发布时间:2019-12-05 17:24文字数:12106字

  摘 要:众包(Crowdsourcing)计算模式因其自身优势,近年来被学术界视为一种高效大规模数据集收集方式。但是,由于众包用户自身能力所限,不同用户提供的答案可能存在不合理的情况。因此,如何将收集到的用户答案进行整合,来推断任务的正确答案,是一项关键问题。

  已有的真实答案预测方法通过挖掘用户可靠性和任务话题之间的相关性来解决这一问题。但是,已有研究仅在有限的任务上起作用,对标准数据集的利用不充分,对于有些任务不兼容。为了考虑兼容性,我们认为任务和用户都存在聚类,进而提出了一个通用的细粒度方法。该方法包括两个方面:建立共聚类和基于共聚类可靠性模型的真实答案预测机制。首先,基于用户对标准任务的回答,利用特定的聚类方法得到用户聚类、任务聚类,建立共聚类可靠性模型。然后对于一系列答案未知的目标任务,根据学习得到的模型,将收集到的用户答案以特定的方式组合,预测出目标任务的真实答案。

  通过理论分析,我们证明了本论文提出的方法适用性强,可以更好的表达用户和任务之间的关系。同时,实验表明,我们的方法可以对目标任务得到更为精确的估计。

  关键词:众包;共聚类模型;答案预测;标准任务

  前 言

  随着互联网的不断发展,众包这种新的生产组织形式应运而生[1] 。企业为了有效地解决技术问题或者是发现创意想法,利用互联网发布各种任务。而网络大众里,有些人是兴趣驱动,有些人是利益驱动,利用自己的时间,通过网络这一媒介,来完成企业发布的任务。众包提供了一种全新的组织大量劳动力的方式,对于软件业和服务业尤其有用。

  本文介绍了众包模式以及众包的广泛应用,包括一些众包平台和众包在科研领域的应用,同时也提出了该模式存在的问题,指出众包的质量控制是一项值得科研工作者去研究探讨的问题,进而提出了本文的众包模式学习方法,通过有效的将用户和任务进行聚类,学习用户类和任务类之间的可靠性,更加有效准确地解决任务,此方法具有良好的通用性。本文完成的主要工作及创新点有:

  (1) 介绍众包模式以及众包的工作流程,列举了一些众包平台和众包在科研领域的应用,阐明了众包的研究价值,同时提出了众包模式中存在的问题。

  (2) 提出用户和任务分别存在聚类,将用户集和任务集分别聚类。同时学习用户聚类和任务聚类,得到共聚类可靠性模型,从而得到比现有方法更为通用的模型。

  (3) 利用学习到的共聚类可靠性模型,结合朴素贝叶斯的思想,采取特定的算法,得到对目标任务序列的真实答案更为精确的估计。

  (4) 我们通过在真实的数据集上进行实验,将该方法和现有基本方法的效果进行对比与分析,验证了该方法的有效性。

  第1章 绪论

  本章首先介绍了众包的研究背景和意义,然后简单介绍了众包国内外研究现状,其次,概述了本文所做的主要工作以及创新点,在本章的最后介绍了这篇论文的组织结构。

  1.1 研究课题的提出

  近年来,产生大规模数据集对于研究和工业应用都有着巨大的价值。传统的策略大多是雇佣对相关领域感兴趣的专家,但想要收集大规模的数据,几乎是要付出很大代价且几乎不可能实现的。因此,众包服务,像AMT(Amazon Mechanical Turk)或者CrowdFlower,通过将将任务分发给全世界的用户,来收集数据集。

  1.2 国内外研究现状及挑战

  由于众包在提供大规模数据集时有着很好的有效性,因此它越来越受欢迎。用户不一定要是领域专家,任务也通常不止分发给一个用户,这导致了用户们的答案质量往往是参差不齐的。因此,如何聚集用户答案来推断任务的真实答案是众包领域的一个关键性挑战。

  一个直观的解决方法是最大值投票法,该方法将被最多数目的用户选择的答案作为最终的真实答案。但是,它没有考虑到一个问题,用户之间的可靠性是参差不齐的当低质量的用户数目比高质量用户数目还多时,这种方法得到的结果并不理想。为了解决这个问题,一系列加权投票的方法被提出,这类方法的宗旨是给有着更高可靠性的用户赋予一个更大的权重,从而该用户所给出的答案对于最终答案的影响因子也更大。然而,这些方法的一个共同特点是,均假设一个用户对于所有任务的可靠性是一致的。其实这是不合理的,因为任务类型是各种各样的,每个用户也都有自己所擅长的任务类型。

  1.3 本文的主要工作及创新点

  本文首先介绍了众包是什么,众包模式是如何工作的,我们研究众包的意义和价值体现在哪,同时提出了众包模式中的存在问题,为此,提出了本文的解决方案,也是本文的核心问题。

  我们充分利用了每个事物都有其代表特征这一想法,认为用户之间存在用户聚类,任务之间存在任务聚类。同一类任务或者同一类用户享有同样的模式而不考虑他们之间的差异性。比如说,一个用户聚类共享的模式是该用户聚类对于各种任务聚类的可靠性。更具体的说,一个用户对于不同的任务类型有着不同的可靠性,但是,我们认为对于一个特定的任务聚类,属于同一个用户聚类的用户们的可靠性是相同的。虽然我们清楚,每个用户都是独一无二的,对于同一任务的认知或者说是可靠性不可能完全相同,但我们将最为相似的用户聚集在一起而不考虑他们之间的细微差别。对于任务来说,也是同理,我们将最为相似的任务聚集在一起而不考虑他们之间细微差别。利用聚类的想法,可以使我们的方法有着更好的通用性和有效性。因此,我们首先学习用户聚类和任务聚类,得到共聚类可靠性矩阵,然后基于该模式,分别通过随机选择一定个数的用户,和基于用户标签及共聚类可靠性矩阵选择用户,来回答目标任务,通过特定的算法获得任务的正确答案推断。

  在本文中,我们首先引入标准任务,即拥有标准答案的一类数据。用户首先对给定的标准任务进行作答,根据作答情况,得到用户特征,采用k-means算法的思想对用户进行聚类,然后计算出任务特征,采用类似的思想对任务进行聚类,学习到用户聚类和任务聚类以后,计算得到共聚类可靠性矩阵,代表同类用户与同类任务的相关性。然后根据学习到的模型,利用朴素贝叶斯算法的思想,预测目标任务的真实答案,获得对目标任务更加精确的推断。最后,通过在模拟仿真实验以及在真实数据集上进行实验,和基准方法进行对比与分析,验证了该众包方法的有效性。

  1.4本文的组织结构

  本文共分为六个章节,各章的内容安排如下:

  第一章:绪论。本章简要地介绍了众包的研究背景以及众包的研究价值,同时也介绍了国内外现有的众包研究现状,指出解决众包的质量控制问题的必要性,进而提出了本文的主要工作和创新点。

  第二章:相关技术和研究工作。本章首先详细介绍了众包的工作流程和一些众包平台,同时介绍了众包在科研领域的应用,并指出了众包研究中的一项关键问题——众包质量控制问题。

  第三章:问题抽象与模型建立。本章对众包工作流程进行抽象,介绍了该众包模式的理论模型,给出该问题的形式化定义。

  第四章:算法设计。本章首先利用聚类算法的思想,给出获得用户簇、任务簇以及共聚类可靠性模型的算法。接着,利用朴素贝叶斯算法的思想,对于答案未知的目标任务,结合已有的用户簇、任务簇和共聚类可靠性模型,推断目标任务的正确答案。

  第五章:实验与对比。本章首先通过仿真实验,展示了在用户规模不同、用户质量不同时该算法得到的结果对比。然后,基于真实的数据集,将设计的算法与两个基准方法所获得的预测答案准确率进行对比,分析该方法的有效性。

  第六章:总结全文,提出未来工作的设想与展望。

  第2章 相关技术和研究工作

  所谓众包(crowdsourcing),是指一个公司或者组织(requester)把需要执行的工作任务(tasks)分解成合适的规模(micro Tasks),借助于众包平台(例如Amazon MTurk或CrowdFlower等)进行发布,互联网用户(Crowds或Workers)可以自愿选择来完成这些任务,当然,这些用户对于公司或组织来说是匿名的,完成任务以后这些用户可以获得相应的奖金。这些任务通常由一些简单操作就可完成,比如判断一句话的表述是否合理,将图片进行分类等。本章详细介绍了众包的特征,众包是如何工作的,众包的应用,列举了一些众包平台,然后介绍了众包模式中存在的问题。

  2.1 众包基本特征

  2.1.1 基本特征

  众包的基本特征包含:(1)计算机自身通常难以解决众包中的任务;(2)通过公开的方式发布一些任务,传递并召集互联网上的大众群体;(3)大众用户独自完成任务,或者协作完成一些任务;(4)是一种分布式的问题解决机制[2] 。

  2.1.2 与外包区别

  外包(outsourcing)是指企业将非核心业务委派给专业的外部公司(往往是因为人力资源有限,并且想要保持住企业组织的核心力量),从而减少成本,凝聚了人力资源,提升了企业效率和形象。

  众包和常规意义上的外包不同,众包的任务分配给的大众网络用户具有不确定性,而外包则是将任务给确定的个体来完成。此外,外包非常注重外包对象是否专业,而众包更注重自由发挥和创意,有一定的随机性[3]。

  最关键的区别在于,外包的合同双方通常不是匿名的,是基于一定的契约精神的。发布者和完成者对于对方的背景、资历等都具有充分的了解才可以确定合作合同,任务实现的媒介也未必是网络平台。而众包的用户对于任务发布人来说,是不知道具体个人信息的,众包平台提供的有限数据就是彼此之间的所掌握的信息。这可能会导致一些众包质量控制问题,比如恶意欺骗。尽管如此,众包还是有其独特的优势。众包的特色就是“众”,集大众的力量,解决大规模的、枯燥的、重复性的任务。

  2.2 众包工作流程

  众包领域的研究的主要包含了三个方面的问题,分别是众包的任务该怎么设计,众包的成本如何做到尽可能地低,还有就是众包用户的质量问题。具体来说,众包领域的研究问题可以细化:微型任务设置、用户奖励策略、任务完成时间的控制、发布者成本控制策略,检测欺骗类型用户,众包结果聚集及答案预测、工作流程设计等[4] 。

  众包的主体包括了任务发布者(requester)和任务完成者,也叫做用户(worker)。任务(tasks)将他们关联到一起。当有任务需求的人想要利用众包来完成自己的任务时,需要按照一定的流程来使用众包。首先他要设计自己的任务,然后可以利用众包平台来发布设计好的任务,等待用户来完成任务。用户可以在众包平台上查找感兴趣的任务,选择性的回答并且提交给众包平台。在任务期限截至以后,任务需求者将用户的答案进行筛选并整合。具体的工作过程如图2.1所示。

  图 2.1 众包工作流程

  2.3 众包应用

  美国加州伯克利大学(University of California, Berkeley)的SETI@home分布式计算项目[5],遍及世界各地的成千上万的个人电脑的闲置计算能力,为他所用。那么,与此类似,成千上万的互联网大众的闲置脑力也可以通过分布式的人力资源网络得到充分的利用。

  2.3.1 Amazon Mechanical Turk

  机器的智能化训练需依靠庞大的数据,谷歌开源的Gooogle Open ImageDatasets,Yooutube-8M中的标记视频等,这些需要按规则分类的数据集必须依靠人类的智慧,才可以区分每一个细微的差别,机器是无法直接完成的。那么这些海量数据由谁来标定是我们需要考虑的,亚马逊的劳务众包平台(AMT)很好的解决了这个问题[6] 。

  亚马逊劳务众包平台,是一个有着十几年历史经验的平台。随着时间推进,平台不断的发展,到今天为止,AMT拥有累计超过50万的用户参与注册。用户们在平台上领取一些微型的任务,完成这些任务从而可以得到相应的报酬。

  AMT会给用户进行评级。往往用户等级越高,相应的酬劳也越高。当任务需求者发布任务需求时,AMT系统会自动将任务优先分配给等级比较高的用户。等级较低的用户被分配到任务的机会也会相对小一点。

  通过实例训练机器的方式被称为监督式学习,而实例的产生,出自于AMT的用户们,也就是在线劳工。ImageNet拥有超过1400万被分类的图片,这其中大部分都是由AMT上5万名用户花费了两年的时间完成的。AMT将这类服务形容为“人工的人工智能”[7] 。

  2.3.2 科研领域应用

  近几年来,众包作为一种很有效的解决问题的方法,被大众所认可。在数据挖掘领域中,众包逐渐应用于科学研究的训练和测试阶段,将其作为科学实验的一个良好的辅助手段。

  在机器学习、信息检索等研究领域里,一个语料库是否优质有着比较重要的影响。通过同一语料库,可以比较不同系统或者算法之间的有效性。然而,如果是通过相关领域的研究者来一项一项地标注知识数据,从零开始建立该研究领域相关的大型数据库,显然是非常浪费时间和精力的,并且成本很高。因此,众包可以很有效地运用于研究领域,解决该问题。

  众包在监督学习中有着一定的应用,监督学习也称为分类或者归纳学习,这一种学习方法与人类的学习模式有着类似之处。人类往往从积累的经验中,来对问题进行思考、归纳和总结,从而再遇到此类问题时具备一定的能力。但是,计算机本身没有人类的智慧,而是要通过搜集大量的数据来进行机器学习,这些大量的数据就类似于人类的经验积累。显然,监督学习中需要有明确类标、且有着一定的可靠性的训练数据集。这种数据集可以通过众包模式来有效获得。可以首先通过众包来标注各个数据的类别,然后利用各种监督学习的方法来学习分类特征,获得分类算法,这也就是计算机对大量数据进行学习的过程,最后还可以利用众包的数据集来衡量算法的优劣程度,以便优化算法。通俗来说,就是把一些对于计算机来说难以解决,但是对于人类来说比较简单的问题,交给众包来解决,这种解决方式高效、成本较低且有着较高的可靠性。

  信息可信度计算,也就是对于信息的可信程度进行估计,这是近几年的一个研究热点[8] 。过去是新闻媒体主导言论的时代,信息往往具有较高的真实性,而随着互联网的蓬勃发展,无数的网民都有了话语权,可以发帖、评论。网民们不需要为自己的言论承担责任,导致网络中充斥着大量无效的、虚假的信息。这种无效的网页内容浪费了我们的时间,严重影响了我们对于信息知识的获取,甚至会误导我们。Carlos Castillo等人在论文中提出了一种判断一篇微博信息是否可信的分类算法[9] ,其中巧妙地运用了众包模式,来进行微博语料的标注。我们可以发现,众包在科学研究中遇到限制和瓶颈时,是一种很好的辅助手段。

  2.4 众包质量控制

  众包可以为任务发布者提供大量的匿名的用户,通过聚集这些用户的智慧和劳动,很多实际问题,而且往往是计算机难以直接完成的,可以得到有效解决。但是,总会存在一些用户,没有很好的为任务发布者完成任务,提交的答案质量低下,造成负面影响。如何将有噪声存在的答案(即错误的干扰答案)聚集起来推测任务的真实解,是众包中一项有挑战性的任务。

  2.4.1 低质量结果产生的原因

  企业和科研的需求日益增加,众包平台日益发展普及,有着越来越多的大众网络用户参与到众包的工作中,这些众包用户显然是多样化的。起初,很多众包用户到众包平台上选择一些任务,往往是因为感兴趣或者是作为一种打发时间的方式。一方面消磨了时间,一方面帮助别人解决了一些问题。金钱上的回报对于这些用户来说不是最主要的目的。有一些众包用户,可能受自身特长技能所限制,完成任务的质量一般。然而,形势严峻的是,随着众包用户的增多,受利益驱动的众包用户也越来越多。其中不乏一些恶意工作者,尽可能付出最少的劳动,对待任务丝毫没有认真严肃的态度,而是随意作答、快速提交,从而导致众包的结果是低质量的。这一问题引起了很多研究者的关注。

  2.4.2 相关工作

  对于含有低质量结果的用户答案,如何将这些答案聚集起来推断任务的真实答案,科研工作者们已经做出了相关的研究。一部分工作考虑将用户的可靠性水平融合进来,作为答案预测的一个因素。David等人提出一种模型,每个用户的可靠性可以被预测,然后使用EM算法来推测真实答案。ZenCrowd[10] 也采用了用户可靠性和EM算法来预测真实答案。尽管他们的模型各不相同,但他们都遵循的原则是,在估计任务真实答案时,赋予更高可靠性的用户更大的权值。但是,他们都不考虑任务之间的异构性,而是假定一个用户对于所有任务都有着相同的可靠性。与之不同的是,我们的方法将用户对于不同的任务有着不同的可靠性作为一个考虑因素,也就是说将用户对于任务的可靠性细粒度化。

  也有一些研究,将用户对于不同任务的细粒度可靠性作为考虑。FaitCrowd[11] 针对任务的描述,采用了话题模型,从而将任务进行聚类,然后估计用户对于属于不同话题聚类的任务的可靠性,从而推断任务的真实答案。Simpson[12] 提出了一种贝叶斯分类组合方法来得到一种更为精确的分类。我们粗略的将这些方法分为两类;一种利用任务描述和任务聚类的关系,另一种对用户对于不同答案的细粒度可靠性进行建模。但是,他们都对任务有着额外的条件,要求任务有特定的描述,或者要求任务的候选答案是非特定的,也就是说仅仅适用于有限的任务。和这些方法不同的是,我们的方法直接从正确性矩阵中学习任务聚类和用户聚类,而对任务的类型没有额外的限制,因此,该方法更为通用。

  基于对标准数据的运用,真实答案预测方法可以被划分为两类。一类是无监督方法,一类是半监督方法。FaitCrowd可以归为第一类,该方法同时推断目标任务的真实答案和用户的可靠性。而采用半监督方法的模型,利用了真实数据来建立可靠性估计。Shah[13] 等人采用了“黄金标准”任务来帮助估计用户的表现水平。

  2.5 本章小结

  作为从各种各样的用户中廉价地收集数据的一种方式,众包模式变得越来越流行。众包往往可以解决计算机难以完成的任务,有着广泛的应用。但是由于人为错误和垃圾邮件的流行,收集到的用户答案往往是有噪声的,对于一项任务,我们希望通过较低的成本获得较高质量的答案,因此,收集并整合用户答案是一项关键问题。

  第3章 问题抽象与模型建立

  我们考虑这样一个众包工作流程:该众包平台包含了若干任务和用户。任务分为标准任务(由众包平台提供)和目标任务(由任务请求者发布)。每个用户需回答平台中所有的标准任务,众包平台收集这些用户答案,然后采用基于用户答案准确率的聚类算法构建用户特征数据库、任务特征数据库以及可靠性数据库。任务请求者发布新的任务,即目标任务。众包平台选择部分用户来完成目标任务,收集用户答案,结合平台中的数据库信息,采用朴素贝叶斯算法的思想,给出目标任务的答案预测。我们的目标是,该众包平台为目标任务提供的答案具有相对更高的准确率,从而更好地为任务请求者服务。

  该众包的工作流程为:

  1. 用户回答平台中的标准任务;

  2. 平台构建用户特征、任务特征和可靠性数据库;

  3. 任务请求者发布任务需求;

  4. 平台选择用户完成任务;

  5. 平台聚集用户答案,提交给任务请求者。

  第4章 算法研究

  4.1 共聚类可靠性矩阵

  聚类是指将一组对象集合分划成多个类别的过程,每一个类别中的对象称为一个簇。一个簇内部的对象彼此相近,簇与簇之间的对象彼此相异。

  在本文的研究任务中,不同的用户有着不同的能力和特长,不同的任务也代表着不同的话题或领域。我们需要根据用户对标准任务的回答,得到用户之间的相似程度,将用户划分到不同的类别中。根据用户聚类和正确性矩阵,再将标准任务进行聚类划分。分别将用户和标准任务进行聚类,由聚类所生成的簇是一组用户或者标准任务的集合,属于同一个簇的用户彼此相近,不同簇之间的用户彼此相异。任务也是同理。

  4.1.1 基于用户回答准确率的任务聚类

  在这里,我将用户对于每一个标准任务的回答情况作为一个用户的特征,即每个用户包含了m个特征。想要将用户聚成l类,则首先随机生成l个聚类中心。对于每个用户,计算出离该用户最近的一个聚类中心,将用户划分为该类别。计算完每个用户所属的类别以后,再重新计算每个类的质心,并更新用户的类别,直到质心不再变化为止[14] :

  1. 随机选取l个初始质心(作为初始cluster);

  2. 重复以下步骤:

  3. 对每个用户特征

  表示第j类用户中正确回答任务i的人数除以第j类用户回答任务i的总人数。根据每类用户对于每个任务的平均准确率矩阵,采用k-means算法进行聚类。将每类用户对于一个任务的平均准确率作为该任务的特征,即每个任务包含了l个特征。想要将任务聚成k类,则首先随机生成k个聚类中心,对于每个任务,计算出距离该任务最近的聚类中心,将任务划分进该类别。计算完每个任务所属的类别以后,再重新计算每个类的质心,并且根据新的质心更新任务的类别,直到质心不再变化为止,由此,我们得到了k个任务聚类:

  1. 对每个标准任务i:

  2. 对每一个用户聚类j:

  3. 计算

  第5章 实验与对比

  首先,我们进行仿真实验,分析了用户人数以及用户可靠性对预测准确率的影响。接着,我们在真实的数据集上进行实验,将该方法与两个基本方法进行对比与分析,验证了该方法的有效性。

  5.1 模拟仿真

  5.1.1 贝塔分布

  在本文的研究问题中,想要表示某一个用户簇对于某一个任务簇的可靠性,也就是该用户簇中的用户对于该任务簇中任务的一种能力体现,可以采取用户簇中正确回答任务簇中任务的人数与该用户簇中所有参与作答该任务簇中任务的总人数的比值来体现。显然,该可靠性值仅能出现于0到1之间,而我们在没有具体历史数据的前提下,用户聚类与任务聚类之间的可靠性具有随机性,这些信息提示我们,共聚类可靠性可以采用贝塔分布[16] 。贝塔分布的概率密度函数为:

  在本文中,我们进行问题抽象时,假设一共有500个用户,4种用户类别。这些用户在4种用户类别上服从对称狄利克雷分布,也就是4个参数均相同,在这里设为0.5。假设一共有20个标准任务,4种任务类别。这些标准任务在4种任务类别上服从对称狄利克雷分布,也就是4个参数均相同,在这里设为0.5。

  5.1.3 模拟用户作答

  假设有m个标准任务,n个用户。每个用户需要回答所有的标准任务,那么在模拟过程中,用户该如何选择答案是我们需要考虑的。由5.1.2节可知,已知标准任务在任务聚类上服从dirichlet分布,用户在用户聚类上也服从dirichlet分布,那么按照该分布所对应的概率选择相应的k和l分别作为该任务和该用户对应的标签,根据k和l从共聚类可靠性矩阵中获取相应的值,作为该用户对于该任务的可靠性,记为x。那么对于一个目标任务,假设有B个候选答案,则该用户回答是正确答案的概率为x,为其他答案的概率是

  1. 对每个标准任务i:

  2. 从B个候选答案中随机选择一个作为正确答案b;

  3. 按照该任务属于K个任务聚类的概率选择一个聚类作为该任务的标签k;

  4. 对每个用户j:

  5. 按照该用户分别属于L个用户聚类的概率选择一个聚类作为该用户的

  目标任务的正确答案。进行100次模拟实验,得到的预测准确率如下图5.1所示。

  图5.1 用户人数对准确率的影响

  将目标任务随机分配给10个用户,得到的平均准确率为0.727,随机分给30个用户时,得到的平均准确率是0.916,而当选取50个用户来完成这些目标任务,并将他们的答案聚集起来预测目标任务的正确答案时,平均准确率高达0.969。显然,让更多的用户加入,完成目标任务,通过我们建立的模型,可以得到更高的准确率。当然,更多的用户回答意味着任务请求人要付出更高的成本。

  (二)用户可靠性对预测率准确的影响

  我们可以将500个用户的可靠性进行排序,来比较从500个用户中随机选取30个用户和选取30个高可靠性用户得到的准确率,如下图5.2所示:

  进行100次模拟实验,得到随机选取30个用户来完成任务的平均准确率为0.918,而根据共聚类可靠性模型选取总体来说更高可靠性的用户来完成目标任务,平均准确率高达0.967。

  5.2 相关预测方法

  为了评价我们的算法在预测目标任务正确答案时的准确率,我们有必要将该算法和一些基础的算法进行对比。在此,我们首先介绍两种即将进行对比的算法。

  5.2.1 majority voting

  多数表决法是一种很朴素的方法。在推断目标任务正确答案时,每一个候选答案都对应一个计数器,每个工作者给出他的答案,与此同时,相应的候选答案的计数器的值加1。指定个数的用户回答完该任务后,选取计数器中值最大的所对应的候选答案作为对于目标任务真实答案的估计。

  5.2.2 weighted voting

  另一种基本的也是经典的方法是加权表决法。该方法将用户的可靠性作为考虑因素。基于用户对标准任务的作答情况,计算每个用户对于标准任务的回答准确率,将该准确率作为该用户的可靠性。当作答目标任务时,每个候选答案有相应的累加器。对于回答该目标任务的用户,将该用户答案所对应的累加器中加上该用户的可靠性。指定个数的用户回答完该任务后,选择累加器最大的答案作为对于该目标任务真实答案的估计。

  5.3方法对比

  5.3.1 k-折交叉验证

  在本小节中,我们采用了真实数据集BlueBird[18],来将新方法和两个基本方法进行对比。该数据集中包括了108个任务和39个用户,通过询问每个用户每张图片中是否有一只鸟来收集用户答案。

  为了充分利用该BlueBird数据集对算法的效果进行测试,采用k-折交叉验证法[19] 。首先将所有任务的顺序打乱,然后将打乱后的任务集合划分为k个子集,依次取其中一个子集作为目标任务集合,其余k-1个子集作为标准任务集合。每一次根据标准任务训练出共聚类模型,用目标任务集合检测算法的有效性。在该实际问题中,我将任务设为2类,用户设为4类。

  5.3.2 对比结果

  在利用测试数据集检测预测答案的准确率时,首先,我们考虑39个用户均加入回答,将实验模拟进行100次,得到的准确率如图5.3所示:

  我们可以发现,由于39个用户全部加入作答,MV方法得到的准确率始终为0.759,WV方法的准确率始终为0.778,而新方法的准确率的平均值达到0.863。

  接着,我们从39个用户中随机选择30个用户来完成任务,经过100次模拟实验,通过计算得到,MV方法的平均准确率为0.757,WV方法的平均准确率为0.791,而新方法的平均准确率可以达到0.849。100次模拟实验的准确率如图5.4所示:

  图5.4 三种方法对比图(部分用户参与作答)

  我们可以发现,总的来说,新的方法是明显优于MV方法和WV方法的,因为新提出的方法可以学习用户特征和任务特征,建立共聚类可靠性模型,基于此,得到更高的预测准确率。当然,WV方法也是优于MV方法的,因为WV方法通过训练数据集,获取了每个用户的基本的可靠性,而MV方法是不考虑这些信息的。

  但是,我们也发现,新提出的方法有很少数的情况下预测的准确率不太理想。由于每一轮模拟实验,都要对用户和任务进行重新的聚类,以及对用户的抽样。由第4章可知,我们采用k-means方法,初始化阶段聚类中心的选择具有随机性,所以每一次实验可能得到不一样的聚类结果。聚类效果的优劣显然对预测的准确率产生一定的影响。

  最终,我们展示在不同的方法下,不同用户分配数对预测准确率的影响。如图5.5,图5.6,图5.7所示。在该数据集中,我们可以发现,增加低可靠性用户不能很好地提升预测答案的准确率:  5.4本章小结

  本章首先介绍了两个基本的真实答案预测方法,然后我们对BlueBird数据集进行k折交叉验证,从而将这三种方法的预测准确率进行对比与分析,验证了新方法的有效性。

  第6章 总结与展望

  6.1 本文总结

  本文首先介绍了众包的含义、工作流程、众包在当下的广泛应用等等,让读者对众包有了基本的了解。然后,笔者简要介绍了众包模式存在的一种问题,即众包用户自身能力有限,不同用户提供的答案可能存在不合理的情况,如何将收集到的用户答案进行整合,来推断任务的正确答案,是一项关键问题。

  基于此,我们提出一种有效的解决方案。通过用户对于标准任务的作答情况,获得每个用户的特征,利用k-means方法将用户进行聚类,然后基于用户作答准确率,得到每个任务的特征,利用相似的算法将任务聚类。基于用户聚类和任务聚类,计算出共聚类可靠性矩阵。同一类用户对于同一类任务具有相同的可靠性。

  接下来,我们就可以基于学习到的用户聚类、任务聚类和共聚类可靠性模型,利用朴素贝叶斯算法的思想,对于真实答案未知的目标任务,推导出每个候选答案为真实答案的可靠性,从而对目标任务进行答案预测。

  最后,我们通过模拟仿真实验实现了该方法,并在真实的数据集上进行实验,将该方法和两个基本的预测方法进行对比与分析,验证了该方法的有效性。

  6.2 后续工作展望

  在实验的过程中,我认为有两处有待提高。

  其一,在对用户和任务进行聚类时,我们可以进一步改进,采用fuzzy-c方法[20] ,得到每个用户对于每一个类的隶属度,而非直截了当地将用户明确归为某一类。因为在第5章用真实数据集来考验算法的时候,我们发现,虽然总的来说,新提出的方法准确率是最高的,但也会存在少数情况下,新的方法不如WV。每一次用户聚类和任务聚类的效果对实验还是有一定影响的,也许我们将聚类的算法进行改进,利用模糊聚类的思想,可以得到更加稳定的、波动更小的结果。

  其二,在对目标任务计算每个候选答案为真实答案的概率时,目标任务的聚类分布其实是未知的,我们采用的学习标准任务在每一个任务聚类上的比例,将该比例序列作为目标任务对于每一个任务聚类的隶属度。可以考虑一个改进方案,将目标任务的聚类分布也当作是未知量,若是这样,未知量的增加使得公式的推导难度加大,复杂度更高,需要通过EM算法[21] ,来预测目标任务的聚类分布,以及每个候选答案为真实答案的概率。

移动版:基于细粒度用户可靠性的众包任务分配研究

本文标签: