第十讲-众包算法

海量数据计算研究中心MassiveDataComputingLab@HIT大数据算法第十讲众包算法请各位评审老师提出宝贵建议！谢谢！本讲内容10.1众包的定义10.2众包的实例10.3众包的要素10.4众包算法例析何为众包?•Outsourcing–外包–已知的雇员•Crowdsourcing–众包–一群不固定，通常数量很大的参与者–将“开源”的思想应用于软件之外最成功的应用:Wikipedia众包的定义•协调一个群体(互联网上的一大群人)做“微工作”(每人做一点贡献)来解决软件或者单个人难以解决的问题•通过一系列的机制和方法来指导和协调群体的行为，从而达到目的volunteersocialfun宽泛的定义众包vs人本计算•众包–大任务到微任务–众包极大程度使用了人本计算•它们不等价请各位评审老师提出宝贵建议！谢谢！本讲内容10.1众包的定义10.2众包的实例10.3众包的要素10.4众包算法例析工业界例子–验证码验证码:每天200MNLP例子–机器翻译•机器翻译–人工评估翻译质量慢而且成本高–非专家和专家认同度高–翻译一个句子$0.10C.Callison-Burch.“Fast,Cheap,andCreative:EvaluatingTranslationQualityUsingAmazon’sMechanicalTurk”,EMNLP2009.B.Bedersonetal.TranslationbyIteractiveCollaborationbetweenMonolingualUsers,GI2010IR的例子–图像搜索TingxinYan,VikasKumar,DeepakGanesan:CrowdSearch:exploitingcrowdsforaccuratereal-timeimagesearchonmobilephones.MobiSys2010:77-90众包搜索:利用众包改进图像搜索图片分类•分类一副图片IR的例子-广告OmarAlonso,DanielE.Rose,BenjaminStewart:Crowdsourcingforrelevanceevaluation.SIGIRForum(SIGIR)42(2):9-15(2008)CV的例子-绘画相似性上边的画在艺术风格上有多大程度相似？非常相似、相似、有些不同、非常不同HumanandMachineDetectionofStylisticSimilarityinArt.AdrianaKovashkaandMatthewLease.CrowdConf2010数据库的例子-CrowdDB•使用众包来回答数据库查询–在哪里使用众包？–如何使用众包？MichaelJ.Franklin,DonaldKossmann,TimKraska,SukritiRamesh,ReynoldXin:CrowdDB:answeringquerieswithcrowdsourcing.SIGMOD2011:61-72请各位评审老师提出宝贵建议！谢谢！本讲内容10.1众包的定义10.2众包的实例10.3众包的要素10.4众包算法例析众包工人在任务上工作的人请求者提交任务平台任务管理提交任务发布任务查找感兴趣的任务收集答案返回答案平台智能任务(HITs)•请求者通过Web服务API创建“智能任务”（HITs）。•工人–登陆–选择HITs–执行之.•请求者评估结果，给完成的HIT打分(满意度).目前1,000,000工人来自100国家完成数以百万HITs请求者&工人建立HIT测试HIT发布HIT查找HITs接受HIT做工作提交HIT拒绝或批准工人的回报•报酬($$$)•有趣（避免无聊）•社交•赚好评/声望•学习新的东西（例如英语）•副产品（例如重验证码）•创建自服务资源（如维基百科）•多重诱因通常是在并行工作任务的报酬•一个HIT多少钱?•微妙的平衡–太少了，没兴趣–太多了，吸引垃圾发送者–付出过多构成反激励–钱并不能提高质量，但是（通常）增加参与性WinterA.Mason,DuncanJ.Watts:Financialincentivesandtheperformanceofcrowds.SIGKDDExplorations(SIGKDD)11(2):100-108(2009)众包中的问题•选择（或自主开发）众包平台•人机交互–付款/激励，界面和交互设计，通信，名誉，招聘，挽留•质量控制/数据质量–信任，可靠性，垃圾邮件检测，标签共识•任务管理•人群管理–结合人类处理单元（HPU）和CPU人机交互•在人机交互中从用户获取输入是很重要的–调查–快速原型–可用性测试–认知走查(cognitivewalkthrough)•在第3页及以后的HITs，不会有工人选择。•许多这样的HITs放在那里超过一个月，始终没有完成。•设计不良的任务发现界面会伤害市场中的每一位参与者！质量控制•工人回答的质量是极为重要的组成部分•将它作为“整体”质量-不仅仅是工人•双向评价–你可能会认为工人做得不好。–同样的工人可能会认为你是一个糟糕的请求者。质量控制•支持率–多数表决–确定始终不同于多数的工人•资格考试–问题：减缓处理过程，很难测试相关性–解决方案：创建主题相关的问题，以便用户在开始评估前熟悉此过程•缺少保证-仍然不足以保证获得好的结果资格测试：优点和缺点•优点–利用好的的工具来控制质量–调整及格标准•缺点–设计和实施测试需要额外的成本–可能会解雇工人，耽误完成时间–难以核实主观任务•尝试创建和任务相关的问题，让工人在开始任务之前熟悉任务处理坏的工人•支付“坏”的工作而不是拒绝它?–赞成:维护声誉，承认设计不良的故障–反对:鼓励欺诈，损害评级系统•用奖金作为奖励–最低支付$0.01且以$0.01作为奖金–比拒绝0.02美元的任务更好•如果垃圾发送者被抓到，则阻塞其未来的工作任务分配•推方法：系统➠工人–系统采取完全的控制将指定的任务分配给谁。•拉方法：工人➠系统–该系统只设置环境，使工人自己给自己（或彼此）的分配分配。任务推荐•迭代推荐•捕捉用户兴趣•估计用户质量•成本-质量权衡请各位评审老师提出宝贵建议！谢谢！本讲内容10.1众包的定义10.2众包的实例10.3众包的要素10.4众包算法例析实体识别IDProductNamePricer1iPadTwo16GBWiFiWhite$490r2iPad2ndgeneration16GBWiFiWhite$469r3iPhone4thgenerationWhite16GB$545r4AppleiPhone416GBWhite$520r5AppleiPhone3rdgenerationBlack16GB$375r6iPhone432GBWhite$599r7AppleiPad216GBWiFiWhite$499r8AppleiPodshuffle2GBBlue$49r9AppleiPodshuffleUSBCable$19现有的技术机器人32机器•基于相似性–相似性函数（例如.Jaccard）–阈值(例如.0.8)•基于学习Jaccard(r1,r2)=0.9≥0.8√Jaccard(r4,r8)=0.10.8×(r1,r2)(r1,r3)(r3,r4)(r5,r6)(r3,r9)匹配不匹配33人•CrowdDB[Franklinetal.SIGMOD’11]SELECTp.id,q.idFROMproductp,productqWHEREp.product_name~=q.product_nameCrowdSQL34简单的解决方案O(n2)Xn=10,000$0.01/HIT$1,000,000•智能任务(HIT)35•基于簇的HIT分批策略O(n2/k2)Xn=10000,k=20$0.01/HIT$2,50036机器+人钱|时间|质量钱|时间|质量钱|时间|质量37混合人机工作流程IDProductNamePricer1iPadTwo16GBWiFiWhite$490r2iPad2ndgeneration16GBWiFiWhite$469r3iPhone4thgenerationWhite16GB$545r4AppleiPhone416GBWhite$520r5AppleiPhone3rdgenerationBlack16GB$375r6iPhone432GBWhite$599r7AppleiPad216GBWiFiWhite$499r8AppleiPodshuffle2GBBlue$49r9AppleiPodshuffleUSBCable$19(r1,r2,0.90)(r4,r6,0.85)(r1,r7,0.82)(r3,r4,0.76)(r4,r7,0.70)(r8,r9,0.55)(r2,r3,0.45)(r2,r7,0.35)(r3,r5,0.31)(r4,r5,0.20)(r3,r6,0.15)(r1,r3,0.10)...0.2(a)去除可能性0.2的对38混合人机工作流程(r1,r2)(r4,r6)YESNOYESNO(r1,r7)(r3,r4)YESNOYESNO(r4,r7)(r8,r9)YESNOYESNO(r2,r3)(r2,r7)YESNOYESNO(r3,r5)(r4,r5)YESNOYESNO(r1,r2)(r1,r7)(r3,r4)(r2,r7)(r1,r2,0.90)(r4,r6,0.85)(r1,r7,0.82)(r3,r4,0.76)(r4,r7,0.70)(r8,r9,0.55)(r2,r3,0.45)(r2,r7,0.35)(r3,r5,0.31)(r4,r5,0.20)(r3,r6,0.15)(r1,r3,0.10)...0.2(a)去除可能性0.2的对(b)产生HITs来验证记录对(c)输出匹配对39HIT生成•为了众包，必须将给定记录对的集合组合到HITs中。1.基于对的HITs2.基于簇的HITS40基于对的HIT41基于簇的HIT42基于对的HIT生成(r1,r2)(r4,r6)YESNOYESNO(r1,r7)(r3,r4)YESNOYESNO(r4,r7)(r8,r9)YESNOYESNO(r2,r3)(r2,r7)YESNOYESNO(r3,r5)(r4,r5)YESNOYESNO(r1,r2,0.90)(r4,r6,0.85)(r1,r7,0.82)(r3,r4,0.76)(r4,r7,0.70)(r8,r9,0.55)(r2,r3,0.45)(r2,r7,0.35)(r3,r5,0.31)(r4,r5,0.20)(r3,r6,0.15)(r1,r3,0.10)...0.243基于簇的HIT生成•目标：给定一个记录对集合P和簇大小阈值K，基于簇的HIT生成问题的优化目标是生成最小数目基于簇的HIT:H1,H2,···,Hh,满足如下两个约束:1.对于任何ℓ∈[1,h],|Hℓ|≤k，其中|Hℓ|表示Hℓ中的记录数2.对于任何(ri,rj)∈P,存在Hℓ(ℓ∈[1,h])使得ri∈Hℓ和rj∈Hℓ44基于簇的HIT生成(r1,r2,0.90)(r4,r6,0.85)(r1,r7,0.82)(r3,r4,0.76)(r4,r7,0.70)(r8,r9,0.55)(r2,r3,0.45)(r2,r7,0.35)(r3,r5,0.31)(r4,r5,0.20)(r3,r6,0.15)(r1,r3,0.10)...0.2r7r4r6r1r2r3r5r8r9r1r2r4r7r3r4r5r6r2r3r8r9簇大小阈值k最小化HITs的数量NP-HardHIT1HIT2HIT3基于簇的HIT45大连通分量(LCC)双层法假设k=4小连通分量(SCC)r7r4r6r1r2r3r5r8r9(r1,r2,0.90)(r4,r6,0.85)(r1,r7,0.82)(r3,r4,0.76)(r4,r7,0.70)(r8,r9,0.55)(r2,r3,0.45)(r2,r7,0