#224 人肉计算(2): 意图博弈 GWAPs

在上一篇文章中我们已经介绍了人肉计算的定义。这篇文章我们来谈谈人肉计算中的「意图博弈」(Game With A Purpose, GWAPs)。

所谓「意图博弈」,指让玩家进行互相博弈,并从博弈过程中收集数据,并用于某种意图。

ESP 游戏

为了说明意图博弈,我们以图像标注这个问题来作为例子。

图像标注是一种对人类来说非常容易,但对计算机视觉算法(目前)来说依然非常困难的一种行为,需要大量的图像搜索和分析。

ESP 游戏[1]的目的是提供并激励人们进行图像标注,放置低质量的标签。

ESP 游戏具有下面的规则:

  • 两个随机选择的玩家会显示相同的图像
  • 这两个玩家不知道他们在玩什么
  • 玩家每次输入同一个标签后会获得一个评分
  • 一段时间之后,图像会发生变化
  • 一段时间之后,游戏会自动结束
  • 一个标签被足够多玩家输入之后,将成为「敏感词」(Taboo word)并显示在图像上,不能在被输入
  • 单数或复数形式的「敏感词」不能被输入(对英文游戏来说)

在这样一个规则下的博弈中,标签的质量是能够被保证的,这是因为:

  • 互相博弈的玩家不能彼此通信(除了他们输入的标签之外)
  • 这个规则一个「良好的标签阈值」,因为若干个标签会被匹配的玩家所接受
  • 如果需要的话,可以通过跟踪图像的独立标签约定,玩家可能会同意

ESP 游戏的评估

在 ESP 游戏推出一年之后,大约有三万人参与了这个博弈,在八十五万张图片上产生了四百万多个标签,其中大约 80% 的玩家游戏时间超过一天,甚至一些人每个星期玩二十个小时。

结果表明,玩家输入的标签是有意义的,而我们所期望获得的标签也已经被玩家输入了。

我们先尝试分析一个简化版本的 ESP 游戏:

  • 没有「敏感词」
  • 标签一致的得分独立

并假设:

  • 对于每个图片都有一个相关标签集合
  • 每个图片都有一个表示它似然值的频率

在这种情况下,以频率递减的方式输入标签的策略最终将导致贝叶斯纳什均衡,因此,每个玩家都能够获得最高分[3]。

对于 ESP 游戏的实验评估来说,有以下结果:

  • 同义词冗余:标记为「guy」的图片同时又有 81% 的标记了「man」
  • 同时出现:标记为「clouds」的 85 章图片中,有 68% 的也被标记了「sky」
  • 频繁的颜色匹配:超过 10% 的「敏感词」都是颜色(其中黑色占所有标签的 3.3%)
  • 越抽象的词约有可能出现「building」比「terraced house」更可能。

当一个机器人只利用显示的敏感词且不使用显示的图像,来预测下一个标签来执行 ESP 博弈时候,能够很好的对每张图片提出 4.3 个标签,并且标签的一致率为 95%。

建模

对于文章的标签预测来解释是不够的,我们需要重新建模:

  • T: 到目前为止图像的「敏感词」集合
  • t: 机器人的下一个标签

考虑下面几点

  1. 根据贝叶斯公式,我们有

    \[ P(t|T) = \frac{P(T|t)P(t)}{P(T)} \]

  2. T 中的标签假设是互相独立的,那么根据最大似然估计的思想我们有(如果图像的种类非常之多,那么这是可以接受的):

    \[ P(T|t) = \Pi_{s\in T}{P(s|t)} \]

  3. 如果图像的数量和种类都非常大,那么对于所有的 T, P(T) 通过相同的值 C 来估计,其中 C 是归一化尝试,使所有 t 之和为 1。

  4. t, P(t) 和 P(t|T) 从文本集合中产生。

结合上面的几点,我们不难得到[4]:

\[ P(t|T) = \Pi_{s\in T}{P(s|t)P(t)\frac{1}{C}} \]

接收者设计

接收者设计」解释了为什么 ESP 游戏搜集的标签是一般的[5]:

「接收者」设计表示人们如何将他们的交际信号传递给其他人:

  • 向中央车站发出的指示取决于询问者以及他是步行还是驾车
  • ESP 游戏对于一个年轻人和一个计算机科学学生来说是不一样的

在 ESP 游戏中,接收者设计产生了许多合适的标签,因为玩家的线索非常少。

ESP 游戏的其他例子

TagATune

TagATune 是一个基于音频的 ESP游戏,收集了音频和音乐的描述。TagATune 指示玩家有以下八个类别之一,他们应该输入什么样的标签[3]:

  • 对象/地点/行动/颜色/心情/电影类型/是否是音乐/无限制内容。

Verbosity

Verbosity 是一个在线的 GWAP,通过以下游戏来收集常识知识:

  • “叙述者”和“猜猜者”配对。
  • 叙述者被给了一个秘密的话,让猜测者通过给她提示来发现这个词。
  • 提示具有预定义句子的形状,空白填充而不使用秘密单词。
  • 叙述者可以看到猜猜的猜测,可以告诉猜测者“热”还是“感冒”。
  • 演员轮流作为叙述者和猜猜。

Verbosity 的提示模板:

  • …用于…
  • …通常接近于…
  • …通常位于…
  • …通常在…
  • …是…的反面
  • …与…相关
  • 「…」是相关词的通配符(例如「Oxford」对于「University」)

Listen Game

[TBA]

US Patent 8,140,518

Common Consensus

Jinx

ARTigo

Combino

Timeline

GWAP 的设计

GWAP 的数据收集机制有:

  • 输出约定(Output-agreement)[13]:
  • 两个玩家彼此不知道对方都是被随机选取的
  • 两个玩家给定相同输入时必须得出相同的输出(不一定同时)
  • 结果匹配时得分
  • 反转问题(Inversion-problem)[13]游戏的例子有 Peekaboom, Phetch, Verbosity 和 Karido:
  • 两个玩家彼此不知道对方都是被随机选取的
  • 一个玩家是「描述者」,另一个玩家是「猜测者」
  • 描述者会给定一个输入
  • 描述者应该描述这个输入,以便猜测着能够在几个类似的加工品上识别出它们
  • 当猜测者正确识别时,两个玩家得分
  • 输入约定(Input-agreement)[14]游戏的例子有 TagAtune:
  • 两个玩家彼此不知道对方都是被随机选取的
  • 它们都被显示为游戏知道的输入(但不是由玩家)被认为是相同或不同的
  • 玩家应该产生描述输入的输出,所以他们的合作伙伴可以评估他们的投入是相同还是不同的
  • 两个玩家评估正确时得分
  • 补充约定(Complementary agreement)[14]游戏有 Polarity:
  • 两个玩家彼此不知道对方都是被随机选取的
  • 每个玩家被要求输出一些其他玩家不能输入的内容
  • 当两个玩家的输出内容匹配时,彼此得分
  • 链式模型(Chain Model)[15]游戏的例子有 GiveALink Slider, Great Minds Think Alike:
  • 玩家应该建立一系列语义相关的对象
  • 一个玩家会被展示一个对象 O
  • 玩家应该选择与对象 O 相关的其他对象
  • 模型不修正玩家的得分情况

    下面的几个分类解释了 ARTigo Gaming Ecosystem 是如何收集数据的[16]:

    • 描述游戏是收集有关人造物(如图像)的描述的游戏,例如 The ESP Game, Polarity
    • 传播游戏是将已经收集到的标签传播到一个新颖的环境(如将标签转换成另一种语言)的游戏,例如 Eligo
    • 多元化游戏产生更精确的标签和/或更深层次的标签,例如 Karido
    • 聚合游戏:例如 TagATag, Sentiment
  • 单人 GWAPs (Single player GWAPs)[17] 介绍了单个玩家的 GWAPs,提供游戏 Odd Leaf Out 来发现语料库中的分类错误。找茬游戏也也是一种单独的娱乐活动。
  • 预录游戏(Prerecorded games)[13]使得有单个玩家也可能同时与多个玩家进行游戏。这时候我们需要一个播放机器人,满足:
  • 记录游戏过程
  • 具备 GWAPS 游戏的冷启动问题的解决方法
  • 很难将游戏设计得有趣,可能导致抵触
  • 可能影响数据收集的质量
  • 对于输入约定来说比较容易
  • 对于反转问题来说很难设计
  • 玩家测试(Player testing)包括想玩家提供已知的正确解决方案
  • 检测作弊玩家
  • 评估玩家贡献的真实性

