12.39 众包机器协同技术介绍

众包机器协同技术的核心想法是众包任务选择，即在一定预算约束下，选择最有“收益”的任务分配给众包工人进行求解。具体来讲，由于存在大量的 HTML 表格，而金钱上的预算又是有限的，假设为 k，能否精心挑选最有“收益”的 k 个表格中的列，让众包将它链接到知识库的概念上。剩余的列可以通过机器的方法，如基于文本相似性或图结构相似性进行匹配，或基于众包答案进行推理。

不难看出，众包机器协同技术的核心挑战在于如何定义“收益”，以及如何选出最有收益的 k 个HTML 表格的列。这里给出解决这些问题的基本想法，具体的技术介绍见文献 [33]。具体而言，有关表格列的收益考虑两方面因素：

● 任务的难度：如果一个任务对于机器来讲比较难，则应优先分配给众包解答。这里的“难度”反映了单纯依赖机器匹配的歧义程度。以图 6 为例，上面的一列机器以较大概率（0.95）认为是电影，而下面的一列机器则比较含糊，歧义性强。直观上讲，下面的列对于机器的难度更大。基于这一想法，提出了使用信息熵度量难度的方法。

● 任务的推理能力：很多时候，如果众包解决了某些任务，可以帮助推断其他任务的答案。图 7给出了两种推理示意：① 左侧是表内推理。如果众包确定了表格的第二列是电影导演，那第一列是电影名称的可能性就提升了。② 右侧是表间推理。如果众包判断了一列的类型，与它相似的列对应到同一类型的可能性就提升了。基于这一想法，提出了基于概率的任务推理模型。
基于上述因素，提出了任务收益（Utility）模型，并证明了挑选整体收益最大的 k 个任务这一问题属于 NP 难问题。为此，提出了一种有效的近似算法，并证明了该算法的近似比是 1 - 1/e（其中 e 为自然对数）。当众包返回 k 个任务的答案后，再根据前面介绍的表内和表间推理其它任务的答案。