Published at:   |   Reading: 3561 words ~8min   |   PV/UV: /

在上一篇文章中我们已经介绍了人肉计算的定义。这篇文章我们来谈谈人肉计算中的「意图博弈」（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

0%