GWAP 生态系统

游戏平台 Artigo 是一个生态系统,某些 GWAP 所需的数据由其他 GWAP 收集[16]:

  • Artigo 游戏和 ARTigo Taboo 收集一般标签
  • Karido 收集更多的具体标签,将艺术作品分开,与ESP游戏变体ARTigo游戏或Artigo Taboo类似
  • Eligo 将标签翻译成其他语言
  • TagATag要求玩家标注一对(艺术品L),其中L是使用ARTigo游戏或Artigo Taboo收集的作品的标签
  • Combino 将标签进行组合

参见 [16]。

进一步阅读的参考文献

[1] Luis von Ahn and Laura Dabbish: “ESP: Labeling Images with a Computer Game”, Proceedings of CHI

[2] Stephen Robertson, Milan Vojnovic, and Ingmar Weber: “Rethinking the ESP Game”, Proceedings of CHI 2009

[3] Shaili Jain and David C Parkes: “A Game-theoretic Analysis of Games with a Purpose”, ACM Transactions on Economics and Computation, 1(1), Article 3, 2013

[4] Stephen Robertson, Milan Vojnovic, and Ingmar Weber: “Rethinking the ESP Game”, Proc. CHI 2009

[5] H. Sacks, E. Scheglo, and G. Jeerson: “A Simplest Systematics for the Organization of Turn-taking for Conversation”, Language, vol. 50, pages 696–735, 1974

[6] Edith Law, Luis von Ahn, Roger B. Dannenberg, and MikeCrawford: “TagATune: A Game for Music and Sound Annotation”, Proc. ISMIR, 2007

[7] L. von Ahn, M. Kedia, and M. Blum: “Verbosity: A Game for Collecting Common-Sense Facts”, Proc. CHI, 2006

[8] Douglas Turnbull, Ruoran Liu, Luke Barrington, and Gert Lanckriet: “A Game-Based Approach for Collecting Semantic Annotations of Music”, Proc. ISMIR, 2007

[9] A. Dasdan, S. Kolay, and C. Drome: “System and Method for Optimizing Search Results Ranking Through Collaborative Gaming”, US Patent 8,140,518, 2012

[10] H. Lieberman, D. Smith, and A. Teeters: “Common Consensus: A Web-based Game for Collecting Commonsense Goals”, Proc. Workshop on Common Sense for Intelligent Interfaces, ACM Int. Conf. Intelligent User Interfaces (IUI), 2007

[11] K. Siorpaes and M. Hepp: “Games with a Purpose for the Semantic Web”, Intelligent systems, 23 (3), 2008

[12] N. Seemakurty, J. Chu, L. von Ahn, and A. Tomasic: “Word Sense Disambiguation via Human Computation”, 2nd KDD Human Computation Workshop, 2010

[13] L. von Ahn and L. Dabbish: “Designing Games With a Purpose”, CACM, Vol. 51, Issue 8, pages 58–67, 2008

[14] E. Law and L. von Ahn L: “Input-Agreement: A New Mechanism for Collecting Data Using Human Computation Games”, Proc. CHI, 2009

[15] L. Weng, R. Schifanella, and F. Menczer: “Design of Social Games for Collecting Reliable Semantic Annotations” Proc. Computer Games (CGAMES), 2011

[16] Christoph Wieser, Francois Bry, Alexandre Berard, and Richard Lagrange: “ARTigo: Building an Artwork Search Engine With Games and Higher-Order Latent Semantic Analysis”, Proc. Disco 2013, Workshop at HComp, 2013

[17] D.L. Hansen, D.W. Jacobs, D. Lewis, A. Biswas, J. Preece, D. Rotman, and E. Stevens: “Odd Leaf Out: Improving Visual Recognition with Games”, Proc. Privacy, security, risk and trust (passat), Social Computing (socialcom), 2011

如果我的文章对你起到了帮助,你可以选择金额不限的捐助,帮助我写出更多的文章。