“众包应用程序的以数据为中心的工作流”- RiturajSingh 博士学位论文

L’UNIVERSITE DE RENNES第601号博士学校数学与信息与通信科学与技术通过RiturajSingh面向众包应用程序的以数据为中心的工作流论文于2021年5月7日研究单位：INRIA、IRISA（UMR 6074）、雷恩-布列塔尼大西洋公司博士学位论文答辩前的报告员：Salima BENBERNOU巴黎笛卡尔大学博士教授Farouk TOUMANI布莱斯帕斯卡勒大学博士教授评审团组成：主席：Stefan Haar，INRIA巴黎-萨克雷研究总监评审员：Albert BENVENISTE INRIA研究总监雷恩-布列塔尼大西洋Marco MONTALI BozenBolzano自由大学副Dir. 论文：Loïc Hélouët INRIA雷恩-布列塔尼大西洋研究员共同导师：Zoltán MIKLÓS雷恩大学讲师一个已知的基因i首先，也是最重要的，我要感谢我的导师Loïc Hélouët和Zoltán Miklós，他们是一个博士生所希望的理想导师。Loïc是绝对辉煌的，他敏锐的逻辑思维与精确的见解和佐尔坦的能力，给予尖锐的反馈与他的剃刀锋利的智力是无与伦比的。他们给了我绝对的自由，鼓励我探索新的想法，提供工具和方法来进行研究，并积极希望倾听我半生不熟的想法。我记得我的第一天，当Loïc告诉我，无论我想，我可以来敲门在他的办公室里，我无耻地敲了他的办公室太多次，我甚至不能跟踪它。谢谢你，佐尔坦，让我在你的办公室里呆了三年，从问刀片问题到白板讨论。我会想念和你分享办公室。除了学术上的声音，他们是非常好的人。从我在法国的第一天起，他们就以各种可能的方式提供帮助，从我的住所到大学--现场形式，评论和教学，一路照顾国防。在过去的三年半里，我永远感激我所得到的那种建议，我确信我还没有从他们那里学到接下来，我要感谢辩护陪审团的成员，他们荣幸地同意我审查这篇论文：Salima Benbernou和Farouk Toumani的报告和相关反馈，Stefan Haar、AlbertBenveniste和Marco Montali在过去几个月里在他们的支持下对这篇论文进行了亲 切 的 评 价 。 我 还 要 感 谢 我 的 CSID 成 员 Emmanuelle Anceaume 和 MatthiasWeidlich进行的年度进展审查和评估。我 想 对 大 卫 · 格 罗 斯 - 安 布 拉 德 的 支 持 和 帮 助 表 示 衷 心 的 感 谢 。 David 在HEADWORK项目的实施和协调中发挥了重要作用。除了从一开始，大卫帮助我很多，使我与Druid团队整合-谢谢!我将永远记住并珍惜与大卫共度的时光--从项目到开发会议，从午餐谈话到电影。我还要对皮埃尔·布尔希斯在证据和合作方面的帮助表示衷心感谢。ii我很幸运，在我的博士学位期间，我是Druid和Sumo团队的一员，还有一群很好的友好研究人员。两个团队成员都非常友好和合作。我将永远珍惜从团队午餐到绿色研讨会的时刻在单打比赛中，我将错过与特里斯坦·阿拉德、米卡尔·富尔索夫、阿诺德·马丁、娜塔莉·贝特朗、奥坎·桑库尔、埃尔韦·马钱德、蒂埃里·杰龙、阿卜杜勒-卡里姆·凯西尔、阿德里安·奥贝尔、伊恩·让泰、约里斯·杜格佩鲁和通波亚琳娜·安-德里亚米兰托（纳蓬）的谈话。特别是，我会想念与伊恩的咖啡休息和我们关于几个当代话题的长时间谈话。如果不说出那些一直在我身边起起落落的朋友的名字，这个学术追求将是不完整的。我想感谢我的朋友们--阿里夫、贾亚布拉塔、苏曼、尼图、阿尼尔班、阿伦、苏门、阿尔潘、阿扬、苏福迪普、苏巴纳、沙比纳和普贾，他们在很短的时间内成为我生命中不可或缺的一部分。谢谢你让这一切发生在雷恩。我想感谢我最亲密的朋友--IIT巴特那朋友--苏布霍、德巴普里亚、里泰什、尼莱什和苏迪普塔的针织品小组。我也想感谢我令人惊叹的朋友- Pratyusha，Chetanya，VedPrakash，Vikas -非常感谢，伙计们!我还要感谢我的一群同学--Himanshu、Anirudh、Jainath、Nitesh、Parimal和Ved，他们总是让我有宾至如归的感觉，即使我在千里之外。你们都是很棒的人，非常爱你们。最后，也是最重要的，我衷心感谢我的父母Ranjit和Rani，他们是我生命中一切事物背后唯一的能量来源。我的父亲，一位学者，是我攻读博士学位的灵感来源。我母亲无限的爱和牺牲无法用语言来描述。我还要感谢我的兄弟Keertiraj和堂兄弟Abhishek、Anamika和Poornima的无限支持和照顾。在结束本节时，我想感谢所有开展这项工作的机构和机关，即：国家研究机构（ANR）、HEADWORK项目（ANR-16-CE 23 -0015）1、Wirk2、国家自然历史博物馆1. http://headwork.gforge.inria.fr/2. https：//www.wirk.io/3. https://www.spipoll.org/R总结iii关键词：众包、以数据为中心的工作流、质量保证简介随着新数据的指数级生成，组织面临着管理数据、设计算法和提取知识所需的信息过载。生成的大多数数据都是非结构化的，由图像、视频和自然语言文本组成。必须对数据进行集成、处理、存储、索引、利用、跟踪和报告，以满足组织在竞争激烈的数据感知市场中的需求。虽然该组织依赖于由数据管理和人工智能算法驱动的自动化机制，但完全自动化仍远未实现。此外，一些任务最好由人来执行，而在这些情况下，人类能够理解各种形式的数据。- 文本、图像和视频。 众包已经成为解决需要人类智能和机器难以解决的任务的一种主要的新范式。例如，实体解析亚马逊机械土耳其人（AMT）、CrowdFlower、Crowle Factory等商业平台通常，所有众包平台都遵循相同的执行工作流客户端有一个任务，并准备iv采购。客户端将任务提交给平台。然后，众包平台将任务分配给多个工作人员。工作人员利用他们的专业知识和信念执行任务，然后将结果返回给平台。该平台汇总、处理结果，作为回报，员工将获得奖励。处理完成后，平台将结果返回给客户端。众包被用于各种领域，如论文的问题与目的大多数当前的众包平台，如AMT，允许执行广泛的任务。所考虑的任务主要是微任务。微任务是小型、快速、独立的任务，需要很少的时间来完成（标记图像、回答简单的布尔问题等）。然而，在现实生活中，任务通常很复杂，需要多个级别的专业知识。 考虑一个复杂的任务：获取昆虫图像这些复杂的任务是一个真正的挑战。首先，需要一个模型来根据较小任务的编排来定义复杂任务。它要求具体说明任务并协调其执行。编排不仅仅是安排微任务的问题：数据必须从一个微任务传递到下一个微任务。此外，整个执行过程必须以一组正确的结果为基础。人群提供的答案是主观的，容易出错。为了减轻问题并最大限度地提高这就是为什么必须汇总来自不同来源的答复。此外，一项复杂的任务有有些任务可能需要几个答案才能达成一致，而v准确的状态。它需要一种机制来最佳地使用预算，并在成本和准确性之间找到一个权衡。因此，部署复杂任务的复杂性以及本论文的目的是定义在传统众包平台之外部署复杂应用程序的技术，以及 提供以数据为中心的算法，以优化成本和准确性。我们通过首先为复杂的工作流定义形式化模型，然后提供概率模型来管理成本和准确性之间的权衡来应对这些挑战。我们还提供了一个工具来检查复杂工作流的终止和正确性属性复杂工作流的模型除了简单的人类智能任务，如标记图像，分析情绪，众包平台有能力执行更复杂的任务。众包的下一个阶段是在现有众包的基础上设计复杂的流程。的确， 许多项目，特别是科学工作流，采用高级复合任务编排的形式每个高级任务可以单独地被认为是一个数据收集任务，或者被认为是一个大数据集的处理，被构造为独立的简单微任务的结果的联合。然而，协调这些高级别任务以实现最终目标需要更高级的过程。很容易遇到这样的情况，即高级别任务的结果类似地，在某些情况下，允许并行处理数据集，然后合并所获得的结果。一个典型的例子是交叉验证由不同的众包工作者返回的响应。许多项目不能被描述为重复的、独立的微任务的集合：它们需要特定的技能和专业知识。vi参与者之间的工作。我们称这样的项目为"复杂任务"。复杂任务的典型形式是高级阶段的编排。这些阶段中的每一个都需要特定的技能，可以被认为是一个新的目标本身，并可以分解成更精细的编排，一直到因此，这些过程是动态的，必须考虑到工人的技能第一个挑战是弥合从这可以通过高阶响应来实现，允许知识渊博的工作人员返回更简单的任务编排，而不是对即时问题的本文的第一个贡献是一个以数据为中心的工作流模型，称为复杂工作流，用于在现有的众包平台上指定、验证和部署复杂的任务。该模型提供了允许设计复杂任务（描述为一组简单任务的编排）的高级结构，并进一步管理员工技能、数据依赖性它允许此外，员工可能会提出改进一项复杂的任务，该任务似乎过于复杂，无法由人群中的一个员工完成这种细化被指定为高阶操作，用于将任务替换为完成的我们已经定义了模型的语法和语义任务分为三类：原子任务（可以由工人在一个步骤中完成）、复杂任务（需要分解为更小任务的编排）和自动化任务（机器可以完成的复杂的工作流被标记为有向非循环图，其中每个节点对应于一个任务，并且边表示任务执行的优先级然后，我们提供了四个语义规则，作为工作流的指导原则。语义规则定义了：vii由工人执行原子任务，执行自动化任务，并将细化形式化。工作者将标记为复杂任务的节点细化为新的工作流，该工作流包含一组任务，这些任务复合地实现了细化节点的目标。复杂工作流的执行包括按照工作流指定的顺序应用任务。任务将其前一个任务在工作流中生成的数据集作为输入，并生成新的数据集或细化当前工作流。可判定性复杂的工作流由一组语义规则定义，用于分配工作人员、编排和执行任务。但是，工作流可能永远无法到达最终配置。这可能是由于工作者输入了工作流无法正确处理的特定数据，或者是由于在运行时出现了无限重写在这种情况下，工作流可能会陷入僵局。此死胡同会阻塞工作流执行流并阻止实现最终目标。即使工作流总是完成，单靠此属性也不足以满足客户的要求。例如，工作流W可能以一组错误的结果结束，即结果不符合客户的要求。在这种情况下，返回的输出对客户端没有任何用处。因此，在完成工作流的同时，确保工作流的准确性非常重要我们将从终止问题开始研究模型的形式属性：给定一个复杂的工作流、一组具有其配置文件和底层数据转换的工作者，一个工作流是否至少为一个执行（存在终止）和一个工作流的所有执行我们已经确定，由于工作流的控制部分（复杂的工作流可以模拟两个计数器），存在性术语通常是不可判定的D’autrepart, la terminaison universelle est décidable, et nous avons présenté un sous-ensemble intéressant 更具体地说，我们限制了在执行复杂工作流期间可能发生的任务细化的数量，并假设该工作流没有被细化。viii任务的递归重写。然后，结束归结为实现。 在工作流的一组有限的执行中的数据依赖关系。我们给出了一个基于最弱前提推导的有限递归复杂工作流终止的算法。最弱前提条件是在[Dij75]中引入的，它是证明程序正确性的一种正式方法。我们证明了FO的片段在前提条件计算下是闭合的。接下来，我们考虑工作流的正确性问题同样，如果输出约束以可判定的FO片段表示，则复杂工作流的校正是可判定的。我们还分析了我们看到复杂的 对于具有最低复杂度的片段，（co）-2EXPTIME中的实体性主要来自描述在初始配置中必须满足的前提条件的公式的指数大小。这可以被认为是棘手的复杂性，但是可以预期原子任务的质量保证所提出的复杂工作流模型允许指定具有复杂工作流的任务，并且可以检查正确性，在模型的合理子集上终止，主要是非递归规范。工作流提供了一种有效的方法来同步不同阶段的复杂任务它们定义了任务的分解、排序和执行方式。但是，它们不提供保证工作流生成的数据质量的机制验证过程也不允许您考虑工作流的成本一般来说，众包平台的任务有一个固定的预算，首先，我们考虑为ix在众包中，工作人员是非常异质的：他们有不同的背景，一个专业领域。由于我们不能只信任一个贡献者，为了应对这种异质性，任务经常被一个基本问题是从返回的结果集推断正确答案另一个挑战是以合理的成本获得可靠的答案。无限的预算可以让大量的员工完成每项任务，但有限的预算需要最大限度地利用资源。我们提出了一种用于众包平台的聚合技术。我们考虑了两个关键因素，即任务的难度和工人L’agrégation est basée sur l’algorithme d’Expectation Maximization [同时，我们还提供了CrowdInc，这是一种迭代标记技术，可以优化收集响应和聚合响应的总成本。该算法实现了一种员工分配策略，该策略根据每个周期计算的动态质量阈值做出决策，从而在员工和员工之间实现良好的折衷。成本和准确性。我们在真实数据集上评估算法以验证我们的方法。我们在多个基准测试中展示了CrowdInc实现了良好的准确性、降低了成本，并将其性能与现有解决方案进行了比较。复杂工作流的质量保证在定义了优化单个阶段的成本和准确性的算法之后工作流中的任务可以通过两种方式执行，即同步执行（一个任务在将结果发送到下一个任务之前处理其所有输入数据）和异步执行（一个任务在数据准备就绪后立即将数据发送到下一个任务）。我们将相位的概念添加到我们的模型中，并对它进行了修改。语义，以考虑任务的复制和响应的聚合。然后，我们将探讨这两种执行类型所带来的挑战我们x我们将聚合算法用于作为工作流一部分的原子任务。我们表明，这两种类型的执行需要不同的阈值机制。同步执行需要一个本地阈值策略，该策略根据分配给阶段的任务和预算派生阈值。相反，最后，我们将我们的结果与传统的众包方法进行了比较，我们发现所提出的技术至少可以达到与在同步模式下以较低预算使用大多数技术相同的精度然而，在大多数情况下，所提出的方法确实节省了一些预算。我们介绍了平台本文的最后一个贡献是一个名为Crowdplex的工具，它实现了前面章节中介绍的终止分析和校正算法。xiTABLE来自C组确认I摘要三序言11导言21.1论文概述和投稿。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...51.2大纲。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ...92最新技术水平112.1众包市场112.2众包空间142.3任务和语言172.3.1以过程为中心的方法182.3.2人工制品中心方法272.4数据282.4.1数据推理302.4.2数据库352.4.3SQL372.4.4以数据为中心的模型402.4.5最弱先决条件422.5质量保证432.5.1聚合技术452.5.2预算优化50面向众包的以数据为553众包的复杂工作流56xii内容表3.1高阶示例573.1.1一个简单的例子：演员受欢迎程度民意调查583.1.2一个真实的实地例子：SPIPOLL倡议593.2预备课程613.3工作流形式化643.4操作语义学673.4.1数据操作673.4.2操作语义学703.5结论774可判定性794.1最弱前提条件的有效计算804.1.1关闭FO类824.2完成复杂的工作流864.2.1符号执行树964.2.2以保证系结终止974.3复杂工作流程的正确性1014.4用例1074.4.1符号执行树108的定义4.4.2检查终止的算法1104.5平台1134.6结论114质量保证117.5原子任务的质量保证1185.1聚集体的基本成分1215.1.1概率论1215.1.2影响众包1225.1.3期望最大化1245.2聚合模型1255.2.1汇总答案1285.3成本模型1305.3.1信心和门槛131xiii内容表5.3.2CrowdInc：优化成本的5.4实验1355.5结论1396复杂工作流程的质量保证1416.1导言1416.2具有聚合的复杂工作流1436.3聚合模型1536.4工作流的成本模型1536.5实验和结果1636.6结论171第173章第一次见面7结论1747.1贡献摘要1747.2前景1757.2.1短期前景1767.2.2长期展望178参考书目183附录202A.1 定理证明1202A.2 定理的证明2206xivISTF.伊古尔斯1.1众包机制。... . . . . . . . . . . . . . . . . . . . . . . ... ...32.1亚马逊机械土耳其人......................................................................................122.2亚马逊机械土耳其人任务列表截图。列表呈现任务集、到期日期和预期奖励。........................................................................ 132.3来自foldIt界面14的屏幕截图2.4Crowdforge框架：基于映射还原模型的拆分和重组复杂的人类计算任务，摘自[Kit+11]。152.5BMPN模型：用例"作业发布"，摘自[ All16 ]。...........................................182.6一个经典的用餐哲学家的问题，被重新表述为佩特里网，摘自[NAC]。212.7处理投诉的净工作流示例，摘自[VDAVHH04]。二十五2.8以ER图表示的业务工件，指定供应商任务，摘自[BHS09]。...................282.9期望最大化算法通用工作流483.1这是一个简单的演员人气民意调查。................................................................583.2重新定义任务的配置文件，如633.3节点n1的重新设计，替换为任务t的配置文件，如图3.2所示。663.4记录到记录算术运算693.5数据集联合703.6语义规则R1723.7语义规则R273的应用3.8语义规则R374的应用3.9语义规则R475的应用xv图列表3.10 复杂的工作流执行。C0表示分配给节点nint的数据D中的初始配置。C1是C 0的后继：工作者u1被分配到节点n2，t2=λ（n2）是一个复杂的任务。C3描述了通过新工作流Wt2（显示）重新配置节点n 2后的配置在灰色矩形中）。..................................................................................................774.1连接操作示例854.2复杂的工作流934.3为图4.2中显示的复杂工作流重写图4.4一个例子显示了送货限制1024.5一个例子显示εEA约束1024.6已完成运行的不同场景：具有和不具有正确的输出集。.............................1034.7原始工作流W（左）。新的工作流表示为WJafter在工作W（右）中重新定义节点n1....................................................................1084.8符号执行树1095.1生成函数。............................................................................................................ 1275.2基于当前消耗预算估计的阈值值和一轮开始时任务剩余的一部分.......................................................................1325.3算法的可能状态21345.4成本与准确度.................................................................................................1386.1智慧城市中的工作流程1446.2独家分叉。.....................................................................................................1466.3非排他性分叉。.............................................................................................1476.4同步执行。.....................................................................................................1476.5异步示例1486.6加入示例1486.7联合例1496.8对应相位示例1566.9具有非独占分叉阶段158的工作流W6.10 具有新阶段pJx替换工作流W158的6.11 具有不同编排的164xvi图列表6.12 工人准确性分布（50名工人）。.......................................................................1656.13 低专业知识的准确性和成本比较1676.14 工作流1上的准确性和成本比较..................................................................1686.15 工作流2上的准确性和成本比较..................................................................1686.16 工作流3中的准确性和成本比较..................................................................1696.17 工作流4中的准确性和成本比较..................................................................1696.18 工作流5中的准确性和成本比较..................................................................170A.1inc（q，cx，qJ）指令的编码。...........................................................................203A.2dec（q，cx，qJ，qJJ）指令的编码。.................................................................. 203A.3非零检验的编码，然后递减。........................................................................... 204A.4 状态更改后的零测试编码205xviiIST T型台2.1CINEMA数据库示例，摘自[AHV95]。...............................................................302.2连接查询结果。.............................................................................................. 384.1终止的复杂性（EXPT代表EXPTIME）。................................................... 1064.2正确性的复杂性（EXPT代表EXPTIME）。............................................... 1065.1数据集描述。.................................................................................................1355.2EM+聚合的比较（具有回忆、特异性任务难度）w.r.t MV、D S、GLAD、PMCRH、LFC、ZenCrowd对鸭子的识别数据集1365.3EM+聚合的比较（具有回忆、特异性任务难度）w.r.tMV、DS、GLAD、PMCRH、LFC、ZenCrowd关于产品标识数据集1365.4EM+聚合的比较（具有回忆、特异性任务难度）w.r.tMV，D S，GLAD，PMCRH，LFC，ZenCrowd对人气的看法137号数据集5.5CrowdInc、MV和静态EM的运行时间（以秒为单位）。........................ 1376.1评估参数166