2

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

 2 years ago
source link: https://changkun.de/blog/posts/human-computation-2/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

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

    P(T|t)=Πs∈TP(s|t)P(T|t)=Πs∈TP(s|t)

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

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

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

P(t|T)=Πs∈TP(s|t)P(t)1CP(t|T)=Πs∈TP(s|t)P(t)1C

接收者设计

「接收者设计」解释了为什么 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

OntoPronto, SpotTheLinks, OntoTube, OntuBay

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK