12.39 众包机器协同技术介绍
众包机器协同技术的核心想法是众包任务选择,即在一定预算约束下,选择最有“收益”的任务分配给众包工人进行求解。具体来讲,由于存在大量的 HTML 表格,而金钱上的预算又是有限的,假设为 k,能否精心挑选最有“收益”的 k 个表格中的列,让众包将它链接到知识库的概念上。剩余的列可以通过机器的方法,如基于文本相似性或图结构相似性进行匹配,或基于众包答案进行推理。
不难看出,众包机器协同技术的核心挑战在于如何定义“收益”,以及如何选出最有收益的 k 个HTML 表格的列。这里给出解决这些问题的基本想法,具体的技术介绍见文献 [33]。具体而言,有关表格列的收益考虑两方面因素:
● 任务的难度:如果一个任务对于机器来讲比较难,则应优先分配给众包解答。这里的“难度”反映了单纯依赖机器匹配的歧义程度。以图 6 为例,上面的一列机器以较大概率(0.95)认为是电影,而下面的一列机器则比较含糊,歧义性强。直观上讲,下面的列对于机器的难度更大。基于这一想法,提出了使用信息熵度量难度的方法。
● 任务的推理能力:很多时候,如果众包解决了某些任务,可以帮助推断其他任务的答案。图 7给出了两种推理示意:① 左侧是表内推理。如果众包确定了表格的第二列是电影导演,那第一列是电影名称的可能性就提升了。② 右侧是表间推理。如果众包判断了一列的类型,与它相似的列对应到同一类型的可能性就提升了。基于这一想法,提出了基于概率的任务推理模型。
基于上述因素,提出了任务收益(Utility)模型,并证明了挑选整体收益最大的 k 个任务这一问题属于 NP 难问题。为此,提出了一种有效的近似算法,并证明了该算法的近似比是 1 - 1/e(其中 e 为自然对数)。当众包返回 k 个任务的答案后,再根据前面介绍的表内和表间推理其它任务的答案。